# Kuratowski's Definition of Ordered Pairs

1. Aug 1, 2009

### gatztopher

Hey all, I have a very basic question. Kuratowski's definition of ordered pairs,

(a, b)K := {{a}, {a, b}}

is not clicking for me. Part of the problem is I haven't had a serious look at naive set theory since high school, but after reading the webs for a couple of hours, things are good for me except for this one piece.

My points of confusion:
1. Why is an ordered pair defined in terms of unordered pairs? Doesn't {{a}, {a, b}} = {{a, b}, {a}} = {{b, a}, {a}}, and if so, how does this in any way become ordered?
2. How was this definition arrived at? Where I've looked, it's usually just stated without any context for why or how it emerged.

I've long been a fan of physicsforum, thanks for your help!

2. Aug 1, 2009

### Hurkyl

Staff Emeritus
Because you can. Things are a lot simpler if everything is a set. If you instead tried to define axiomatic set-and-ordered-pair theory, you have to worry about all sorts of niggling details, like "can an ordered pair be an element of a set?"

The only important properties of ordered pairs are (or can be derived from):
(1) There is a function L you can apply to them.
(2) There is a function R you can apply to them.
(3) p=q if and only if L(p)=L(q) and R(p)=R(q)
(4) For any two sets x and y there is an ordered pair p such that L(p)=x and R(p)=y

Can you come up with a suitable definition of the functions L and R that, together with this definition of "ordered pair" would satisfy these axioms?

(One might call L(p) the "left" component of the pair, and R(p) the "right" component)
(The names of these two functions are by no means standard)

By the way, (4) defines a logical function whose domain is pairs of sets, and whose range is ordered pairs. We might the evaluation of this function at x and y as (x,y). (This is well-defined because of (3))

Last edited: Aug 1, 2009
3. Aug 1, 2009

### HallsofIvy

All that {a, {a, b}} says is that you are looking at the pair {a, b} and that "a" is distinguised from "b" since it also occurs as a member of the set, not just as a member of {a,b}. The "order", "a before b" or "b before a" is irrelevant. The crucial point is that the 'ordered pair', (a, b), is not the same as the "ordered pair" (b, a) which is true in this definition because the ordered pair (a,b) is represented as the set {a, {a,b}} and the ordered pair (b,a) is represented as the set {b, {a,b}}, clearly different sets for a different from b. The whole point is to give a definition of "ordered pair" in terms of sets which have presumably been defined earlier.

4. Aug 1, 2009

### SW VandeCarr

If I wanted to specify a set $$\forall{x}\in{Z}:1<x<5$$, would this imply the ordered set {2,3,4} if $$Z$$ is considered the ordered set of integers? Can I assume that $$Z$$ is an ordered set?

Last edited: Aug 1, 2009
5. Aug 1, 2009

### CRGreathouse

What's an ordered set?

If you mean tuple, then no: $$x\in\mathbb{Z}:1<x<5=\{2,3,4\}=\{4,3,2\}=\{2,3,3,3,3,4\}.$$

6. Aug 1, 2009

### SW VandeCarr

Perhaps I should say totally ordered set (antisymmetric, transitive and total). In this case I'm thinking of the natural order of the integers such that every integer has a successor. So if $$\mathbb{Z}$$ is the set of all integers, then {2,3,4} is the subset I want (ordered just this way). How do I specify this in set theoretical notation? Also is $$\forall$$ not defined in ZFC? Does this automatically kick the expression into a second order logic?

Last edited: Aug 1, 2009
7. Aug 1, 2009

### CRGreathouse

Sets are inherently unordered: for any a and b, {a, b} = {b, a}. Perhaps what you want is an ordered triple: (a, b, c). (a, b, c) ≠ (a, c, b) whenever b ≠ c.

1. For all is defined in ZFC.
2. "For all x in Z" can be expressed in first-order logic.
3. ZFC is far stronger than second-order logic.

8. Aug 1, 2009

### Hurkyl

Staff Emeritus
Actually, he might be thinking of an ordered set -- models of which in ZFC are ordered pairs $(X,\leq)$ where $\leq$ is a binary relation on X that is reflexive, symmetric, transitive, and any two elements are comparable. (totality)

9. Aug 1, 2009

### SW VandeCarr

OK. Now I feel I'm getting somewhere. How can I express an ordered n-tuple in set theoretical notation (ZFC)? Suppose n is infinite such as in $$\mathbb{Z}$$?

10. Aug 1, 2009

