PUMaC 2025 · 加试 · 第 3 题
PUMaC 2025 — Power Round — Problem 3
题目详情
- ZFC proves (Bew( ⌜ φ ⌝ ) ∧ Bew( ⌜ φ ⇒ ψ ⌝ )) = ⇒ Bew( ⌜ ψ ⌝ ). The G¨ odel sentence G is then constructed, using a clever trick, so that ZFC proves the sentence G ⇐⇒ ¬ Bew ( ⌜ G ⌝ ). It follows easily that ZFC ⊬ G : if not, then we would have both ZFC ⊢ Bew ( ⌜ G ⌝ ) (by the 1st provability condition) and ZFC ⊢ ¬ Bew ( ⌜ G ⌝ ) (by the definition of G ), which contradicts the consistency of ZFC . Unfortunately, G¨ odel was not able to show that ZFC ⊬ ¬ G without introducing some additional assumptions. In 1936, J. Barkley Rosser got around this problem by slightly tweaking the definition of Bew ( ⌜ φ ⌝ ), and thus he also gets credit for the theorem. We won’t go into the details here. In the paper that G¨ odel introduced his first incompleteness theorem, he also sketched a proof of his second incompleteness theorem , which we state below. Definition 3.4.3 — The sentence Con( ⌜ ZFC ⌝ ) is defined as ¬ Bew( ⌜ ⊥ ⌝ ). Theorem 3.4.4 (G¨ odel) If ZFC is consistent, then ZFC ⊬ Con( ⌜ ZFC ⌝ ). The proof is quite technical and provides little insight. After assuming for the sake of contradiction that ZFC ⊢ Con ( ⌜ ZFC ⌝ ), it is basically a matter of figuring out how to use the provability conditions given above to deduce that ZFC ⊢ G , which would produce a contradiction due to the first incompleteness theorem. Contrary to popular belief, Con( ⌜ ZFC ⌝ ) does not state that ZFC (the base theory) is consistent. After all, “ ZFC is consistent” is a meta -mathematical statement! Instead, the sentence Con ( ⌜ ZFC ⌝ ) states that the coded theory ⌜ ZFC ⌝ is consistent, and ⌜ ZFC ⌝ is, of course, not the same as ZFC . 27 4 Models of Set Theory (180 points) It’s time to get even more meta ! In the last section, we discussed the phenomenon of a sentence being independent from ZFC . But barring contrived examples like the G¨ odel sentence, how would we show that something like the continuum hypothesis is independent? Perhaps it is best to begin with a simpler example from arithmetic. Suppose that we start from some “axioms” about integers, say the following: ( x + y ) + z = x + ( y + z ) , x + y = y + x, x + 0 = x, x + ( − x ) = 0 , ( x · y ) · z = x · ( y · z ) , x · 1 = x, x · 0 = 0 , x · ( y + z ) = ( x · y ) + ( x · z ) , for all x, y, z . These are known as the ring axioms . Now, we ask: is it possible to prove or disprove the statement 0 ̸ = 1 from the ring axioms? Well, of course we can’t disprove it – it’s true! But it turns out that we also can’t prove it. To see why, imagine an alien civilization that uses a bizarre number system, in which all numbers are equal . In particular, they believe that 0 = 1. But they also believe that all of the ring axioms are true. If we somehow came up with a proof of 0 ̸ = 1 using only the ring axioms, then the proof would work equally well for the aliens’ number system, and they could use it to show that 0 ̸ = 1. However, that is not true in the alien number system! Therefore, such a proof cannot exist. What we’ve done here is construct a new setting (a new “number system”) in which all the ring axioms hold, but in which 0 ̸ = 1 fails. In general, a setting in which the ring axioms hold is called a ring . For example, we have a ring Z of integers, in which 0 ̸ = 1 is true. But the aliens also have a ring { 0 } , consisting of just one number, in which 0 ̸ = 1 is false. If a statement can be proved from the ring axioms, then it must be true in all rings, and since the statement 0 ̸ = 1 is true in some rings but false in others, it must be independent from the ring axioms. We can apply the same ideas to set theory. Let’s define a model of ZFC as a “setting” in which the axioms of ZFC hold true. (This will be made rigorous below.) In order to prove that the continuum hypothesis is independent from ZFC , all we need to do is to exhibit a model of ZFC in which CH is true, and a model of ZFC in which CH is false. Of course, this is much easier said than done... 4.1 Relativization (30 points) Before giving a rigorous definition of a model, we need to study some aspects of logical formulas in detail. Definition 4.1.1 — The universal quantifier is the symbol ∀ , and the existential quantifier is the symbol ∃ . A quantifier is one of these two symbols. Let φ be a formula, written formally (so no abbreviations). If a quantifier occurs as part of the expression ∀ x or ∃ x for some variable x , then that occurrence of the quantifier in φ is unbounded . If a quantifier occurs as part of ( ∀ x ∈ X ) or ( ∃ x ∈ X ) for some variables x and X , then that occurrence of the quantifier is bounded . For example, let’s write down the axiom of union formally: ∀ X ∃ U ∀ y ( y ∈ U ⇐⇒ ( ∃ x ∈ X ) y ∈ x ) . There are four quantifiers in this sentence: two universal quantifiers and two existential quantifiers. The first three quantifiers are unbounded, and the last one is bounded. 28 Every formula can be rewritten such that all quantifiers are unbounded: we can just replace all occurrences of ( ∀ x ∈ X ) φ ( x ) with ∀ x ( x ∈ X = ⇒ φ ( x )) and ( ∃ x ∈ X ) φ ( x ) with ∃ x ( x ∈ X ∧ φ ( x )). Definition 4.1.2 — Let φ be a formula. For a class M , the relativization of φ to M M , denoted φ , is the formula obtained by writing φ such that all quantifiers are unbounded, and then replacing all instances of ∀ x with ( ∀ x ∈ M ) and all instances M of ∃ x with ( ∃ x ∈ M ). If φ is true, then we say that φ is true in M . For example, let φ be the formula Y = P ( X ), which is short for ∀ A ( A ∈ Y ⇐⇒ ∀ x ( x ∈ A = ⇒ x ∈ X )) . M After we relativize to M , the resulting formula φ is ( ∀ A ∈ M )( A ∈ Y ⇐⇒ ( ∀ x ∈ M )( x ∈ A = ⇒ x ∈ X )) . M Intuitively, φ states that “ M thinks that φ is true”, as M can only “see” sets that are in M . Anthropomorphism is quite common in set theory :)
解析
暂无解答链接。
Original Explanation
No solutions link available.