29
$\begingroup$

I've seen this Kuratowski definition for ordered pairs, but can't fathom why it implies an order to $x$ and $y$

$(x,y):=\{\{x\}, \{x,y\}\}$

As I understand sets, $\{\{x\}, \{x,y\}\}$ is also $\{\{x,y\}, \{x\}\}$. Only when I think about the Axiom of Union does $\{\{x\}, \{x,y\}\}$ "collapse down" to $S = \{x, y\}$, but that doesn't give me much either. All I can see is some as yet hidden message in the set saying "I am the set $\{x,y\}$ and my order of $x$ first is indicated by having $\{x\}$ along for the ride."

$\endgroup$
23
  • 2
    $\begingroup$ think about ordering by set inclusion $\endgroup$ Commented May 2, 2016 at 2:27
  • 6
    $\begingroup$ The defining property of ordered pairs is the following: For all $a,b,c,d$, $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$. Kuratowski's definition has this property, so it is suitable for all our needs involving ordered pairs. The word "order" is used in a non-formal way here, simply because, intuitively, "$a$ comes before $b$ in $(a,b)$". $\endgroup$ Commented May 2, 2016 at 2:43
  • 2
    $\begingroup$ What's important to understand is that the Kuratowski definition is merely one of many possible encodings of ordered pairs into the language of set theory. All we need from an encoding is to be able to decode it, that is, to recover $x$ and $y$ unambiguously from it. Can you see how to do that from the set $\{\{x\},\{x,y\}\}$? Can you see why you couldn't do that from just the set $\{x,y\}$? $\endgroup$
    – user856
    Commented May 2, 2016 at 2:49
  • 2
    $\begingroup$ math.stackexchange.com/questions/62908/… $\endgroup$
    – Asaf Karagila
    Commented May 2, 2016 at 5:59
  • 3
    $\begingroup$ because $\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$ if and only if $a=c$ and $b=d$. $\endgroup$ Commented Sep 12, 2019 at 2:53

7 Answers 7

54
$\begingroup$

You said:

I can't fathom why it implies an order to $x$ and $y$

It doesn't really. The $x$ and $y$ in the ordered pair $(x, y)$ don't really have an order. Who's to say that the $x$ is first and the $y$ is second? If you read right-to-left, you'd say that the $y$ was first and the $x$ was second.

The important thing isn't which is first. The important thing is that the set we pick to represent $(x,y)$ must be different from the set that represents $(y, x)$, because these are different pairs.

As you pointed out $\{x, y\}$ is the same set as $\{y, x\}$. But let's consider the Kuratowski pairs $(x,y)$ and $(y,x)$:

$$\begin{eqnarray} (x,y) = \{\{x\},\{x,y\}\} \\ (y,x) = \{\{y\},\{x,y\}\} \end{eqnarray} $$

Hey look, they’re different sets. That's what we needed.

Kuratowski's definition was preceded by a number of others. The one by Felix Hausdorff may make you feel more comfortable:

$$\begin{eqnarray} (x,y) = \{\{x, 1\}, \{y,2\}\} \\ (y,x) = \{\{y, 1\}, \{x,2\}\} \end{eqnarray} $$

Now the order you wanted is explicit.

But it is important to realize that the $1$ and $2$ here are completely arbitrary markers! It would have worked just as well for Hausdorff to have used some different markers to indicate which component was first:

$$\begin{eqnarray} (x,y) = \{\{x, \text{potato}\},\{y,\text{banana}\}\}\\ (y,x) = \{\{y, \text{potato}\},\{x,\text{banana}\}\}\\ \end{eqnarray} $$

Now you can recognize the first component of the pair because it is associated with $\text{potato}$.

The point is that the details of the particular representation aren't important. We only care that the representation does what we need it to. For ordered pairs, we need to be able to form the pair $(x, y)$ for any $x$ and $y$; we need to be able to extract the components again, and crucially, we need $(x,y) $ to be equal to $(a, b)$ if and only if $x=a$ and $y=b$. Both Kuratowski's and Hausdorff's definitions do this, and so do many others.

Which definition we pick is not really important. What is important is that the objects we choose to represent ordered pairs must behave like ordered pairs. If we get that much, we are mathematically satisfied. The Kuratowski definition is used not because it captures some basic essence of "ordered pair"-ness, but because it does what we need it to do, which is just enough.

