Take my Infinity final exam!
How well can you answer the questions on the final exam for my Infinity course?
My undergraduate students and I have been studying infinity and paradox all semester here at the University of Notre Dame, following The Book of Infinity, with all my favorite conundrums. The book will appear soon with MIT Press.
We just wrapped up the class with a final exam, and I thought it would be fun to share the exam questions here (some slightly edited), so that the rest of my readers here can have a chance to think about the questions as well.
Have a go! Post your solutions in the comments section below.
Instructions. For each question, answer as fully and robustly as possible, with a brief essay explaining the main points and arguments at stake and bringing fully to light all the relevant philosophical issues. Incorporate diagrams or technical matters, if any, as a part of the narrative flow. Some questions are open-ended, and feel free to take any position on the matter, provided you can defend it well.
Defend or criticize the view that the Cantor-Hume principle is in fundamental harmony with Euclid's principle.
Defend or criticize the argument: “The set of rational numbers cannot be countable, because between any two rational numbers there are more.” Give a full explanation of your position.
How is the distinction between potential and actual infinity manifested in the usual treatment of infinite series in calculus, such as the series
\(\sum_{n=0}^\infty \frac1{2^n}\)particularly in light of the definition of the value of an infinite sum as the limit of finite partial sums.
Provide a careful argument, with all details correct, that the set of real numbers is uncountable.
Explain, as though to a child, how to count up to the ordinal number
\(\omega^2+\omega\cdot2+3.\)Include a picture of the various prominent ordinals that appear along the way, distinguishing between the simple limit ordinals and the compound limit ordinals.
Tell the story of the continuum hypothesis, as fully as possible. What does it assert exactly? What are the central historical developments? What are the central philosophical issues to which it gave rise? How was it eventually resolved or does it remain unresolved?
Tell the story of the axiom of choice, as fully as possible. What does it assert exactly? Who first introduced it and for what purpose? What philosophical perspectives on the nature of mathematical ontology might lead one to adopt the axiom of choice or to deny it?
What is your analysis of the following sentences:
What are your answers? Kindly post in the comments below. I have opened up the comments section to all subscribers, whether free or paid.
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 🙂