Questions 11-14 Pre-Write

11. Statement: $\mathbb{N}$ is well-ordered.
Proof: Suppose towards contradiction that X $\subset$ $\mathbb{N}$ has 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}$, 1 is not 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.

12. Statement: If y is not free in ϕ, using the ∃-introduction rule returns an invalid deduction.
Proof Attempts:
1. ϕ=∀y(xЄy→yЄx)
ϕ[y|x]=∀x(xЄy→yЄx) true
∀y∃x(xЄy→yЄx) true
2. ϕ=∀y(x = ¬x)
ϕ[y|x]=∀x(x = ¬x) false
3. ϕ=∀y(y = ¬x)
ϕ[y|x]=∀x(y = ¬x) true
∀y∃x(y = ¬x) true

13. Statement: 5²ⁿ⁺¹+2²ⁿ⁺¹ is divisible by 7 for all n Є $\mathbb{N}$.
Proof: We can begin by proving that 5²ⁿ⁺¹+2²ⁿ⁺¹ being divisible by 7 is true for the base case, n = 0.
5²⁽⁰⁾⁺¹+2²⁽⁰⁾⁺¹ =
5¹+2¹=
5+2=7
7/7 =1
Based on this idea, assume the argument holds true for n=k.
5^2k+1+2^2k+1=7J where JЄ$\mathbb{N}$
2^2k+1=7J-5^2k+1
Next, we must show that the argument holds for n=k+1.
5^2(k+1)+1+2^2(k+1)+1=5^2k+3+2^2k+3
=5^2k+1(5²)+2^2k+1(2²)
=25(5^2k+1)+4(2^2k+1)
=25(5^2k+1)+4(7J-5^2k+1)
=25(5^2k+1)+28J-4(5^2k+1)
=21(5^2k+1)+28J
=7[3(5^2k+1)+4J]
7[3(5^2k+1)+4J] will always be divisible by 7 regardless of the value of k as long as k Є $\mathbb{N}$. Hence, 5²ⁿ⁺¹+2²ⁿ⁺¹ is divisible by 7 for all n Є $\mathbb{N}$

14. Statement: If X is a finite set and f is an injective function from X→X, then f is bijective.
Proof: Suppose towards contradiction that f is injective but not surjective and thus not bijective. There then must be a point yЄX such that there is no point zЄX with f(z)=y. Since f is a function, every xЄX must be the x-coordinate in the relation f. Hence, we must have some z₁≠z₂ with f(x₁) = f(z₂) which is not possible. Thus, f must be bijective.