In 1931 a twenty-five-year-old in Vienna published a paper proving that mathematics cannot fully formalise itself: any consistent formal system rich enough to do arithmetic contains true statements it cannot prove, and — worse — cannot even prove its own consistency (Gödel, Kurt, 1931). 𐃏 This page walks the actual argument: what the theorem says precisely, the two technical inventions that power it (Gödel numbering and diagonalisation), and — just as important — the long list of things it does not say.
Discrete Mathematics
discrete mathematics is the mathematics of structures that come in separate, countable pieces — integers, truth values, finite sets, graphs — as opposed to the smooth continuum of analysis. 𐃏 no limits, no derivatives; instead: induction, counting, and exact structure. it is the native mathematics of computation — every data structure, algorithm, database query and cryptographic protocol below this page is discrete mathematics wearing a lab coat (Epp, Susanna S., 2019).
the field is less a single theory than a federation of subfields sharing a toolkit (induction, pigeonhole, bijection, recurrence). the map:
the subfields
sets, functions and sequences
the substrate everything else is written in. sets and subsets, cartesian products, the algebra of union/intersection/complement (de morgan’s laws live here), functions as special relations, injections/surjections/bijections, and sequences as functions on \(\mathbb{N}\). cardinality is where the subject briefly touches the infinite: countable versus uncountable, and cantor’s diagonal argument. this page already has developed notes — start there.
logic
the rules of the game. propositional logic (connectives, truth tables, normal forms, satisfiability), first-order logic (quantifiers and models), natural deduction, and the proof techniques — direct, contrapositive, contradiction, induction — that the rest of mathematics quietly assumes. also where SAT solving and the soundness/completeness theorems live.
combinatorics
the art of counting without listing. permutations and combinations, the binomial theorem, pigeonhole, inclusion-exclusion, and recurrence relations (fibonacci, towers of hanoi, the master theorem’s natural habitat). generating functions are the power tool: they turn counting problems into algebra (Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren, 1994).
graph theory
dots and lines, taken seriously. degree and the handshake lemma, trees and their five equivalent characterisations, eulerian and hamiltonian traversals, planarity and euler’s formula \(V - E + F = 2\), colouring, and matchings via hall’s theorem. the algorithmic side (BFS, DFS, shortest paths, spanning trees) lives under data structures & algorithms.
number theory
the integers under a microscope. divisibility and the euclidean algorithm, bezout’s identity, unique factorisation, modular arithmetic and the chinese remainder theorem, fermat’s little theorem and euler’s totient — culminating in RSA, where 2300 years of “useless” mathematics turned into the lock on your bank account.
adjacent topics
three topics from the classical discrete-maths syllabus live elsewhere in this wiki or await their own pages:
- recurrence relations — set up in combinatorics; solved asymptotically by the master theorem over in classical algorithms.
- finite automata & formal languages — really theory of computation; they belong with the computer-science pages.
- discrete probability — counting with weights; the combinatorics page is the prerequisite.
theorem index
the headline results, and where each one lives:
| theorem | home |
|---|---|
| de morgan’s laws | sets (set form), logic (propositional form) |
| pigeonhole principle | combinatorics |
| inclusion-exclusion principle | combinatorics |
| handshake lemma | graph theory |
| euler’s formula \(V-E+F=2\) | graph theory |
| chinese remainder theorem | number theory |
| fermat’s little theorem | number theory |
| RSA correctness (via euler’s theorem) | number theory |
| master theorem | classical algorithms |
| gödel’s incompleteness theorems | incompleteness |
how to read this section
the dependency order is roughly the diagram left to right: sets and logic are prerequisites for everything, combinatorics and graph theory are independent of each other, and number theory only needs induction and the well-ordering principle. 𐃏 epp (Epp, Susanna S., 2019) covers the whole federation at undergraduate pace; graham, knuth and patashnik (Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren, 1994) is the deeper cut on the counting and number-theoretic side.
see also
- data structures & algorithms — discrete mathematics, executed
- classical algorithms — where the recurrences get solved
References
Epp, Susanna S. (2019). Discrete Mathematics with Applications, Cengage Learning.
Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley.
logic is the study of valid inference: which conclusions are forced by which premises, independent of what the premises are about. 𐃏 it splits cleanly into a syntax (formulas, and rules for pushing them around) and a semantics (truth assignments, models), and the deepest theorems in the subject are exactly the ones that say when the two agree (Epp, Susanna S., 2019).
number theory studies the integers on their own terms — divisibility, primes, remainders — and for two millennia it was the purest of pure mathematics, prized precisely because it was useless. 𐃏 then in 1977 the RSA cryptosystem turned euclid, fermat and euler into load-bearing internet infrastructure. this page walks the classical results in dependency order and ends at that payoff (Epp, Susanna S., 2019).
graph theory began in 1736 when euler noticed that a walking-tour puzzle about seven bridges in königsberg was really a question about dots and lines — and that the geometry (lengths, positions, the river) was irrelevant. 𐃏 that act of abstraction — keep the incidence structure, discard everything else — is the whole subject. a graph is the minimal mathematical model of “things, some pairs of which are related”, which is why it keeps turning up: networks, molecules, dependencies, state machines, social graphs (Epp, Susanna S., 2019).
“The introduction of suitable abstractions is our only mentail aid to organize and master complexity” — E. W. Dijkstra. 1930-2002
Sets
Proper Subset
Let A and B be sets. A is proper subset of B \(\iff \exists \forall a \in A, a \in B\), but \(\exists\) at least one element of B \(\not\in A\).
Cartesian Product
Given sets \(A_1, A_2, …, A_n\), their Cartesian Product is the set of all ordered n-tuples \((a_1, a_2, …, a_n)\) where \(a_1\in A_1, a_2\in A_2, …, a_n\in A_n\).
Backlinks (3)
1. Linear Algebra /wiki/mathematics/linear-algebra/
linear algebra is the study of vector spaces and the structure-preserving maps between them. it is the one branch of mathematics that computers execute natively — every model fit, every graphics frame, every pagerank iteration is matrix arithmetic — and the local model that calculus reduces every smooth problem to. 𐃏 the plot of this page: spaces, then maps, then the four subspaces every matrix carries, then the two great factorisations — the spectral theorem and the svd (Anton, Howard, 2010).
2. Wiki /wiki/
Knowledge is a paradox. The more one understand, the more one realises the vastness of his ignorance.