Foundations: What Mathematics Stands On

Ask a child for the biggest number they know, then say "plus one". You have just done mathematics. You did not check every number. You gave a short argument that works for all of them, and no list could ever match it. That move, certainty about something endless from a few steps of reasoning, is what a first mathematics course is really about.

It is also a little frightening, because it asks what the steps are allowed to be. What counts as a legal move? What are numbers made of? Is there a largest infinity? Around 1900 mathematicians found that the loose answers they had used for centuries produced actual contradictions, and rebuilt the ground floor. What they built, and the discovery in 1931 that the building can never be finished, is what this course teaches.

A graduate does not carry the axioms around. A graduate carries a feel for what a proof is, for which statements are slippery, and for the fact that "infinite" is not one thing.

Everything is a collection: sets

A set is a collection of things, and the only question you may ask about a set is which things are in it. Order does not matter, repeats do not matter. {1, 2, 3} and {3, 2, 1, 1} are the same set. That sounds too thin to build anything on, yet by 1900 almost all of mathematics had been rewritten in the language of sets: a function is a set of input-output pairs, a number can be a set (zero is the empty set, one is the set containing the empty set, and so on), a shape is a set of points.

The first surprise is how fast sets multiply. A subset is a collection you can form by picking some of a set's elements. For each element there are two choices, in or out, and the choices are independent. So a set with n elements has

Five elements give 32 subsets; ten give 1,024; a mere 30 give over a billion. The collection of all subsets of S is the power set of S, and it will matter again when we reach infinity. Switch elements in and out below; each choice of in/out is a binary number, which is why the count is a power of two.

Logic: "for all" and "there is" do not commute

A proof is a chain of statements, so the first skill is reading one exactly. Two phrases carry most of the weight. "For all" (∀) claims something about every member; one counter-example kills it. "There exists" (∃) claims at least one member works; one example proves it. And the order you write them in changes the meaning.

"Everybody loves somebody" is: for every person, there is someone they love. "Somebody is loved by everybody" is: there is one person, whom all love. The first can be true while the second is false, if everyone loves a different person. The reverse never happens. This is the exact trap in the definition of a limit (next course): "for every ε there is a δ" is not the same as "there is a δ that works for every ε", and confusing them is how false proofs happen.

Two more habits. To negate a statement, flip the quantifiers and negate the end: the opposite of "everybody loves somebody" is "somebody loves nobody". And an implication "if P then Q" is only broken by P true and Q false; it is equivalent to its contrapositive, "if not Q then not P" ("if the grass is dry, it did not rain"). Many proofs are easier backwards. Make your own relation below.

Proof by contradiction: the biggest prime does not exist

The most powerful single move in mathematics is to assume the opposite of what you want and watch it fall apart. Two proofs, both over 2,000 years old, show how it feels. Euclid gave the first in his Elements; the second is traditionally credited to the early Greek mathematicians.

Infinitely many primes. Suppose, for contradiction, you had a complete list of primes. Multiply them all together and add 1; call it N. Divide N by any prime on your list and the remainder is 1, because the product part divides evenly. So no prime on the list divides N. But every number above 1 has some prime factor (that is the quiet fact the proof leans on), so a prime outside your list exists. The list was not complete. The trick is the "+1": it manufactures a number your list cannot reach. Note that N itself need not be prime; the proof only says a new prime divides it.

The square root of 2 is irrational. Suppose √2 = p/q in lowest terms. Then p² = 2q², so p² is even, so p is even, say p = 2r. Then 4r² = 2q², so q² = 2r² and q is even too. Both even contradicts "lowest terms". The trick is choosing lowest terms first, so that a shared factor of 2 is forbidden.

Infinity comes in sizes: Cantor's diagonal

Two sets are the same size if you can pair their elements one to one, with none left over on either side. That is how a child checks that every guest has a chair. Applied to infinite sets it gives strange results: the even numbers pair with all the counting numbers (2n with n), so there are "as many" evens as numbers. A set you can list as a first, second, third... item is called countable. The whole numbers, the integers and even the fractions are countable.

In 1891 Georg Cantor published a short argument that the real numbers are not. Take any supposed list of infinite sequences of 0s and 1s (think: which numbers are in each set). Build a new sequence by going down the diagonal and flipping each entry: it differs from the first sequence in the first place, from the second in the second place, and so on. It cannot be anywhere on the list. The trick is making the new object disagree with the n-th item at the n-th place, so it differs from everything at once.

Read each row of the grid as a subset of {1, ..., n}, and the argument becomes Cantor's theorem: no list of subsets of S, indexed by the elements of S, can contain every subset. The missing one is D = {x : x is not in its own row}. That works for any set at all, so the power set is always strictly bigger, and there is no largest infinity. The proof is the same one you can run on a finite grid.

Cantor's names for the sizes: the countable infinity is ℵ₀ ("aleph-null"); the reals have size 2^ℵ₀, which is bigger. Whether anything sits between them is the continuum hypothesis, and we will get to what happened to that question.

Russell's paradox and the axioms

Early set theory allowed any rule to define a set: "the set of all things that are red", "the set of all sets". Around 1901 Bertrand Russell asked about the set R of all sets that do not contain themselves. Is R a member of itself? If yes, then it is a set that contains itself, so by its own rule it should be out. If no, it is a set that does not contain itself, so it should be in. Either way, a contradiction. It is the barber who shaves exactly those men who do not shave themselves: who shaves the barber?

Gottlob Frege, who had just finished the first great attempt to base arithmetic on logic, received Russell's letter at the worst moment. The repair that most of mathematics now uses is Zermelo–Fraenkel set theory (ZF, or ZFC with the axiom of choice). Zermelo's 1908 system replaced "any rule makes a set" with a safer one, separation: given a set A you may carve out the members satisfying a rule, but you cannot conjure a set out of thin air. Then {x in A : x not in x} is fine; it just turns out not to be a member of A. Fraenkel and Skolem sharpened the system in 1922 and added replacement. Its main ingredients, in plain words:

Axiom	What it lets you do
Extensionality	Sets with the same members are the same set.
Pairing, Union	Form {a, b}; gather the members of members.
Power set	All subsets of a set form a set.
Infinity	An infinite set exists (the counting numbers).
Separation, Replacement	Carve out by a rule; swap members for their images.
Foundation	No set contains itself, and no endless descending chain of memberships.
Choice	From any family of non-empty sets you can pick one from each.

The axiom of choice is the one that has history. It is needed for many theorems (every vector space has a basis) and also gives weird ones, like the Banach–Tarski paradox of 1924, which cuts a ball into pieces that reassemble into two balls the same size. The pieces are not measurable, so nothing physical is violated. Most mathematicians accept it; constructive mathematicians, who insist on explicit constructions, do not. A graduate knows which of their proofs use it.

What the rules cannot settle: Gödel and the continuum

David Hilbert hoped for a single formal system strong enough for all of mathematics, provably free of contradiction, and able to decide every statement. In 1931 Kurt Gödel showed that this cannot be had. His first incompleteness theorem: any consistent system that can express basic arithmetic, and whose axioms can be listed by a computer program, has true statements it cannot prove. His second: such a system cannot prove its own consistency.

The sketch has three steps, and the first is the one to see. The trick is to turn statements into numbers. Give each symbol a code, and encode a formula by raising successive primes to those codes. Now a statement about formulas is a statement about numbers, which the system can express. Second, with some work, "this number codes a proof of that formula" becomes an arithmetic statement. Third, build a sentence G that says, via the coding, "I am not provable". If the system proves G, it proves something false (assuming it is sound). If it does not, then G is true and unprovable. Try the coding yourself.

Gödel's result did not make mathematics unreliable. It said the foundations are never "finished". And it has a concrete sibling. The continuum hypothesis says nothing lies between the size of the counting numbers and the size of the reals. Gödel showed in 1940 that ZFC cannot disprove it (assuming ZFC is consistent); Paul Cohen showed in 1963, with a new method called forcing, that ZFC cannot prove it either. Set theorists still disagree about what that means: some hope a compelling new axiom will settle it, and others think it has no single true answer. As far as anyone can tell, the answer is not in the axioms we have.

Two more statuses so you can tell open from closed. Closed: the incompleteness theorems and the independence of CH are proved. Open: whether any natural new axiom decides CH. And the earliest question we asked, whether ZFC itself is consistent, cannot be proved inside ZFC (if it is consistent), by Gödel's second theorem.

What a graduate just sees

• A statement with "for all" is killed by one counter-example; one with "there exists" is proved by one example. The order of the two changes the meaning.
• To prove "if P then Q" you may prove "if not Q then not P"; to prove something never happens, assume it does and chase the consequence.
• A subset is an in/out choice for each element, so a set of n things has 2ⁿ subsets.
• "Infinite" is not one size. Pairing things one to one is the test, and the diagonal beats any list.
• "The set of everything satisfying X" is dangerous. Carve from a set you already have.
• Every proof starts from something assumed. The honest questions are which axioms, and what follows.
• There are statements, true or not, that a given system cannot settle, and that is a theorem, not a failure of effort.

Where it shows up next

• Real Analysis (34/72): the ε–δ definition is nested quantifiers, and the real numbers are built from sets of rationals.
• Abstract Algebra (34/73): a group is a set with an operation, and everything is proved from axioms in the style you just met.
• Topology (34/76): a space is a set with a chosen family of subsets, and the axiom of choice shows up as a real theorem (Tychonoff's).
• Computer science: the diagonal argument reappears as Turing's proof that no program can decide whether every program halts. The same trick, applied to programs rather than numbers.
• Practice: proof assistants like Lean and Coq check proofs against a fixed foundation, exactly the "legal moves" idea made mechanical.

If you want to go deeper

• 📘 Textbook. Richard Hammack, Book of Proof. The standard free first text on proof, sets and logic, offered online by the author.
• 📘 Textbook. Herbert Enderton, Elements of Set Theory (Academic Press, 1977). The classic next step into axiomatic set theory, if you want the real ZF development.
• 📘 Gentler. Agustín Rayo, On the Brink of Paradox (MIT Press, 2019). Puzzles from infinity to Gödel's theorem, with almost no formal prerequisites.
• 🌐 Free course. MIT OpenCourseWare 24.118 Paradox and Infinity (Spring 2019, taught by Agustín Rayo): infinities, paradoxes, computability and Gödel, built on his book.