### Hurkyl

Staff Emeritus
Once you have enough scaffolding, it's generally more efficient to define ordered tuples as functions whose domain is Nn. (That's the set of all natural numbers less than n. 0 is a natural number)

Another generally useful way to define n-tuples is to build them out of ordered pairs.

Last edited: Aug 1, 2009
11. Aug 1, 2009

### rasmhop

There are many ways to define such tuples, but the important thing is that they behave similarly. Anyway for finite n-tuples we often simply define it as the ordered pair where the first coordinate is a (n-1)-tuple and the second is an element of the underlying set. For countably infinite tuples (more commonly known as sequences) we often define them as a function f from the set of positive integers to the underlying set. Then f(1) is the first element, f(2) the second, etc. This of course assumes you have an acceptable definition of a function and for that purpose we often need the notion of an ordered pair.

12. Aug 1, 2009

### CRGreathouse

If n is infinite you really need a function (as Hurkyl suggests) rather than a tuple. The way I would define a k-tuple would probably preclude k being infinite in any well-founded set theory like ZFC. (Someone want to check this? I was thinking (a, b, ..., z)_k =def ((a, (b, ..., z))_{k-1})_k, where k is the number of elements.)

13. Aug 1, 2009

### SW VandeCarr

Now it's getting more clear. It seems defining some ordering principle over a countable set should be straightforward. I've done it for years working with data sets. Ultimately, it's almost always a function from the set of positive integers, now that I think about it. Essentially, I need some algebraic notation in addition to (or perhaps instead of) set theoretical notation. Thanks very much all for your help.

14. Aug 1, 2009

### Hurkyl

Staff Emeritus
Do remember that if you really and truly want to push everything back into set theory, there are set-theoretic models of the integers.

15. Aug 1, 2009

### SW VandeCarr

Thanks. I'll keep that in mind. For now, I will simply define a function from the set of positive integers.

Last edited: Aug 1, 2009
16. Aug 2, 2009

### yossell

I'm not too sure what you're asking here. 'All' is like other logical constants, 'not', 'and' and the like - it's normally just part of the background language in which the axioms of ZFC are formulated. (Incidentally, the difference between first and second order is usually treated as a difference in what kinds of variables 'All' can bind - whether there are second order variables X that the quantifiers can bind, or just first order ones x - I'm implicitly reading your 'All' as 'All x' rather than 'All X'). 'All x' just is part of first order logic. So, it's very much part of first (and second order) ZFC - but not really because of very much to do with sets as because, well, it's just part of the background logical framework. In the same sense, 'all' is part of first order arithmetic too.

There are those who think that first order ZFC, being subject to the usual expressive and logical deficiencies of first order logic (such as the fact that any first order theory (including ZFC) has a countable model) *should* be formulated using second order terms. - the first schemas of replacement and comprehension are too weak and need to be replaced with genuine second order axioms. However, the discussion becomes quite philosophical at this point, with some claiming that second order quantification is really just familiar (unrestricted) quantification over *all* the sets in disguise, not really any different from what we always meant by familiar first order quantification.

yossell

17. Aug 2, 2009

### SW VandeCarr

Actually I was trying to extract the totally ordered set {2,3,4} from the set of all integers. I should have used $$\forall{X}$$ and $$x\in{X}$$ instead of $$\forall{x}$$. I still don't know how to do this using set theoretical notation. Perhaps you could show me. I take it this would be a second order logic (ie a logic over sets rather than just individuals).

Last edited: Aug 2, 2009
18. Aug 2, 2009

### CRGreathouse

If by 'totally ordered set' you mean a pair (X, <=) where X is a set and <= is a total antisymmetric relation over X, then I think you want ({2, 3, 4}, (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)). This would usually be described as '{2, 3, 4} with its usual order'.

This doesn't even require first-order logic; propositional will do.

Last edited: Aug 2, 2009
19. Aug 2, 2009

### SW VandeCarr

Wow! That's not very efficient. Are there no shorter expressions in ST notation? It becomes practically unfeasible if I'm trying to extract a long series in natural order from $$\mathbb{Z}$$ using ST notation.

EDIT: I see one error I made. I should have defined $$X$$ as a subset of $$\mathbb{Z}$$ and $$x\in{X}:1<x<5$$. This still doesn't specify the order. Even the simpler expression X={2,3,4} doesn't guarantee order. At least this no longer requires a second order logic since I omitted 'forall X'. I suppose a simple default specification could be $$X=a_{i},a_{i+1},a_{i+2},........,a_{k}}$$. As far as I know, Set Theory doesn't involve substitutions for unspecified constants. I suppose I could call this an algebraic expression in vector form. All I need to extract a series of consecutive integers in natural order from the set of all integers is to specify a_i and a_k.

