Kuratowski's Definition of Ordered Pairs

[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!

 

[Hurkyl]

1. Why is an ordered pair defined in terms of unordered pairs?

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?"

Doesn't {{a}, {a, b}} = {{a, b}, {a}} = {{b, a}, {a}}, and if so, how does this in any way become ordered?

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))

 

[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.

 

[SW VandeCarr]

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.

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?

 

[CRGreathouse]

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

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\}.$$

 

[SW VandeCarr]

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\}.$$

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?

 

[CRGreathouse]

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?

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.

Also is $$\forall$$ not defined in ZFC? Does this automatically kick the expression into a second order logic?

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.

 

[Hurkyl]

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)

 

[SW VandeCarr]

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.

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}$$?

 

[Hurkyl]

Once you have enough scaffolding, it's generally more efficient to define ordered tuples as functions whose domain is N_n. (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.

 

[rasmhop]

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

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.

 

[CRGreathouse]

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}$$?

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.)

 

[SW VandeCarr]

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.

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.

 

[Hurkyl]

Essentially, I need some algebraic notation in addition to (or perhaps instead of) set theoretical notation. Thanks very much all for your help.

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

 

[SW VandeCarr]

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

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

 

[yossell]

Also is $$\forall$$ not defined in ZFC? Does this automatically kick the expression into a second order logic?

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

 

[SW VandeCarr]

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.
yossell

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).

 

[CRGreathouse]

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}$$ 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 individuals).

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.

 

[SW VandeCarr]

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.

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.

 

[yossell]

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

.

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.

 

[CRGreathouse]

Wow! That's not very efficient.

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.

 

[SW VandeCarr]

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.

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.

 

[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.

 

[SW VandeCarr]

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.

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?

 

[SW VandeCarr]

.

i'm not sure whatyou 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 <?

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)

On the first/second order logic front - it seems as though you take first order quantifiers 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.

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

 

[yossell]

SW,

hmmmm -

so I suppose I find that wiki quote misleading.

There just are first-order formulations of set-theory. And the axioms of ZFC that say, for instance, that for any x and y there is a set which is x u y is not second order just because x and y are sets. It's a perfectly good first order axiom.

I find the Stanford encyclopedia article
http://plato.stanford.edu/entries/logic-higher-order/
clearer here.

Second order quantification (in some of its guises) can be regarded/modelled as a special kind of quantification over the first order domain - but there's nothing to stop the first order domain consisting of sets rather than individuals. Second order quantification can be regarded as quantification over ALL the subsets of the first order domain, the full powerset. Delicate problems involving proper classes arise when the first order variables are supposed to range over all the sets themselves (there is no powerset of all the sets) - but for most applications, this can be ignored.

I'm still not sure what you're looking for I'm afraid. I get the formulas b < a and the like - but I'm not sure how these are linked to particular sets.

Sorry, don't feel like I'm being much help.

 

[SW VandeCarr]

I'm still not sure what you're looking for I'm afraid. I get the formulas b < a and the like - but I'm not sure how these are linked to particular sets.

That's my question exactly. How are these formulas linked to particular sets?

 

[yossell]

In post 18 CRgreathouse showed how these formulas could be related to sets, yet you seemed unhappy with the efficiency of the answer. So it seemed as though you are looking for something more than simply how these formulas are related to sets. Is this wrong?

 

[SW VandeCarr]

In post 18 CRgreathouse showed how these formulas could be related to sets, yet you seemed unhappy with the efficiency of the answer. So it seemed as though you are looking for something more than simply how these formulas are related to sets. Is this wrong?

No, it's not wrong. Expressions like that are needed in foundations theory, but Set Theory, to me at least, is also of practical value. My Harper Collins Dictionary of Mathematics EJ Borowski and JM Borwein eds, 1991 p421 defines an 'ordered set' as "a sequence of elements that is distinguished by both identity and by the order of elements, so that $$\langle{a,b}\rangle$$ is not identical to $$\langle{b,a}\rangle$$ unless a=b." I'm not sure how well established this use of angle brackets is as part of Set Theory. I assume they are not formal symbols under ZFC.

 

[CRGreathouse]

There should be provision for the convenient expression of arbitrarily long tuples and any data density.

Again, it sounds like you want a data structure rather than set theory of any kind.

Perhaps ZFC is too formal and naive ST is more appropriate.

Doesn't help. The difference matters only when you're doing set builder notation with funny things.

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?

I don't know what you intend by appending K. But why write {} when you mean ()? There's already a notation for what you're trying to do, and I can't understand what problem you have with it.

 

[CRGreathouse]

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)

So write that, and say that you have a total order. Depending on what the individual variables are you could represent it more efficiently if needed (say in binary), but since no one on this thread except possibly you knows what you want it's hard to say more.

For example, if you have n numbered variables and a total order amongst them, you could store it as about n ceil(log_10(n) + 5) bytes in ASCII ("a_1413 < a_2208 < ..."), or n ceil(log_256 n) bytes in a binary format, or ceil(log_2(n!)) in factoradic, and so on. But none of this has anything to do with ZFC or Kuratowski.

 

[CRGreathouse]

No, it's not wrong. Expressions like that are needed in foundations theory, but Set Theory, to me at least, to me, is also of practical value.

Practical, yes, but there's no reason to only use one formalization. Use whatever is convenient.

You don't write the Pythagorean theorem as "=+^a2^b2^2c", do you?

My Harper Collins Dictionary of Mathematics EJ Borowski and JM Borwein eds, 1991 p421 defines an 'ordered set' as "a sequence of elements that is distinguished by both identity and by the order of elements, so that $$<a,b>$$ is not identical to $$<b,a>$$ unless a=b." I'm not sure how well established this use of angle brackets is as part of Set Theory. I assume they are not formal symbols under ZFC.

The definition is standard. The notation is not -- () is more common. But you can extend just about any set theory you want with this definition without strengthening it

 

[SW VandeCarr]

Again, it sounds like you want a data structure rather than set theory of any kind.

Yes, but it's very useful to define ST concepts like union, intersection, subset, set membership and set elements for data sets. It also relates to the distinction I make between equality and identity which was the topic of another post in this forum.

 

[CRGreathouse]

Yes, but it's very useful to define ST concepts like union, intersection, subset, set membership and set elements for data sets.

OK, now I'm convinced you want a data structure. Computer science spends a lot of time working out new data structures that are faster at certain combinations of such operations. See for example
http://www.cs.sunysb.edu/~algorith/files/set-data-structures.shtml
for a list of implementations.

 

[SW VandeCarr]

OK, now I'm convinced you want a data structure. Computer science spends a lot of time working out new data structures that are faster at certain combinations of such operations.

Thanks. I'm interested in combining concepts from Set Theory with object oriented programming among other things.

http://books.google.com/books?id=4x...esult&ct=result&resnum=4#v=onepage&q=&f=false