Key Concepts & Formulas
- $$\text{Modus ponens: } P,\; P \to Q \;\vdash\; Q$$
- $$\text{Modus tollens: } \lnot Q,\; P \to Q \;\vdash\; \lnot P$$
- $$P \to Q \;\equiv\; \lnot Q \to \lnot P$$
- $$\lnot(P \land Q) \;\equiv\; \lnot P \lor \lnot Q$$
- $$\text{Strong induction: assume } P(1) \ldots P(k), \text{ prove } P(k+1)$$
- Well-Ordering Principle
- $$\forall x\,\exists y \;\text{ vs }\; \exists y\,\forall x \;\text{(quantifier order matters)}$$
- $$\text{Russell's Paradox: } S = \{x : x \notin x\}$$
- Gödel's 1st Incompleteness Theorem
- $$\text{Proof by contradiction: assume } \lnot P, \text{ derive contradiction}$$
1Easy
Using a truth table, prove that \((P \to Q) \land (Q \to R)\) logically implies \(P \to R\) (hypothetical syllogism). Then provide a formal proof using inference rules.
Show Hint
For the truth table, enumerate all 8 combinations of \(P, Q, R\). Verify that whenever both \(P \to Q\) and \(Q \to R\) are true, \(P \to R\) is also true. For the formal proof, assume \(P\), derive \(Q\) by modus ponens, then derive \(R\).
2Medium
Prove by strong induction that every integer \(n \geq 2\) can be written as a product of prime numbers.
Show Hint
Base case: \(n = 2\) is prime (product of one prime). Inductive step: assume true for all \(k\) with \(2 \leq k \leq n\). If \(n+1\) is prime, done. If not, \(n+1 = ab\) with \(2 \leq a, b \leq n\), and apply the inductive hypothesis to both \(a\) and \(b\).
3Medium
Prove by contradiction that \(\sqrt{2}\) is irrational. Then adapt the proof to show that \(\sqrt{3}\) is irrational.
Show Hint
Assume \(\sqrt{2} = a/b\) in lowest terms. Then \(2b^2 = a^2\), so \(a\) is even. Write \(a = 2k\), get \(2b^2 = 4k^2\), so \(b\) is even — contradicting "lowest terms." For \(\sqrt{3}\), use divisibility by 3 instead.
4Hard
Explain Russell's Paradox. Then show how the Axiom Schema of Separation (Comprehension) in ZF set theory resolves it by restricting what can form a set.
Show Hint
In naive set theory, let \(S = \{x : x \notin x\}\). Then \(S \in S\) iff \(S \notin S\) — a contradiction. ZF's Separation axiom only allows \(\{x \in A : \phi(x)\}\) for an existing set \(A\), preventing the paradox since we cannot form the "set of all sets" first.
5Easy
Negate the following statement formally: "For every \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x\), if \(|x - a| < \delta\) then \(|f(x) - L| < \epsilon\)." Write the negation in both symbolic and plain English.
Show Hint
Push negation inward: \(\lnot\forall\) becomes \(\exists\), \(\lnot\exists\) becomes \(\forall\), and negate the innermost statement. The result is: "There exists \(\epsilon > 0\) such that for all \(\delta > 0\), there exists an \(x\) with \(|x - a| < \delta\) and \(|f(x) - L| \geq \epsilon\)."
6Medium
Prove by contraposition: If \(n^2\) is even, then \(n\) is even. Compare this approach with a direct proof and a proof by contradiction.
Show Hint
Contrapositive: "If \(n\) is odd, then \(n^2\) is odd." Let \(n = 2k + 1\). Then \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), which is odd. Direct proof: if \(n^2 = 2m\), use unique factorization. Contradiction: assume \(n\) is odd and \(n^2\) is even, reach the same conclusion.
7Hard
State Gödel's First Incompleteness Theorem precisely. Explain the key ideas of the proof: Gödel numbering, self-reference, and the construction of the undecidable sentence.
Show Hint
Theorem: Any consistent, recursively axiomatizable formal system \(S\) that can express basic arithmetic contains a sentence \(G\) that is true but unprovable in \(S\). The proof encodes "I am not provable in \(S\)" via the diagonal lemma (self-reference through Gödel numbering). If \(G\) is provable, \(S\) proves a falsehood; if \(\lnot G\) is provable, \(S\) proves its own consistency, contradicting the second theorem.
8Medium
Prove by induction that for all \(n \geq 1\): $$\sum_{k=1}^{n} k^3 = \left[\frac{n(n+1)}{2}\right]^2$$ What is the relationship between this identity and \(\sum k\)?
Show Hint
Base case: \(1^3 = \left[\frac{1 \cdot 2}{2}\right]^2 = 1\). Inductive step: assume \(\sum_{k=1}^{n} k^3 = \left[\frac{n(n+1)}{2}\right]^2\). Add \((n+1)^3\) and show it equals \(\left[\frac{(n+1)(n+2)}{2}\right]^2\). The beautiful identity: the sum of the first \(n\) cubes equals the square of the sum of the first \(n\) natural numbers.
9Hard
Prove Cantor's theorem: For any set \(A\), there is no surjection from \(A\) onto its power set \(\mathcal{P}(A)\). Use this to show there are infinitely many distinct cardinalities.
Show Hint
Suppose \(f: A \to \mathcal{P}(A)\) is surjective. Let \(B = \{a \in A : a \notin f(a)\}\). Since \(f\) is surjective, \(B = f(b)\) for some \(b\). Then \(b \in B\) iff \(b \notin f(b) = B\) — contradiction. For infinitely many cardinalities: iterate \(|A| < |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(A))| < \ldots\)
10Easy
Determine whether each is a proposition, and if so, state its truth value: (a) "This sentence is false." (b) "\(x + 3 = 7\)." (c) "Every even number greater than 2 is the sum of two primes." (d) "Close the door."
Show Hint
(a) Not a proposition — it's self-referential and has no definite truth value (the Liar Paradox). (b) Not a proposition — it's an open sentence (a predicate). (c) A proposition — this is Goldbach's conjecture (unknown truth value, but still either true or false). (d) Not a proposition — it's a command.
11Medium
Prove using the Well-Ordering Principle that every nonempty set of natural numbers has a least element. Then use it to prove there are no infinite strictly decreasing sequences of natural numbers.
Show Hint
The Well-Ordering Principle is an axiom for the natural numbers. For the second part: if \(a_1 > a_2 > a_3 > \ldots\) were infinite, then \(\{a_1, a_2, \ldots\}\) is a nonempty subset of \(\mathbb{N}\) with no least element (for any \(a_n\), \(a_{n+1} < a_n\)), contradicting Well-Ordering.
12Hard
Prove the Schröder-Bernstein Theorem: If there exist injections \(f: A \to B\) and \(g: B \to A\), then there exists a bijection \(h: A \to B\).
Show Hint
Define \(C = A \setminus g(B)\), and let \(D = C \cup g(f(C)) \cup g(f(g(f(C)))) \cup \ldots\) (the union of iterates). Let \(D = \bigcup_{n=0}^{\infty} (g \circ f)^n(C)\). Define \(h(a) = f(a)\) if \(a \in D\), and \(h(a) = g^{-1}(a)\) if \(a \notin D\). Show \(h\) is well-defined and bijective.