**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.**

**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.**

**Pf:**

If $x < Succ(y)$, then $x\in Succ(y)$.

This would then mean that $x\in \{y\bigcup \{y\}\}$.

If this is true, then either:

$\left(x\in y\right) \vee \left(x\in \{y\}\right)$.

If $x\in \{y\}$, then $x=y$. This would mean that $Succ(x)=Succ(y)$.

On the other hand, if $x\in y$, then $x<y$.

This would mean two possibilities:

$Succ(x)<y \vee Succ(x)=y$

Using the L.H.S, if $Succ(x)<y$, then $Succ(x)\in y$. If $Succ(x) \in \{y\bigcup \{y\}\}$,

Then $Succ(x)<Succ(y)$.

On the R.H.S., if $Succ(x)=y$, then since $y\in \{y\bigcup \{y\}\}$,

$Succ(x) \in Succ(y)$ and so $Succ(x)<Succ(y)$.

**Pf of b:**

Suppose both x and y are distinct elements of $\mathbb{N}$The base case is vacuously true for the empty set.

Suppose $x<y$, then using the lemma above, either $Succ(x)<y \vee Succ(x)=y$. Since there is no $x$ that is either greater than or equal to $y$, there is exactly only one possibility: that $x<y$.

It is the same reasoning for the relation $y<x$ except $y$ and $x$ are flipped.

Lastly, if $x=y$, then using Axiom of Formation, $x\notin y \wedge y \notin x$

**16. 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\bigcup\{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.**

Suppose $x\in y \wedge y\in x$ holds.

Thus each set is defined as having eachother within them: $x:= \{y....\}$ and $y:=\{x...\}$

Since both are elements of eachother,

$x:=\{\{x...\}...\}$ and $y:=\{\{y....\}...\}$.

There's gotta be some way that an element of an element of a set cannot be equal to the set.

Will revisit.