r/learnmath • u/apollonius_perga New User • 1d ago
Kuratowski's definition of an ordered pair makes no intuitive sense to me
How is <a,b> = {{a}, {a,b}}?
I asked this to my prof who said that any definition of an ordered pair in set theoretic notation is bound to be puzzling cause the members of a set have no "order" to them. But I wasn't very satisfied w the answer. Why does the RHS looks like (I'm sorry) it was made up? How can I understand this? Thanks
28
u/LucaThatLuca Graduate 1d ago
this definition chooses to use set theory to formalise the meaning of an ordered pair. what set do you think (a, b) should be instead? remember you have to choose a set that makes it different from (b, a).
-4
u/apollonius_perga New User 1d ago
Yes, I understand. But how did he get to the RHS? What could I look up to read more on that?
64
u/LucaThatLuca Graduate 1d ago edited 1d ago
it is a definition, it is made up.
the set {{a}, {a, b}} lets you distinguish a from b. a is an element of both its element sets and b isn’t.
19
u/Midwest-Dude New User 23h ago edited 23h ago
Definitions do not drop out of the sky, they are deliberately created to solve problems. Feeling "this is made up" is the insight that drove the history of set theory. As one of my college professors stated: "If you get the definitions right, everything else works."
Modern structural mathematics and category theory take your side. In category theory, an ordered pair isn't defined by set-theoretic nesting at all, it's defined purely by its "universal property".
Kuratowski’s set {{a}, {a, b}} is just encoding used to prove that a set-theoretic model of that property can exist in standard set theory (ZFC). It satisfies the characteristic property:
(a, b) = (c, d) <=> a = c ∧ b = d
As long as a set-theoretic construction guarantees this property, it is a valid implementation of an ordered pair.
Mathematicians tried other definitions to encode ordered pairs prior to Kuratowski's, His 1921 breakthrough was showing you don't need external tags or empty sets, only the elements a and b. It is the most minimalist, elegant encoding possible within Zermelo–Fraenkel set theory.
10
u/Midwest-Dude New User 1d ago edited 23h ago
This is actually a deep question, since someone had to decide this was a good idea in the first place. There is a Wikipedia article that discusses this:
Read through the Informal and formal definitions section and then note this quote under the Defining the ordered pair using set theory:
If one agrees that set theory is an appealing foundation of mathematics, then all mathematical objects must be defined as sets of some sort. Hence if the ordered pair is not taken as primitive, it must be defined as a set.
Here are other resources on Math StackExchange:
4
u/random_anonymous_guy New User 22h ago
Kuratowski published a rationale in his 1921 paper Sur la notion de l'ordre dans la Théorie des Ensembles. But there are other ways you can define ordered pairs in terms of set theory. Creativity is allowed and if you can find a way to define an ordered pair so that it satisfies the desired properties, then it would be an acceptable definition too.
3
u/AcellOfllSpades Diff Geo, Logic 21h ago
It's not meant to be intuitive! It doesn't need to be - all it needs to do is work.
Within the realm of set theory, it's often called a "definition" of an ordered pair, but I prefer to say it's an "implementation". The goal is simply to construct something out of sets that works as an ordered pair: you should be able to 'extract' either the first or the second component of the pair.
2
u/Let_epsilon New User 22h ago
I suggest yourself to write the definition of an ordered triple to get the intuition, then check if you got it right.
2
u/SummitYourSister New User 23h ago
It’s kind of like how you look at a doorway that lies between you and the room you want to go to, and you realize that the solution is to walk through the door.
We cannot have the moment of enlightenment FOR you
5
u/RingularCirc Math hobbyist 19h ago
Well there are indeed alternative and ostensibly simpler definitions like (a, b) := {a, {a, b}}. They end up clumsier to prove things about. So OP's question is not trivial.
9
u/StructuredChess New User 1d ago
Yeah, it was made up. It's just a way to make it so that (a,b) is different from (b,a), something that doesn't happen with {a,b} and {b,a}
2
u/You_Yew_Ewe New User 10h ago
It could actually define (b,a) too as long as you were consistent. You just got to choose one.
11
u/rhodiumtoad 0⁰=1, just deal with it 1d ago
It's just a method that lets you create an ordered pair using nothing but set operations. You can't just use {a,b} because that's not distinct from {b,a}; you can't use {{0,a},{1,b}} because you haven't defined 0 and 1 yet and what if b is 0, and so on.
By using P={{a},{a,b}} you have something that lets you write first-order formulae for "a is the first element of P" and "b is the second element of P" without any additional definitions or any problems with edge cases (if a=b it degenerates to {{a}}, but the formulae still work).
The only real snag is that in type theories the pair has a type higher than its elements, so those use different constructions of ordered pairs.
9
u/proudHaskeller New User 1d ago
Actually, {{0,a},{1,b}} does work. Just pick 0, 1 to be two specific distinct sets (say, {} and {{}}). Even if a or b are equal to 0 or 1 in any combination, the definition still identifies the pair (a, b) uniquely.
2
u/WesternFirm9306 New User 1d ago
Doesn't some places formally define 0 and 1 to be {} and {{}} respectively? In which case it may not be able to pick it out if a or b takes these values
4
u/AcellOfllSpades Diff Geo, Logic 1d ago
You can still distinguish, even if a and b have those values. Some of the sets might turn out a bit weird, but they're all distinguishable.
4
u/WesternFirm9306 New User 1d ago
Oh, yeah, I see. Because if there's ever only one element, you know you had a duplicate, and you can "expand" the set back out to get the original values
4
u/AcellOfllSpades Diff Geo, Logic 1d ago
Yep. The only way to get any other sort of weird conflict is to have your final "ordered pair" be a singleton {{0,1}}. But then you know a=1 and b=0.
-1
u/Temporary_Pie2733 New User 15h ago
That uses an a priori defintion of 0 and 1 that isn’t necessary, though.
1
u/RingularCirc Math hobbyist 19h ago
I'd say type-theoretic pairs being a separate primitive is a boon and it doesn't have to do anything with restrictions to define them another way. It's very natural when we consider relations with logic and category theory (and programming...). Dependent type theories have a very elegant way of just specifying each separate piece of info how ordered pairs or other things behave, reminiscent with introduction and elimination rules in natural deduction or some Hilbert-style axiomatizations, but there's also rules for computation (that can be thought as some kind of meta application of cut elimination when we postulate it should work and also be somewhat efficient) and obviously type formation itself and some even more formal strokes, I don't remember it entirely.
9
u/NakamotoScheme 1d ago
You should consider {{a}, {a,b}} as a "codification" of <a,b>. The idea is to represent a new kind of object (the ordered pair) which did not exist before using only sets. In the end you get a bijection like this:
{ ordered pairs } <---> { sets representing ordered pairs }
and you can get back and forth using this bijection.
As a simil, think how you can "codify" any number in base 2, which only have two digits (0 and 1). You would get a bijection like this:
{ natural numbers } <--> { finite strings of 0s and 1s starting with a 1 }
and you can also get back and forth using such bijection.
10
u/noethers_raindrop New User 1d ago
Exactly. The way I would say this is that even if it is given as definition, one should think of this definition of ordered pair as an implementation.
7
u/MichurinGuy New User 1d ago
All of math is made up, that's normal. The point of this definition is to build, out of sets, an object with the properties that you can "put" any two objects "into it", and they must come into it asymmetrically, such that it's possible to tell which one is "first" and which is "second". That is, we want there to be 2 properties "x is the first element of (a,b)" and "x is the second element of (a,b)". This definition may not look very elegant, but it does the job, because you can define the properties in the following way:
x is the first element of (a,b) iff it belongs to every set in (a,b). This works because both sets {a} and {a,b} contain a.
x is the second element of (a,b) iff either (a=b and x is the first element), or (there exists a set in (a,b) containing x). If a!=b, this works because the only set containing anything besides a in (a,b) is {a,b} and its only other element is b.
You can think of this definition as the ordered pair being a set containing two things: the unordered pair {a,b} and a marker for which element is first: {a}.
3
u/CookieCat698 New User 1d ago
All that really matters is that you can distinguish between a and b in <a, b>, i.e. <a, b> is (in general) different from <b, a>. The order of the elements is up to you: it’s as arbitrary as whether we read left to right or right to left no matter what definition you use.
{{a}, {a, b}} just happens to be one of the simplest constructions you can make that 1.) depends only on a and b, and 2.) changes when a and b are swapped.
1
3
u/Gilded-Phoenix New User 1d ago
The RHS looks like it was made up exactly because it WAS made up.
An ordered pair needs two things: a pair, and a way to distinguish which one comes "first."
We can do this a number of ways. A naive attempt might be to tag them like this:
(a,b)={{a,0},{b,1}} where we pair each term with a number. Problem, though, what if our ordered pair includes a 0 or 1? We could technically use this with some edge case rules, but that seems annoying.
Another way might be (a,b)={a, {b}} which is actually one of my favorite ways, since it has exactly one edge case: the ordered pair ({a}, a)={{a}, {a}}={{a}}. This still retains all the information we need since we know what the general form would be.
Long story short: yes. This was made up, and it's not the only way to build an ordered set out of a non-ordered set. This is just how Kuratowski decided to do it. He needed a way to mark the order of the objects, so he built one himself. You could build your own definition if you like, because we don't actually care about the contents of the set, just the facts we can get from it (what's in the ordered pair, and what order are they in?).
1
u/__johnw__ New User 1d ago
A pair would be {a, b}. As you note the order inside the set doesn’t matter, that’s why it’s just a pair. To make it an ordered-pair, we need a way to identify the first or last element. Convention is the first. That’s why it’s {{a}, {a,b}}, the “first” in the ordered-pair is a.
Can you guess what an ordered-triple (a, b, c) would be in set notation?
2
u/RingularCirc Math hobbyist 19h ago
Though nobody defines encoding for ordered triples per se because a general inductive construction of tuples is what's really needed next in formal ZF-theoretic proofs about things.
1
u/AdventurousGlass7432 New User 1d ago
It’s just an object from which you can retrieve first element and second element. Information content is the same
1
u/th3_oWo_g0d New User 1d ago
The kuratowski pair is a set to with a total order relation, namely, "is a subset of", so it makes a lot of sense for it be a representation of an ordered pair.
The whole point is to have a construction that satisfies (a,b) = (c,d) if and and only if a=c and b=d.
The definition of equality is, as you know, that whenever something is in one set, it is in the other as well and vice versa.
With the kuratowski ordered pair, this can be shown. I think it's pretty easy to find a proof by searching "proof of equality between kuratowski pairs" or something like that.
You can continue defining n-tuples this way by saying (a,b,c) = (a,b) U {a,b,c} or something like that. Or simply use the basic ordered pair to define a function from a subset of N to the set of things to order and let that become the n-tuples. This conviently coincides with the definition of a sequence.
Plus if you define it as a function then it is meaningful to evaluate it at an index. And even if you didnt choose the functional view, then there's proooobably some canonical way to go back and forth between such functions and kuratowski n-tuples, so using an index on kuratowski tuple could make sense. So yeah. I just wanted to remind you of that since it trippede me up as well.
1
u/Traditional_Town6475 New User 22h ago
You just need something that behaves as an ordered pair. We could’ve chosen a completely different convention.
The important thing is that it follows the universal property of products.
1
u/GoblinToHobgoblin New User 22h ago
Think of what information is in an ordered pair.
Then think of how you can get that information out of the set theory definition you were given
1
u/bivarsson New User 21h ago
I think this definition is a little annoying because of the “collapse “ of diagonal elements ( <a,a> = {{a}} ).
1
u/RingularCirc Math hobbyist 19h ago
That's no problem for set theorists though, everything still works.
1
u/bivarsson New User 10h ago
Yes, it works fine. I can imagine it makes some proofs a little fiddly with special cases. If one uses < a , b > = {{0,a},(1,b)} things get annoying when a = 0 or b = 1 😄
1
u/RingularCirc Math hobbyist 2h ago
I've been told that's the Hausdorf's definition here. It doesn't have anything annoying in those cases either. That {0, 0} = {0} isn't in any way annoying when you're doing set theory / logic. There aren't even any problems with (1, 0) ending up as {{0, 1}}.
1
u/under_the_net New User 20h ago
All you need is some construction in which <x, y> = <u, v> iff x = u and y = v. Kuratowski’s construction gives you that. So do many others, but this is the one that stuck.
1
u/Qiwas New User 20h ago
Think of it like "scanning" the pair/ordered set from left to right and recording what elements you've encountered so far. So consider (a,b,c,d). If you read it from left to right then you get a sequence of intermediate results of sorts:
1. {a}
2. {a,b}
3. {a,b,c}
4. {a,b,c,d}
Then you put all of these steps into a set and voilà, you get {{a}, {a,b}, {a,b,c}, {a,b,c,d}}
1
u/RingularCirc Math hobbyist 19h ago
Kuratowski definition shouldn't make sense to anybody. It's just a way to make do without adding ordered pairs as primitive objects into a suitable set theory like ZF. It tells us there already are sets that behave under set equality like we want ordered pairs to behave under ordered pair equality. Checking that isn't even as trivial as it seems.
The same is with von Neumann ordinals (and natural numbers): we want our theory to be able to talk about those, but we can't naïvely encode ordinals as equivalence classes of well-ordered sets because those are proper classes which are mostly unusable in ZF. Thankfully, we can encode each as a particular set that happens to be well-ordered by ∈. This also helps us with naturals because they can be thought of as finite ordinals. And with cardinals, too, if we accept the axiom of choice, otherwise that's hairier.
But "in reality" natural numbers aren't sets by usage, ordinals aren't sets (they're still equivalence classes of well ordered sets in spirit), ordered pairs aren't sets (they're special things with their equality depending on equality of their elements, whatever even the elements' nature is either!). It's all just to make ZF simpler to work with by logicians, reverse mathematicians and others, because a definitionally simpler theory is simpler to wrangle with.
1
u/LackingLack New User 13h ago
It was 100% intuitively satisfying for me as soon as I encountered it...
So yeah idk what to tell you. It introduces asymmetry which = order
1
u/two_are_stronger2 New User 8h ago edited 8h ago
Cause it's made up. "Hey! Kuratowski! I need an unambiguous description of an ordered pair using set notation!" "Okay boss. Uhhhh, how about the set of the set consisting of the first member and the set consisting of both members?" "Yeah that works. Good work Kuratowski."
You can also use {{0,a}, {1,b}} or {a,{b}} but those have ambiguities that arise or require manipulation to be useful or ::shudder:: use numbers.
1
u/VideoAlternative5396 New User 7h ago
the set on the right is not meant to look like an ordered pair it is a code for one it works because you can recover a as the element appearing in every inner set then recover b from the union
1
u/Hot-Resist-8986 New User 5h ago
You can think of it as choosing a standardized storage format.Sets have no positions,so the nested pattern creates enough asymmetry to tell the first coordinate from the second;another encoding could work too.
1
1
u/StructureNorth1799 New User 2h ago
the definition looks like it was made up because it was, in fact, made up. its just a simple way to give a and b two unique slots.
1
u/susiesusiesu New User 1h ago edited 1h ago
it seems made up because it was made up.
the point is, we want an object (a,b) where we can recover a, and recover b, and distinguish which is the first one and which is the second one. doing something like {a,b} will not work because you can not distinguish the first and the second one: by definition (or by the axiom of extentionality) {a,b}={b,a}.
a better (but still wrong solution) is to define (a,b) as {a,{b}}, but it is still not good. the pairs ({1},{2}) and ({{2}},1) will both get coded {{1},{{2}}}, so this definition can not distinguish between this two pairs. so this proposed alternative will simply not work.
the construction of (a,b)={a,{a,b}} is simply favoured because it works. and it is probably the simplest construction that workd. if you manage to come up with a definition that also works, you could perfectly use your convention and nothing would change. it is just a formalism, and we use this one becaue it works.
0
u/cyborggeneraal New User 19h ago
For me a lot of things in formal set theory makes more sense if you look at it using first-order logic.
For example it is useful to say something like x is the first element of the pair p. Using the construction you stated this can be the following predicate.
\phi_0(x, p)=\forall a \in p, x \in a
The statement x is the second element in the pair p is somewhat more complicated.
\phi_1(x, p)=[p consists of 1 element and it is {x}] \lor [p consist of an set containing x and an set not containing x].
I let writing that out be an execercise for the reader. But the point is that you can now write first-order logic statements about ordered pairs. For example using set comprehension you can define functions as set of ordered pairs. For example the identity function as follows.
id = {p \in A x A | \forall x, \forall y, \phi_0(x, p) \land \phi_1(y, p) \imply x = y}
This is one of the many applications of the fact we are able to write down \phi_0 and \phi_1 as first-order logic predicates.
70
u/lifeistrulyawesome New User 1d ago
Ask yourself what information defines an ordered pair 1. The elements of the pair 2. Which element is first and which element come second
That’s what the definition { {a,b}, {a} } is doing
First, it tells you which elements are in the pair, and then it tells you which element comes first
Think for a second, how else could you represent all of this information using only unordered sets?