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)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 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)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
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.