Questions 15-17 Post Write

15. Statement: For all x,y∈\$\mathbb{N}\$, if x<y, then either Succ(x)<y or Succ(x)=y.
Proof: Suppose x, yЄ\$\mathbb{N}\$ and x<y. The statement is vacuously true for y=0, x<0. We then assume that the statement holds for y, that x<Succ(y), and succ(y)Є\$\mathbb{N}\$. If x<Succ(y), from the definition of <, we get x∈Succ(y). Succ(y) then becomes {y U {y}}.
x∈{yU{y}}
x∈y V x∈{y}
If x∈{y}, x=y and Succ(x)=Succ(y)
If x∈y, x<y which means Succ(x)<y or Succ(x)=y.
Succ(x)<y
Succ(x)∈y
Succ(x)∈{y U{y}}
Succ(x)∈Succ(y)
Succ(x)<Succ(y)
If Succ(x)=y, then succ(x)<succ(y) as yЄyU{y} and yЄsucc(y) implying succ(x)Єsucc(y) and succ(x)<succ(y).
b. Statement: ∀x,y∈\$\mathbb{N}\$(x<y∨y<x∨x=y)
Proof: We can prove this by using induction on y. If y=0, ∀x,y∈N(x<0∨0<x∨x=0). It follows that y<x∨x=y. Only one of these can hold as \$\mathbb{N}\$ is well-ordered (Lemma Q11) and for a given y, x is either 0 or greater than 0. We then assume that the statement holds for all y and prove it for succ(y).
∀x,y∈N(x<succ(y)∨succ(y)<x∨x=succ(y)). Using the lemma from Q15a, x<succ(y) is true. If succ(y)<x, succ(y)Єx and yU{y}Єx. It follows that yЄx or {y}Єx. If yЄx, y<x is true which satisfies the hypothesis. Similarly, if {y}Єx, y=x which is also true. If x=succ(y) and y<succ(y), y<x.

16. Statement: If y<succ(x) then y ≤x.
Proof: Suppose x, yЄN and y<succ(x).
y<{xU{x}}
yЄxVyЄ{x}
y<xVy=x
y≤x

17. Statement: For all sets x,y, it is impossible for both x∈y and y∈x to hold.
Proof: Suppose that there exists arbitrary sets x and y such that the x∈y and y∈x both hold. The set z is the set containing both x and y, z = {x, y}. By foundation, z must be disjoint from either x or y. Two sets are said to be disjoint sets if they have no element in common. However, x ∩ z ∋ y and y ∩ z ∋ x means that the set is not disjoint. Thus, the statement violates foundation and cannot hold.

page revision: 4, last edited: 03 Mar 2018 17:03