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.

Comments - Andrew Furash

Looks great!