Practice Proofs with Lurch

Assignment #06 Propositional Logic

1. Theorem (why there’s no contradiction- rule).  $\xcont\implies \text{anything}$
2. Theorem (double negative). $A\iff \xnot (\xnot A)$
3. Theorem (negating an implication).  $\neg(R\implies S)\implies R \xand \neg S$
4. Theorem (another De Morgan).  $\xnot (P \xor Q)\ximplies \xnot P \xand \xnot Q$
5. Theorem (excluded middle).  $n$ is prime or $n$ is not prime

Assignment #07 Predicate Logic

1. Theorem (sometimes the same).  $(\forall x.\forall y.P(x,y))\implies (\forall z.P(z,z))$
2. Theorem (alternate or-). $(\forall x.\neg L(x))\iff \neg (\exists x.L(x))$

Assignment #08 Peano arithmetic and induction

1. Theorem 7.2 (no number is its own successor).   $\forall n.n\neq\sigma(n)$
2. Theorem 7.3 (alternate definition of $\sigma$). $\forall n.\sigma(n)=n+1$
3. Theorem 7.5 (additive identity, part 2). $\forall n.0+n=n$
4. Theorem 7.6 (commutativity of adding $1$). $\forall n.1+n=n+1$

Assignment #09 Peano arithmetic and induction

1. Theorem 7.7 (commutativity of addition).   $\forall m.\forall n.m+n=n+m$
2. Theorem 7.11 (multiplicative identity).   $\forall n.1\cdot n=n \xand n\cdot 1=n$

Assignment #10 Ch. 6Ch. 7

1. Theorem 6.12 (quantifier fun).   $(\forall x.P(x) \xor Q(x)) \xand (\exists y.\neg P(y)) \implies (\exists z.Q(z))$
2. Theorem 7.12 (left distributive law).  $\forall m.\forall n.\forall p.p\cdot(m+n)=p\cdot m+p\cdot n$

Assignment #11 Peano arithmetic and induction

1. Theorem 7.19 (successors are bigger). $\forall n.n\lt\sigma(n)$
2. Theorem 7.33 (everything divides zero). $\forall n.n\mid 0$
3. Theorem (product with even is even). $\forall m.\forall n.n\text{ is even}\implies m\cdot n\text{ is even}$
4. Theorem (successors of evens are odd). $\forall n.2\cdot n+1\text{ is odd}$

Assignment #12 Ch. 5Ch. 6Ch. 7Recursive Sequences

1. Theorem (prop warm up). $((S\implies T\text{ or }\neg U)\implies S)\implies S$
2. Theorem 6.17 (de-quantify). $(\forall x.Q(x)\implies P)\iff(\exists x.Q(x))\implies P$
3. Theorem 7.16 (zero divisors). $\forall m.\forall n.m\cdot n=0\implies m=0\text{ or }n=0$
4. Theorem 7.21 (minimum difference). $\forall m.\forall n.m\lt n\iff\sigma(m)\leq n$
5. Theorem 7.37 (common divisors divide sums). If $p\mid m$ and $p\mid n$, then $p\mid(m+n)$
6. Theorem 8.3 (c) (power laws). $(z^m)^n=z^{m\cdot n}$
7. Theorem 8.6 (b) (distributive law). $\displaystyle\sum_{k=0}^n s\cdot a_k=s\cdot\sum_{k=0}^n a_k$
8. Theorem (simple fact. fact). If $0\lt n$, then $n\mid n!$
9. Theorem (successors of evens are odd). $2\cdot n+1\text{ is odd}$

Assignment #13 Recursive Sequences

1. Theorem 8.4 (c). $(n+1)^2=n^2+(2\cdot n+1)$
2. Theorem 8.16 (sum of the first n Fibs). For any natural number $n$, $\displaystyle 1+\sum_{k=0}^n F_k=F_{n+2}$
3. Theorem 8.13 (closed formula for binomial coefficients). For any natural numbers $m$ and $n$, $\displaystyle (m!\cdot n!)\cdot\binom{m+n}{n}=(m+n)!$

Assignment #14 Ch. 8Set Theory

