Downloadable at https://web.evanchen.cc/handouts/NaturalProof/NaturalProof.pdf.

I don’t know why I thought to write this, but it’s been bugging me for a year or two now that I’ve never seen the answer to “what is a proof” written out quite this way. So here you go.

It’s a bit weird for me to be writing an article that contains “you can stop reading here” as the second sentence, but first time for everything, I guess.

Model theory is really meta, so you will have to pay attention here.

Roughly, a “model of $\mathsf{ZFC}$” is a set with a binary relation that satisfies the $\mathsf{ZFC}$ axioms, just as a group is a set with a binary operation that satisfies the group axioms. Unfortunately, unlike with groups, it is very hard for me to give interesting examples of models, for the simple reason that we are literally trying to model the entire universe.

1. Models

(Prototypical example for this section: $(\omega, \in)$ obeys $\mathrm{PowerSet}$, $V_\kappa$ is a model for $\kappa$ inaccessible (later).)

Definition 1. A model $\mathscr M$ consists of a set $M$ and a binary relation $E \subseteq M \times …$

(Standard post on cardinals, as a prerequisite for forthcoming theory model post.)

An ordinal measures a total ordering. However, it does not do a fantastic job at measuring size. For example, there is a bijection between the elements of $\omega$ and $\omega+1$:

$$\begin{array}{rccccccc} \omega+1 = & \{ & \omega & 0 & 1 & 2 & \dots & \} \\ \omega = & \{ & 0 & 1 & 2 & 3 & \dots & \}. \end{array}$$

In fact, as you likely already know, there is even a bijection between $\omega$ and $\omega^2$:

$$\begin{array}{l|cccccc} + & 0 & 1 & 2 & 3 & 4 & \dots …$$

This is a draft of an appendix chapter for my Napkin project.

In the world of olympiad math, there’s a famous functional equation that goes as follows: $$f : {\mathbb R} \rightarrow {\mathbb R} \qquad f(x+y) = f(x) + f(y).$$ Everyone knows what its solutions are! There’s an obvious family of solutions $f(x) = cx$. Then there’s also this family of… uh… noncontinuous solutions (mumble grumble) pathological (mumble mumble) Axiom of Choice (grumble).

There’s also this thing called Zorn’s Lemma. It sounds terrifying, because it’s equivalent to the Axiom of Choice, which is also terrifying because why not.

In this post I will try to de-terrify …

This is a continuation of my earlier set theory post. In this post, I’ll describe the next three axioms of ZF and construct the ordinal numbers.

1. The previous axioms

As review, here are the natural descriptions of the five axioms we covered in the previous post.

Axiom 1 (Extensionality). Two sets are equal if they have the same elements.

Axiom 2 (Empty Set Exists). There exists an empty set $\varnothing$ which contains no elements

Axiom 3 (Pairing). Given two elements $x$ and $y$, there exists a set $\{x,y\}$ containing only those two elements. (It is permissible to have $x=y$, meaning that if $x$ is a set then so is $\{x\}$.)

Axiom 4 (Union). Given a set $a$, we can create $\cup a$, the union of the …

Back in high school, I sometimes wondered what all the big deal about ZFC and the Axiom of Choice was, but I never really understood what I read in the corresponding Wikipedia page. In this post, I’ll try to explain what axiomatic set theory is trying to do in a way accessible to those with just a high school background.

1. Motivation

What we’re going to try to lay out something like a “machine code” for math: a way of making math completely rigorous, to the point where it can be verified by a machine. This would make sure that our foundation on which we do our high-level theorem proving is sound. As we’ll see in just a moment, this is actually a lot harder to do than it sounds – there are some traps if we try to play too loosely with our definitions.

First of all …