Confusion over definition of relations in set theory

["Don't panic!"]

I'm coming from a physics background, but find pure mathematics extremely interesting, so have decided to try and gain a more fundamental understanding of the subject. I've recently been reading up on relations and how one can define them as sets of ordered pairs. I am particularly interested in how one can define the equality and inequality relations of real numbers in terms of sets of ordered pairs, and from this be able to prove the transitive properties of both relations (and the symmetry and reflexive properties of equality). So far, however, I've been unable to find any notes (pdfs) that give an explanation that I can grasp conceptually. For instance, I've seen equality defined as [tex]S\subseteq\mathbb{R}^{2}=\lbrace (x,x)\in\mathbb{R}^{2} \vert\; x\in\mathbb{R}\rbrace[/tex] but I have to admit (much to my embarrassment) that I'm struggling to understand what this "means" conceptually?! Isn't one required to explicitly state the relation that two elements of [itex]\mathbb{R}[/itex] must satisfy in order to be in this set? Or is it just that one states that an element [itex]x\in\mathbb{R}[/itex] is always equal to itself and hence we can construct a set of ordered pairs containing only one element, i.e. the set containing the single element [itex]\lbrace x\rbrace[/itex] such that [tex](x,x)=\lbrace\lbrace x\rbrace, \lbrace x,x\rbrace\rbrace = \lbrace\lbrace x\rbrace\rbrace[/tex]
As such, given that the defining property of ordered pairs, [tex](a,b)=(c,d)\iff a=c \wedge b=d[/tex] it follows that [tex](x,x)=(x,y)\iff x=y[/tex] thus defining the equality relation between two elements of [itex]x\in\mathbb{R}[/itex]?!

 

[Stephen Tashi]

For instance, I've seen equality defined as [tex]S\subseteq\mathbb{R}^{2}=\lbrace (x,x)\in\mathbb{R}^{2} \vert\; x\in\mathbb{R}\rbrace[/tex] but I have to admit (much to my embarrassment) that I'm struggling to understand what this "means" conceptually?! Isn't one required to explicitly state the relation that two elements of [itex]\mathbb{R}[/itex] must satisfy in order to be in this set?

That definition wouldn't help you prove that 2 + 3 = 5, but (via the notational convention that "x" denotes the same number everywhere it occurs in the definition) it would let you prove 5 = 5. So the definition has some content. It says (under the usual equality relation defined on the real numbers) that each real number is equal to itself.

Or is it just that one states that an element [itex]x\in\mathbb{R}[/itex] is always equal to itself and hence we can construct a set of ordered pairs containing only one element, i.e. the set containing the single element [itex]\lbrace x\rbrace[/itex] such that [tex](x,x)=\lbrace\lbrace x\rbrace, \lbrace x,x\rbrace\rbrace = \lbrace\lbrace x\rbrace\rbrace[/tex]

You may have the correct idea, but your notation is misleading. We have to distinguish between the element [itex] x [/itex] and the set [itex] \{x\} [/itex] that consists of the single element [itex] x [/itex]. An element of the equality relation [itex] S [/itex] is an ordered set of the form [itex] (x,x) [/itex]. This is not the same as an ordered pairs of sets whose members are [itex] x [/itex].

Set theory would be simple if the relations "element of" and "subset of" did not allow recursive elaboration. There would be only two things to worry about: elements and sets. However, set theory allows the notion of sets whose members are sets. So if we accept that [itex] x \in A [/itex] we have [itex] \{ x\} \subset A [/itex]. But this allows to define a set [itex] B [/itex] that contains the single set [itex] \{x\} [/itex] as an element . Then [itex] x \notin B [/itex], but [itex] \{x\} \in B [/itex].

 

["Don't panic!"]

That definition wouldn't help you prove that 2 + 3 = 5, but (via the notational convention that "x" denotes the same number everywhere it occurs in the definition) it would let you prove 5 = 5. So the definition has some content. It says (under the usual equality relation defined on the real numbers) that each real number is equal to itself.

Is there a better way to define the equality relation?

You may have the correct idea, but your notation is misleading. We have to distinguish between the element x x and the set {x} \{x\} that consists of the single element x x . An element of the equality relation S S is an ordered set of the form (x,x) (x,x) . This is not the same as an ordered pairs of sets whose members are

Sorry, when I said element I had meant that the set [itex]\lbrace x\rbrace[/itex] containing a single element [itex] x[/itex] is the single element of the set [itex]\lbrace\lbrace x\rbrace\rbrace[/itex].

