logic
14 theorems carry this thread across the degree.
The principle of mathematical induction
If a statement holds for 1 and its truth at n forces its truth at n+1, it holds for every natural number.
The well-ordering principle
Every non-empty set of natural numbers has a least element, and this is equivalent to induction.
The pigeonhole principle
If n+1 objects are placed in n boxes, some box holds at least two.
The irrationality of √2
No ratio of integers squares to 2; the proof is the classic argument by contradiction.
The infinitude of the primes
There is no largest prime; assuming a finite list yields a contradiction.
The uncountability of the reals
No list can enumerate all real numbers — Cantor's diagonal argument.
Cantor's theorem
A set never has the same cardinality as its power set: |P(A)| > |A|.
Zorn's lemma
Every chain-bounded poset has a maximal element — equivalent to choice.
The compactness theorem
A theory is satisfiable iff every finite subset is.
The Löwenheim–Skolem theorem
First-order theories with infinite models have models of every infinite size.
Gödel's completeness theorem
Every logically valid first-order formula is provable.
Gödel's incompleteness theorems
Sufficiently strong consistent systems cannot prove their own consistency.
The division algorithm
Every integer divides another with a unique quotient and a unique remainder below the divisor.
Equivalence relations and partitions
Equivalence relations and partitions of a set are the same data: the classes of a relation partition it, and every partition comes from exactly one relation.