1. Theorem 9.9 (subset is reflexive). For any set $A$, $A\subseteq A$
2. Theorem (everyone’s subset). For any set $A$, ${}\subseteq A$
3. Theorem 9.11 (subset is transitive). For any sets $A$, $B$, and $C$, if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$
4. Theorem 8.10 (sum of the first n odd numbers). For any natural number $n$, $\displaystyle\sum_{k=0}^n(2\cdot k+1)=(n+1)^2$
5. Theorem 8.25. If $a_0=0$ and $\forall n.a_{n+1}=3\cdot a_n+2$, then for any natural number $n$, $a_n+1=3^n$

Assignment #15 Set Theory

1. Theorem 9.5 (double negative). $(A’)'=A$
2. Theorem 9.7 (a set of sets). ${1,2}\in{A:{1}\subseteq A}$
3. Theorem 9.8 (Cartesian calculation). ${2}\times{3,5}={[2,3],[2,5]}$
4. Theorem 9.22 (relative complement is not associative). If $x\in A\cap(B\cap C)$, then $A\setminus(B\setminus C)\neq(A\setminus B)\setminus C$
5. Theorem 9.30 (even more De Morgan). $\displaystyle\left(\bigcup_{i\in I}A_i\right)‘=\bigcap_{j\in I}A_j’$
6. Theorem 9.34 (power set of complements). If $A\subseteq B$, then $\mathscr{P}(B’)\subseteq\mathscr{P}(A’)$

Assignment #16 Set Theory

1. Theorem 9.14 (contravariance). If $A\subseteq B$, then $B’\subseteq A’$
2. Theorem 9.30 (not a subset). If $\neg(A\subseteq B)$, then $\exists x.x\in A\cap B’$

Assignment #17 Real Numbers

1. Theorem 10.2 (a) (shortest proof ever). $-0=0$
2. Theorem 10.2 (b) (double negative). $-1\cdot -1=1$
3. Theorem 10.2 (c) (the only two real numbers we know so far). $0\lt 1$
4. Theorem 10.4 (cancellation for multiplication). If $z\neq 0$ and $z\cdot x=z\cdot y$, then $x=y$
5. Theorem 10.9 (inverse inverse). If $x\neq 0$, then $(x^{-1})^{-1}=x$
6. Theorem 10.17 (asymmetry). If $x\lt y$, then $\neg(y\lt x)$
7. Theorem 10.18 (adding inequalities). If $w\lt x$ and $y\lt z$, then $w+y\lt x+z$
8. Theorem 10.21 (negating an inequality). If $x\lt y$, then $-y\lt -x$

Assignment #18 Real Numbers

1. Theorem 10.2 (d) (a third real number?). $-1\neq 1$ and $-1\neq 0$
2. Theorem 10.14 (signed products). $(-x)\cdot(-y)=x\cdot y$

Assignment #19 Real Numbers

1. Theorem ($\leq$ is transitive). If $x\leq y$ and $y\leq z$, then $x\leq z$
2. Theorem (translation for $\leq$). If $x\leq y$, then $x+z\leq y+z$
3. Lemma (zero is smallest). If $n\in\mathbb{N}$, then $0\leq n$
4. Corollary (seriously, it’s smallest). If $m\in\mathbb{N}$ and $m\leq 0$, then $m=0$
5. Theorem (natural differences). If $m\in\mathbb{N}$, $n\in\mathbb{N}$, and $m\leq n$, then $n-m\in\mathbb{N}$
6. Theorem (Peano Axiom I $\Leftarrow$). If $0\leq k$ and $m+k=n$, then $m\leq n$
7. Theorem (Peano Axiom I $\Rightarrow$). If $m\in\mathbb{N}$, $n\in\mathbb{N}$, and $m\leq n$, then $\exists k\in\mathbb{N}.m+k=n$

Assignment #20 Real Numbers

1. Theorem (nonzero products and inverses). If $x\neq 0$ and $y\neq 0$, then $x^{-1}\neq 0$ and $x\cdot y\neq 0$
2. Theorem (product of inverses). If $x\neq 0$ and $y\neq 0$, then $x^{-1}\cdot y^{-1}=(x\cdot y)^{-1}$

Assignment #21 Real Numbers

1. Theorem 10.20 (d) (signed products). If $x\lt 0$ and $0\lt y$, then $x\cdot y\lt 0$
2. Theorem (another real number). There is a real number strictly between 0 and 1, i.e., $\exists r.0\lt r\text{ and }r\lt 1$

Assignment #22 Ch. 10Functions

1. Theorem 11.1 (composition is associative). If $h:A\to B$, $g:B\to C$, and $f:C\to D$, then $f\circ(g\circ h)=(f\circ g)\circ h$
2. Theorem 10.46 (image of subsets). If $f:A\to B$, $S\subseteq T$, and $T\subseteq A$, then $f(S)\subseteq f(T)$

Assignment #23 Functions

1. Theorem 11.13 (a) (identity maps are injective). The map $\mathrm{id}_A$ is injective
2. Theorem 11.13 (b) (identity maps are surjective). The map $\mathrm{id}_A$ is surjective
3. Theorem 11.8 (composition of injective maps is injective). If $f:A\to B$, $g:B\to C$, $f$ is injective, and $g$ is injective, then $g\circ f$ is injective
4. Theorem 11.9 (composition of surjective maps is injective). If $f:A\to B$, $g:B\to C$, $f$ is surjective, and $g$ is surjective, then $g\circ f$ is surjective
5. Theorem 11.15 (image of inverse image). If $f:A\to B$, $S\subseteq B$, and $f$ is surjective, then $f(f^\mathrm{inv}(S))=S$

Assignment #24 Functions and Relations

1. Theorem 11.22 (equivalence induced by a function). If $x\sim_1 y\iff f(x)=f(y)$, then $\sim_1$ is an equivalence relation
2. Theorem 11.31 (a partial order). If $S\sim_2 T\iff S\subseteq T$, then $\sim_2$ is a partial order

Assignment #06 Propositional logic

1. Theorem (Iff is stronger): $(P\Leftrightarrow Q)\Rightarrow(Q\Rightarrow P)$
2. Theorem (the other way around): $\neg(\neg A)\Rightarrow A$
3. Theorem (Modus Tollens): $(S \Rightarrow T)\text{ and } \neg T \Rightarrow \neg S$
4. Theorem (atomic statements don’t have to be variables): $0 \lt x\text{ or }x\lt 10 \Rightarrow x\lt 10\text{ or } 0\lt x$
5. Theorem (excluded middle): $K\text{ or } \neg K$

Assignment #07 Propositional logic

1. Theorem (implies is transitive): $((P\Rightarrow Q)\text{ and }(Q \Rightarrow R)) \Rightarrow (P \Rightarrow R)$
2. Theorem (alternate or-): $(S\text{ or } T)\text{ and } \neg S \Rightarrow T$

Assignment #08 Predicate logic with Equality

1. Theorem (alpha equivalence warm up): $(\forall x.P(x)) \Rightarrow (\forall y.P(y))$
2. Theorem (same thing but for exists): $(\exists x.P(x)) \Rightarrow (\exists y.P(y))$
3. Theorem (commuting quantifiers): $(\forall x.\forall y.x\text{ loves }y) \Rightarrow (\forall y.\forall x.x\text{ loves }y)$
4. Theorem (same thing for exists): $(\exists x.\exists y.x\text{ loves }y) \Rightarrow (\exists y.\exists x.x\text{ loves }y)$
5. Theorem (De Morgan): $\neg (S\text{ and }T) \Rightarrow \neg S\text{ or } \neg T$
6. Theorem (De Morgan): $\neg (\forall x.R(x)) \Rightarrow (\exists x.\neg R(x))$
7. Theorem ($=$ is transitive): $x=y\text{ and }y=z \Rightarrow x=z$

Assignment #09 Logic theorems

1. Theorem 5.10 (some are the same): $(\forall x.\forall y.P(x,y)) \Rightarrow (\forall z.P(z,z))$
2. Theorem 5.16 (excluded middle): $(\forall x.Q(x))\text{ or } (\exists x.\neg Q(x))$
3. Theorem 4.22 (alternate $\Rightarrow$): $(R \Rightarrow S) \Rightarrow \neg R\text{ or }S$

Assignment #10 Logic review