$\endgroup$
11
  • 1
    $\begingroup$ Great answer. I would just add that one reason Kuratowski's definition is used more IMO is that it is aesthetically pleasing and contains no extraneous notions unlike Hausdorff's. $\endgroup$
    – DRF
    Commented May 2, 2016 at 5:56
  • 2
    $\begingroup$ @DRF: And it's much easier to prove! $\endgroup$
    – user21820
    Commented May 2, 2016 at 10:16
  • $\begingroup$ "That's all we needed" -- not quite we need that $(a,b)\ne(x,y)$ whenever $a\ne x$ or $b\ne y$, not merely in the special case that $a=y$ and $b=x$. $\endgroup$ Commented May 2, 2016 at 13:13
  • $\begingroup$ Yes. I elaborated on this and gave the complete and correct statement in the next-to-last paragraph. $\endgroup$
    – MJD
    Commented May 2, 2016 at 13:34
  • 1
    $\begingroup$ @zyx Certainly, but then again that definition is definitely not aimed at computer programmers, and anywhere it's likely to be used the size of the pair (even when we assume transitive closure) will be the same as the bigger of the elements (or finite). $\endgroup$
    – DRF
    Commented May 2, 2016 at 16:42
8
$\begingroup$

Just how you define order pairs concretely is an "implementation detail". Whichever definition you adopt just has to meet a basic requirement: from $\langle x, y \rangle$, you must be able to uniquely recover each of $x$ and $y$ with (preferably simple) functions $first(z)$ and $second(z)$.

The Kuratowski construction meets this criterion.

$first((x,y)) = x$

Note that $\{x\} = \{x\} \cap \{x,y\} = \bigcap \{\{x\}, \{x,y\}\} = \bigcap z$ where $z = (x,y)$. Now, as for any set, $\bigcup\{x\} = x$. So if $z = (x,y)$ then $x = \bigcup \bigcap z$, so we can define $first$ as: $$ first(z) = \bigcup \bigcap z. $$

$second((x,y)) = y$

Taking the union gives $\{x,y\} = \{x\} \cup \{x,y\} = \bigcup \{\{x\}, \{x,y\}\} = \bigcup z$ where $z = (x,y)$. Consider $\{x,y\} \setminus \{x\}$, which in terms of $z$ is $\bigcup z \setminus \bigcap z$. It's equal to $\emptyset$ if $y = x$, and equal to $\{y\}$ otherwise. So in any case we can recover (return) $y$ by defining $$ second(z) = \begin{cases} \\ &first(z)&\quad\text{if $\bigcup z \setminus \bigcap z = \emptyset$}, \\ &\bigcup (\bigcup z \setminus \bigcap z) &\quad\text{otherwise}, \\ \end{cases}$$

These definitions meet the essential requirement: $$ z = (x, y) \iff [first(z) = x \text{ and } second(z) = y], $$ and all three functions have elementary definitions.


A fact I used repeatedly and might as well prove: $\bigcup \{x\} = x$.

For any set $A$, $\bigcup A$ is the set of all things $z$ that are members of some thing $y$ in $A$: that is, $\bigcup A = \{ z\mid (\exists y\in A)\,z\in y\}$. In "union of a family of sets" notation, $\bigcup A = \bigcup_{a\in A} a$. So $\bigcup \{x\} = \{z\mid(\exists y\in \{x\})\,z\in y\} = \{z\mid(\exists y = x)\,z\in y\} = \{z\mid z\in x\} = x$.

$\endgroup$
4
  • $\begingroup$ Isn't $\bigcup A = A$, i.e, $\bigcup \{x\}=\{x\}\neq x$? $\endgroup$ Commented May 2, 2016 at 4:38
  • $\begingroup$ @YoTengoUnLCD No, it's not. I added the details to the end of the answer. $\endgroup$
    – BrianO
    Commented May 2, 2016 at 5:48
  • $\begingroup$ Being able to make a working $first(x,y)$ and $second(x,y)$ sounds like a proposition $P$ as I've seen propositions used in abstract algebra. I guess I have to wrap my head around making a $first$ and $second$ function that, indeed, takes Kuratowski as he defined it and remains consistent. It's a bit like building a skyscraper from the top floor down. It now seems like K had these $first$ and $second$ functions in his head to start with, i.e., his method wasn't out of thin air, right? And yet I knew Axiom of Union might have something to do with this -- so I'm not totally dense! $\endgroup$
    – 147pm
    Commented May 3, 2016 at 2:58
  • $\begingroup$ The essential intuition is as @AndresCaicedo said in a comment to your question: an $n$-tuple $(x_1, x_2, ... x_n)$ is represented by the set of $n$ increasing subsets $\{x_1\}, \{x_1, x_2\}, ... \{x_1, x_2 ... x_n\}$. These are linearly ordered by $\subseteq$. If you take their intersection you get $\{x_1\}$, etc. In the general case you'd define the projection functions by recursion, but think about how you would construct $first$, $second$ and $third$ in the case of $n = 3$. $\endgroup$
    – BrianO
    Commented May 3, 2016 at 23:02
