15. Statement: For all x,y∈N, if x<y, then either Succ(x)<y or Succ(x)=y.

Proof: We can begin by proving that the statement holds for y=0. If x<0, the statement is vacuously true as Succ(x)=y. We then assume that the statement holds for y and that x<Succ(y). The y+1 case can be proved by using Succ(y) in place of y. x<Succ(y) from the definition of <, we get x∈Succ(y). Succ(y) by definition then becomes {y U {y}}.

x ∈ {y U {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

Succ(x)={y U {y}}

Succ(x)=Succ(y)

b. Statement: (N,<) satisfies trichotomy.

Proof: We can begin by proving that the statement holds for y=0. As we are dealing with the natural numbers, x<0 is false so either x=0 or 0<x. For the base case, either of these could be true. We then assume that the statement holds for y. y<x holds as y<Succ(y) and thus x=Succ(y). Using the lemma from 15 a, we can show that x=y (x∈{y}) and x<y.

16. Statement: If y<succ(x) then y ≤x.

Proof: y<{x U {x}}

y Є x V y Є{x}

y<x V y=x

y ≤x

17. Statement: For all sets x,y, it is impossible for both x∈y and y∈x to hold.

Proof: Let x be a set of elements in a set S. Assume x exists in the set S'. Let the set of sets with the elements in S' be denoted by S''. Assume towards contradiction that x∈y and y∈x both hold. x and y are both sets by definition. If x ∈ S', then by x∈y, y∈S' and y∈S'' but y does not exist in S. However, y∈x says y∈S, this is a contradiction.

Comments - Andrew Furash

Nice work here.