Let me try. I didn't know until today what the Cantor-Hume and Euclid's principle were (I mean, I wasn't aware of those names), so I'll skip question 1, and I'm not sure what you expect at question 3 (I suppose these philosophical arguments about potential and actual infinity were discussed in your lectures).
2. ℚ is countable, as can be seen by enumerating irreducible fractions, e.g., by a spiral on an infinite lattice in the plane. The argument proposed therefore leads to a false conclusion. The error is in assuming that an enumeration of the rationals must be an increasing function $φ$ (leading to the purported contradiction between the fact that all rationals between $φ(0)$ and $φ(1)$ must be in the range of $φ$ while there is no integer between 0 and 1 to be their preimage), while the definition of a countable set only requires it to be a bijection.
4. By Cantor's theorem, $|ℕ| < |𝒫(ℕ)|$, thus it is enough to inject $𝒫(ℕ)$ into $ℝ$. This can be done by encoding a subset $X ⊆ ℕ$ by the real whose representation in base 3 is $0.(δ_X(0))(δ_X(1))(δ_X(2))⋯$, where $δ_X(n)$ is defined to be the digit $1$ if $n ∈ ℕ$, $0$ otherwise. This encoding is injective because two representations in base 3 which do not end in a $2^ω$ suffix define different reals. (This is the point of using base 3 instead of base 2.)
(As an aside for intuitionists, by a very nice result of Bauer & Hanson this year https://arxiv.org/abs/2404.01256, it is consistent with intuitionistic higher-order logic that there exists a surjection $ℕ → ℝ$.)
5. We first count by the natural numbers: 0, 1, 2, 3, … Then “after an infinite amount of time” we are done enumerating them and we start over from a special symbol written $ω$, so $ω$, $ω+1$, $ω+2$, $ω+3$, … After waiting again “infinitely long”, we start over with $ω⋅2$, $ω⋅2+1$, $ω⋅2+2$, $ω⋅2+3$, … We iterate this with $ω⋅3$, $ω⋅4$, and so on, and after “infinitely many infinitely long waiting times”, we reach a new stage written $ω^2$. At this point, we enumerate $ω^2$, $ω^2+1$, $ω^2+2$, …, infinitely, then $ω^2 + ω$, $ω^2 + ω + 1$, $ω^2 + ω + 2$, …, infinitely, then $ω^2 + ω⋅ 2$, $ω^2 + ω⋅2 + 1$, $ω^2 + ω⋅2 + 2$, $ω^2 + ω⋅2 + 3$, and we finally stop here.
The most prominent ordinals in this enumeration are:
- Finite ordinals, especially 0, 1, 2, and 42 🙂 (0 is the only ordinal which is neither successor nor limit, 1 is the first successor.)
- $ω$, the first limit ordinal,
- $ω⋅2$, the second limit ordinal,
- $ω^2$, the first compound limit ordinal (to be honest, I did not know until today what a compound limit ordinal is).
6. The continuum hypothesis (CH) is the assertion $ℵ_1 = 2^{ℵ_0}$, i.e., that the first uncountable cardinal ($ℵ_1$) is the cardinal of the continuum ($2^{ℵ_0}$), or in layman terms, that there is no infinity strictly between that of the natural numbers and that of the real numbers.
Georg Cantor, who founded set theory by introducing the concept of cardinal and proving the uncountability of $ℝ$, famously failed to prove or disprove CH (which he believed to be true). Gödel proved in the thirties (I think) that CH holds in the constructible universe $L$ defined by him. This shows that CH is consistent with ZFC, meaning $\text{Con}(\text{ZFC}) ⇒ \text{Con}(\text{ZFC}+\text{CH})$: indeed (reasoning externally in ZFC), if ZFC is consistent, then it has a model (by Gödel's completeness theorem), and the internal L in this model is a submodel that additionally satisfies CH.
Much later (somewhere in the sixties?), Cohen invented forcing and used it to show that the negation of CH is also consistent with ZFC.
The central philosophical question around CH is whether it may be settled satisfactorily at all. This is not resolved categorically by the independence from ZFC, since ZFC is a relatively arbitrary theory (e.g., it is disputable whether the axiom of replacement should really be included, as it is unnecessary for almost all of mathematics, except set theory itself, and a few theorems of a set-theoretic flavors such as Martin's Borel determinacy theorem). However, the absence of any convincing axiomatic set theory, all of whose axioms would be “obviously” true to a working mathematician, and which settles CH, has led most to believe the question cannot be resolved.
If one believes in the absolute, platonic existence of ordinals and the cumulative hierarchy (as I personally do), then CH is either true or false, only we cannot convincingly know which possibility (just as aliens exist or do not exist, although we cannot know for sure). In a more formalist stance, we may explore ZFC + CH and ZFC + ¬CH as parallel universes, neither of which is more correct than the other. (I am not sure I could explain this view more precisely, since I disagree with it. I find it understandable, however, that one might not see the cumulative hierarchy as the definitive answer to the question “what's a set?”, so one may argue that we are simply exploring two alternative “definitions” of sets. But I do personally believe in the cumulative hierarchy as an absolute concept and view it as the standard model for set theory just as much as ℕ is the standard model for arithmetic.)
7. The axiom of choice (AC) asserts, equivalently:
- That every surjection is a retract,
- That every cartesian product of non-empty sets is non-empty,
- That every set $X$ has a choice function, i.e., $f : 𝒫(X)∖\{∅\} → X$ such that $∀ Y ∈ 𝒫(X)∖\{∅\}, f(Y) ∈ Y$.
Less obviously, it is also equivalent to these two famous statements:
- Zermelo's well-ordering principle: Every set can be well-ordered. Proving this was Zermelo's original motivation for introducing AC.
- Zorn's lemma: In a poset where every chain has an upper bound, there exists a maximal element.
While a good part of mathematics can be developed without AC, it is necessary to prove many important statements, such as:
- Cantor-Schröder-Bernstein theorem: If there are injections $A → B$ and $B → A$ then there is a bijection $A ↔ B$,
- A countable union of countable sets is countable (however we do not need AC if we have an explicit bijection with ℕ at hand for each of the sets, only to choose such a bijection if we only suppose these exist),
- Every vector space has a basis (with surprising consequences like “the groups $(ℝ, +)$, $(ℝ^n, +)$ and $(ℝ[X], +)$ are isomorphic”),
- Krull's theorem: Every proper ideal is contained in a maximal proper ideal,
- Steinitz's theorem: Every field has an algebraic closure.
Although originally controversial, AC is usually accepted nowadays, and is often used implicitly, e.g., it is usually not pointed out in the proof that a countable union of countable sets that we need AC to choose a bijection for each set. (As a personal anecdote, I once argued in a discussion about how to state CH without AC that $ω_1$ could be injected into $ℝ$ without AC by diagonalization, until it was pointed out that I had unconsciously applied AC to choose a countabilization of every ordinal $<ω_1$.)
Some people believe AC to be false on the basis that it has unintuitive consequences, such as the (in)famous Banach-Tarski paradox. I personally believe that this is a poor argument since there are other (in my opinion) equally unintuitive results which do not (I think) require AC, such as Peano curves.
In a purely realist stance, AC should be true because the elements in the sets exist platonically. On the other hand, from a more proof-theoretic point of view, the axiom of choice may look suspicious because it sounds like a form of infinitary proofs.
From the perspective of intuitionism, AC is not acceptable in intuitionistic set theory because it entails excluded middle, a result known as Diaconescu's theorem. For the proof, take a proposition $P$ and consider the sets $U = \{x ∈ \{0, 1\} | x = 0 ∨ P\}$ and $V = \{x ∈ \{0, 1\} | x = 1 ∨ P\}$. The existence of a choice function on $\{U, V\}$ allows to extract whether $U = V$ and trace back to $P ∨ ¬P$.
In type theory, the situation is more complicated. For example, in the calculus of constructions, AC formulated with the existence type that lives in the impredicative sort, $∃$, is not provable and its translation in set-theoretic models is exactly the set-theoretic AC, but if we formulated with type-level existence $Σ$, it becomes provable. I am quite sure Diaconescu's theorem does not hold, although I do not believe this has been formally proven; we do recover the theorem if we add propositional extensionality (paralleling the implicit use of the axiom of extensionality in the set-theoretic proof).
From the point of view of the Brouwer-Heyting-Kolmogorov interpretation of proofs, while excluded middle is a kind of “omniscience oracle” operator which chooses between two alternatives by “seering” which of $P$ and $¬P$ is true, choice is a form of non-determinism since it “chooses” between many equally allowable alternatives.
8. At first glance, this may appear to be a paradox (if the first sentence is true, the second is false, then some sentence below is true, contradicting the first, and if the first sentence is false, some sentence below is true and we can repeat the same argument). The apparent contradiction is resolved by Tarski's undefinability theorem, which prevents a logic from formalizing its own notion of truth. This is essentially the same paradox and resolution as the liar's paradox.
My first reaction is to interpret each line as a distinct sentence φ₀, φ₁, …, and to ask whether there exists a consistent truth-valuation for these sentences.
Assuming that φ₀ valuates to true entails that φ₁ is false, which means that some φᵢ, i > 1 is true. However, due to φ₀, we already know φᵢ must be false.
So, φ₀ must valuate to false. But this entails that some φᵢ, i > 0 must be true, and we can repeat the argument above to produce another contradiction.
Therefore valuating φ₀ as either true or false forces an inconsistency, so overall the sentences admit no self-consistent valuation.
To do this analysis I had supposed that each sentence is distinct. However, since each sentence is equal in content then we might interpret the diagram as denoting a *single* sentence φ stating "φ is false". This situation also admits no consistent valuation function.
Both of these situations are in some sense absurd. One can view logic as a tool for modelling the behaviour of other systems (eg, real-world truth), but in this case our sentences pertain to nothing but themselves. The system is modelling nothing (or modelling itself?). It is of no consequence whether these sentences are true or false, and from that perspective we might say that every valuation is equally valid, because they are all equally meaningless 🙂
The claim that "The set of rational numbers cannot be countable, because between any two rational numbers there are more" is wrong ... but I am sympathetic to that thought process
Roughly, a countable set is one that has the same shape as ℕ; namely, it can be placed in sequence like ℕ:
0 → 1 → 2 → 3 → ⋯
ℚ looks entirely different from this, with an surplus of elements sitting in the gaps between each natural.
If there were only a finite number of elements in each gap, we may dismiss the difference by noticing that there is still a *next* element after 0: so we call that 1, and we call the element after that 2, and so on, "stretching out" the tightly-packed elements to match the shape of ℕ
But with ℚ, there is no next element after 0! And indeed, we can "stretch out" ℚ as much as we like and it will never match the shape of ℕ
This thought process makes it intuitive that ℚ is not countable.
It's mistaken, however, because the definition of countability does not restrict us only to "stretching out" a set to match it with ℕ. Contrarily, we can entirely re-order elements, if we like. If we can match a set with ℕ, allowing for reordering, then the set is countable.
And, in fact, there is a way to reorder ℚ to match ℕ, so ℚ is countable. One such way is to match n ∈ ℕ to an element of ℚ as follows. Prime factorize n as n = 2ᵃ 3ᵇ 5ᶜ ⋯, and then match n to sgn(a) ⋅ (b/c) ∈ ℚ. This matching gives an enumeration of rationals where every q ∈ ℚ is mentioned, some more than once. Now drop all but the first copy of each duplicate, and what we're left with is a re-ordering of ℚ into the shape of ℕ.
Wow this is fascinating. I am a HS math teacher, with a MS in math education. I have some graduate level math experience, but limited. Furthest I’ve gone is an introduction to real analysis and some number theory. What books would you recommend me to start with so I can better understand infinity and these questions? Maybe the one you mentioned in your post? Thanks!
Yes, this course was based on my new book, The Book of Infinity, which has been serialized here at Infinitely More, if you follow the link in the post. It will also soon appear with MIT Press.
Wonderful exam! Really wish more classes had exams like this! I will try to write up my solutions soon! :) One question though, what is "Euclid's principle"? On a quick google search I didn't find anything that looked relevant to the context.
Let me try. I didn't know until today what the Cantor-Hume and Euclid's principle were (I mean, I wasn't aware of those names), so I'll skip question 1, and I'm not sure what you expect at question 3 (I suppose these philosophical arguments about potential and actual infinity were discussed in your lectures).
2. ℚ is countable, as can be seen by enumerating irreducible fractions, e.g., by a spiral on an infinite lattice in the plane. The argument proposed therefore leads to a false conclusion. The error is in assuming that an enumeration of the rationals must be an increasing function $φ$ (leading to the purported contradiction between the fact that all rationals between $φ(0)$ and $φ(1)$ must be in the range of $φ$ while there is no integer between 0 and 1 to be their preimage), while the definition of a countable set only requires it to be a bijection.
4. By Cantor's theorem, $|ℕ| < |𝒫(ℕ)|$, thus it is enough to inject $𝒫(ℕ)$ into $ℝ$. This can be done by encoding a subset $X ⊆ ℕ$ by the real whose representation in base 3 is $0.(δ_X(0))(δ_X(1))(δ_X(2))⋯$, where $δ_X(n)$ is defined to be the digit $1$ if $n ∈ ℕ$, $0$ otherwise. This encoding is injective because two representations in base 3 which do not end in a $2^ω$ suffix define different reals. (This is the point of using base 3 instead of base 2.)
(As an aside for intuitionists, by a very nice result of Bauer & Hanson this year https://arxiv.org/abs/2404.01256, it is consistent with intuitionistic higher-order logic that there exists a surjection $ℕ → ℝ$.)
5. We first count by the natural numbers: 0, 1, 2, 3, … Then “after an infinite amount of time” we are done enumerating them and we start over from a special symbol written $ω$, so $ω$, $ω+1$, $ω+2$, $ω+3$, … After waiting again “infinitely long”, we start over with $ω⋅2$, $ω⋅2+1$, $ω⋅2+2$, $ω⋅2+3$, … We iterate this with $ω⋅3$, $ω⋅4$, and so on, and after “infinitely many infinitely long waiting times”, we reach a new stage written $ω^2$. At this point, we enumerate $ω^2$, $ω^2+1$, $ω^2+2$, …, infinitely, then $ω^2 + ω$, $ω^2 + ω + 1$, $ω^2 + ω + 2$, …, infinitely, then $ω^2 + ω⋅ 2$, $ω^2 + ω⋅2 + 1$, $ω^2 + ω⋅2 + 2$, $ω^2 + ω⋅2 + 3$, and we finally stop here.
The most prominent ordinals in this enumeration are:
- Finite ordinals, especially 0, 1, 2, and 42 🙂 (0 is the only ordinal which is neither successor nor limit, 1 is the first successor.)
- $ω$, the first limit ordinal,
- $ω⋅2$, the second limit ordinal,
- $ω^2$, the first compound limit ordinal (to be honest, I did not know until today what a compound limit ordinal is).
6. The continuum hypothesis (CH) is the assertion $ℵ_1 = 2^{ℵ_0}$, i.e., that the first uncountable cardinal ($ℵ_1$) is the cardinal of the continuum ($2^{ℵ_0}$), or in layman terms, that there is no infinity strictly between that of the natural numbers and that of the real numbers.
Georg Cantor, who founded set theory by introducing the concept of cardinal and proving the uncountability of $ℝ$, famously failed to prove or disprove CH (which he believed to be true). Gödel proved in the thirties (I think) that CH holds in the constructible universe $L$ defined by him. This shows that CH is consistent with ZFC, meaning $\text{Con}(\text{ZFC}) ⇒ \text{Con}(\text{ZFC}+\text{CH})$: indeed (reasoning externally in ZFC), if ZFC is consistent, then it has a model (by Gödel's completeness theorem), and the internal L in this model is a submodel that additionally satisfies CH.
Much later (somewhere in the sixties?), Cohen invented forcing and used it to show that the negation of CH is also consistent with ZFC.
The central philosophical question around CH is whether it may be settled satisfactorily at all. This is not resolved categorically by the independence from ZFC, since ZFC is a relatively arbitrary theory (e.g., it is disputable whether the axiom of replacement should really be included, as it is unnecessary for almost all of mathematics, except set theory itself, and a few theorems of a set-theoretic flavors such as Martin's Borel determinacy theorem). However, the absence of any convincing axiomatic set theory, all of whose axioms would be “obviously” true to a working mathematician, and which settles CH, has led most to believe the question cannot be resolved.
If one believes in the absolute, platonic existence of ordinals and the cumulative hierarchy (as I personally do), then CH is either true or false, only we cannot convincingly know which possibility (just as aliens exist or do not exist, although we cannot know for sure). In a more formalist stance, we may explore ZFC + CH and ZFC + ¬CH as parallel universes, neither of which is more correct than the other. (I am not sure I could explain this view more precisely, since I disagree with it. I find it understandable, however, that one might not see the cumulative hierarchy as the definitive answer to the question “what's a set?”, so one may argue that we are simply exploring two alternative “definitions” of sets. But I do personally believe in the cumulative hierarchy as an absolute concept and view it as the standard model for set theory just as much as ℕ is the standard model for arithmetic.)
7. The axiom of choice (AC) asserts, equivalently:
- That every surjection is a retract,
- That every cartesian product of non-empty sets is non-empty,
- That every set $X$ has a choice function, i.e., $f : 𝒫(X)∖\{∅\} → X$ such that $∀ Y ∈ 𝒫(X)∖\{∅\}, f(Y) ∈ Y$.
Less obviously, it is also equivalent to these two famous statements:
- Zermelo's well-ordering principle: Every set can be well-ordered. Proving this was Zermelo's original motivation for introducing AC.
- Zorn's lemma: In a poset where every chain has an upper bound, there exists a maximal element.
While a good part of mathematics can be developed without AC, it is necessary to prove many important statements, such as:
- Cantor-Schröder-Bernstein theorem: If there are injections $A → B$ and $B → A$ then there is a bijection $A ↔ B$,
- A countable union of countable sets is countable (however we do not need AC if we have an explicit bijection with ℕ at hand for each of the sets, only to choose such a bijection if we only suppose these exist),
- Every vector space has a basis (with surprising consequences like “the groups $(ℝ, +)$, $(ℝ^n, +)$ and $(ℝ[X], +)$ are isomorphic”),
- Krull's theorem: Every proper ideal is contained in a maximal proper ideal,
- Steinitz's theorem: Every field has an algebraic closure.
Although originally controversial, AC is usually accepted nowadays, and is often used implicitly, e.g., it is usually not pointed out in the proof that a countable union of countable sets that we need AC to choose a bijection for each set. (As a personal anecdote, I once argued in a discussion about how to state CH without AC that $ω_1$ could be injected into $ℝ$ without AC by diagonalization, until it was pointed out that I had unconsciously applied AC to choose a countabilization of every ordinal $<ω_1$.)
Some people believe AC to be false on the basis that it has unintuitive consequences, such as the (in)famous Banach-Tarski paradox. I personally believe that this is a poor argument since there are other (in my opinion) equally unintuitive results which do not (I think) require AC, such as Peano curves.
In a purely realist stance, AC should be true because the elements in the sets exist platonically. On the other hand, from a more proof-theoretic point of view, the axiom of choice may look suspicious because it sounds like a form of infinitary proofs.
From the perspective of intuitionism, AC is not acceptable in intuitionistic set theory because it entails excluded middle, a result known as Diaconescu's theorem. For the proof, take a proposition $P$ and consider the sets $U = \{x ∈ \{0, 1\} | x = 0 ∨ P\}$ and $V = \{x ∈ \{0, 1\} | x = 1 ∨ P\}$. The existence of a choice function on $\{U, V\}$ allows to extract whether $U = V$ and trace back to $P ∨ ¬P$.
In type theory, the situation is more complicated. For example, in the calculus of constructions, AC formulated with the existence type that lives in the impredicative sort, $∃$, is not provable and its translation in set-theoretic models is exactly the set-theoretic AC, but if we formulated with type-level existence $Σ$, it becomes provable. I am quite sure Diaconescu's theorem does not hold, although I do not believe this has been formally proven; we do recover the theorem if we add propositional extensionality (paralleling the implicit use of the axiom of extensionality in the set-theoretic proof).
From the point of view of the Brouwer-Heyting-Kolmogorov interpretation of proofs, while excluded middle is a kind of “omniscience oracle” operator which chooses between two alternatives by “seering” which of $P$ and $¬P$ is true, choice is a form of non-determinism since it “chooses” between many equally allowable alternatives.
8. At first glance, this may appear to be a paradox (if the first sentence is true, the second is false, then some sentence below is true, contradicting the first, and if the first sentence is false, some sentence below is true and we can repeat the same argument). The apparent contradiction is resolved by Tarski's undefinability theorem, which prevents a logic from formalizing its own notion of truth. This is essentially the same paradox and resolution as the liar's paradox.
So… how well would I have fared in your exam? 🙂
#8
My first reaction is to interpret each line as a distinct sentence φ₀, φ₁, …, and to ask whether there exists a consistent truth-valuation for these sentences.
Assuming that φ₀ valuates to true entails that φ₁ is false, which means that some φᵢ, i > 1 is true. However, due to φ₀, we already know φᵢ must be false.
So, φ₀ must valuate to false. But this entails that some φᵢ, i > 0 must be true, and we can repeat the argument above to produce another contradiction.
Therefore valuating φ₀ as either true or false forces an inconsistency, so overall the sentences admit no self-consistent valuation.
To do this analysis I had supposed that each sentence is distinct. However, since each sentence is equal in content then we might interpret the diagram as denoting a *single* sentence φ stating "φ is false". This situation also admits no consistent valuation function.
Both of these situations are in some sense absurd. One can view logic as a tool for modelling the behaviour of other systems (eg, real-world truth), but in this case our sentences pertain to nothing but themselves. The system is modelling nothing (or modelling itself?). It is of no consequence whether these sentences are true or false, and from that perspective we might say that every valuation is equally valid, because they are all equally meaningless 🙂
#2
The claim that "The set of rational numbers cannot be countable, because between any two rational numbers there are more" is wrong ... but I am sympathetic to that thought process
Roughly, a countable set is one that has the same shape as ℕ; namely, it can be placed in sequence like ℕ:
0 → 1 → 2 → 3 → ⋯
ℚ looks entirely different from this, with an surplus of elements sitting in the gaps between each natural.
If there were only a finite number of elements in each gap, we may dismiss the difference by noticing that there is still a *next* element after 0: so we call that 1, and we call the element after that 2, and so on, "stretching out" the tightly-packed elements to match the shape of ℕ
But with ℚ, there is no next element after 0! And indeed, we can "stretch out" ℚ as much as we like and it will never match the shape of ℕ
This thought process makes it intuitive that ℚ is not countable.
It's mistaken, however, because the definition of countability does not restrict us only to "stretching out" a set to match it with ℕ. Contrarily, we can entirely re-order elements, if we like. If we can match a set with ℕ, allowing for reordering, then the set is countable.
And, in fact, there is a way to reorder ℚ to match ℕ, so ℚ is countable. One such way is to match n ∈ ℕ to an element of ℚ as follows. Prime factorize n as n = 2ᵃ 3ᵇ 5ᶜ ⋯, and then match n to sgn(a) ⋅ (b/c) ∈ ℚ. This matching gives an enumeration of rationals where every q ∈ ℚ is mentioned, some more than once. Now drop all but the first copy of each duplicate, and what we're left with is a re-ordering of ℚ into the shape of ℕ.
Both of these were fun to write, thanks for the prompts :)
Wow this is fascinating. I am a HS math teacher, with a MS in math education. I have some graduate level math experience, but limited. Furthest I’ve gone is an introduction to real analysis and some number theory. What books would you recommend me to start with so I can better understand infinity and these questions? Maybe the one you mentioned in your post? Thanks!
Yes, this course was based on my new book, The Book of Infinity, which has been serialized here at Infinitely More, if you follow the link in the post. It will also soon appear with MIT Press.
Great! I look forward to reading it.
Wonderful exam! Really wish more classes had exams like this! I will try to write up my solutions soon! :) One question though, what is "Euclid's principle"? On a quick google search I didn't find anything that looked relevant to the context.
Euclid's principle asserts "the whole is greater than the part".
These are so good! Sounds like it was a fun class.