5
$\begingroup$

The point of the ordered is for it to satisfy the following property: $$(a,b) = (c,d) \text{ if and only if }a=c\text{ and }b=d.$$ The definition given satisfies that condition; it doesn’t matter how it satisfies it, just that it does.

It is true that $(a,b)$ is both $\{ \{a\},\{a,b\}\}$ and $\{\{a\}, \{b,a\}\}$ and $\{\{a,b\},\{a\}\}$ and $\{\{b,a\},\{a\}\}$. It doesn’t matter: they are all the same set and they all “are” $(a,b)$. The point is that $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$.

To verify that this happens, note that if $a=c$ and $b=d$, then $$(a,b) = \{\{a\},\{a,b\}\} = \{\{c\},\{c,d\}\} = (c,d).$$

Conversely, suppose that $(a,b)=(c,d)$. That means that the sets $\{\{a\},\{a,b\}\}$ and $\{\{c\},\{c,d\}\}$ are equal as sets.

To verify that this implies that $a=c$ and $b=d$, consider two cases:

Case 1. $a=b$. Then $(a,b) = \{ \{a\},\{a,b\}\} = \{\{a\},\{a,a\}\} = \{ \{a\}\}$.

As this is equal to $\{\{c\},\{c,d\}\}$, then $\{c\}\in\{\{a\}\}$, which means $\{c\}=\{a\}$, which means $c=a$. And $\{c,d\}\in\{\{a\}\}$, so $\{c,d\} = \{a\}$, hence $d=a=b$. Thus, $a=c$, and $b=d$ in this case.

Case 2. $a\neq b$.

Recall that is $X$ is a set, whose elements are sets, then $$\begin{align*} \cup X &= \bigcup_{S\in X}S\\ \cap X &= \{s\in\cup X\mid s\in S\text{ for all }S\in X\}. \end{align*}$$

If $(a,b) = (c,d)$, then, as sets, $\cap (a,b) = \cap (c,d)$. We have $$\begin{align*} \cap (a,b) &= \cap\{ \{a\},\{a,b\}\}\\ &= \{a\}\cap\{a,b\} = \{a\}\\ \cap (c,d) &= \cap \{ \{c\},\{c,d\}\}\\ &= \{c\}\cap\{c,d\} = \{c\}. \end{align*}$$ Therefore, $\{a\}=\{c\}$, so $a=c$.

And $\cup (a,b) - \cap (a,b)$ must be equal to $\cup(c,d)-\cap(c,d)$, so $$\begin{align*} \cup(a,b)-\cap(a,b) &= \cup\{ \{a\},\{a,b\}\} - \{a\}\\ &= (\{a\}\cup\{a,b\})- \{a\}\\ &= \{a,b\} - \{a\} = \{b\};\\ \cup(c,d)-\cap(c,d) &= \cup\{ \{c\}, \{c,d\}\} - \{c\}\\ &= (\{c\}\cup\{c,d\})-\{c\} = \{c,d\}-\{c\} = \{d\}, \end{align*}$$ so we must have $\{b\}=\{d\}$, and therefore $b=d$.

In both cases, if $(a,b)=(c,d)$, as sets, then $a=c$ and $b=d$.

Which is what we want from an ordered pair. So now that we know this definition will guarantee this, we can safely forget about it in general and just use the “defining property” of the ordered pair: $(a,b) = (c,d)$ if and only if $a=c$ and $b=d$.

$\endgroup$
9
  • $\begingroup$ Isn't $\{a,\{a,a\}\} = \{a, \{a\}\}$ and not $\{\{a\}\}$? $\endgroup$ Commented Sep 12, 2019 at 3:33
  • $\begingroup$ @CharlesHudgins : Yes... so what? The ordered pair $(a,a)$ is $\{\{a\},\{a,a\}\}$, not $\{a,\{a,a\}\}$. $\endgroup$ Commented Sep 12, 2019 at 3:35
  • $\begingroup$ I assume you're referring to Case 1; note that in case 1, the left-hand set you've written never appears. $\endgroup$ Commented Sep 12, 2019 at 3:35
  • $\begingroup$ Oh, apologies. I'm used to a different (wrong?) definition of $(a,b)$ as $\{a, \{a,b\}\}$. I just completely missed the difference. Using your definition, what you've written seems right. $\endgroup$ Commented Sep 12, 2019 at 3:37
  • $\begingroup$ What is the point of the Kuratowski definition? The regular or standard definition is $(a,b) = (c,d) \text{ if and only if }a=c\text{ and }b=d$, it seems much simpler. Is there something vague or bad about the standard definition. Are we trying to reduce everything to sets, to the point of sometimes unnecessary complexity. $\endgroup$
    – john
    Commented Feb 23, 2022 at 23:07
