PRELIMINARY
11. Prove that any nonempty subset $X$ of the natural numbers $\mathbb{N}$ has a least element.
As silly as it sounds, for some reason I'm not sure how to prove that no element of $\mathbb{N}$ equals any other element of $\mathbb{N}$, but once that is done, we can show easily that $\forall{\{A,B \in \mathbb{N}\}}\lnot(A = B) \rightarrow (A < B \cup B > A)$. Thus, every subset has a minimum.
12. Give an example of an invalid deduction using the ∃introduction rule if we don't require y to be free in ϕ.
Suppose $\Phi$ is $\forall{y}(y=x)$. It can easily be shown that $\forall{y}(y=x) \vdash (\forall{y}(y=x))[yx]$. However, $\exists{x}\forall{y}(y=x)$ is obviously false, as one x cannot equal every possible y. Thus, to deduce that the premise $\forall{y}(y=x) \vdash (\forall{y}(y=x))[yx]$ implies that $\forall{y}(y=x) \vdash (\exists{x}\forall{y}(y=x))$ would be an invalid deduction.
13. Using induction, prove that $5^{2n+1}+2^{2n+1}$ is divisible by 7 for all $n \in \mathbb{N}$.
Assume that $5^{2n+1}+2^{2n+1}$ is divisible by 7 for some $n$. Consider base case $n=0$. $5^{2(0)+1} + 2^{2(0)+1} = 5 + 2 = 7$. 7 is clearly divisible by 7. Now, we will prove that the fact that $5^{2n+1}+2^{2n+1}$ is divisible by 7 proves that $5^{2(n+1)+1}+2^{2(n+1)+1}$ is also divisible by 7. To simplify this process, we use modular arithmetic to prove that the fact that $(5^{2n+1}+2^{2n+1}) \mod 7 = 0$ proves that $(5^{2(n+1)+1}+2^{2(n+1)+1}) \mod 7 = 0$.
To start, assume $(5^{2n+1}+2^{2n+1})\mod{7} = 0$.
(1)Now, recall the addition property of modular arithmetic, $(A+B)\mod C = (A\mod{C}+B\mod{C})\mod{C}$, and the multiplication property of modular arithmetic, $(A\cdot B)\mod C = [(A\mod{C})\cdot (B\mod{C})]\mod{C}$. Thus,
(2)by the addition and multiplication properties respectively. Next, we can take the following steps by using the addition property in reverse and simplifying.
(4)Now, we can apply the multiplication property again to show
(7)We simplify and apply the addition property in reverse one last time.
(8)Finally, we know that $(5^{2n+1} + 2^{2n+1})\mod{7} = 0$, so we can substitute and simplify:
(9)Now, since we have proven that the fact that $(5^{2n+1}+2^{2n+1}) \mod 7 = 0$ proves that $(5^{2(n+1)+1}+2^{2(n+1)+1}) \mod 7 = 0$, we have completed the inductive process and have proven that $5^{2n+1}+2^{2n+1}$ is divisible by 7 for all $n \in \mathbb{N}$. QED
14. What are injective and bijective???
FINALS:
11. Prove that $\mathbb{N}$ is wellordered, that is that any nonempty subset has a least element.
Consider X, an arbitrary nonempty subset of $\mathbb{N}$. Suffice it to prove that if X has no least element, then X is the empty set. This would contradict the fact that X is nonempty.
We know that, in the case of the natural numbers, $0 < 1 < 2 < ... < n$. Thus, since a subset X cannot contain a repeated element, we can say that for all subsets with any two or more arbitrary elements, it will have a least element. If X contains just one element, that element is clearly the least element. Therefore, the only way a set can have no least element is if it has no elements at all. This would mean that X is the empty set. QED

If X is not empty, X can either have one element or more than one element. If X has one element, clearly that element is the least element. If has multiple elements, we can simply show that all elements of $\mathbb{N}$ are unequal, since if $n_{1} \neq n_{2}, \{n_{1},n_{2}\}\in \mathbb{N}$, then either $n_{1} < n_{2}$ or $n_{2} < n_{1}$.
In order to prove that all elements of $\mathbb{N}$ are unequal, we may simply prove that $n_{k} \in \mathbb{N}$ has fewer elements than $succ(n_{k})$. Consider base case k = 0. In this case, $n_{k} = \emptyset$, with zero elements, and $succ(n_{k}) = \{\emptyset\}$, with one element. Now, consider the case of
12. Give an example of an invalid deduction using the ∃introduction rule if we don't require y to be free in ϕ.
Suppose $\Phi$ is $\forall{y}(y=x)$. It can easily be shown that $\forall{y}(y=x) \vdash (\forall{y}(y=x))[yx]$. However, $\exists{x}\forall{y}(y=x)$ is obviously false, as one x cannot equal every possible y. Thus, to deduce that the premise $\forall{y}(y=x) \vdash (\forall{y}(y=x))[yx]$ implies that $\forall{y}(y=x) \vdash (\exists{x}\forall{y}(y=x))$ would be an invalid deduction.
13. Using induction, prove that $5^{2n+1}+2^{2n+1}$ is divisible by 7 for all $n \in \mathbb{N}$.
Assume that $5^{2n+1}+2^{2n+1}$ is divisible by 7 for some $n$. Consider base case $n=0$. $5^{2(0)+1} + 2^{2(0)+1} = 5 + 2 = 7$. 7 is clearly divisible by 7. Now, we will prove that the fact that $5^{2n+1}+2^{2n+1}$ is divisible by 7 proves that $5^{2(n+1)+1}+2^{2(n+1)+1}$ is also divisible by 7. To simplify this process, we use modular arithmetic to prove that the fact that $(5^{2n+1}+2^{2n+1}) \mod 7 = 0$ proves that $(5^{2(n+1)+1}+2^{2(n+1)+1}) \mod 7 = 0$.
To start, assume $(5^{2n+1}+2^{2n+1})\mod{7} = 0$.
(10)Now, recall the addition property of modular arithmetic, $(A+B)\mod C = (A\mod{C}+B\mod{C})\mod{C}$, and the multiplication property of modular arithmetic, $(A\cdot B)\mod C = [(A\mod{C})\cdot (B\mod{C})]\mod{C}$. Thus,
(11)by the addition and multiplication properties respectively. Next, we can take the following steps by using the addition property in reverse and simplifying.
(13)Now, we can apply the multiplication property again to show
(16)We simplify and apply the addition property in reverse one last time.
(17)Finally, we know that $(5^{2n+1} + 2^{2n+1})\mod{7} = 0$ by the inductive hypothesis, so we can substitute and simplify:
(18)Now, since we have proven that the fact that $(5^{2n+1}+2^{2n+1}) \mod 7 = 0$ proves that $(5^{2(n+1)+1}+2^{2(n+1)+1}) \mod 7 = 0$, we have completed the inductive process and have proven that $5^{2n+1}+2^{2n+1}$ is divisible by 7 for all $n \in \mathbb{N}$. QED