1. Theorem (ex falso quodlibet): If Dracula fears Alice and Dracula does not fear Alice then Bob loves Alice.
2. Theorem 4.29 (the most beautiful?): $S \Rightarrow (S \Leftrightarrow S\text{ or }(\neg S \text{ and } S))$
3. Theorem 4.25 (shunting): $((P \text{ and } Q) \Rightarrow R) \Leftrightarrow (P \Rightarrow (Q \Rightarrow R))$
4. Theorem 5.21 (avoiding vacuous domains): $(\exists x. x = x)\text{ and }(\forall y. T(y)) \Rightarrow (\exists z. T(z))$
5. Theorem 5.5 (distributivity): $(\exists x. A(x) \Rightarrow B(x)) \Leftrightarrow (\forall y. A(y)) \Rightarrow (\exists z. B(z))$

Assignment #11 Logic review

1. Theorem (Pierce’s Law): $((S \Rightarrow T) \Rightarrow S) \Rightarrow S$
2. Theorem (quantifier fun): $(\forall x.\exists y.\forall z.A(x,y,z)) \Rightarrow (\forall z.\forall x.\exists y.A(x,y,z))$

Assignment #12 Peano arithmetic and Induction

1. Theorem 7.3 (no number is its own successor): $n\neq\sigma(n)$
2. Theorem 7.4 (alternate definition of $\sigma$): $\sigma(n)=n+1$
3. Theorem 7.5 (associativity of addition): $(m+n)+p=m+(n+p)$
4. Theorem 7.6 (additive identity, part 2): $0+n=n$
5. Theorem 7.7 (commutativity of adding $1$): $1+n=n+1$
6. Theorem 7.8 (commutativity of addition): $m+n=n+m$

Assignment #13 Peano arithmetic and Induction

1. Theorem 7.11 (left multiplication by zero): $0\cdot m=0$
2. Theorem 7.19 (nonzero naturals are positive):
   • (a) $0\leq n$
   • (b) $0\lt n \Leftrightarrow n\neq 0$

Assignment #14 Sequences, Recursion, and Induction

1. Theorem 8.3 (a) (a useful identity): $n^2=n\cdot n$
2. Theorem 8.3 (b) (useful identity): $2\cdot n=n+n$
3. Theorem 8.2 (b) (power law): $z^m\cdot z^n=z^{m+n}$
4. Theorem 8.2 (c) (power law): $(z^m)^n=z^{m\cdot n}$
5. Theorem 8.4 (quadratic beats linear): If $a+b\leq n$ then $a\cdot n+b\leq n^2$

Assignment #15 Sequences, Recursion, and Induction

1. Theorem 8.7 (Fib fun): $F_{n+3}+F_n=2\cdot F_{n+2}$
2. Theorem 8.5 (b) (basic sum property): $\displaystyle \sum_{i=0}^n s\cdot a_i = s\cdot \sum_{i=0}^n a_i$
3. Theorem 8.11 (closed formula for binomial coefficients): $\displaystyle(m!\cdot n!)\cdot \binom{n+m}{m}=(n+m)!$

Assignment #16 Real numbers and Field axioms

1. Theorem 9.3 (cancellation for addition): If $x+z=y+z$ then $x=y$
2. Theorem 9.2 (b) (signed product): $(-1)\cdot(-1)=1$
3. Theorem 9.2 (c) (harder than it looks): $0\lt 1$
4. Theorem 9.2 (d) (not mod 2): $-1\neq 1$

Assignment #17 Real numbers and Field axioms

1. Theorem 9.4 (cancellation for multiplication): If $z\neq 0$ and $z\cdot x=z\cdot y$ then $x=y$.
2. Theorem 9.6 (multiplicative inverses are unique): If $z\cdot x=1$ and $z\cdot y=1$ then $x=y$.
3. Theorem 9.10 (alternate additive inverse): $-x=-1\cdot x$
4. Theorem 9.18 (adding inequalities): If $w\lt y$ and $x\lt z$ then $w+x\lt y+z$.
5. Theorem 9.23 (scaling by a negative): If $z\lt 0$ and $x\lt y$ then $z\cdot y\lt z\cdot x$.
6. Theorem (between): There exists a real number strictly between 0 and 1, i.e., $\exists r.0\lt r \text{ and }r\lt 1$.

Assignment #18 Elementary Set Theory

