How can the ordered pair (a,b) be defined as {{a},{a,b}}?

[BifSlamkovich]

Main Question or Discussion Point

Please explain the logic, as this is the definition provided by the book I am referring to.

 

[Stephen Tashi]

Please explain the logic, as this is the definition provided by the book I am referring to.

Are you requesting that someone make up a definition where that is done?

If you want to know about a definition in a book, you should quote the entire definition.

 

[Hurkyl]

Please explain the logic, as this is the definition provided by the book I am referring to.

The only thing you need to check to see this model of ordered pairs works is that (a,b)=(c,d) implies a=c and b=d.

So which part do you have trouble with?

• Checking this fact
• The basic idea of modeling ordered pairs (or other concepts) with sets
• Coming up with the list of properties that a model of the notion of ordered pair would have to satisfy

 

[BifSlamkovich]

The only thing you need to check to see this model of ordered pairs works is that (a,b)=(c,d) implies a=c and b=d.

So which part do you have trouble with?

• Checking this fact
• The basic idea of modeling ordered pairs (or other concepts) with sets
• Coming up with the list of properties that a model of the notion of ordered pair would have to satisfy

Checking this fact and the basic idea of modeling ordered pairs with sets.

 

[Akshay_Anti]

Even i have the same doubt. One of the books i referred to says, this is the rigorous way of defining an ordered pair (a,b). But I am unable to figure out how this definition satisfies the definition or condition of ordered pairs?

 

[StatOnTheSide]

The catch is that {a} can never be equal to {b,c} with b being distinct from c. This is a consequence of axiom of extentionality. So if you define (a,b)={{a},{a,b}}, there is no way that (b,a) can be equal to (a,b).

If you are asking me as to why it is constructed this way or as to a contructive way of arriving at this construction, I have not come across any book which treats it that way.
Many axioms are simply stated and are not given a completely satisfactory explaination as to how the definition was arrived at even though the why part is usually explained quite well.

I studied set theory recently so I thought my comments might be helpful.

 

[Erland]

Ordered pairs and sets are different types of objects. For sets, {a,b}={b,a}, while for ordered pairs (a,b)=(b,a) is false unless a=b.
As a part of the programme to reduce all mathematics to set theory, one wants to define all objects as sets, so that one has only one fundamental type of object. Therefore, mathematicians tried to define ordered pair as a kind of set.

For such a definition to be useful, ordered pairs defined by it must have the following basic property, which expresses precisely what we ordinary mean with an ordered pair:

(a,b)=(c,d) => a=c and b=d, for all a,b,c,d.

Mathematicians came up with some different definitions, all satisfying this property.

http://en.wikipedia.org/wiki/Ordered_pair.

It was the Polish mathematician Kazimierz Kuratowski who in 1921 came up with the definition that is now most commonly used: the one in which the ordered pair (a,b) is defined as the set {{a},{a,b}}. This definition, like the alternatives, has no deeper meaning other than that one can prove that the above property holds for it. Presumably, Kuratowski just wanted something that satisfied this property and found this one by playing around a little. Apparently, this definition was considered as simpler or more useful or more aesthetically pleasing than the other alternatives by most mathematicians, whence it "won" over these alternatives.

We must therefore prove the above property from this definition, that is:

{{a},{a,b}}={{c},{c,d}} => a=c and b=d.

To prove this, assume that the two sets are equal. Since {a} lies in the left hand set, it also lies in the right hand set. Hence {a}={c} or {a}={c,d}. In the first case, a=c. In the second case, we must have both c=a and d=a, since {a} is singelton. Thus, in both cases, a=c.
Next, {a,b} lies in the LH set, so it also lies in the RH set, that is, using a=c, {a,b}={a} or {a,b}={a,d}. In the first case, we have b=a, and since {a,d} lies in the RH set, it also lies in the singelton LH set {{a}}, so {a,d}=a, which gives d=a=b, so b=d.
In the second case, we may assume that a =/= b (otherwise, the first case applies). Then {a,b}={a,d} gives b=d. Thus, in both cases, b=d.
We have proved that a=c and b=d hold in all cases.

 

[StatOnTheSide]

Similar to ordered pairs, I have always wondered why the numbers are defined the way it is in set theory. 0 = empty set, 1={0} etc.

I know that if you assume this definition, then along with the recursion theorem, addition, multiplication etc can be derived.

The problem is not so much as to HOW it works or WHY it works. The problem is that in most of the other subjects that I have studied, almost any definition or axiom is sort of constructive. Take for example the simple definiton of resistance in electrical engineering. It is found that current is linearly proportional to voltage. Therefore we define resistance as the ratio of voltage to current through a resistor.

But in here, there is no earthly reason why 0 has to be equal to an empty set. In Set Theory text books, the author simply starts out saying that the definition of natural numbers is this. Various questions simply spring to my mind at that moment.

