Finalized Homework Problems 15-17

15. a. Prove that for all x,y∈N, if x<y, then either Succ(x)<y or Succ(x)=y. (We say that Succ(x) is an immediate successor of x.)) Hint: Use induction on y.
Pf:**

We induct on $y$.
The statement is vacuously true for $y=0$.
Suppose the statement is true for $y=k$.
Consider the statement with the condition $y=Succ(k)$.
If $x<Succ(k), \ \text{then}\ x\in k\cup\{k\}$. Then either $x=k$ or $x\in k$.
If $x=k$, then $Succ(x)=Succ(k)$.
If $x\in k, \text{and thus}\ x<k\ \text{with}\ k<Succ(k), \Longrightarrow Succ(x)<Succ(k)$

b. Prove that (N,<) satisfies trichotomy: For all x,y∈N, exactly one of the following holds: x<y,x=y, or y<x. Hint: Again use induction on one of the variables. Apply the lemma in part a. at an appropriate point.

We induct on y.
The statement is vacuously true for $y=0$.
Suppose the statement is true for $y=n$, Then consider the statement with the condition $y=Succ(n)$.
If $x<Succ(n)$, using the lemma from 15a, either $Succ(x)<Succ(n)$ or $Succ(x)=Succ(n)$ is true.
If $Succ(x)<Succ(n)$, in which case, $x$ can't be equal to $Succ(n)$ nor greater than since
$x<Succ(x)$.
If $Succ(x)=Succ(n)$, then $x=n$. In which case, since $n\in Succ(n)$, and $x=n$, $x\ in Succ(n)$.
The proof is the same for the opposite condition where $x>Succ(n)$.
Now suppose that $x=Succ(n)$. Then $x= n\cup \{n\}$.
If this is true, $x$ cannot be greater than or less than $Succ(n)$.

16. (Preliminary for Th, Feb 22; finalized Sat, March 3) Using only results proven in class or assigned earlier (i.e., don't use induction), show that for all natural numbers x,y, if y<Succ(x), then y≤x.

Pf:
Suppose true.
Then $y\in x\cup\{x\}$.
Either $y\in x$ or$y\in \{x\}$
This would mean that either $y<x$ for the first case or that $y=x$ in the second case.

17. Prove that for all sets x,y, it is impossible for both x∈y and y∈x to hold.
Pf:
Suppose that there exists a set $B:=\{x,y\}$.
In order for $x\in y$ and $y\in x$ to hold, $B$ must be disjoint with one of its elements.
However, consider some $b\in B$ such that
$y\in x\cap b$ and $x\in y\cap b$.
Thus the statement violates foundation and cannot hold.