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.

(Prof. Simmons, 2-26-18)
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. (Not necessary to suppose non-empty; just suppose has no least element and show is empty; the contradiction isn't used for anything here.)

We know that, in the case of the natural numbers, $0 < 1 < 2 < ... < n$. (Not clear what the purpose of this is, other than to say that $n$ is an arbitrary natural number.) 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 (This is what we are trying to prove, but we haven't established it.). 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

Comments - Andrew Furash
12 and 13 look good. I would recommend not using modular arithmetic to write this proof, however. We have only just defined addition and multiplication let alone modular arithmetic.

FINAL #14

14) Theorem: If X is a finite set and f is and injective function from $X \rightarrow X$. then f is bijective.

The theorem is proven if it can be shown more generally that any injective function from one finite set to another of the same cardinatlity is surjective. So, let f be an injective function from a set X to a set Y with equal cardinality. Therefore, assume for the purpose of induction that for any two sets both with cardinality n, an injective function between them is surjective.

Because f: $X\rightarrow Y$ is an injective function between two sets of the same cardinality, by definition of injection every point $a\in X$ must have an image $f(a) \in Y$, and because f is a function, that image must be unique. And since the domain and codomain have the same cardinality, every point in Y has a preimage in X. Therefore, the statement is true for cardinality n.

Now consider removing one arbitrary element, a, from X. Now that set X has cardinality n-1, to maintain equal cardinalities between X and Y, a point must be removed from Y, and, since f must still be an injective function, one has no choice but to remove f(a) from Y. Now, both sets have cardinality n-1, and the function maintains bijectivity. This process can be repeated all the way to n = 0. Thus, since for all cardinalities less than n the theorem holds, by induction the theorem is proven. $QED$

Comments - Andrew Furash
What you say is the definition of injective actually is the definition of 'well-defined.' Just because a mapping is injective does not mean that every element is mapped to an element in the co-domain. You have the right idea in your last paragraph for an inductive argument. You could have just proven a base case and this and arrived at a valid proof.

page revision: 53, last edited: 26 Feb 2018 20:18