Questions 15-17 Pre-Write

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License