How do the ZFC axioms produce the ideas of order?

Question

The notion of order (and cardinality, for that matter) seems so basic to me that I can't imagine how it could be derived from anything.

In an answer to a previous question I learned that all the concepts in ZFC can be derived from the rules of logic and the concept of membership.

I'm comfortable with first-order logic and elementary set theory (but not much more than that).

How is the notion of order built up from just first-order logical principles and membership? I've just started learning how notions can be built from these principles, so if other notions need to be built in order to build order, it would help me a great deal if you could show how those notions are built.

Thank you.

Answer 1

To answer your question, we need to know what you mean by "order". The term has lots of uses in math.

In your comment, you explained you had in mind ordered pairs: $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$. In ZFC, one usually defines $(a,b)$ to be the set $\{\{a\},\{a,b\}\}$. This is a trick: while $\{a,b\}=\{b,a\}$ even if $a\neq b$, we have $$\{\{a\},\{a,b\}\}\neq\{\{b\},\{b,a\}\}$$ if $a\neq b$.

In fact, if $$\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$$ then $a=c$ and $b=d$. Proof: if $a\neq b$, then the left-hand-side is a set containing two sets, so we must also have $c\neq d$. So each side contains exactly one singleton (a singleton is a set containing a single element). So the singletons must be equal, so $a=c$. So the remaining elements of the two-element sets, $b$ and $d$, must also be equal. However, if $a=b$, then the left-hand-side is just $\{a\}$. (Because $\{a,a\}=\{a\}$.) So $c=d$ and $a,b,c,d$ are all equal.

I'll leave the rest of my original answer as maybe still interesting. Note that this definition of $(a,b)$ is just a trick: using the language I use below, we could say that $\{\{a\},\{a,b\}\}$ plays the role of $(a,b)$ in ZFC.

So if you mean the ordering of the natural numbers, then there is one answer; if you mean the ordering of the rationals, or of the reals, those both lead to different answers.

The ZFC axioms formalize certain intuitions about sets. Traditionally in ZFC, we define natural numbers, rationals, etc., as certain kinds of sets. For example, here's a collection of sets that can be used to play the roles of natural numbers:

{} (the empty set)

{{}} (a set with 1 element)

{{},{{}}} (a set with 2 elements, namely the sets on the previous two lines)

etc.

So we just define 0 to be {}, 1 to be {0}, 2 to be {0,1}, 3 to be {0,1,2} etc.

I said "play the role" above, because no number-theorist actually thinks of 3 as the set {0,1,2}. The point is that for number theory, we don't really care what 3 is, just the relations it has to the other natural numbers. Or in other words, the properties of the system of natural numbers as a whole. These ZFC definitions of the natural numbers enables us to build up a system with all the desired properties.

Zermelo (the Z in ZFC) actually originally used a different bunch of sets for the natural numbers, namely 0={}, 1={{}}, 2={{{}}}, 3={{{{}}}}, etc.; von Neumann used the other collection, which turns out to be technically much more convenient. For one thing, we can define $x<y$ (for natural numbers $x$ and $y$) to mean $x\in y$ (since $x$ and $y$ are sets with this approach, and $y$ is the set of all natural numbers less than itself).

We could say that Zermelo and von Neumann cast the same play with a different actors.

That's how it goes for other collections of common mathematical objects, like (say) the reals. Dedekind and Cantor both gave ways of defining real numbers as certain (rather complicated) sets. The sets playing the role of (say) the real numbers $e$ and $\pi$ are very different with Cantor's and Dedekind's definitions. Also, the definition of $x<y$ (in terms of the basic set-theoretic concept of $\in$) is quite different with Cantor's and Dedekind's definitions. Nonetheless, "$e<\pi$" holds with either definition.

Why do we construct the natural numbers, the reals, etc., as certain kinds of sets in ZFC? Why not treat them as primitive objects in their own right, with no internal structure? Well, you could do that. This approach leads to something called "set theory with atoms", i.e., objects that are not sets (the atoms), and then sets built up out of the atoms. While this may seem more natural, it's technically more complicated. You now have two kinds of mathematical objects to worry about: the atoms, and sets. It's just slicker to build up your mathematical universe out of one kind of object: the set.

(Nonetheless, for certain theoretical purposes, set theorists have studied set theory with atoms.)

Answer 2

Mathematical notions are translated to definitions (in most cases), which include axioms.

We define cardinality in terms of bijections. We say that $|A|=|B|$ if there exists a function whose domain is $A$ and its range is $B$, and it is injective. And we say that $|A|\leq|B|$ if there exists an injection from $A$ to $B$ (which weakens the above to say that the range of the function is a subset of $B$). Let us work towards that.

In the language of set theory we only have $\in$, but we can define as shorthand a lot of other things, $\varnothing,\subseteq,\mathcal P$ and so on. So when we write something like "There is no surjection from a set $A$ onto its power set" we don't have to write this insanely long sentence which will be impossible to understand. (This is somewhat similar to writing software, where you don't just write all the code at once, you add functions and procedures that enrich your language.)

Now. There are some notions which are abstract (like the concept of a function) which we can "implement" in set theory by deciding that a particular object is always interpreted as sets of a certain form. Then we have the prove that indeed this interpretation satisfies the definition of the abstract notion. For example the ordered pair $(a,b)$ is a mathematical object satisfying $(a,b)=(c,d)\iff a=c\land b=d$. In set theory we may choose to define $(a,b)$ as the set $\{\{a\},\{a,b\}\}$. There are other definitions which work, but this one is pretty standard. So now when we write "ordered pair" we mean to say that it is a set which has the above property.

Next, functions. We can define a function as a set of ordered pairs with the property that if $(a,b)$ and $(a,c)$ are in that set, then $b=c$. This ensures that $f(a)$ is a well-defined object. So now we can write a formula with a free variable $x$, whose content is "Every element of $x$ is an ordered pair, and if two ordered pairs share the same left-coordinate then they are equal."

Then we can write similar formulas saying that $x$ is the domain of a function $f$, and that $y$ is the range of that domain, and that $f$ is an injection, or a bijection.

Finally. We can write a formula $\varphi(A,B)$ "There exist a function $f$ whose domain is $A$ and its range is $B$ and $f$ is injective". Simply by composing all the previous things that we expressed. Now given $V$ a universe of $\sf ZFC$ and $A,B\in V$ are two sets, then $V\models\varphi(A,B)$ if it is true (in $V$) that $|A|=|B|$.