Logic and proof

Part (a).

<1>1. \(A \implies B\) is true.

<1>2. \(A \vee B\) is false.

<1>3. Hence \((A \implies B) \implies (A \vee B)\) is \(\text{true} \implies \text{false}\), which is false.

<1>4. Q.E.D.

Part (b).

<1>1. The statement is of the form \(P \implies Q\), where \(P = (\text{all blockoids are split}) \wedge (\text{some blockoid is nontrivial})\) and \(Q = (\text{there is a short blockoid})\).

<1>2. The negation of \(P \implies Q\) is \(P \wedge \neg Q\).

<1>3. Hence the negation is: “All blockoids are split, and some blockoid is nontrivial, and there is no short blockoid.”

<1>4. Q.E.D.

<1>1. Assume \(A\), and suppose \(\forall x\,P(x)\).

The negation of uniform convergence is \[ \exists\varepsilon_0>0\ \forall N\in\mathbb N\ \exists n>N\ \exists x\in\mathbb R: |f_n(x)-f(x)|\geq\varepsilon_0. \]

For example, let \(f_n(x)=x/n\) and \(f(x)=0\). For each fixed \(x\), one has \(x/n\to0\). The convergence is not uniform. Take \(\varepsilon_0=1\). For every \(N\), choose \(n=N+1\) and \(x=n\). Then \[ |f_n(x)-f(x)|=1. \]

