PUMaC 2025 · 加试 · 第 4 题

Problem 4.1.2 (10 points) Prove that any ∆ formula is absolute for any transitive class. (Hint: when working 0 with formulas, a common strategy is to induct on the length of the formula.) 29 If a formula φ ( x , . . . , x ) is logically equivalent to a ∆ formula ψ ( x , . . . , x ), then it 1 n 0 1 n is not hard to see that φ ( x , . . . , x ) is also absolute in any transitive class. (By logically 1 n equivalent, we mean that the sentence ∀ x · · · ∀ x ( φ ( x , . . . , x ) ⇐⇒ ψ ( x , . . . , x )) can 1 n 1 n 1 n be proven logically, without using the axioms of ZFC .) For example, • “ x ⊆ y ” is short for ( ∀ z ∈ x ) z ∈ y , which is ∆ . 0 • “ x = ∅ ” is equivalent to ¬ ( ∃ y ∈ x ) y = y , which is ∆ . 0 • “ x is transitive” is short for ( ∀ y ∈ x ) y ⊆ x , which is ∆ . 0 • “ α is an ordinal” is equivalent to ( ∀ x ∈ α )( x ⊆ α ∧ x is transitive), which is ∆ . 0 • “ y = x ∪ { x } ” is equivalent to x ⊆ y ∧ x ∈ y ∧ ( ∀ z ∈ y )( z ∈ x ∨ z = x ), which is ∆ . 0 • “ z = { x, y } ” is equivalent to x ∈ z ∧ y ∈ z ∧ ( ∀ w ∈ z )( w = x ∨ w = y ), which is ∆ . 0 In particular, “ y = { x } ” is equivalent to a ∆ formula. 0 • “ z = ( x, y )” is equivalent to ( ∃ s ∈ z )( ∃ p ∈ z )( z = { s, p } ∧ s = { x } ∧ p = { x, y } ), so it is equivalent to a ∆ formula. 0 • “ f is a function X → Y ” is equivalent to ( ∀ x ∈ X )( ∃ y ∈ Y )(( ∃ p ∈ f ) p = ( x, y ) ∧ ( ∀ z ∈ Y )(( ∃ q ∈ f ) q = ( x, z ) = ⇒ y = z )) ∧ ( ∀ p ∈ f )( ∃ x ∈ X )( ∃ y ∈ Y ) p = ( x, y ). If that was too complicated to parse, feel free to skip it. Of course, this is also ∆ . 0 S • The following are all equivalent to ∆ formulas: z = x ∪ y ; z = x ∩ y ; Y = X ; 0 T Y = X ; Z = X × Y ; R is a relation; X = dom ( R ); X = ran ( R ); f is a function; f is an injection/surjection/bijection X → Y . Therefore, these formulas are all absolute in any transitive class. Of course, not every formula is equivalent to a ∆ formula. First of all, sentences are 0 never ∆ : since all variables in the sentence are bound by quantifiers, the sentence must 0 start with an unbounded quantifier (possibly after a ¬ symbol). Second of all: