Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been struggling understanding Kuratowski's definition of ordered pairs. I understand what it means but I don't see why I should accept it. I've seen this question and this one, most importantly --- through reading the wiki page I've realised one thing.

The only reason $(a,b)=\{\{a\},\{a,b\}\}$ is accepted is because it satisfies

$(a,b)=(c,d) \iff (a=c) \land (b=d)$

Am I not misunderstanding this? If I can come with my own exotic definition which satisfies the above iff statement, would it be accepted?

share|improve this question
2  
What definition would you prefer? –  mrf Feb 19 '13 at 20:49
12  
Or why would you not accept it? –  Mariano Suárez-Alvarez Feb 19 '13 at 20:49
2  
I'm not disputing it (don't misunderstand me), I'm just confused as it is not "natural". I'm just wondering whether is it universally accepted because it only statifies $(a,b)=(c,d) \iff (a=c) \land (b=d)$ –  Adeeb Feb 19 '13 at 20:54
11  
If you find it unnatural, then perhaps knowing Kuratowski's motivation may help: He wanted to code an order: $a$ comes first, then $b$, "$a<b$". A simple way of coding a linear ordering is by listing its initial segments. In this case, this is $\emptyset,\{a\},\{a,b\}$. Since we always know that $\emptyset$ is there, we do not need it, so the list is simply $\{a\},\{a,b\}$. The set of these initial segments is the ordered pair. –  Andres Caicedo Feb 19 '13 at 23:25
2  
You asked “If I can come with my own exotic definition which satisfies the above iff statement, would it be accepted?” I thought you might be interested to know that the first set-theoretic definition of the ordered pair, before Kuratowski's, was Norbert Wiener's: $\langle a,b\rangle = \{\{\{a\},\emptyset\},\{\{b\}\}\}$. –  MJD Apr 8 at 13:35
show 6 more comments

8 Answers

up vote 28 down vote accepted

We accept this definition because it works, and it works very well.

However do note that almost nobody cares about the actual encoding of ordered pairs, and in most cases set theorists don't really care either. You just want a definition which satisfies the property which you have quoted.

I can't recall any substantial proof in set theory which actually refer to this definition of ordered pairs. Instead we just use the fact that there is some $\varphi(x,y,z)$ which is true if and only if $z$ represents the ordered pair $(x,y)$. Had I chose a different encoding, the proof would stay the same.

So why do we use it? Well, it tells us that set theory is strong enough to support an internal definition of ordered pairs which is another "thumbs up" in its favor as a foundational theory. But also we use it because it was there when we needed such definition, and once you have a working machine you don't really bother replacing the cogs which work perfectly.

Note that on its own, the object of an ordered pair is very uninteresting. So we don't really bother with finding a "better" definition, because nobody really cares about how you encode. We just want to know that it exists within our mathematical universe, and if our mathematical universe is based on set theory (in one way or another) then we want to know that we don't need an extra type in the world in order to have ordered pairs.

share|improve this answer
    
Well, if you make some assertions about truncating the universe at some small rank or something silly like that, it might be important what kind of pairing function you use... (There's a comment in Hodges's Model theory about someone using definitions which made Lemma 4.3.1 false.) –  Zhen Lin Feb 20 '13 at 0:11
    
Zhen Lin, of course there is some importance, but you can't argue that truncating the universe is an argument here. If you truncate the universe it need not be a model of ZFC anymore, and no reason to think it would have the same proofs. Similarly for any other theory, and of course that the whole point of the Kuratowski definition is that we have an internally definable way to do this. So even if you truncate the universe, and the result is a universe then you're in the clear. But of course I'm not saying that arbitrary truncating can't affect the choice of encoding, that's just wrong. –  Asaf Karagila Feb 20 '13 at 0:39
    
(Because I always say stuff like this) The only theory I know of where choice of ordered pair matters is NF, where different choices of ordered pair affect several theorems about the ordinals, or make NF turn out not to be a category. In that setting there's a very clear choice for why to accept Quine (type-level) pairs over Kuratowski's, but naturalness is not it. –  Malice Vidrine Apr 8 at 10:07
add comment

Apart from the one you quote, the second property about ordered pairs that is needed for development of set theory is that $$ A\times B = \{ x \mid \exists a\in A, b\in B: x = (a,b) \} $$ must be a set whenever $A$ and $B$ are. Kuratowski pairs makes this easy to prove because $A\times B$ is a subset of the power set of the power set of $A \cup B$.

One might imagine other definitions of ordered pairs where one needed to appeal to the Axiom of Replacement in order to prove that $A\times B$ always exists. Being able to do it with the Power Set and Subsets alone can be seen as somewhat tidier.

share|improve this answer
add comment

It doesn't matter what definition of ordered pair you use: {{a},{a,b}} is fine.. {{0,a},{1,b}} is fine

What's really important is that the category of sets has products and the universal property of a product that gives us the ability of pair and unpair and gives the equality relation you stated.

share|improve this answer
add comment

Alternatively, you might enhance the language of set theory to include the notion of ordered pairs and add a few axioms accordingly. But then you'd have all kinds of mixed objects: Sets with pairs of a set and a pair of sets and whatnot as elements producing the weirdest combinations in the results of e.g. taking powersets or unions. This includes the necessity to treat pairs as urelements but of a "non-atomic" nature. All in all the theory might become a lot more wound-up without any real gain. Kuratowski allows us to both work with ordered pairs and work in a world where everything is a set. While "custom-types" makes the everiday mathematical work easier, the set-theoretical "monoculture" makes the foundation comfortably more trust-worthy.

All we need about Kuratowski's definition is indeed the fundamental property of ordered pairs as you mention it. The same applies for other constructions that can be performed with set theory: All we usually need about $\mathbb N$ is that it obeys the Peano axioms. Where applicable, we may work with $\mathbb N$ as a given set with opaque elements $0,1,2,\ldots$ and there is no need to accept definitions like $0:=\emptyset, 1:=\{\emptyset\}, 2:=\{\emptyset,\{\emptyset\}\}, \ldots, Sn:=\{n\}\cup n$ that put this on set-theoretic grounds. Just as with pairs, there are alternatives (such as $Sn:=\{n\}$). It may not be of practical use, but is comforting that a set that models the Peano axioms can be constructed easily and need not be added explictly to the theory.

The further constructions of $\mathbb Z, \mathbb Q, \mathbb R, \mathbb C$ may be used as further examples: We don't work with (Kuratowski) pairs of sets of equivalence classes of pairs of equivalence classes of pairs of finite ordinals when computing zeroes of the Riemann zeta function, rather we work with facts like that $\mathbb C$ is an algebraically closed field and do as if e.g. complex numbers are just objects of a new type. And again there are differnt choices that don't make a difference in the end (real numbers as Dedekind cuts or as equivalence classes of Cauchy ssequences?). A need to look under the hood of all constructions involved may arise when we want to communicate unambiguously what we talk about ("Why is $0.\bar9=1$?", though that could be done with the axioms the constructions model) and want to face doubts about the "existence" of the subject matter ("Why can we talk about the set of all Lebesgue integrable functions but not about the set of all sets?").

share|improve this answer
    
A comparison with programming help: set theory definitions are like "machine code", necessary (but evil!), you dont want to use machine code if you dont must. Usual mathematical, higher-level language is like object-oriented programming. Much better! –  kjetil b halvorsen Apr 8 at 9:35
add comment

Why Set theory without the axiom of foundation? is an article explaining an alternative implementation of ordered pairs, apparently due to Quine. It's much less obvious than the Kuratowski definition, but has the added benefit that $x = \langle z, x \rangle$ can be true without contradicting the standard Axiom of Foundation (the linked paper goes into more detail as to why and how you'd do that).

To describe the construction, I'll need some notation: $s$ is the function that takes a finite von Neumann ordinal (i.e. a member of $\omega$) and adds 1 to it, leaving everything else untouched, $z(x) = x \cup \{0\}$, and if $f$ is a function then $f“x$ is the set $\{ f(y) : y \in x \}$.

Then $s“x$ and $s“y$ are sets from which we can easily recover $x$ and $y$, and which don't contain $0$.

