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.