2
$\begingroup$

Say you have the ordered pairs $(x,y),(a,b)$, i.e, $\{\{x\},\{x,y\}\}$, idem for the other.

What do you do if I ask them if they're equal? You test equality as sets. It turns out that they're equal iff $x=a$ and $y=b$ (why?).

$\endgroup$
0
$\begingroup$

We define $(x, y)$ as $\{\{x\}, \{x, y\}\}$. This absolutely implies an order: the first element of the ordered pair is the one that appears on its own in a singleton. $(y, x)$ would be $\{\{y\}, \{x, y\}\}$.

Take $\{\{5\}, \{3, 5\}\}$, for example. Is that $(5, 3)$ or $(3, 5)$? The correct answer is completely unambiguous.

$\endgroup$
0
$\begingroup$

We have that $$(a,b)=\{ \{a\},\{a,b\}\}$$ and that $$(b,a)=\{ \{b\},\{b,a\}\}=\{ \{b\},\{a,b\}\}$$ The two sets differ by a single element, namely $\{a\}$ and $\{b\}$.

$\endgroup$
13
  • $\begingroup$ ... if $a\neq b$. Otherwise, both are equal to $\{\{a\}\}$. $\endgroup$ Commented Sep 12, 2019 at 3:07
  • $\begingroup$ This is actually something I've long wondered about set theory. Do we identify $\{a,a\}$ with $\{a\}$? Is $\{a,a\}$ even a legal set? $\endgroup$ Commented Sep 12, 2019 at 3:14
  • $\begingroup$ @CharlesHudgins Set cannot have duplicates because each element is distinct On the same note they are unordered. Problem is these definitions are not in one place and you need many texts etc. $\endgroup$ Commented Sep 12, 2019 at 3:17
  • 3
    $\begingroup$ @NewStudent: That’s not accurate. Sets are determined by their elements. The Axiom of Extensionality says that $A=B$ if and only if for every $x$, $x\in A\iff x\in B$. So the set $\{a,a\}$ is a perfectly “legal” set, and is equal to the set $\{a\}$ and to the set $\{a,a,a,a,a,a,a,a\}$, etc., because of the Axiom of Extensionality. It’s the same reason why $\{a,b\}$ is the same set as $\{b,a\}$ is the same set as $\{a,b,a\}$ is the same set as $\{b,b,b,b,a,a,a,b,a,b,a,b,a,b\}$, etc. $\endgroup$ Commented Sep 12, 2019 at 3:30
  • 1
    $\begingroup$ I'm not sure if logicians like it or not, but Halmos' Naive Set Theory is a pretty nice introduction for those of us who just want enough set theory to get on with other parts of mathematics. $\endgroup$ Commented Sep 12, 2019 at 3:34
0
$\begingroup$

The order in sets usually has no impact. {a,b} = {b,a}

But the number of members in a set DOES have an impact. {a,b} $\neq$ {a,b,c}

The reason they are not equal is because {a,b} contains 2 members, while {a,b,c} contains 3 members. And if two sets have a different number of members then they are not equivalent to each other. They are different sets.

Kurtovsky uses this fact in an ingenious way. First he takes the ordered pair and puts it in a set which has two members. But, as opposed to the ordered pair, each of these members is a set in itself. Lets call them member-set-1 and member-set-2.

(a,b) = { member-set-1, member-set-2 }

Of course this in itself is no good. Because in set theory {a,b} = {b,a}. But watch closely:

Next he brings the members of the ordered set into his groups.

member-set-1 = {a}

This means that the first member of the Kurtovsky Pair Set contains the first member of the paired couple: $a$ in it. And only the first member. (The "Abscissa").

Inside the second member of the Kurtovsky Pair Set he brings BOTH members of the paired couple, both $a$ and $b$!

member-set-2 = {a,b}

Notice that $a$ - the "abscissa" - is in both the first and second members of the Kurtovsky Pair Set, but $b$ - the "ordinate" is only in the second member.

Now we'll see how Kurtovsky forced the mathematical notation to be used "against itself" so that any (x,y) where x is different from y, is not equal to (y,x).

According to the formula: (x,y) = { {x}, {x,y} } we have x twice and y once in the set. Right?

But according to the formula: (y,x) = { {y}, {y,x} } now we have y twice and x only once. Clearly NOT the same as (x,y).

Looking at it another way: (x,y) = { {x}... etc.

Meaning there is a set with x and only x in it.

While (y,x) = { {y}... etc. Here there is no set with x and only x in it. So clearly the two sets are different.

Nice.

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .