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 =
7/7 =1
Based on this idea, assume the argument holds true for n=k.
52k+1+22k+1=7J where JЄ$\mathbb{N}$
Next, we must show that the argument holds for n=k+1.
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.

Comments - Andrew Furash
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!

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