PUMaC 2025 · 加试 · 第 11 题
PUMaC 2025 — Power Round — Problem 11
题目详情
- With the exception of asking questions on Piazza, communication outside your team of 8 students about the content of these problems is prohibited. 2 Introduction and Advice In this Power Round, we will dive into the world of axiomatic set theory , which is the rigorous foundation for all of mathematics. We will ask and answer fundamental questions, such as “what is a set?” If you think this question is trivial, it is not : if you’re not careful, you run into all kinds of logical paradoxes. Building on the foundations, we will investigate the famous Continuum Hypothesis, which essentially asks: how large is the set R of real numbers? The answer turns out to be quite surprising: there is no way for us to know for sure how large it is! A large part of the difficulty in this Power Round will arise from the rigor required when working with the formal concepts. Since we need to put everything on completely solid footing, things that might seem obvious can often be quite nontrivial to prove. So, it is important to make sure that your logic is airtight. Here is some further advice with regard to the Power Round: • Read the text of every problem! Many important ideas are included in the problems and may be referenced later on. In addition, some of the theorems you are asked to prove are useful or even necessary for later problems. Even if you don’t solve a problem, you can assume its results for future problems. • Make sure you understand the definitions! A lot of the definitions are not easy to grasp; don’t worry if it takes you a while to fully understand them. If you don’t, then you will not be able to do the problems. Feel free to ask clarifying questions about the definitions on Piazza. • Don’t make stuff up! On problems that ask for proofs, you will receive more points if you demonstrate legitimate and correct intuition than if you fabricate something that looks rigorous just for the sake of having “rigor”. • Check Piazza often! Clarifications will be posted there. If you have a question, it is possible that it has already been asked and answered in a Piazza thread. If not, you can ask it, as long as you don’t ask a public question that reveals any part of your solution to a problem. • Don’t cheat! As stated in Rules and Reminders, you may NOT use any references such as books or electronic resources (unless otherwise specified). If you cheat, you will be disqualified and banned from PUMaC, your school may be disqualified, and relevant external institutions may be notified of any misconduct. Good luck, and have fun! – Zongshu Wu, Power Round Czar We would like to acknowledge and thank many individuals and organizations for their support; without their help, this Power Round (and the entire competition) could not exist. Please refer to the solutions for the Power Round for full acknowledgments and references. 3 Contents 1 Zermelo-Fraenkel Set Theory (50 points) 6 1.1 Logical Formulas (10 points) . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 The Axioms of ZFC (30 points) . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Classes (10 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Philosophical Discussion: The Meta Theory . . . . . . . . . . . . . . . . . 11 2 Ordinals (180 points) 12 2.1 The Basics of Ordinals (75 points) . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Induction and Recursion (60 points) . . . . . . . . . . . . . . . . . . . . . 14 2.3 Well-Orders (45 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Philosophical Discussion: Natural Numbers . . . . . . . . . . . . . . . . . 18 3 Cardinals (180 points) 19 3.1 The Basics of Cardinals (60 points) . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Cardinal Arithmetic (60 points) . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Cofinality (60 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 Interlude: G¨ odel’s Incompleteness Theorems . . . . . . . . . . . . . . . . . 26 4 Models of Set Theory (180 points) 28 4.1 Relativization (30 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2 Working in a Model (40 points) . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3 The von Neumann Hierarchy (70 points) . . . . . . . . . . . . . . . . . . . 32 4.4 The Constructible Universe (40 points) . . . . . . . . . . . . . . . . . . . . 34 5 Forcing (160 points) 37 5.1 Names and Interpretation (40 points) . . . . . . . . . . . . . . . . . . . . 37 5.2 The Forcing Relation (40 points) . . . . . . . . . . . . . . . . . . . . . . . 39 5.3 Adding Cohen Reals (80 points) . . . . . . . . . . . . . . . . . . . . . . . 41 5.4 Epilogue: Towards Easton’s Theorem . . . . . . . . . . . . . . . . . . . . . 43 4 Notation • iff: if and only if. • ¬ : ¬ φ means “ φ is false”. • ∧ : φ ∧ ψ means “ φ and ψ ”. • ∨ : φ ∨ ψ means “ φ or ψ ”. • = ⇒ : φ = ⇒ ψ means “ φ implies ψ ”. • ⇐⇒ : φ ⇐⇒ ψ means “ φ iff ψ ”. • ∀ : ∀ x φ ( x ) means “ φ ( x ) holds for all x ”. • ∃ : ∃ x φ ( x ) means “ φ ( x ) holds for some x ”. • x ∈ X means “ x is an element of X ” or “ X contains x ”. • ( ∀ x ∈ X ) φ ( x ) means ∀ x ( x ∈ X = ⇒ φ ( x )), “ φ ( x ) holds for all x ∈ X ”. • ( ∃ x ∈ X ) φ ( x ) means ∃ x ( x ∈ X ∧ φ ( x )), “ φ ( x ) holds for some x ∈ X ”. • ∃ !: ∃ ! x φ ( x ) is short for ∃ x ( φ ( x ) ∧ ∀ y ( φ ( y ) = ⇒ x = y )), “ φ ( x ) holds for exactly one x ”. Similarly, ( ∃ ! x ∈ X ) φ ( x ) is short for ∃ ! x ( x ∈ X ∧ φ ( x )), “ φ ( x ) holds for exactly one x ∈ X ”. • ⊆ : x ⊆ y is short for ( ∀ z ∈ x ) z ∈ y . • { F ( x ) ∈ X : φ ( x ) } is short for { y ∈ X : ∃ x ( y = F ( x ) ∧ φ ( x )) } . A Note on Rigor In this Power Round, you may freely use any of the rules of logic, so there is no need to be pedantic about that. Furthermore, for problems that ask you to prove things about meta-mathematical objects (such as formulas), you may use informal arguments. After all, we do not give rigorous definitions for meta-mathematical objects, so being rigorous in your proofs is not even possible. However, you must be very rigorous when proving things about sets. This is especially important in the first section, where we build everything up from the foundations. You are not allowed to write things like { x } or { x, y, z } or X × Y before they are introduced (unless you define them yourself and prove that they work)! 5 1 Zermelo-Fraenkel Set Theory (50 points) At first glance, the mathematical concept of a set could not be simpler: it is simply any collection of things. However, after some careful thought, things start to break down. In 1901, Bertrand Russell considered the set R = { x : x / ∈ x } , consisting of all sets that don’t contain themselves. So, does R contain itself? Well, by definition, R contains R if and only if R does not contain R ! This paradox, known as Russell’s paradox , indicates that something is wrong with our na¨ ıve notion of sets. The only way to resolve this paradox is to declare that R does not exist – that there is no set consisting of precisely those sets that don’t contain themselves. In other words, we need to part ways with the idea that any collection of things can be a set. Since we can’t make the assumption that any collection forms a set, we instead make a different (and much more complicated) list of assumptions in order to work with sets. These are known as the axioms of Zermelo-Fraenkel set theory ( ZFC ), named after Ernst Zermelo and Abraham Fraenkel, who developed it in the early 20th century. 1.1 Logical Formulas (10 points) Before we get started, we need to say some words about how mathematical logic works in the world of axiomatic set theory. Read this part carefully! In set theory, sets are the only kind of mathematical object. Everything is a set. To talk about sets, we use formulas . Definition 1.1.1 — A formula (in set theory) is a statement about sets, involving some number of variables , which represent sets. If a formula explicitly depends on a variable, then the variable is called free . Otherwise, the variable is called bound . If a formula has no free variables, then it is called a sentence . The expression φ ( x , x , . . . , x ) refers to some formula whose free variables are 1 2 n among x , x , . . . , x . (It might be the case that some of the variables x are bound, 1 2 n i or do not occur in the formula at all.) By itself, this definition probably doesn’t make a whole lot of sense, so we give many examples to illustrate what it means. • x ∈ y is a formula with two free variables, x and y . The meaning of this statement depends on what sets we substitute in place of x and y . • ∃ x ( x = y ) is a formula with one free variable, y , and one bound variable, x . The meaning of this statement depends on y , but it does not depend on x , because x is just a dummy variable without an actual value assigned to it. Instead, we say that we are quantifying over x using the symbol ∃ . • ∀ x ( ¬ x ∈ x ) has no free variables, so it is a sentence. Similarly, we are quantifying over x using the symbol ∀ . • x ∈ y ∧ ∀ x ( y ∈ x ) is... erm... is x free or bound?? It is free in its first occurrence, but bound in its later occurrences. Such cursed situations are technically allowed in logic, but for obvious reasons, it is a very bad idea to write formulas like this, so we will assume that this never happens. 6 Any formula can be written in terms of the symbols = (equality), ∈ (set membership), and the logical symbols ¬ , ∧ , ∨ , ⇒ , ⇔ , ∀ , ∃ defined in the Notation section. Usually, we will abbreviate formulas using other symbols, such as ⊆ . For instance, we can abbreviate ( ∀ z ∈ x ) z ∈ y as x ⊆ y . Notice that when performing such abbreviations, bound variables can disappear, but the free variables don’t change. In the example above, after we abbreviate the formula, the bound variable z disappears, but the free variables are x and y regardless.
解析
暂无解答链接。
Original Explanation
No solutions link available.