Write \[ P:\ f\text{ has a local minimum at }a, \qquad Q:\ f'(a)=0\text{ or }f\text{ is not differentiable at }a. \] The contrapositive is \(\neg Q\Rightarrow\neg P\), namely:

If \(f\) is differentiable at \(a\) and \(f'(a)\ne0\), then \(f\) does not have a local minimum at \(a\).

This is true because it is logically equivalent to the original statement \(S\).

The converse is \(Q\Rightarrow P\), namely:

If \(f'(a)=0\) or \(f\) is not differentiable at \(a\), then \(f\) has a local minimum at \(a\).

This is false. For example, \(f(x)=x^3\) at \(a=0\) has \(f'(0)=0\) but no local minimum there. Also \(f(x)=x^{1/3}\) is not differentiable at \(0\) and has no local minimum there.

<1>1. Let the universe be all animals, and let \[ B(x),S(x),F(x),Y(x),W(x),K(x) \] mean respectively that \(x\) is a bird, can swim, is a fish, can fly, is a whale, and can walk.

The first negation is: \[ \text{There is an }x\in\mathbb R\text{ such that }|x-y|<2017 \text{ for every }y\in\mathbb R. \]

Using the pointwise definition of continuity on \(\mathbb R\), the second negation is: \[ \exists x\in\mathbb R\ \exists\varepsilon>0\ \forall\delta>0\ \exists y\in\mathbb R: |x-y|<\delta\ \text{ and }\ |f(x)-f(y)|\geq\varepsilon. \]

1. The negation is: \[ \text{For every real }x\text{ there exists a real }y\text{ such that }|x-y|\le1. \]

2. Making the hidden quantifiers explicit, the original assertion says that for every closed interval \([a,b]\) and every continuous \(f:[a,b]\to\mathbb R\), there exists \(x\in[a,b]\) such that \(f(x)\le f(y)\) for every \(y\in[a,b]\). Its negation is therefore: \[ \text{There exist }a\le b\text{ and continuous }f:[a,b]\to\mathbb R\text{ such that for every }x\in[a,b] \] \[ \text{there exists }y\in[a,b]\text{ with }f(y)<f(x). \]

3. Interpreting \(n\) as an arbitrary integer, the negation of the biconditional is that there exists an integer \(n\) for which exactly one side holds; equivalently, \[ \text{either }3n+1\text{ is even and }n^2+4\text{ is composite,} \] or \[ 3n+1\text{ is odd and }n^2+4\text{ is prime.} \]

For part (a), the statement is \[ \exists m\in\mathbb Z_{>0}\;\forall x\in S_m, \bigl(x\ge \alpha_m\ \text{and}\ f_m(x)=0\bigr). \] Negating successively gives \[ \forall m\in\mathbb Z_{>0}\;\exists x\in S_m \quad\text{such that}\quad x<\alpha_m\ \text{or}\ f_m(x)\ne0. \]

For part (b), the flaw is that conditions (1) and (2) force \(T\) to contain every integer \(n\ge m\), but they do not forbid \(T\) from also containing positive integers smaller than \(m\). For example, with \(m=3\), the set of all positive integers satisfies (1) and (2), but is not \(\{n:n\ge3\}\).

The correct conclusion from (1) and (2) is \[ \{n\in\mathbb Z_{>0}:n\ge m\}\subseteq T. \] Indeed, induction on \(r\ge0\) gives \(m+r\in T\). To obtain equality, add the hypothesis \[ T\subseteq\{n\in\mathbb Z_{>0}:n\ge m\}. \] Then the two inclusions give \[ T=\{n\in\mathbb Z_{>0}:n\ge m\}. \]

Let \(P\) = “there exists a purple apple” and \(Q\) = “all lemons are pink”. The statement is \(P \Rightarrow Q\).

Part (a).

<1>1. Negation: \(\neg(P \Rightarrow Q) \equiv P \wedge \neg Q\).

<1>2. Hence the negation is: “There exists a purple apple, and some lemon is not pink.”

<1>3. Converse: \(Q \Rightarrow P\).

<1>4. Hence the converse is: “If all lemons are pink, then there exists a purple apple.”

<1>5. Contrapositive: \(\neg Q \Rightarrow \neg P\).

<1>6. Hence the contrapositive is: “If some lemon is not pink, then there is no purple apple.”

Part (b).

<1>1. The contrapositive is logically equivalent to the original statement.

<1>2. Hence the contrapositive must be true.

<1>3. The converse is not necessarily true.

<1>4. The negation is false.

<1>5. Q.E.D.

The answers are false, false, true, true, false. We use the quadratic-tower criterion for straightedge-and-compass constructibility [@DF04]. In particular, a constructible algebraic number lies in a finite tower of quadratic extensions of \(\mathbf Q\), and its degree divides \(2^m\) for some \(m\). Finitely many constructible numbers lie in a common such tower: adjoin their quadratic generators successively, noting that each new extension has degree at most \(2\). Their sums and products are therefore constructible as well.

<1>1. Part (a) is false. An explicit counterexample is \[ f(x)=x^4-4x^2+x+1. \]

<1>2. Part (b) is false, and in fact no root of an irreducible sextic over \(\mathbf Q\) is constructible.

<1>3. Part (c) is true.

<1>4. Part (d) is true, with \(E\) and \(K\) viewed in a common algebraic closure \(\overline F\).

<1>5. Part (e) is false. For \(|F|=p^a\) and \(|E|=p^b\), the field \(E\) has a subfield isomorphic to \(F\) if and only if \(a\mid b\).

1. The negation is: \[ \text{For every integer }x\text{ there is an integer }y\text{ such that }x+y\text{ is even.} \]

2. The negation is: \[ \text{There is an odd integer }x\text{ and an integer }y\text{ such that }xy\text{ is even.} \]

3. The negation is: \[ \text{There exists }\varepsilon>0\text{ such that for every }N\in\mathbb N \text{ there is }n>N\text{ with } \left|\frac{n+2}{n+1}-1\right|\ge\varepsilon. \] These follow by replacing each quantifier by its opposite and negating the final predicate.

1. Lemma: \(f\) is injective \(\iff f\) has a left inverse \(\inverseof{f}\) satisfying \(\inverseof{f} f(a) = a\).

   Suppose \(f,g: A \to A\) are injective and \(x,y \in A\), we want to show that \((f\circ g)(x) = (f\circ g)(y) \implies x = y\). So suppose \(f(g(x)) = f(g(y))\). Since \(f\) is injective, \(f\) has a left inverse, so \(g(x) = g(y)\), and since \(g\) is injective \(x = y\). \(\qed\)

Goal: Prove that if \(A\) is a set and \(f, g: A \to A\) are injective functions, then their composition \(f \circ g: A \to A\) is injective.

<1>1. Definition: A function \(h: A \to A\) is injective if for all \(x, y \in A\), \(h(x) = h(y) \implies x = y\).

<1>2. Assume \(f: A \to A\) and \(g: A \to A\) are injective functions. Let \(x, y \in A\) and assume \((f \circ g)(x) = (f \circ g)(y)\).

<1>3. \(f(g(x)) = f(g(y))\).

<1>4. \(g(x) = g(y)\).

Applying the definition of injectivity to the elements \(g(x), g(y) \in A\) with \(f(g(x)) = f(g(y))\) from <1>3 yields \(g(x) = g(y)\).

<1>5. \(x = y\).

Applying the definition of injectivity to \(x, y \in A\) with \(g(x) = g(y)\) from <1>4 yields \(x = y\).

<1>6. Conclusion: \(f \circ g\) is injective.

By <1>1, \(f \circ g\) is injective. Q.E.D.

If \(f(x_1)=f(x_2)\), then applying \(g\) gives \[ x_1=g(f(x_1))=g(f(x_2))=x_2. \] Thus \(f\) is injective.

For each \(x\in X\), the element \(f(x)\in Y\) satisfies \(g(f(x))=x\). Thus \(g\) is surjective.

Let \(X=\{1\}\), \(Y=\{1,2\}\), \(f(1)=1\), and \(g(1)=g(2)=1\). Then \(g\circ f=\operatorname{id}_X\), while \(f\) is not surjective and \(g\) is not injective.

The condition is that \(f\) is injective.

For every map and every \(S\subseteq X\), one has \(S\subseteq f^{-1}(f(S))\). If \(f\) is injective and \(x\in f^{-1}(f(S))\), then \(f(x)=f(s)\) for some \(s\in S\). Injectivity gives \(x=s\), so \(x\in S\). Thus equality holds.

Conversely, suppose the equality holds for every \(S\subseteq X\). If \(f(a)=f(b)\), then \[ b\in f^{-1}(f(\{a\}))=\{a\}, \] so \(b=a\). Hence \(f\) is injective.

We need to show that \(R\) is reflexive, transitive, and symmetric. 1. Reflexive: this would say that \(x\sim x \iff x^2-4x = x^2-4x\), which is true. 2. Transitive: suppose \(x\sim y\) and \(y\sim z\), we want to show \(x\sim z\). But we have \[ x^2 - 4x = y^2-4y ~\&~ y^2-4y = z^2-4z \implies x^2-4x = y^2-4y = z^2-4z \] 1. We want to show \(x\sim y \implies y \sim x\), which follows because \(x^2-4x = y^2-4y \iff y^2-4y = x^2-4x\). 2. The equivalence classes: \[\begin{align*} x^2-4x &= 0: &\theset{0, 4}\\ x^2-4x &= -3: &\theset{1,3} \\ x^2-4x &= -4: &\theset{2} \\ x^2-4x &= 5: &\theset{5} \end{align*}\]

If \(f\) and \(g\) are surjective and \(c\in C\), choose \(b\in B\) with \(f(b)=c\), then choose \(a\in A\) with \(g(a)=b\). Hence \((f\circ g)(a)=c\), so \(f\circ g\) is surjective.

The converse claim is false. Let \[ A=\{0\},\qquad B=\{0,1\},\qquad C=\{0\}, \] let \(g(0)=0\), and let \(f\) be the unique map \(B\to C\). Then \(g\) is not surjective, while \(f\circ g:A\to C\) is surjective.

For \(n=k\), \[ \sum_{m=k}^{k}\binom{m}{k}=\binom{k}{k}=1=\binom{k+1}{k+1}. \] Assume \[ \sum_{m=k}^{n}\binom{m}{k}=\binom{n+1}{k+1}. \] Then Pascal’s identity gives \[ \sum_{m=k}^{n+1}\binom{m}{k} =\binom{n+1}{k+1}+\binom{n+1}{k} =\binom{n+2}{k+1}. \] Thus the identity holds for all \(n\ge k\) by induction.

The binomial theorem states \[ (x+y)^m=\sum_{j=0}^m\binom mj x^{m-j}y^j. \] For \(m=5\), each intermediate binomial coefficient \(\binom5j\), \(1\le j\le4\), is divisible by \(5\). Hence \[ (x+y)^5\equiv x^5+y^5\pmod5. \]

We prove the final congruence by induction on \(n\). The case \(n=1\) is the preceding identity. If \[ (x+y)^{5^n}\equiv x^{5^n}+y^{5^n}\pmod5, \] then raising both sides to the fifth power preserves congruence, and applying the case \(m=5\) with \(X=x^{5^n}\) and \(Y=y^{5^n}\) gives \[ (x+y)^{5^{n+1}} \equiv (x^{5^n}+y^{5^n})^5 \equiv x^{5^{n+1}}+y^{5^{n+1}}\pmod5. \] Thus the claim holds for every \(n\ge1\).

<1>1. For every \(n\ge1\), \[ \gcd(F_{n+1},F_n)=\gcd(F_n,F_{n-1}). \]

<1>2. Iterating <1>1 gives \[ \gcd(F_{n+1},F_n)=\gcd(F_1,F_0)=1 \] for every \(n\ge0\).

<1>3. Hence every two successive Fibonacci numbers are relatively prime.

For \(n\ge1\), let \[ S_n=n^3+(n+1)^3+(n+2)^3. \] We prove by induction that \(9\mid S_n\).

For \(n=1\), \[ S_1=1+8+27=36, \] which is divisible by \(9\).

Assume \(9\mid S_n\). Then \[ S_{n+1}-S_n=(n+3)^3-n^3 =9(n^2+3n+3), \] which is divisible by \(9\). Hence \(S_{n+1}\) is divisible by \(9\). By induction, the sum of the cubes of any three consecutive positive integers is divisible by \(9\).

1. Use the fact that \(\sum_{i=1}^n i = \frac 1 2 n(n+1)\), so \[\begin{align*} \sum_{i=1}^{n+1} i^3 &= \sum_{i=1}^{n} i^3 + (n+1)^3 \\ &= \left( \sum_{i=1}^{n} i \right)^2 + (n+1)^3 \\ &= \left( \frac 1 2 n(n+1) \right)^2 + (n+1)^3 \\ &= \frac 1 4 n^2(n+1)^2 + (n+1)(n+1)^2 \\ &= \frac 1 4 (n+1)^2 (n^2 + 4(n+1)) \\ &= \frac 1 4 (n+1)^2(n+2)^2 \\ &= \left( \frac 1 2 (n+1)(n+2)\right)^2 \\ &= \left( \sum_{i=1}^{n+1} i \right)^2. \qed \end{align*}\]

For \(n=0\), \[ \int_0^\infty e^{-x}\,dx=1=0!. \]

For the inductive step, integration by parts gives \[ \int_0^\infty x^ne^{-x} = -x^ne^{-x}\bigg\rvert_0^\infty - \int_0^\infty -nx^{n-1}e^{-x} = -x^ne^{-x}\bigg\rvert_0^\infty + n \int_0^\infty x^{n-1}e^{-x} \\ \equalsbecause{I.H.} -x^ne^{-x}\bigg\rvert_0^\infty + n (n-1)! \\ \equalsbecause{L.H.$\times n$}0 + n(n-1)! = n!. \qed \]

For \(n=1\), \[ \sum_{k=0}^{0}a^k=1=\frac{a-1}{a-1}. \] Assume \[ \sum_{k=0}^{n-1}a^k=\frac{a^n-1}{a-1}. \] Then \[ \sum_{k=0}^{n}a^k =\frac{a^n-1}{a-1}+a^n =\frac{a^{n+1}-1}{a-1}. \] Thus the formula holds for all positive integers \(n\) by induction.

Base case: for \(n=1\), we have \(a_1 = 1 \leq a_2 = \frac{16} 3 \leq 10.\) Suppose this holds for \(k < n\), then \[ a_{n-1} \leq a_n = \frac{a_{n-1}}{3} + 5 \implies 3a_{n-1} \leq a_{n-1} + 15 \implies a_{n-1} \leq \frac{15}{2} \]

and thus we have \[ a_{n+1} = \frac{a_n}{3} + 5 = \frac{1}{3}(a_n + 15) \\ = \frac{1}{3}((\frac{a_{n-1}}{3} + 5) + 15) \\ = \frac{a_{n-1} + 60}{9} \\ \leq \frac{\frac{15}{2} + 60}{9} \\ = \frac{150}{18} \\ < \frac{180}{18} = 10, \]

and \(a_{n+1} \leq 10\). Moreover, note that the relation \(a_{n+1} = \frac{a_n}{3} + 5\) can be rewritten as \[ a_n = 3a_{n+1} - 15, \\ a_{n-1} = 3a_n - 15. \] Using the inductive hypothesis \(a_{n-1} \leq a_n\), we can thus write \[ 3a_n - 15 = a_{n-1} \leq a_n = 3a_{n+1} - 15, \] from which we get \(3a_{n} - 15 \leq 3a_{n+1} - 15\) and thus \(a_{n} \leq a_{n+1}\).

To compute \(\lim_{n\to\infty}a_n\), perhaps there are easier ways, but we can just use generating functions. Note that the limit exists by the Monotone Convergence Theorem. Let \(A(x) = \sum_{n=0}^\infty a_n x^n\) where \(a_0 = 0\). Then applying the magic sauce, we have \[\begin{align*} a_n = \frac{1}{3}a_{n-1} + 5 &\implies \sum_{n=1}^\infty a_nx^n = \frac{1}{3}\sum_{n=1}^\infty a_{n-1}x^n + 5\sum_{n=1}^\infty x^n \\ &\implies A(x) - a_0 = \frac 1 3 xA(x) + 5\left( \frac 1 {1-x} - 1\right) \\ &\implies A(x)\left(1 - \frac x 3\right) = 5\left( \frac x {1-x}\right) \\ &\implies A(x) = 15\left(\frac 1 {3-x} \right)\left(\frac x {1-x} \right) \\ &\implies A(x) = \frac{15x}{(3-x)(1-x)} \\ &\implies A(x) = \frac{-\frac{45}{2}}{3-x} + \frac{\frac{15}{2}}{1-x} \\ &\implies A(x) = \frac 3 2 \left(-5 \left( \frac{1}{1-\frac x 3} \right) + 5\left( \frac 1 {1-x}\right) \right) \\ &\implies A(x) = \frac{15}{2} \sum_{n=0}^\infty \left(1 - \left( \frac 1 3\right)^n\right)x^n \\ &\implies a_n = \frac {15} 2 \left(1 - \left( \frac 1 3\right)^n\right) \end{align*}\]

and so we find \[ \lim_{n\to\infty}a_n = \lim_{n\to\infty}\frac {15} 2 \left(1 - \left( \frac 1 3\right)^n\right) = \frac{15}{2}. \qed \] > Alternatively: \[ a_{n+1} = \frac 1 3 a_n + 5 \implies \lim_{n\to\infty} a_{n+1} = \lim_{n\to\infty} \frac 1 3 a_n + 5 \\ \implies L = \frac 1 3 L + 5 \implies \frac 2 3 L = 5 \implies L = \frac {15} 2 \]

A permutation of \(k\) elements chosen from an \(n\)-element set is an ordered list of \(k\) distinct elements. Its number is \[ P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}. \]

A combination of \(k\) elements from an \(n\)-element set is an unordered \(k\)-element subset. Its number is \[ \binom nk=\frac{n!}{k!(n-k)!}. \]

Let \(X\) be a \(k\)-element set and \(Y\) an \(n\)-element set. Fix an ordering \(x_1,\ldots,x_k\) of \(X\). An injective function \(f:X\to Y\) is determined uniquely by the ordered list \[ (f(x_1),\ldots,f(x_k)), \] whose entries must be distinct. Conversely every ordered list of \(k\) distinct elements of \(Y\) defines an injection. Therefore the number of injections is \[ P(n,k)=\frac{n!}{(n-k)!}. \]