1. Why do we need to define numbers?
2. Is this the ONLY way to define numbers?
3. Is there a reason for defining numbers this way? What was the thinking behind it?

I guess these are more philosophical in nature. The mathematics behind it is understandable but after being used to numbers for such a long time, if someone is introduced to the concept of numbers as being equal to sets, then a lot of questions arise for which the answers are not really available in text books.

I guess it makes a h_uge difference to have a professor teach Set Theory because then, he can clarify such doubts and help the student mature into pure math in an organic way. I have been doing self study of the subject and I find it very hard to understand the motivation for the things that they do in Set Theory even though the math itself is not super hard to understand.

 

[Hurkyl]

There are at least three reasons to define numbers as such:

• A relative consistency proof: a theorem that says if "set theory is consistent" then "number theory is consistent" also.
• A means to apply our knowledge of sets to the study of numbers
• A means to apply our knowledge of numbers to the study of sets

You may also be interested in the notions of formal theories and of models: the formal theory of Peano arithmetic consists of the statements one can prove about number theory (using Peano's axioms), without any interpretation of what numbers "mean". A model is a method of assigning "meaning" to the elements of the formal theory in a way such that the theorems remain true when so interpreted.

Both notions are very useful, and IMO it is very useful to be able to consider them as separate notions.

 

[StatOnTheSide]

Makes sense. I do not know what IMO stands for.......might be a dumb question to ask though :).

 

[Hurkyl]

"In My Opinion". A common variant is IMHO: "In my Humble Opinion". You also get IMNSHO occasionally too.

 

[Hurkyl]

The reason to define ordered pairs, though, is different: I believe the main purpose is for convenience. It means we can lay out a "axiomatic theory of sets" and still make use of ordered pairs, rather than having to go through the effort of making an "axiomatic theory of sets and ordered pairs".

 

[Erland]

1. Why do we need to define numbers?
2. Is this the ONLY way to define numbers?
3. Is there a reason for defining numbers this way? What was the thinking behind it?

1. For about 100 years, mathematicians have endeavoured to reduce all mathematics to set theory. It is presumably perceived as simple (in some sense) and aesthetically rewarding to base all mathematics upon one simple theory. Therefore, one wants all objects, including numbers, to be defined as certain sets.

2. I know of two ways to define the the natural numbers:

i) 0 = {} = Empty set, 1={0}, 2={1}, 3={2}, etc.
ii) 0 = {}, 1={0}, 2={0,1}, 3={0,1,2}, etc.

There could very well be other ways to make such definitions which are unknown to me.

3. These definitions have no deeper meaning, they are just convenient ways to define numbers as sets, in such a way that one can do arithmetics with them (prove all theorems of arithmetics etc.).

I prefer ii), because it can be generalized to transfinite ordinals in a way that i) cannot, as far as I know. It has also the nice property that < is the same as set membership, that is: m<n iff m$\in$n.

 

[StatOnTheSide]

Thanks for the notes :).

 

[Akshay_Anti]

so, you are saying that it is based on the the unification of various branches of mathematics??

 

[Erland]

so, you are saying that it is based on the the unification of various branches of mathematics??

Basically yes.

 

[Akshay_Anti]

my doubt solved in an awesome manner. thanx to all!!!

 

[Stephen Tashi]

so, you are saying that it is based on the the unification of various branches of mathematics??

Think about it this way:

MR X: challenges you to define "ordered pair" using only notions from elementary set theory.

YOU: "An ordered pair (a,b) is a set whose first element is a and whose second..."

MR X: "No, no no! You can't talk about a 'first' or 'second' element in a set. That type of order isn't defined for sets. The set {a,b} is the same set as the set {b,a}."

YOU: "But ordering is a basic notion. Ordering relations are part of elementary mathematics."

MR. X: The challenge is to define 'ordered pair' using only things are are defined in elementary set theory. A 'relation' is defined as a set of ordered pairs, so you can't define an 'order' relation until you have defined an 'ordered pair'."

YOU:"Ok, an ordered pair (a,b) is a function from the integers {1,2} to the set {a,b} such that f(1) = a and ..."

MR. X: "No, no, no! The integers aren't part of basic set theory. And you can't define a 'function' until you have defined an ordered pair anyway. Functions are special sets of 'ordered pairs'."

 

[StatOnTheSide]

Is there a poof somewhere that there is no other way of defining ordered pairs or numbers using only sets? In other words, is this construction unique? If it is not, please refer me to a book which does give an alternative. Otherwise please point me to the proof that this construction is unique.

Also, please do feel free to correct me if my question itself does not make sense.

 

[Erland]

Is there a poof somewhere that there is no other way of defining ordered pairs or numbers using only sets? In other words, is this construction unique?

It is not unique:

http://en.wikipedia.org/wiki/Ordered_pair

However, among the alternatives given in this link, Kuratowski's definition seems to be the simplest one.