Now, the punchline: $\langle x, y \rangle = s“x \cup z“(s“y)$.

$s“x$ is recoverable as $\{z \in \langle x, y \rangle : 0 \not\in z\}$;

$s“y$ is $\{z \setminus \{0 \}: z \in \langle x, y \rangle, 0 \in z \}$.

This defines projections $\pi_1$ and $\pi_2$ onto the first and second components respectively, so $\langle a,b \rangle = \langle c,d \rangle \implies a = c \wedge b = d$. You can check that $x \mapsto \langle \pi_1(x), \pi_2(x) \rangle$ is the identity, so that the converse holds.

share|improve this answer
    
You should say what $s$ does to sets that are not finite ordinals. –  Zhen Lin Feb 20 '13 at 0:09
    
Done!${}{}{}{}{}$ –  Ben Millwood Feb 20 '13 at 20:37
add comment

We all agree about the "arbitrary" nature of Kuratowski's definition, and about the possibility of replacing it with other "conventions" (equally arbitrary), provided that they satisfy the basic properties (already discussed).

But please, note that the lack of a mathematical definition of ordered couple forced two of the "founding fathers" of modern mathematical logic to "waste" hundreds of pages (full of formulae) of their masterpiece (see Alfred North Whitehead & Bertrand Russell, Principia Mathematica Vol I (1910) : SECTION C: CLASSES AND RELATIONS, strating from :§20. GENERAL THEORY OF CLASSES [page 196-on] and §21. GENERAL THEORY OF RELATIONS [page 212-on]) in order to "duplicate" all the basic result stated in terms of propositional functions of one variables

$\psi(x)$

"representing" classes,

also for propositional functions of two variables

$\psi(x, y)$,

"representing" (dyadic) relations.

Thus, all we "mathematical students" must every night address a little prayer for the benefit of Kuratowski's soul ...

share|improve this answer
add comment

You understand mostly correctly. What you seem to be missing is

  • why we even bother with a definition,
  • that we might not even stick to a single definition.

The reason we bother with a definition is so that we only have to develop "set theory", rather than having to develop "set and ordered pair theory".

The reason we might not want to stick to a single definition is that other definitions can have useful properties in various cases. Examples include

  • It is often useful to consider an ordered pair to be a function with domain $\{0, 1\}$; especially in the context of working with $n$-tuples.
  • Certain domains can have specific interesting encodings; e.g. in number theory, it is sometimes useful to consider elements of $\mathbb{Z}/(pq)$ (i.e. the integers modulo $pq$) to be ordered pairs whose first component is an element of $\mathbb{Z}/p$ and whose second component is an element of $\mathbb{Z}/q$.
share|improve this answer
add comment

This answer is very late, and I think others have answered quite adequately, but I do have some thoughts on this.

As others have pointed out, no one really cares what ordered pairs are, only what they do. You can imagine that a book on axiomatic set theory might include the following text:

"PROPOSITION. Given sets A and B, there exists a set A×B and two functions p₁ : A×B → A and p₂ : A×B → B such that, for any elements a ∈ A and b ∈ B, there is a unique element (a,b) ∈ A×B with p₁(a,b) = a and p₂(a,b) = b. (This set is a product of A and B, its elements are ordered pairs, and the functions are projections.)

"PROOF. Given a ∈ A and b ∈ B, let (a,b) := {{a},{a,b}}, where a ∈ A and b ∈ B; then ..."

Having proven this proposition, the author might later say, "Consider the subset of A×B given by...". But he probably wouldn't refer back to the proof, and in particular not to its use of the Kuratowski definition. All the important properties of ordered pairs are contained in the proposition itself.

What you might then ask is, "Why define ordered pairs as sets at all, rather than taking them as primitive?" The answer is that we simply have no need to do so. From an external perspective, every theorem of ZFC is actually a theorem about models of ZFC, saying in effect "Any structure that satisfies the axioms of ZFC must also satisfy this property." From this perspective, adding unnecessary axioms is equivalent to adding unnecessary hypotheses to a theorem: unaesthetic and possibly misleading.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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