Homework problems 9-13 Finalized J.O.

9. Using our logical axioms and structural rules as discussed in class (but not the axioms of ZFC), give a formal proof that equality is symmetric: i.e., prove ⊢∀x∀y(x=y→y=x) in our formal system.

• $\{(x=y)\}\vdash x=y$ by the Law of Assumption
• $\{(x=y)\}\vdash y=y$ axiom
• $\{(x=y)\}\vdash y=x$ by (=E)
• $\vdash(x=y\rightarrow y=x)$ by ($\rightarrow$I)
• $\vdash\forall x\forall y(x=y\rightarrow y=x)$ by $\forall$I

10 a. Using our logical axioms and structural rules as discussed in class (but not the axioms of ZFC), give a formal proof of ⊢∃x(x=x). You could say that our logic assumes that at least one thing exists.
b. Can you prove that there exist at least two things? (If nothing else, give an unofficial wff expressing that there exist at least two things.)

Pf of (a):

1. $\vdash\left(x=x\right)$ by =I
2. $\left[y|x\right]\left(y=y\right)$ by $\exists I$
3. thus $\exists x\left(x=x\right)$

Pf of (b):
Unofficial WFF version: $\exists x\exists y \left(x\neq y\right)$

Given (a), must do the same for another element $z\neq x$

1. $\vdash\left(z=z\right)$ by =I
2. $\left[y|z\right]\left(y=y\right)$ by $\exists I$
3. $\text{since} x\neq z, \text{then there exist two separate things}$

11. Prove that N is well-ordered: every nonempty subset X of N has a least element.

(Prof. Simmons, 2-26-18: This has some of the right ideas, but it doesn't prove that $\mathbb{N}$ is well ordered.)

Pf:
Suppose there is a non-empty set $X$ such that $X\subset \mathbb{N}$ where:

1. $1\in X$
2. $k+1 \in X \text{for each} k\in X$

(By (ordinary) induction, this is just $\mathbb{N}$; that doesn't prove that $\mathbb{N}$ is well ordered. Also recall our convention that the naturals start with 0.)

Consider the complement $X^C$. And suppose $X^C$ has a least element (that can't be 1 or anything bigger than 1 because it would have to contain any numbers immediately before it). (This is the heart, but it needs to be stated more clearly. Use induction explicitly: "Suppose all natural numbers less than $k$ belong to $X^C$. Then $k$ also belongs to $X^C$ lest $k$ be a least element.")
Therefore, there is no smallest element of $X^C$. Since this is true, $X^C$ is empty. Therefore, $X$ is the set of all $\mathbb{N}$ which are well ordered.

12.Give an example of an invalid deduction (i.e., the conclusion is not true even though the hypothesis is) using the ∃-introduction rule if we don't require y to be free in ϕ. (Hint: find a simple formula ϕ involving ∀y such that ϕ[y|x] is always true but ∃xϕ is not.)

• $\phi = \forall y(x=y)$
• $\phi\left[x|y\right] = \forall y(y=y)$
• $\exists x\phi := \exists x\forall y(x=y)$

13. Using induction, prove that $5^{2n+1}+2^{2n+1}$ is divisible by 7 for all n∈N.
Pf:
This works for the base case (n=0):
$5^{2(0)+1} +2^{2(0)+1} = 5^{1 + 2^1} = 7^1, \text{so then} \rightarrow7|7$

Now suppose $n=k$ for all $k\in \mathbb{N}$, then $n=k+1$ also holds:

$5^{2(k+1)+1} + 2^{2(k+1)+1}$
$= 5^{2k+3} + 2^{2k+3}$
$=5^{2k}\times 5^3 + 2^{2k}\times 2^3$
$=5^{2k}\times 125 + 2^{2k}\times 8$
Since $5^{2k}+2^{2k}$ holds, then if $125+8=133$ is divisible by 7, then $5^{2n+1}+2^{2n+1}$ is always divisible by 7. Since $133\div 7 =19$, it always holds.