Mg Problems 11 14

PRELIMINARY

11. Prove that any non-empty 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))[y|x]$. 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))[y|x]$ 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)
\begin{align} (5^{2(n+1)+1}+2^{2(n+1)+1}) \mod 7 = (5^{2n+3}+2^{2n+3}) \mod 7 = (5^2\cdot 5^{2n+1}+2^2\cdot 2^{2n+1}) \mod 7 = (25\cdot 5^{2n+1}+4\cdot 2^{2n+1}) \mod 7 \end{align}

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)
\begin{align} (25\cdot 5^{2n+1}+4\cdot 2^{2n+1}) \mod 7 = [(25\cdot 5^{2n+1})\mod{7}+(4\cdot 2^{2n+1})\mod{7}] \mod 7 \end{align}
(3)
\begin{align} = ([(25\mod{7})\cdot (5^{2n+1}\mod{7})]\mod{7}+[(4\mod{7})\cdot (2^{2n+1}\mod{7})]\mod{7})\mod 7 \end{align}

by the addition and multiplication properties respectively. Next, we can take the following steps by using the addition property in reverse and simplifying.

(4)
\begin{align} = [(25\mod{7})\cdot (5^{2n+1}\mod{7}) + (4\mod{7})\cdot (2^{2n+1}\mod{7})]\mod{7} \end{align}
(5)
\begin{align} = [4\cdot (5^{2n+1}\mod{7}) + 4\cdot (2^{2n+1}\mod{7})]\mod{7} \end{align}
(6)
\begin{align} = [4\cdot (5^{2n+1}\mod{7} + 2^{2n+1}\mod{7})]\mod{7} \end{align}

Now, we can apply the multiplication property again to show

(7)
\begin{align} [4\cdot (5^{2n+1}\mod{7} + 2^{2n+1}\mod{7})]\mod{7} = [(4\mod{7})\cdot (5^{2n+1}\mod{7} + 2^{2n+1}\mod{7})\mod{7}]\mod{7} \end{align}

We simplify and apply the addition property in reverse one last time.

(8)
\begin{align} = [4\cdot (5^{2n+1} + 2^{2n+1})\mod{7}]\mod{7} \end{align}

Finally, we know that $(5^{2n+1} + 2^{2n+1})\mod{7} = 0$, so we can substitute and simplify:

(9)
\begin{align} = (4\cdot 0)\mod{7} = 0\mod{7} = 0 \end{align}

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 well-ordered, that is that any non-empty subset has a least element.

Consider X, an arbitrary non-empty 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 non-empty.

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))[y|x]$. 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))[y|x]$ 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)
\begin{align} (5^{2(n+1)+1}+2^{2(n+1)+1}) \mod 7 = (5^{2n+3}+2^{2n+3}) \mod 7 = (5^2\cdot 5^{2n+1}+2^2\cdot 2^{2n+1}) \mod 7 = (25\cdot 5^{2n+1}+4\cdot 2^{2n+1}) \mod 7 \end{align}

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)
\begin{align} (25\cdot 5^{2n+1}+4\cdot 2^{2n+1}) \mod 7 = [(25\cdot 5^{2n+1})\mod{7}+(4\cdot 2^{2n+1})\mod{7}] \mod 7 \end{align}
(12)
\begin{align} = ([(25\mod{7})\cdot (5^{2n+1}\mod{7})]\mod{7}+[(4\mod{7})\cdot (2^{2n+1}\mod{7})]\mod{7})\mod 7 \end{align}

by the addition and multiplication properties respectively. Next, we can take the following steps by using the addition property in reverse and simplifying.

(13)
\begin{align} = [(25\mod{7})\cdot (5^{2n+1}\mod{7}) + (4\mod{7})\cdot (2^{2n+1}\mod{7})]\mod{7} \end{align}
(14)
\begin{align} = [4\cdot (5^{2n+1}\mod{7}) + 4\cdot (2^{2n+1}\mod{7})]\mod{7} \end{align}
(15)
\begin{align} = [4\cdot (5^{2n+1}\mod{7} + 2^{2n+1}\mod{7})]\mod{7} \end{align}

Now, we can apply the multiplication property again to show

(16)
\begin{align} [4\cdot (5^{2n+1}\mod{7} + 2^{2n+1}\mod{7})]\mod{7} = [(4\mod{7})\cdot (5^{2n+1}\mod{7} + 2^{2n+1}\mod{7})\mod{7}]\mod{7} \end{align}

We simplify and apply the addition property in reverse one last time.

(17)
\begin{align} = [4\cdot (5^{2n+1} + 2^{2n+1})\mod{7}]\mod{7} \end{align}

Finally, we know that $(5^{2n+1} + 2^{2n+1})\mod{7} = 0$ by the inductive hypothesis, so we can substitute and simplify:

(18)
\begin{align} = (4\cdot 0)\mod{7} = 0\mod{7} = 0 \end{align}

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

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