proof are important: you don’t understand something until you proof it. We want to come up with the right level of proof—this is a challenge.

• good proofs should be clear
• good proofs should be correct and convincing
• good proofs has layers: “cover the ‘hot’ technical details with various levels of intuition”

Typically, in writing proofs, it could be helpful to write three levels of detail:

1. “hint” of the proof - “proof by contradiction, proof by induction, follows from…”
2. “sketch” of the proof - a one-paragraph of the description of the main ideas
3. the proofy proof

• lecture proof are usually very scant of the third-level details
• you should think about how to fill in the details!

methods of proof

• construction
• contradiction
• induction / strong induction
• most powerful type of proof—reductions, connecting problems together

interactive proof systems

We have two parties of a game, the proves and verifier. Something is a well-formed proof system IF BOTH:

A proof structure that uses induction.

base case

Prove some base case \(n_0\)

inductive step

Prove that, given \(n\), \(n_{j} \implies n_{j+1}\).

Based on the wise words of a crab, I will start writing down some Proof Design Patterns I saw over Axler.

• inheriting properties (splitting, doing, merging) “complex numbers inherit commutativity via real numbers”

• construct then generalize for uniqueness and existence

• try to remember to go backwards

• to prove IFF

• zero is cool, and here too!, also \(1-1=0\)

  • \(0v = 0\)
  • \(1-1 = 0\)
  • \(v-v=0\) a.k.a. \(v+(-v)=0\)
  • \(v+0 = v\)

• distributivity is epic: it is essentially the only tool to connect scalar multiplication and addition in a vector space

Based on the wise words of a crab, I will start writing down some Proof Design Patterns I saw over Axler everything.

• inheriting properties (splitting, doing, merging) “complex numbers inherit commutativity via real numbers”

• construct then generalize for uniqueness and existence

• try to remember to go backwards

• to prove IFF

• zero is cool, and here too!, also \(1-1=0\)

  • \(0v = 0\)
  • \(1-1 = 0\)
  • \(v-v=0\) a.k.a. \(v+(-v)=0\)
  • \(v+0 = v\)

• distributivity is epic: it is essentially the only tool to connect scalar multiplication and addition in a vector space

Suppose \(\qty(G,s,t) \in \neg \text{STCONN}\), meaning no path \(s \to t\) exists in \(G\).

setup

For \(l \in \qty {0,1, \dots, n}\), define \(R_{l} \subseteq V\) is the set of all vertices readable from \(s\) in \(\leq l\) steps. \(R_0 \subseteq R_1 \subset … R_{n}\). Meaning \(R_0 = \qty {s}\). Goal: convince \(V\) that \(t \not \in R_{n}\).

Define: \(r_{l} = |R_{l}|\). What’s the size of \(r_{l}\)? It’s at most \(O\qty(\log \qty(n))\) size. Notice that storing \(R_{l}\) takes \(O\qty(n \log n)\) or at least \(O(n)\) space by storing either IDs or at least bitstring of everything.