PUMaC 2025 · 加试 · 第 2 题

Problem 2.3.3 (20 points) Prove that for any set X , there exists a bijection f from X to some ordinal α , and conclude that there exists a well-order on X . (Hint: use the axiom of choice.) This problem establishes the well-ordering theorem : every set can be well-ordered. It was first proven by Ernst Zermelo in 1904. The axiom of choice (often abbreviated as AC ) is crucial in proving the well-ordering theorem. If your solution didn’t use it, then it is wrong! In fact, if we work in ZF , which is ZFC without choice, then we can prove that 17 AC is equivalent to the well-ordering theorem. (Problem 2.3.3 establishes one direction: AC implies the well-ordering theorem. You are welcome to try the other direction, but we won’t need this result.) Many set theorists see the well-ordering theorem as somewhat unintuitive. It states 3 that all sets can be well-ordered, including, for instance, R . How would you well-order R ? It’s not something you can write down explicitly (without using AC ), and the field of descriptive set theory , which studies R from a set-theoretic perspective, tells us that such a well-order would have bizarre properties. There is a famous joke by Jerry Bona: The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn’s lemma? ( Zorn’s lemma is another result equivalent to the axiom of choice, and it is used in many areas of mathematics, but it has a rather complicated statement.) 2.4 Philosophical Discussion: Natural Numbers In this section, we spent a lot of effort defining what natural numbers are, and making sure that the logic is completely airtight. However, if you look carefully, you may notice that we have actually been secretly using natural numbers since the very beginning of this Power Round! For instance, when we wrote “let φ ( x, p , . . . , p ) be a formula”, we 1 n were invoking the concept of natural numbers, as n is a natural number. Did we commit the error of using a concept before defining it? Don’t worry – we didn’t. When we write something like φ ( x, p , . . . , p ), the number 1 n n lives in the meta theory, instead of the base theory. It is a “meta natural number”, if you will. So, we were using meta natural numbers in the meta theory, before defining natural numbers in the base theory. This is not circular reasoning! But things still feels a bit suspicious. If we need meta natural numbers to formalize natural numbers, then we can ask: where do the meta natural numbers come from? We would need a “meta meta theory” to formalize the meta natural numbers, and a “meta meta meta theory” to formalize that, and so on. Turtles all the way down. And the issue is not just with natural numbers. If we want to formalize logic, then we would need a logical system in which to do so. It seems that an infinite regress is unavoidable. In practice, logicians and set theorists deal with this problem by ignoring it. After all, we have to start somewhere . Instead of getting stuck in a fruitless cycle of formalization, we choose the meta theory as our starting point, and take it for granted. (In particular, there will be no such thing as a “meta meta theory”.) From there, we can specify the basic rules of logic, and list out the axioms of the base theory ZFC . In fact, we can go further, and formalize a copy of ZFC inside the base theory! To do logic within our set-theoretic framework, we encode each formula φ as a natural number ⌜ φ ⌝ , called the G¨ odel number of φ (named after Kurt G¨ odel), and formalize all of the rules of logic within the base theory. Finally, we write down the G¨ odel numbers of the axioms of ZFC . The resulting set of G¨ odel numbers is called the coded theory . The coded theory can be thought of as a copy of ZFC , inside the base theory ZFC , and one level “below” the base theory. In an abuse of notation, the coded theory is usually also denoted ZFC , but we shall write ⌜ ZFC ⌝ to avoid confusion. 3 We won’t give a precise definition of R in this Power Round. 18 3 Cardinals (180 points) Infinite sets behave quite differently than finite sets, as famously illustrated in David Hilbert’s Grand Hotel. Imagine a hotel with infinitely many rooms, numbered 0 , 1 , 2 , . . . , each occupied by a guest, say, Room n is occupied by Guest n . The hotel is full, and yet, it can accommodate more guests: by moving Guest n to Room n + 1 for all n , Room 0 is left vacant for a new guest, say Guest ω , to move into. In other words, the two sets ω = { 0 , 1 , 2 , . . . } and ω + 1 = { 0 , 1 , 2 , . . . , ω } have the same “size”, in some sense, even though ω is a proper subset of ω + 1. But are there any infinite sets that have a larger size than ω ? In 1874, Georg Cantor answered this question in the affirmative: he proved that the set R of real numbers has strictly more elements than ω . If a guest for every real number came to Hilbert’s Hotel, then the hotel would not be able to accommodate everyone. More precisely, the size of a set X is measured by its cardinality | X | , a special kind of ordinal called a cardinal . For example, the cardinality of { a, b, c } is 3, because { a, b, c } has 3 elements, and the cardinalities of ω and ω + 1 are ℵ = ω , which is the smallest 0 infinite cardinal. After ℵ , the next cardinal is ℵ , and then ℵ , and after infinitely many 0 1 2 of these, we reach ℵ . In fact, there is a cardinal ℵ for every ordinal α . ω α All of the informal ideas above will be made fully rigorous in what follows. 3.1 The Basics of Cardinals (60 points) Definition 3.1.1 — Two sets X and Y are equinumerous , denoted X ≈ Y , if there exists a bijection f : X → Y . For example, we have already seen that ω and ω + 1 are equinumerous. It is also not hard to show that ω and ω · 2 are equinumerous: we can define a bijection f : ω · 2 → ω via f ( n ) = 2 n and f ( ω + n ) = 2 n + 1, where n < ω .