To be honest I'm struggling to understand why equality is defined as [tex]\lbrace (x,x)\in\mathbb{R}^{2}\vert\;x\in\mathbb{R}\rbrace ?[/tex]

 

[micromass]

Sorry, when I said element I had meant that the set [itex]\lbrace x\rbrace[/itex] containing a single element [itex] x[/itex] is the single element of the set [itex]\lbrace\lbrace x\rbrace\rbrace[/itex].

To be honest I'm struggling to understand why equality is defined as [tex]\lbrace (x,x)\in\mathbb{R}^{2}\vert\;x\in\mathbb{R}\rbrace ?[/tex]

It's not really defined like that. The book you're reading is wrong, although I do understand what they're trying to say. Rather, equality is a primitive notion which is given no definition. It just satisfies three axioms. See http://en.wikipedia.org/wiki/First-order_logic#Equality_and_its_axioms

The book doesn't say this because it doesn't want to show you how to develop math from scratch. It already assumes that equality and sets are notions which are intuitive enough not to need an explanation. But I think it's rather poor form to define equality like you said. There are many better examples than this.

 

[Stephen Tashi]

Is there a better way to define the equality relation?

To investigate other ways, you would have to study how the real numbers are defined in terms of simpler mathematical structures. I have never studied how to begin with something like the "Peano Axioms" and develop the definition of the real numbers. In real analysis, it is common to study how to begin with the rational numbers and define the real numbers in terms of "Dedekind cuts". Then equality on the real numbers can be defined in terms of some simpler equality relation. So, yes, I think there are ways to define equality on the real numbers using more primitive concepts However, these ways are only "better" if you like that sort of thing.

Sorry, when I said element I had meant that the set [itex]\lbrace x\rbrace[/itex] containing a single element [itex] x[/itex] is the single element of the set [itex]\lbrace\lbrace x\rbrace\rbrace[/itex].

Then you shouldn't write things like [itex] (x,x) = \{\{x\},\{x,x\}\} [/itex] (where [itex] = [/itex] is the equality relation on sets .

To be honest I'm struggling to understand why equality is defined as [tex]\lbrace (x,x)\in\mathbb{R}^{2}\vert\;x\in\mathbb{R}\rbrace ?[/tex]

To say [itex] S [/itex] is an "equality relation" on a set of things guarantees , by definition of an equality relation, that the relation is "reflexive". Thus, for each thing [itex] x [/itex] we have [itex] (x,x) \in S [/itex] and this is denoted [itex] x= x [/itex]. Technically, if you talk about an equality relation [itex] S [/itex] on the real numbers, you wouldn't have explicitly say that [itex] (x,x) \in S [/itex]. You'll have to read carefully to see whether your text is just defining a notation convention (e.g. The meaning of "[itex]=[/itex]" for numbers vs "[itex]=[/itex]" for sets.)

For the ordered pairs definition of an equality relation to have interesting content, you need to consider things that are equal in some respects without being identical in all respects. For example, x and y may be different numbers but if we only consider the aspects "odd" and "even", we can define an equivalence relation that captures the idea of "same with respect to odd-ness or even-ness". (2,4) is not is an element of the usual equality relation defined on the real numbers, but (2,4) is an element of the equivalence relation of "both are the same with respect to odd-ness or even-ness".

 

[micromass]

Then you shouldn't write things like [itex] (x,x) = \{\{x\},\{x,x\}\} [/itex] (where [itex] = [/itex] is the equality relation on sets .

But that is the standard definition of an ordered pair. I'm not sure I understand your objection.

 

["Don't panic!"]

by definition of an equality relation, that the relation is "reflexive"

Is this just that an element [itex]x[/itex] should be, by definition, equal to itself?

To be specific, I'm unsure why it is defined as [itex]\lbrace (x,x)\in\mathbb{R}^{2}\vert\; x\in\mathbb{R}\rbrace[/itex], why not as [itex]\lbrace (x,y)\in\mathbb{R}^{2}\vert\; x\in\mathbb{R}\wedge y\in\mathbb{R}\rbrace[/itex]?!
The former was the definition given in an example I read in a set of notes on introductory set theory.

But that is the standard definition of an ordered pair. I'm not sure I understand your objection.

Yes, that's what I thought as well. I don't really understand the objection either?!

 

[Stephen Tashi]

Is this just that an element [itex]x[/itex] should be, by definition, equal to itself?

Yes.

why not as [itex]\lbrace (x,y)\in\mathbb{R}^{2}\vert\; x\in\mathbb{R}\wedge y\in\mathbb{R}\rbrace[/itex]?!