Last edited: Aug 2, 2009
20. Aug 2, 2009

### yossell

.

Hi SW,
I'm still not entirely sure I've understood what you're looking for - so sorry if this what I say isn't helpful or misses the mark in some way.

Firstly, if your intention is really to find expressions in pure set-theoretic notation, then expressions are going to be very long and unwieldy, even for rather simple things. This is because the only non-logical primitive of the language of ZFC is $$\in$$, the membership relation. Not even '{' and '}' are part of the language of ZFC, not even 'x $$\in$$ {x}' or 'A U B' are strictly in the sentence in the language of ZFC. Instead, operations like U can be defined in ZFC using just first order language and the $$\in$$.

Of course, it's next to impossible to comprehend ZFC without using these terms. It's typically shown how 'x is a pair', 'x is the unique union of y and z' and so on can be defined in set-theoretic terms, and then we write sentences like 'x = {y, z}', 'x = y U z ' to make life simple, but we're aware that these are really shorthand for much longer sentences that involve only the logical constants (oh, and I'm including = as one of these here) and the membership relation.

If we allow ourselves to use this new but defined terminology, then our definitions can obviously become shorter. A lot of work goes into defining the reals or the natural numbers in set-theory, for example, but once we have shown that it can be done, we can then introduce a new symbol for them as a shorthand, and give definitions of other sets in terms of them.

Whether or not there is a simple definition of the set you want to pick out depends upon what you will allow us to use, which defined predicate and operations we are permitted to use in our definitions. If you said more about the parameters of the problem you have in mind, which notions you will allow to appear in the definition, then I might be able to say something more helpful.

It's also still not clear to me what set it is you have in mind when you talk of 'the totally ordered set {2, 3, 4}. Are you looking for the pair that CRG suggested? That is, when you ask for the set X totally ordered by <, you are looking for the pair whose first element is X, and whose second element is the set of pairs of X ordered by <?

On the first/second order logic front - it seems as though you take first order quantifiers to range over individuals, second order quantifiers to range over sets. This isn't what I take the distinction to amount to - in ZFC, there are NO individuals and the first order quantifiers range over sets.

Last edited: Aug 2, 2009
21. Aug 2, 2009

### CRGreathouse

So don't specify the order, just note that you're using the usual order on the integers.

If I had any idea what you were doing I might be able to give more specific recommendations.

22. Aug 2, 2009

### SW VandeCarr

It's not your fault. I simply don't know Set Theory well enough to understand it uses and limitations. I don't know if you read the edit to my previous post. All I want to do is extract an ordered tuple of indefinite length from the set $$\mathbb{Z}$$. I had already settled on a simple way to do it for consecutive integers and it's easy to modify this specification on the computer for non-consecutive ordering including permutations of selected segments of the series.

23. Aug 2, 2009

### CRGreathouse

How large can the tuples be, and how sparse? It seems what you're looking for is more like a data structure than anything else.

24. Aug 3, 2009

### SW VandeCarr

Well, yes. I suppose you could say that. Set Theory (ST) notation should be developed for large data sets. ST concepts would seem natural for data sets. There should be provision for the convenient expression of arbitrarily long tuples and any data density. Perhaps ZFC is too formal and naive ST is more appropriate. The OP used {{a}{a,b}} to express an ordered pair (a,b)K. Suppose we want to select a permutation of the set {1,2,3}; say (2,1,3). Using the notation of the OP (and I may botch this): (2,1,3)K:={{{2},{2,1}}{{2}{2,3}}{{1}{1,3}}}. Why can't I just write {2,1,3}K?

Last edited: Aug 3, 2009
25. Aug 3, 2009

### SW VandeCarr

b>a, c>b (antisymmetric); c>a (transitive); c>b>a (total). Just say I want to extend this process through the whole alphabet. I can obviously do this by typing a simple command on the computer, but I want a formal and concise expression like (a<b<c<.....<y<z)

Every definition of first and second order logic that I've seen states that first order variables range over individuals and second order variables range over sets and individuals. You're using the term 'quantifiers'. I take $$\forall{X}$$ to define the range of X (a variable over sets).
http://en.wikipedia.org/wiki/Second-order_logic

Last edited: Aug 3, 2009