The Axiom of Pairing

The axiom of pairing is an interesting beast. It looks simple, and in fact, it
is simple. But it opens up a range of interesting things that we'd like to be able
to do. For example, without the axiom of pairing, we wouldn't be able to formulate the
cartesian products of sets - and without cartesian product, huge ranges of interesting and
important areas of mathematics would be inaccessible to us. (Note that I'm saying that
pairing is necessary, not that it's sufficient. You also need replacement
to get the projection functions that are part of the usual definition of the cartesian
product.)

So how does the axiom of pairing enable cartesian product?

The simplest answer to that comes from thinking about what cartesian product
does. Given two sets, A and B, the cartesian product is the set of ordered
pairs
where the first element of the pair is an element from A, and the second is an
element from B.

What's an ordered pair in terms of sets? Naively, you might come up with something like
if a∈A, and b∈B, then the ordered pair (a,b) would be the set containing a and b:
{a,b}. And clearly, the axiom of pairing does guarantee that we can do that: it
says that if a and b are sets, then {a,b} is a set.

Unfortunately, that definition doesn't work. A and B can be overlapping sets. Suppose A
was the set {1,2,3}, and B was the set {2,3,4}. Then using the above definition, the pair
(2,3), would be represented as the set {2,3}; and the pair (3,2) would be represented as
the set {3,2}. But sets aren't ordered - so {2,3}={3,2}. But (2,3)≠(3,2). So our naive
attempt is no good - it generates unordered pairs, where we want ordered
pairs.

So our representation of ordered pairs needs to have some way of distinguishing which
element of a pair came first. How do we say which element of a pair comes first? Well, if
we've got an unordered pair {a,b}, the way we can say which element came first is
by created another unordered pair, which contains two sets: the first
unordered pair, and a set containing the member of that unordered pair which
should come first. That sounds a bit confusing, but it's clear once you see an example. If
(a,b) is an ordered pair, then {a,b} is the unordered pair containing a and b. To
make it ordered, we create the pair {{a},{a,b}}. {{a},{a,b}} is the set representation of
the ordered pair. We can tell which member of the set representation identifies the first
element of the ordered pair by using a subset test: if {x,y} is the set representation of
an ordered pair, then either x⊂y or y⊂x. If x⊂y, then x identifies the first
element of the pair; otherwise, y does.

The ordered pair clearly exists: by the axiom of pairing, given a and b, we know that
the set {a,b} exists; and by a second application of pairing, given {a} and {a,b}, we know
that the set {{a},{a,b}} exists.

It's worth pointing out here that since set theory considers a function to be nothing more than a collection of ordered pairs that construction above also means that the axiom of pairing allows us to define functions in terms of sets.

The axiom of pairing does more than just give us a way to do ordered pairs - or even
ordered tuples. What it does is give us the ability to describe all sorts of
structures in terms of sets. It's sort of the "cons" function of set theory: if we
can find a way to describe a structure in terms in terms of pairings, we can build it with
sets. And since we can define ordered lists, unordered collections, pairings, tuples, and
more using pairs as a basis, we can describe pretty much any mathematical
structure using set theory - thanks to the axiom of pairing.

Tags

More like this

Even though this post seems to be shifting back to axiomatic set theory, don't go thinking that we're done with type theory yet. Type theory will make its triumphant return before too long. But before that, I want to take a bit of time to go through some basic constructions using set theory. We'…
So, what's set theory really about? We'll start off, for intuition's sake, by talking a little bit about what's now called naive set theory, before moving into the formality of axiomatic set theory. Most of this post might be a bit boring for a lot of you, but it's worth being a bit on the…
Before I dive into the depths of todays post, I want to clarify something. Last time, I defined categorical products. Alas, I neglected to mention one important point, which led to a bit of confusion in the comments, so I'll restate the important omission here. The definition of categorical product…
Sets are truly amazing things. In the history of mathematics, they're a remarkably recent invention - and yet, they're now considered to be the fundamental basis on which virtually all of mathematics is built. From simple things (like the natural numbers), to the most abstract and esoteric things…

It's worth mentioning that (a,b) = {{a},{a,b}} is not the only way of getting ordered pairs from sets. For example, they could be defined (a,b) = {a,{b}}.

By Canuckistani (not verified) on 23 May 2007 #permalink

Note that I'm saying that pairing is necessary, not that it's sufficient. You also need replacement to get the projection functions that are part of the usual definition of the cartesian product.

Not so. Once all cartesian products A x B exist, we have UU(A x B) = A u B. The range of the projection function already lies in a set, so we don't need replacement to construct it.

Really, and as I noted in an earlier comment, replacement isn't necessary for most "ordinary" mathematics.

To #1: (a,b) = {a,{b}} is not a valid definition, because

( {{}} , {{}} ) = ( {{{}}} , {} ) = { {{}} , {{{}}} }.

By Chad Groft (not verified) on 23 May 2007 #permalink

Canuckistani: The problem with (a,b) = {a,{b}} is that a and b could be nested sets. If you're using the {} = 0, {{}} = 1 encoding, {{{}} {{}}}
could be (0,1) or (1,0).

To reiterate what others have said - the simple pairing {a,{a,b}} doesn't quite work: you can work out cases of sets where you won't be able to correctly determine which element is the first member because of inclusion issues. The {{a},{a,b}} construction works specifically because it makes the problems impossible: given a two-member set {x,y} in ordered pair form in the double-paired form, either x⊂y or y⊂x. The only way you can create something seemingly ambiguous is when you've got a pair like (2,2), which would expand to {{2},{2,2}} = {{2},{2}} = {{2}}. But in that case, there's still no ambiguity: the pair only reduces to a single set when the two members of the pair are equal.

That's why we do the double-paired construction. It makes all ambiguities in the pairings impossible.

Some day I will post a comment here and be right the first time. But not today.

I somehow managed to pick an example where there's no ambiguity since it doesn't matter which one you "unwrap" to get the second value. A better example would be the set containing one and two. It could be either the pair (2,0) or the pair (1, 1).

Yup, I'm wrong. But there are other ways to set up ordered pairs...

By Canuckistani (not verified) on 24 May 2007 #permalink

Think of a thick old book that could have been so much better with ordered pairs as we know them.

By Pete Dunkelberg (not verified) on 25 May 2007 #permalink

I wrote about the problems with this definition of Pair / Tuple in an artical titled "The Trouble with Triples (and other Tuples)" back in 2003 on my blog Gregor's World.

This definition of "pair" can work in certain cases, but you are left with a construct that has some unsatisfying characteristics. For example, for a set X: is it a pair? a triple? an n-tuple? Not a tuple at all? You can't really tell for sure. If you assume it is an n-tuple, can you tell what n is? No, you cannot. If you had a set of tuples, some of them 2-tuples, and some of them 3-tuples, could you separate them into two sets, one with only the 2-tuples, and one with only the 3-tuples? No, you can't do that, either.

This calls into question whether we should be trying to model a temporal structure (tuple) with an atemporal one (set), or the other way around...

Minor point: (a,b) = {a,{a,b}} does work, if you also assume Foundation. Here (a,b) has two elements u and v, where u is an element of v (and by Foundation, v is not an element of u). Then a = u and b is the other element of v. It's {a,{b}} which necessarily breaks.

By Chad Groft (not verified) on 30 May 2007 #permalink