Hacker News Reader

Comment by nphardon | Hacker News Reader

If the universe contains a finite amount of information, would that disprove the existence of an infinite set? I.e. if the representation of a number contained more information than the amount of information available in the entire universe.

View on HN

Not really. Math uses no physical observation, only axioms. Nothing can "prove" or "disprove" axioms. However, if observation supports the axiomatic theory, then we use the theory for physical prediction. If observation doesn't, then we don't use the theory. Does that count as "disproof"?

In practice, infinite sets never exist as enumerations of every element, but as ways to generate more elements along with descriptions for which elements to include. Infinite set theories allow for equivocating a finite description with the infinite enumeration. In contrast, programming languages usually make a distinction between data (always finite) and data generation (possibly infinite). I would think that counts as a "disproof" in a way.

There exist subsets of the natural numbers which are infinite, but which are not finitely definable in first-order arithmetic.

For example? And does "first-order arithmetic" mean ZFC?

I got this example from an LLM:

  1. Fix a formal system S. In the LLM example, it uses first-order arithmetic, but I don't see why we wouldn't be able to use ZFC.
  2. Let D be the set of subsets of the natural numbers N which are definable by a finite formula in S.
  3. There are countably many finite formulas, so |D| <= |N|.
  4. Cantor's theorem says that the size of the power set of N is greater than |N|.
  5. Therefore there must be subsets of N which are not definable by a finite formula in S.

If you disagree with this, I would be interested to know.

Not happy to respond to LLM talk, but you seem interested anyway. Some sleight of hand happens between "fixing a formal system" and using Cantor's theorem for the metamathematical analysis, as if we use classical set theory anyway. Note that you cannot construct any particular example of a non-definable set, which should cast doubt of existence. I'll disagree by pointing to anti-classical set theories. The axiom of infinity proves independence from ZFC, so I can freely replace the axiom of infinity with its negation, then the natural numbers no longer form a set. Some constructive analysis systems include an axiom that every real-valued function is continuous (as discontinuous functions are undecidable).

https://en.wikipedia.org/wiki/Axiom_of_infinity#Independence

https://en.wikipedia.org/wiki/Constructive_analysis#Anti-cla...

This was the answer I was looking for. You're reminding me that existence of infinity is an axiom, like parallel lines dont intersect. We can remove that axiom and get a new mathematical framework, but by their nature, axioms are not something to prove or disprove.

Exactly. For example, John Mayberry wrote "The Foundations of Mathematics in the Theory of Sets" (2000). Half of the book consists of philosophical arguments for his "Euclidean set theory" contrasted against the big bad "Cantorian set theory". He takes inspiration from Euclid's common notion 5 "the whole is greater than the part". On page 277, formula 8.3.1, his Axiom of Euclidean Finiteness goes like this: any injective endofunction is also surjective, ∀f∀Y((f:Y→Y ∧ 1to1(f)) ⇒ onto(f)).

I've come to believe that many related incompatible theories have interpretations between each other. For example, hyperbolic geometry has a Euclidean-like Poincare disk model, and Euclidean space exists locally in a hyperbolic space. Boolean logic contains intuitionistic logic (just add the law of excluded middle), but intuitionistic logic contains Boolean logic through the double negation translation. Similar might happen for finite set theories, infinite set theories, and neutral set theories. The fun includes finding the right translation so that we can all enjoy our different tastes in axioms.

You’d have to define what you mean by “existence” here. Clearly, there are infinite sets we can represent with a finite sequence of symbols. We can also imagine and reason about alternative universes with an infinite amount of information. You’d have to argue about how doing so would somehow be an incorrect thing to do.

It's a very interesting idea; if you want to learn more about it, look up "ultrafinitism".

Reply on news.ycombinator.com