1. Theorem 10.5 (double negative): $\left(A’\right)'=A$
2. Theorem 10.32 (always in the power set): $\{~~\}\in \mathscr{P}(A)$
3. Theorem 10.34. (power sets of subsets): If $A\subseteq B$ then $\mathscr{P}(A)\subseteq\mathscr{P}(B)$.
4. Theorem 10.38 (relative complement is not associative): If $x\in A$, $x\in B$, and $x\in C$ then $(A\setminus B)\setminus C\neq A\setminus (B\setminus C)$.
5. Theorem 10.7 (a set of sets): $\{\,1,2\,\}\in\left\{\,Y:\{\,1\,\}\subseteq Y\right\}$

Assignment #19 Elementary Set Theory

1. Theorem 10.23(b) (∩ distributes over ∪): $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$
2. Theorem 10.37 (subsets are contagious): If $A \subseteq C$ and $B\subseteq D$ then $A\times B\subset C\times D$.
3. Theorem 10.31 (not a subset): $A \nsubseteq B$ if and only if $\exists x.x \in A \cap B’$
4. Theorem 10.27 (Baby De Morgan): $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$
5. Theorem 10.29 (Papa De Morgan): $\displaystyle\left(\bigcap_{i \in I} A_i\right)’ = \bigcup_{j\in I} A_j’$

Assignment #20 Functions and Composition

1. Theorem 10.41 (composition is associative): If $h\colon A \to B$, $g\colon B \to C$, $f\colon C \to D$ then $$f\circ(g\circ h)=(f\circ g)\circ h.$$
2. Theorem 10.53 (a) (identity maps are injective): The map $\mathrm{id}_A$ is injective.
3. Theorem 10.53 (b) (identity maps are surjective): The map $\mathrm{id}_A$ is surjective.
4. Theorem 10.46 (image of subsets): If $f\colon A \to B$, $S \subseteq T$, and $T \subseteq A$ then $f(S)\subseteq f(T)$.

Assignment #21 Functions and Composition

1. Theorem 10.43 (a linear bijection): If $f\colon \mathbb{R} \to \mathbb{R}$ and $\forall x.f(x)=3\cdot x+1$ then $f$ is bijective.
2. Theorem (inverse images respect intersection): If $f\colon A \to B$, $S \subseteq B$, $T \subseteq B$ then $$f^\mathrm{inv}(S \cap T)=f^\mathrm{inv}(S) \cap f^\mathrm{inv}(T)$$
3. Theorem (inverse functions are bijective): If $f\colon A \to B$ and $f$ is bijective then $f^{-1}$ is bijective.
4. Theorem 10.52 (inverse of a composition): If $f\colon A \to B$, $g\colon B \to C$, $f$ is bijective, and $g$ is bijective then $$(g \circ f)^{-1} = f^{-1} \circ g^{-1}$$

Assignment #22 Equivalence relations and Partial Orders

1. Theorem (integer associates) Define $\sim$ to be the relation on $\mathbb{Z}$ such that for all $x,y\in \mathbb{Z}$, $$x\sim y\text{ if and only if }y=x\text{ or }y=−x$$ Then $\sim$ is an equivalence relation.
2. Theorem ($\subseteq$ is a partial order) Let $A$ be a set and suppose $\sim$ is a relation on $\mathscr{P}(A)$ such that for all $S,T\in\mathscr{P}(A)$ $$S\sim T\text{ if and only if }S\subseteq T$$ Then $\sim$ is a partial order.

Assignment #23 Equivalence relations and Partial Orders

1. Theorem 10.65 Congruence mod $m$ is an equivalence relation on the set of integers.
2. Theorem 10.66 (class representatives): Every integer $a$ is congruent mod $m$ to a unique natural number that is less than $m$.

Assignment #24 Modular arithmetic

1. Theorem 10.68 (modular addition): For any integers $a,b,c,d$, if $a \underset{m}{\equiv} b$ and $c \underset{m}{\equiv} d$ then $a+c \underset{m}{\equiv} b+d$
2. Theorem 10.69 (modular multiplication): For any integers $a,b,c,d$, if $a \underset{m}{\equiv} b$ and $c \underset{m}{\equiv} d$ then $a\cdot c \underset{m}{\equiv} b\cdot d$

Final Exam!– try your hand at the Math 299 Final Exam from Spring 2024.

• A. The Logic of Love
• B. Nostalgia for Calculus
• C. Putnam Practice
• D. Topo-logical