That would say that for each pair of real numbers [itex] x,y [/itex] that [itex] x= y [/itex]. (e.g. 5 = 3 )

Yes, that's what I thought as well. I don't really understand the objection either?!

My objection is groundless if the definition of [itex] (x,x) [/itex] is [itex] \{\{x\},\{x,x\}\} [/itex].

 

["Don't panic!"]

So is the set constructed from this notion that a real number is equal to itself, so any ordered pair [itex](x,y)\in\mathbb{R}^{2}[/itex] is a member of the equality relation [itex]S[/itex], if and only if [itex]x=y[/itex], i.e. [tex](x,y)\in S\iff x=y ?[/tex]

 

[HallsofIvy]

Yes, that is exactly what "equality" means.

You might be confusing this with the more general notion of "equivalence relation". A "relation between sets A and B" is any set of ordered pairs, (a, b) with a in A, b in B. An "equivalence relation" is a relation on a single set, "so between A and A" that satisfies 3 conditions:
reflexive: if x is in A, then (x, x) is in the relation.
symmetric: if (x, y) is in the relation, then (y, x) is also,
transitive: if (x, y) and (y, z) are in the relation then (x, z) is also.

Of course "=", in which (x, y) is in the relation if and only if x= y satisfies all of those and is, in a sense, the "ideal" or "model" equivalence relation. But there are other equivalence relations. Consider the set R= {(x, y)| x^2= y^2} where x and y are integers. This relation is reflexive since x^2= x^2 is certainly true for all x. It is also symmetric since if x^2= y^2 then y^2= x^2. Finally, if x^2= y^2 and y^2= z^2 then x^2= z^2.

Given any "equivalence relation", we can define "equivalence classes"- subsets of the base set A such that all of the elements in one such subset are "equivalent" to each other. It can be shown that such equivalence classes "partition" set A. That is, every element of A is in one and only one of those subsets. For "=", the equivalence classes are exactly the "singleton" sets- sets that contain exactly one member of A. The equivalence relation defined by "x^2= y^2" has equivalence classes {0}, {-1, 1}, {-2, 2}, {-3, 3}, ...

 

["Don't panic!"]

Yes, I do find the whole notion of equivalence relations slightly confusing in some sense if I'm honest, in particular, of two objects are related, but the relation is not equality, how does one denote this (other than [itex] a\mathcal{R} b[/itex])? For example, in physics one often defines an equivalence class of Lagrangians in which two Lagrangians are considered equivalent iff they describe the same dynamics (i.e. they lead to the same equations of motion). This corresponds to them differing by a total derivative. Can one then write that [tex] \mathscr{L}' \;\mathcal{R}\;\mathscr{L}\iff\mathscr{L}'=\mathscr{L}+\frac{df} {dt} [/tex]
Also, as another example, can the inequality relation of real numbers be defined as [tex]\lbrace (x, y)\in\mathbb{R}^{2} \vert\;x-y\in\mathbb {R} ^{+}-\lbrace 0\rbrace\rbrace[/tex]

Finally, can one prove the transitive property of equality as follows: Let [itex] x=y[/itex] and [itex] y=z[/itex]. It follows that [itex] (x, y) \in S[/itex] and [itex] (y, z) \in S[/itex]. Now, since [itex] x=y[/itex], then [itex] (y, z) =(x, z)[/itex] and so [itex] (x, z)\in S[/itex]. Also, since [itex] (y, z) \in S[/itex] it follows that [itex] (z, y) \in S[/itex] by symmetry, and so, as [itex] x=y[/itex], [itex] (z, y) =(z, x)[/itex] it follows that [itex] (z, x)\in S[/itex]. Hence, [itex] x=z[/itex].

 

[Stephen Tashi]

but the relation is not equality,

"Equality" is not different concept that an equivalence relation. In a given context, it becomes tedious to keep writing "A is equivalent to B with respect the the equivalence relation S". "Equality" and "equals" are abbreviations used when the equivalence relation being discussed is clear from the context (e.g. in discussing sets, "equal" refers to equality with respect to the equivalence relation defined on sets, when discussing real numbers, "equal" refers to the equivalence relation defined for numbers, etc.) People just write "equal" without giving the details of "with respect to".

The closest thing to "pure" equality would be what I would call notational equality. If we use the symbol "x" to represent something then within the scope of the same discussion an "x" in one place represents the same thing as "x" in another place in the sense that whatever mathematical properties one "x" has, the other "x" also has. With computer languages the "scope" of symbols has strict rules. In written mathematics, the language is more informal. Sometimes "x" means something in one paragraph and something different different in the next paragraph, but sometimes writers go on for pages and pages using "x" to represent the same thing.

