Questions 9-10 Pre-Write

9.Statement: ⊢∀x∀y(x=y→y=x)
-will use ∀I and →I
1. For →I: Σ, φ ⊢ ψ implies Σ ⊢ φ → ψ. So what are φ and ψ? If φ is x=z, φ[x|z] implies x=x which is true by definition. Thus, x is free in φ so φ[y|z] gives x=y. Similarly, if ψ is z=x, φ[x|z] implies x=x, and ψ[y|z] gives y=z.
Σ, (x=y) ⊢ (y=x) gives Σ ⊢ (x=y) → (y=x)
2. If from 1 we get that θ = (x=y) → (y=x), the application of ∀I gives Σ ⊢ ∀x∀y(x=y) → (y=x) provided that x and y are not free in Σ.

10. Statement: ⊢∃x(x=x)
1. (x=x) is an atomic formula
2. ⊢(x=x) exists from 1 by the axiom of =I
3. In order to apply ∃I from 1, Σ⊢φ[y|x] must hold. If φ equals (x=x), it follows that (x=x)[y|x] is true as y=y is always true, so x must be a free variable not bound by any quantifiers. Thus, it holds that ⊢∃x(x=x).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License