Prelim Problems 15-17 J.O.

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.

page revision: 18, last edited: 22 Feb 2018 03:19