19
$\begingroup$

Among several possible definitions of ordered pairs - see below - I find Kuratowski's the least compelling: its membership graph (2) has one node more than necessary (compared to (1)), it is not as "symmetric" as possible (compared to (3) and (4)), and it is not as "intuitive" as (4) - which captures the intuition, that an ordered pair has a first and a second element.

alt text(source)

Membership graphs for possible definitions of ordered pairs (≙ top node, arrow heads omitted)

1: (x,y) := {   x   , {   x   ,   y } }
2: (x,y) := { { x } , {   x   ,   y } } (Kuratowski's definition)
3: (x,y) := { { x } , { { x } ,   y } }
4: (x,y) := { { x , 0 }  ,  { 1 , y } } (Hausdorff's definition)

So my question is:

Are there good reasons to choose Kuratowski's definition (or did Kuratowski himself give any) instead of one of the more "elegant" - sparing, symmetric, or intuitive - alternatives?

$\endgroup$
9
  • $\begingroup$ My hypothesis would be that in case of non-Kuratowski definitions one would have some more technical dificulties in development of ordinal arithmetic in ZFC. $\endgroup$
    – SNd
    Apr 23, 2011 at 23:30
  • 2
    $\begingroup$ What is 1 in 4.? $\endgroup$
    – user9072
    Apr 24, 2011 at 0:51
  • $\begingroup$ @unknown (google): I think the idea in option 4 is that the constants 0 and 1 are fixed and chosen ahead of time --- certainly it doesn't matter up to isomorphism what they are, so set them to be some physical objects, if you like. $\endgroup$ Apr 24, 2011 at 2:46
  • 4
    $\begingroup$ An obvious remark: the aim of these definitions is not to capture the essence of "ordered pair", but just to bring this notion into the language of set theory (in the same spirit of von Neumann's definition of ordinal numbers, for instance). So it really doesn't matter which one we choose. $\endgroup$ Apr 24, 2011 at 6:15
  • 4
    $\begingroup$ Sorry: 0 is {}, and 1 is {0} = {{}}. $\endgroup$ Apr 24, 2011 at 8:34

3 Answers 3

48
$\begingroup$

Kuratowski's definition arose naturally out of Kuratowski's idea for representing any linear order of a set $S$ in terms of just sets, not ordered pairs. The idea was that a linear ordering of $S$ can be represented by the set of initial segments of $S$. Here "initial segment" means a nonempty subset of $S$ closed under predecessors in the ordering. When applied to the special case of two-element sets $S$, this gives the Kuratowski ordered pair.

$\endgroup$
24
$\begingroup$

Of course there are many pairing functions, and they all have the crucial property that from the pair $(x,y)$, one can reconstruct both $x$ and $y$. And although your question has been answered, let me point out that all four of the ordered pair definitions that you consider have the property that the von Neumann rank of the pair $(x,y)$ is strictly greater than the ranks of $x$ and $y$. Thus, for your functions, if $x$ and $y$ are in $V_\alpha$, then the pair $(x,y)$ can only be guaranteed to appear by $V_{\alpha+2}$.

But actually, this rank-increasing feature is sometimes annoying, and there occasionally arises in set-theoretic argument the need or desire for a flat pairing function, a pairing function that does not increase rank in this way. Specifically, what is desired is a pairing function $\langle x,y\rangle$ such that whenever $x,y\in V_\alpha$ for infinite $\alpha$, then also $\langle x,y\rangle\in V_\alpha$, for the same rank $\alpha$. (Note that one cannot achieve this for finite $\alpha\gt 1$, since there are too many pairs to fit.) With such a flat pairing function, every infinite $V_\alpha$ is closed under pairing, and this is sometimes important or at least convenient in inductive arguments, or in arguments about $\alpha$-strong cardinals and in similar situations, where one wants to consider only sets of a given rank, but one also wants to use pairs.

It is a fun exercise to prove that flat pairing functions exist, and I encourage you to try it on your own, before reading what I write below. But the definitions are all somewhat more involved than the comparatively simple definitions you provide, since they achieve the flatness property. As Hurkyl says, we ultimately care only about the existence of the function with the desired properties, rather than its exact nature.

Here is one way to construct a flat pairing function. Define $\langle x,y\rangle=x^0\cup y^1$, where $x^0$ is obtained by replacing every natural number $n$ in any element of $x$ by $n+1$ and adding the object $0$, whereas $y^1$ just replaces $n$ inside elements of $y$ with $n+1$. Thus, we can tell from any element of $x^0\cup y^1$ whether it came from $x$ or $y$, by looking to see if it contains $0$ or not, and we can reconstruct the unmodified set by removing $0$ and replacing all $n+1$ with $n$ again, and so it is a pairing function. And one can check that $\langle x,y\rangle$ has the same rank as the maximum rank of $x$ and $y$, if this max is infinite, and so this is a flat pairing function, as desired.

$\endgroup$
2
  • 2
    $\begingroup$ Flat pairing functions are particularly important in type theory. For example we can regard every set of natural numbers as a code for a pair of sets, without leaving second-order arithmetic. Similarly every set of sets of natural numbers can be viewed as a code for a pair of sets of sets, without leaving third order arithmetic. I have heard flat pairing functions are also useful for non-ZF set theories such as New Foundations, although I don't know much about that area. $\endgroup$ Apr 24, 2011 at 17:59
  • 4
    $\begingroup$ This "flat" pairing function described above is what some people know as "Quine's definition" of an ordered pair. en.wikipedia.org/wiki/Ordered_pair#Quine-Rosser_definition As far as I know, this is the definition used by people working in NF and similar theories, it has the advantage that every set is an ordered pair and so the functions first(-) and second(-) (projections) are total functions instead of partial ones. $\endgroup$ Apr 4, 2012 at 14:45
20
$\begingroup$

How one models ordered pairs is not particularly important; what matters is the existence of a pairing function $(-,-)$ along with functions $\text{first}(-)$ and $\text{second}(-)$ satisfying the requisite properties.

Which definition you use only matters for a brief period between the definition and the point where its properties have been proven, at which point you promptly forget the details of the definition -- so the only real point of deliberating definitions is to make this period as painless as possible for others.

I haven't thought through all of the possibilities, but I will offer an example that $\text{first}(-)$ is tricky to define for your definition 1. The 'obvious' choice seems to be $$ z = \text{first}(P) \equiv z \in P \wedge \exists a: z \in a \in P $$ which turns out to depend on the axiom of foundation to be well-defined! (consider a $y$ satisfying $y = \{ x, y \}$) I, personally, would have more confidence in being correct if I was trying to develop the properties of ordered pairs from definitions 2 or 4, rather than from 1 or 3.

$\endgroup$
11
  • 1
    $\begingroup$ I think this answer basically hits the mark. To the OP: It's the 21st century, so why do you care how to define ordered pairs in some set theory, when there are better languages available for doing mathematics? $\endgroup$ Apr 24, 2011 at 2:26
  • 6
    $\begingroup$ Actually, definition 1 itself depends on the axiom of foundation to be a good model of ordered pairs. If x satisfies x={{x,y}, z}, then by definition 1: ({x,y}, z) = { {x,y}, { {x,y}, z } } = { {x,y}, x } = (x, y) $\endgroup$
    – user13113
    Apr 24, 2011 at 2:33
  • 5
    $\begingroup$ Theo, regarding your first comment, is it your view that it isn't necessary to define an ordered pair concept in set theory? Or are you saying that it isn't necessary or desirable to do set theory at all? $\endgroup$ Apr 24, 2011 at 11:20
  • 2
    $\begingroup$ @Theo, one appeal of set theory as a foundations is that while it's simple in the sense that it only takes membership as primitive, thus allowing for a cleaner analysis of the foundations, it's expressive power is such that it can interpret most of mathematics, thus for the mathematician who wants to take "ordered pair" as a primitive notion, he or she can do so without raising new foundational questions. Are you suggesting a language that doesn't take membership as primitive? If so, how would you address concerns that membership ought to be a primitive notion? (continued) $\endgroup$ Apr 24, 2011 at 17:50
  • 1
    $\begingroup$ Or are you suggesting a language that takes additional things as primitive? If so, is the payoff in additional expressive power enough to make up for the loss of simplicity? Maybe these questions are too broad for a comment thread, but what the heck. $\endgroup$ Apr 24, 2011 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.