Questions 11-13 Post-Write

13. Statement: 52n+1+22n+1 is divisible by 7 for all n Є \$\mathbb{N}\$.
Proof: We can begin by proving that 52n+1+22n+1 being divisible by 7 is true for the base case, n = 0.
52(0)+1+22(0)+1 =
51+21=
5+2=7
7/7 =1
Based on this idea, assume the argument holds true for n=k.
52k+1+22k+1=7J where JЄ\$\mathbb{N}\$
22k+1=7J-52k+1
Next, we must show that the argument holds for n=k+1.
52(k+1)+1+22(k+1)+1=52k+3+22k+3
=52k+1(52)+22k+1(22)
=25(52k+1)+4(22k+1)
=25(52k+1)+4(7J-52k+1)
=25(52k+1)+28J-4(52k+1)
=21(52k+1)+28J
=7[3(52k+1)+4J]
7[3(52k+1)+4J] will always be divisible by 7 regardless of the value of k as long as k Є \$\mathbb{N}\$. Hence, 52n+1+22n+1 is divisible by 7 for all n Є N. ∎

12. Statement: If y is not free in ϕ=∀y(x=y), using the ∃-introduction rule returns an invalid deduction.
Proof: 1. ⊢∀y(x=y)
2. ⊢∀y(y=y) from 1 by ϕ[y|x]
3. ⊢∃x∀y(x=y) from 1 by ∃I
However, ⊢∃x∀y(x=y) is not a valid deduction because there does not exist an x that for all y x=y. ∎

11. Statement: \$\mathbb{N}\$ is well-ordered.
Proof: Let X ⊂ \$\mathbb{N}\$ have no least element. If 0 Є \$\mathbb{N}\$, then X will have a least element and we would be done. Now suppose 0 is not an element in \$\mathbb{N}\$, thus, 1 cannot be an element in \$\mathbb{N}\$, and n-1 is not an element in \$\mathbb{N}\$. If n Є X under these assumptions, then X would have a least element. So, n is not an element in \$\mathbb{N}\$ for every n Є \$\mathbb{N}\$. Therefore, X=∅, but \$\mathbb{N}\$ is not the empty set. Hence, \$\mathbb{N}\$ has a least element and is thus well-ordered. ∎

(Prof Simmons, 2-25-15): This is on the right track (showing that a subset of \$\mathbb{N}\$ with no least element is empty). The induction is a bit unclear: 1 and \$n-1\$ not belonging to \$X\$ isn't sufficient to show \$n\notin X\$; you need that every element less than \$n\$ not belong to \$X\$. You should also explain what \$n\$ is (an arbitrary natural number used for induction) when you first use it. The last line is problematic; having a least element doesn't make a set well ordered.

For 12, you have the right idea, but your number 1 is already an incorrect statement. You need to start with something that is correct and conclude with something incorrect.
13 looks good!

page revision: 2, last edited: 26 Feb 2018 18:27