Mg Problems 15 17

PRELIMINARY

15)
a. Theorem: For all $x,y \in \mathbb{N}$, if $x<y$, then either $Succ(x) < y$ or $Succ(x) = y$.

To prove this, we must use induction. Consider first the base case of $y=\{\emptyset\}$, or $y=1$. Note that in order for $x < y$ to hold, y cannot be zero, or the null set, as by definition, $x\in y$. Thus, we cannot have both $x,y \in \mathbb{N}$ and $x<y$ if y is anything less than 1.

Now, in the base case, the only $x \in \mathbb{N}$ satisfying $x<y$ is $x = 0$, or $x = \emptyset$. Therefore, we can clearly see that since $Succ(\emptyset) = \{\emptyset\}$, $Succ(x) = y$. Thus, the theorem holds for y = 1. We will now assume that the theorem holds for some $y \in \mathbb{N}$ and prove from this that the theorem holds for $Succ(y)$.

If $x=Succ(y)$, then $Succ(x) = Succ((Succ(y))$, and the theorem holds. If $x < y$, then $Succ(x) \in y$ or $Succ(x) = y$, by the inductive hypothesis. If $Succ(x) = y$, then $Succ(y)=Succ(Succ(x))$, and since $k \in Succ(k)$ for all k, $Succ(x) \in Succ(y)$, meaning $Succ(x) < Succ(y)$, and the theorem holds. $QED$

b. Theorem: $(\mathbb{N}, <)$ satisfies trichotomy, i.e. for all $x,y \in \mathbb{N}$, exactly one of the following holds: $x<y$, $x=y$, or $y<x$.

First, we will show that the three relations, $x<y$, $x=y$, and $y<x$, are mutually exclusive. Suppose toward contradiction that the $x<y$ and $y=x$ both hold. As $x<y$, for the natural numbers $x\in y$. By substitution, we see that $x\in{x}$. Following from foundation, we know that this is impossible. Therefore, it cannot be the case that $x<y$ and $y=x$. Analogous logic proves that $y<x$ and $y=x$ cannot both hold. To finish the proof that the statements are mutually exclusive, we must show that $x<y$ and $y<x$ cannot both hold. This is proven in 17 below.

From here, we must simply show that one of the three relations must hold for all $x,y\in\mathbb{N}$. We shall induct on y. Consider base case $y=0$, or written $y=\emptyset$. If $x=\emptyset$, obviously $x=y$ by transitivity. If $x\neq\emptyset$, $x\in \mathbb{N}\backslash{0}$. For any such x, $\emptyset \in x$ by the construction of the natural numbers, and therefore $y \in x$, or $y < x$, and the statement holds. Now we will assume that for some $y\in \mathbb{N}$, $x<y$, $x=y$, or $y<x$. We must simply prove that either $x < Succ(y)$, $x = Succ(y)$, or $Succ(y) < x$ for all $x\in \mathbb{N}$. From 15(a), we know that if $y<x$ then either $Succ(y) < x$ or $Succ(y) = x$, and either way the statement holds. If $y=x$, then by definition $y\in Succ(y)$ and therefore $x \in Succ(y)$, proving $x<y$. Again the statement holds. Finally, if $x<y$, then $x \in Succ(y)$ because $Succ(y)$ by definition contains y and all elements of y. $QED$

16. Theorem: For all $x,y\in \mathbb{N}$, if $y<Succ(x)$ then $y\leq{x}$. (Note: Prove with theorems from earlier, not by induction.)

To begin, we may clarify that the statement $y\leq{x}$ is shorthand for $((y=x)\vee (y<x))$. Now, the from the statement $y< Succ(x)$, we can say by the definitions of $<$ and $Succ$ that $y \in \{x \cup \{x\}\}$. This being the case, we know that either $y\in x$ or $y\in\{x\}$. If $y\in x$, then $y<x$ by definition. If $y\in\{x\}$, since $\{x\}$ has but one element, $x$, it must be the case that $y=x$. From this we can say that for all $x,y\in\mathbb{N}$, either if $y<Succ(x)$ then $y<x$ or $y=x$, abbreviated $y\leq{x}$. $QED$

17. Theorem: For all sets $x,y$, it is impossible for both $x \in y$ and $y \in x$ to hold.

Suppose not. Let $x,y$ be arbitrary sets. $x \in y$ implies that $y=\{x, ...\}$, and $y \in x$ implies that $x=\{y, ...\}$, with the notation "$...$" implying any number of other elements. Since $x\in y \wedge y \in x$, we can substitute into either set and say that $y = \{\{y, ...\},...\}$. Following from the axiom of foundation, we know that a set cannot be contained within itself. However, the element $\{y,...\}\in y$ contains y. Thus, by contradiction, for all sets $x,y$, it is impossible that both $x\in y$ and $y\in x$ hold. $QED$.

_
FINALS

15)

