Prove it! 2020 Announcements

Welcome to Prove it! Math Academy 2020. We will post announcements and other information here. Check back often for the latest updates!

Prove the following using only the rules of natural deduction for propositional logic given in the lecture notes. Your proof should be written in the formal proof style. You can use Lurch to check your proofs. If you finish these and want more practice there are more problems in the lecture notes you can try. Feel free to ask an instructor for help if you get stuck.

• 1. The Most Beautiful Tautology? $P \Rightarrow (P \Leftrightarrow P \text{ or } (\neg P \text{ and }P))$Bonus: Do you see why is it beautiful?
• 2. Alternate form of implication. $(P \Rightarrow Q) \Leftrightarrow (\neg P \text{ or } Q)$
• 3. Associativity of or. $P \text{ or } (Q \text{ or } R) \Leftrightarrow (P \text{ or } Q) \text{ or } R$
• 4. Pierce’s Law $((P \Rightarrow Q) \Rightarrow P) \Rightarrow P$

Prove the following using only the rules of natural deduction for predicate logic given in the lecture notes. Your proof should be written in the formal proof style. You can use Lurch to check your proofs. If you finish these and want more practice there are more problems in the lecture notes you can try. Feel free to ask an instructor for help if you get stuck.

• 1. Yet another DeMorgan. $\neg(\forall x,P(x)) \Leftrightarrow \exists y, \neg P(y)$
• 2. A good one to ponder. $(\exists x, P(x) \Rightarrow Q(x)) \Leftrightarrow (\forall y, P(y)) \Rightarrow (\exists z, Q(z))$
• 3. Only one Mother. $ (\forall x,\exists !y,M(x,y)) \text{ and }\neg (A=B) ⇒ \neg (M(C,A) \text{ and }M(C,B))$

• 1. Carefully read section 6.10 of the Lecture Notes linked to belown on deriving rules of inference from theorems and definitions. See if you can derive the template form of the rule of inference for induction on page 30 from a rule of inference that has no premises and concludes axiom N4, using the rules in section 6.10.
• 2. Prove the following using only the rules of natural deduction for predicate logic given in the lecture notes. Your proof should be written in the semiformal proof style using any of the shortcuts we went over. All quantified variables represent natural numbers. Note that Lurch does not have the Peano Axioms built in (though you could define them if you wanted to.) Feel free to ask an instructor for help if you get stuck.
  • a. Nonzero implies successor. $\forall n,n\neq 0\Rightarrow \exists m, n=\sigma(m)$
  • b. No number is it’s own successor. $\forall n,n\neq \sigma(n)$
  • c. Associativity of Addition. $\forall n,\forall m, \forall p, (n+m)+p=n+(m+p)$

• Prove the following using only the rules of natural deduction for predicate logic with equality, the Peano Axioms, and the recursive definitions of the symbols given in the lecture notes. You can Your proof should be written in the semiformal proof style using any of the shortcuts we went over. You can use any of the theorems about natural numbers that appear at the end of section 7.5 in the lecture notes. All quantified variables represent natural numbers. You cannot use any negative signs or subtraction in your proofs because we have not yet defined those. Feel free to ask an instructor for help if you get stuck.
  • 1. Row sum in Pascal’s triangle. $$ \sum_{k=0}^n {n \choose k}=2^n$$
  • 2. Factorial vs. Exponential Growth. For all natural numbers $n\geq 4$, $$2^n\lt n!$$
  • 3. A Fibonnaci binomial theorem? Suppose $n$ is a natural number. Then $$\sum_{k=0}^n \binom{n}{k}\cdot F_k = F_{2n}$$

• Prove the following using only the rules of natural deduction for predicate logic with equality and the axioms for the Real numbers given in the lecture notes. Your proof should be written in the semiformal proof style using any of the shortcuts we went over.
  • 1. Trichotomy. For every real number $x$ exactly one of the following is true:
    1. $x\lt 0$
    2. $x=0$
    3. $0\lt x$
  • 2. Equivalence relation on the Power Set. Define a relation $\sim$ on $\mathcal{P}(\mathbb{N})$ such that for all $U,V\in\mathcal{P}(\mathbb{N})$ $$U\sim V\text{ if and only if } \forall n\in\mathbb{N}, \left(\exists m\in U, n\lt m\right)\Leftrightarrow \left(\exists m\in V, n\lt m\right)$$ Prove $\sim$ is an equivalence relation and give a simple description of the equivalence classes.
  • 3. Composition of bijections. If $f\colon A\to B$ and $g\colon B\to C$ are bijections, then so is $g\circ f$, and $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$

• Give a combinatorial proof of the following identities.
  • 1. Pascal’s recursion. Show that for any natural numbers $n$ and $k$, we have $$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.$$
  • 2. A Fibonacci identity. Let $F_n$ be the $n$th Fibonacci number, which can be defined as the number of ways to climb an $n$-stair staircase from stair $1$ to stair $n$ using steps of size $+1$ or $+2$ at each step. Prove that $$F_0+F_1+F_2+\cdots+F_n=F_{n+2}-1.$$
  • 3. Catalan numbers. Let $C_n$ by the $n$th Catalan number, defined as the number of Dyck paths (that stay weakly above the diagonal) in an $n\times n$ grid. (Note that $C_0=1$.) Show that the Catalan numbers satisfy the recurrence $$C_{n+1}=C_0C_n+C_1C_{n-1}+C_2C_{n-2}+\cdots + C_nC_0.$$

• The 2020 Prove it! Conference is today! See the Prove it! Challenge Rules linked to below for details. All final drafts of the student articles and slides will be officially collected at the start of the conference. Make sure they compile correctly in Overleaf. Game on!!

• It’s the final day of 2020 Prove it! Math Academy. Today we will discuss life after Prove it! See the Prove it! Schedule linked to below for details.

Congratulations to all twelve Prove it! Math Academy graduates in the class of 2020. You clearly showed your enthusiasm and talent for mathematics and now you can Prove it!

2020 Prove it! Math Academy Photo Album

Next up… USAMTS!