Also, as another example, can the inequality relation of real numbers be defined as [tex]\lbrace (x, y)\in\mathbb{R}^{2} \vert\;x-y\in\mathbb {R} ^{+}-\lbrace 0\rbrace\rbrace[/tex]

That looks like a definition for [itex] y < x [/itex]

Finally, can one prove the transitive property of equality as follows:

Equality (of a given sort) is defined as type of equivalence relation, so it is a transitive relation by definition. ( If you don't define equality as an equivalence relation, what are you taking for the definition of "=" ?)

 

["Don't panic!"]

"Equality" is not different concept that an equivalence relation.

Would it be fair to say that equality is the archetypal equivalence relation?

That looks like a definition for y<x y < x

Yes, sorry I wrote it the wrong way round by mistake, I had meant [itex]\lbrace(x,y)\in\mathbb{R}^{2}\vert\; y-x\in\mathbb{R}^{+}-\lbrace 0\rbrace\rbrace[/itex]

I've seen in some texts that say you can prove the transitive property of inequality, I see how I could do this from the definition above, but am I misinterpreting it again like I did with equality?

 

[Stephen Tashi]

Would it be fair to say that equality is the archetypal equivalence relation?

Are you offering "equality" as an undefined concept? - in the sense of "same in all respects"? If so, then I'll go along with it being archetypal - in the sense that specific kinds of equality in mathematics (like equality between numbers) are abstractions of that intuitive idea.

It's an interesting question for logicians whether one may define an "super-duper" equivalence relation by: "[itex] A [/itex] is super-duper equivalent to [itex] B [/itex] means than for each equivalence relation [itex] S [/itex] , [itex] (A,B) \in S [/itex]". Does that work or does it lead to some sort of recursive paradox?

That's the sort of equivalence you'd need to express the stipulation (in some proof, for example) that two symbols like "A" and "B", shall represent the "same" thing. ( The fact there are two different symbols involved shows it isn't the symbols that are the "same" , it is what they represent that is the "same".)

I've seen in some texts that say you can prove the transitive property of inequality, I see how I could do this from the definition above,

I agree. You can prove the transitive property of the "<" relation from your definition of "<" and some simple properties of the signs produced by algebraic operations.

 

[HallsofIvy]

I disagree with Stephen Tashi that ""Equality" is not a different concept than an equivalence relation." "Equality" is very specifically defined as "x= y if and only if 'x' and 'y' are names (possibly different, possibly the same) for the same object. "Equivalence" is a much more general notion, defined as I gave above, that includes "equality" as one specific equivalence relation.

 

[Stephen Tashi]

"Equality" is very specifically defined as "x= y if and only if 'x' and 'y' are names (possibly different, possibly the same) for the same object.

That definition isn't a safe interpretation of the notation "x=y". For example, equality of sets has a specific definition. The concept of "being the same object" isn't specific, until one says what properties of a thing distinguish it as a particular type of object. For example, as sets, {3,2} = {2,2,3} because the distinguishing property of a set is what elements it contains. As another example, in developing the definition of the rational numbers from the integers, we need a specialized definition for the relation [itex] \frac{a}{b} = \frac{c}{d} [/itex].

I agree that the interpretation of written mathematics does involve the concept of "these are two names for the same thing". This is part of the meta-language used in discussing math and I don't know if it can be given a formal definition. The general scenario is that the definition of a mathematical object will specify it has certain properties. If you use the symbol "X" to represent only one particular kind of mathematical object (e.g. a set) then any mathematical object Y that has the same properties as those involved in the definition is "the same" object. However if you use the symbol "X" to represent something in reality or something that is several different types of mathematical objects (e.g. a function is a set with additional properties, a group is set with additional properties) then the relation of "being the same" is not mathematically specific. For example let X be a computer algorithm (by which I mean it is something in reality, a specific set of instructions written in a specific computer language). What does it mean to say "Y is the same algorithm as "X"? In the context of a mathematical discussion, it probably wouldn't mean that X and Y were in the same memory locations on the same computer. It probably wouldn't mean that the code for X had the same indentations from the left margin as used in the code for Y.

 

["Don't panic!"]

I think I've managed to get myself into a confused spiral. In the past I've just accepted the notion of equality, but now I'm unable to accept it in my head without a more rigorous definition.

 

[Stephen Tashi]

People make jokes about politicians discussing the meaning of "is". However, in mathematics, it's a respectable topic !