a. Theorem: For all $x,y \in \mathbb{N}$, if $x<y$, then either $Succ(x) < y$ or $Succ(x) = y$.

Proof: Let sets $x,y \in \mathbb{N}$ exist such that $x<y$. To show the theorem is true for all $x,y$, we will induct on $y$. Consider base case $y=0$, or $y=\emptyset$. The theorem is vacuously true, since there exist no $x \in \emptyset$. Now, suppose that for some $y$, for all $x<y$, either $Succ(x) < y$ or $Succ(x) = y$. From here, we must prove that the theorem holds for $Succ(y)$. First, $x<y$ by definition means $x\in{y}$.

If $x<Succ(y)$, then, by the definition $Succ(y)=\{y \cup \{y\}\}$, either $x \in y$ or $x=y$. If $x \in y$, then by the inductive hypothesis, either $Succ(x) < y$ or $Succ(x) = y$. In both cases, $Succ(x) \in Succ(y)$ because everything in $y$ is in $\{y\cup\{y\}\}$ and $y \in Succ(y)$, and the theorem holds. If $x=y$, then, since $y \in Succ(y)$, $x \in Succ(y)$, and again the theorem holds. $QED$

b. Theorem: $(\mathbb{N}, <)$ satisfies trichotomy, i.e. for all $x,y \in \mathbb{N}$, exactly one of the following holds: $x<y$, $x=y$, or $y<x$.

Proof: First, we will show that the three relations, $x<y$, $x=y$, and $y<x$, are mutually exclusive. Suppose toward contradiction that the $x<y$ and $y=x$ both hold. As $x<y$, for the natural numbers $x\in y$. By substitution, we see that $x\in{x}$. Following from foundation, we know that this is impossible. Therefore, it cannot be the case that $x<y$ and $y=x$. Analogous logic proves that $y<x$ and $y=x$ cannot both hold. To prove that the statements are mutually exclusive, we must now show that $x<y$ and $y<x$ cannot both hold. This is proven in 17 below.

Next, we must prove that, for all $x,y \in \mathbb{N}$, one of the three relations holds. We shall induct on y. Consider base case $y=0$, otherwise written $y=\emptyset$. If $x=\emptyset$, obviously $x=y$ by transitivity. If $x\neq\emptyset$, $x\in \mathbb{N}\backslash{0}$. For any such x, $\emptyset \in x$ by the construction of the natural numbers, and therefore $y \in x$, or $y < x$, and the statement holds. Now we will assume that for some $y\in \mathbb{N}$, $x<y$, $x=y$, or $y<x$. We must simply prove that either $x < Succ(y)$, $x = Succ(y)$, or $Succ(y) < x$ for all $x\in \mathbb{N}$. From the inductive hypothesis, we know that $x<y$, $x=y$, or $y<x$ must be the case for all $x$. From 15(a), we know that if $y<x$ then either $Succ(y) < x$ or $Succ(y) = x$, and either way the statement holds. If $y=x$, then by definition $y\in Succ(y)$ and therefore $x \in Succ(y)$, proving $x<y$. Again the statement holds. Finally, if $x<y$, then $x \in Succ(y)$ because $Succ(y)$ by definition contains y and all elements of y. $QED$

16. Theorem: For all $x,y\in \mathbb{N}$, if $y<Succ(x)$ then $y\leq{x}$. (Note: Prove with theorems from earlier, not by induction.)

Let sets $x,y \in \mathbb{N}$ exist such that $y<Succ(x)$. To begin, we may clarify that the statement $y\leq{x}$ is shorthand for $((y=x)\vee (y<x))$. Now, the from the statement $y< Succ(x)$, we can say by the definitions of $<$ and $Succ$ that $y \in \{x \cup \{x\}\}$. This being the case, we know that either $y\in x$ or $y\in\{x\}$. If $y\in x$, then $y<x$ by definition. If $y\in\{x\}$, since $\{x\}$ has but one element, $x$, it must be the case that $y=x$. From this we can say that for all $x,y\in\mathbb{N}$, if $y<Succ(x)$ then $y<x$ or $y=x$, abbreviated $y\leq{x}$. $QED$

17. Theorem: For all sets $x,y$, it is impossible for both $x \in y$ and $y \in x$ to hold.

Proof: Suppose not. Let there exist set $z = \{x,y\}$, where $x\in{y}$ and $y\in {x}$. By the axiom of foundation, either x or y must be disjoint from z. But $x \in y$ and $x \in z$, and $y \in x$ and $y \in z$. This contradicts foundation. $QED$