# Naive set theory question on “=”

So I picked up a couple of good undergraduate-level books over the weekend and have been working through them...

In Algebra: Chapter 0, the author of the text writes:

The prototype of the well-behaved relation is '=', which corresponds to 'the diagonal' $$\{ (a, b) \in S \times S \, | \, a = b \} = \{(a, a) \, | \, a \in S \} \subseteq S \times S$$

The problem I'm having is that the way I'm interpreting this expression makes it seem uninteresting, almost tautological, which I'm thinking can't be correct. What I think this expression is saying is this: Suppose I give you elements $a$ and $b$ in the set $S$ to compare for equality. To do that, write $a = b$ as the ordered pair $(a,b)$, which is the same element as $(a, a)$, which by a previous definition we are told is true iff $\{b\} = \{a\}$.

But when I try to bring this to a concrete level, by letting $S$ be the set of all polynomials with integer coefficients, say, I become confused. Since $(0, 6x + (-6)x)$ is not the same ordered pair as $(0, 0)$, aren't we left to conclude that $(6x + (-6)x) \neq 0$? That doesn't seem right. The only thing I can see this definition being useful for is writing tautologies like $A = A$.

And then I wondered: What does it mean to write an expression like $x^2 = 2x$? Am I correct in saying that the "$=$" there is not the same "$=$" as in the definition given above? How would one write the definition of this new "$=$" in set-theoretic terms, with universal quantifiers?

-
For your second question I guess typically we are implicitly defining the set $S = \{ x \in \mathbb{R} : x^2 = 2x \}$ or something like it. –  Qiaochu Yuan Mar 1 '11 at 22:06

First of all the way you approach the definition is wrong and obfuscating which leads to your second question. Also, your confusion regarding the polynomials stems from a common problem a lot of people have when they start dealing with (a bit more) abstract mathematics: They mix up the object with the representation of the object.

What your definition says is this: Imagine I give you two objects $a,b\in S$ to compare for equality. These two objects are equal if and only if they are one and the same. Typically, the set theoretic approach to a binary relation on a set $S$, is an $R\subset S\times S$. This means that the equality relation is $E=\{(a,a)\in S\times S : a\in S\}$, which means that $a=b$ if and only if $(a,b)\in E$ which is true exactly when $a$ and $b$ are one and the same (or more concisely -which I purposely avoided- exactly when $a=b$). This may sound pointless and uninteresting and tautological. Actually Wittgenstein in "Tractatus Logico-philosophicus" points out this apparent pointlessness of "$=$". But such a concept is fruitful mathematically because the mathematical interest in the elements of $S$ lies in their properties: We want to know about the form, the structure of a mathematical universe and our only means of describing it is through a mathematical language. Saying $3=3$ is uninteresting but saying that for every $x,y$ we have $(x+y)^2=x^2+y^2+2xy$ tells you something and the fact that given any number $n\geq 3$ you can never find positive natural numbers $a,b,c$ such that $a^n+b^n=c^n$ is not trivial at all.

Now regarding your confusion, as others have pointed out you are mixing the expressions of polynomials with polynomials. $6x-6x$ is a description of a polynomial and so is $0$. But these two descriptions talk about the same polynomial. This is essentially the information conveyed by writing $0=6x-6x$ (see the usefulness of the equality relation here). Using objects that are -in some sense- different to indicate the same thing is something we do all the time, even outside of mathematics. Without this we wouldn't be able to communicate, since words as physical objects are different from one another, even though they may spell the same thing. Every time you see letters on a paper, you ignore their physical nature (their consisting of atoms that you have most probably never encountered before, and definitely not in that form) and only care about what they symbolise.

Finally, regarding you second question: Formally, no, it is the same definition. In a formal environment the standard definition of the meaning of the symbol "$=$" is always the diagonal. An expression such as $x^2=2x$ doesn't have any meaning whatsoever because $x$ is a free variable. We assign a truth value (true or false) in sentences which are defined as formulas that contain no free variable. Intuitively, ask yourself the following: First of all what is this $x$? Secondly, a relation is defined as a subset of the Cartesian product of a set. What is this set? For "$=$" to be a relation in the formula $x^2=2x$ would mean that $x^2$ and $2x$ are elements of a set. So your question isn't well defined. What we mean when we say that some $a\in\mathbb{R}$ (for example) satisfy $x^2=2x$ is that $a^2=2a$, or that the $a^2$ is the same number with $2a$, which is exactly the definition of the equality I (and the book you are studying) presented.

Edit: When you write a mathematical sentence like "$2+3=5$" or "$(\forall x)((2x)^2=4x^2)$" you have to keep in mind that these are strings of symbols. As Calvin points out these strings don't have a specific meaning. Meaning is something we equip on a language. Tarski's definition of truth intuitively is pretty much what we do when we teach very young children the meaning of words. We show them the objects and say "This is a CAR". Through repetition, children learn to equip the concept of an automobile to the sound "car".

Tarski said roughly the same: Assume that we have a set $S$, a function $f:S\times S\to S$, a relation $E\subset S\times S$ and some elements $a,b,c\in S$. Now I come up with a language that has symbols "$+$", "$=$" and "$0$", "$1$", "$2$". Then we can assign to each symbol an actual objects, for example we will say that "$+$" will represent $f$, "$=$" will represent $E$ and each of "$0$", "$1$", "$2$" will represent $a,b,c$ respectively. Now we can say that the sentence "$2+1=3$" is true in the world $(S,f,E,a,b,c)$ exactly when $(f(b,a),c)\in E$. In practice we try to use the same symbols for similar functions and relations and this is why we reserve the symbol "$=$" for the diagonal relation.

-
@Apostolos First of all, thank you for your great answer. I'm still a bit confused, so let me be explicit: Is (Description 1 of $a$, Description 2 of $a$) $\in E$? –  Uticensis Mar 2 '11 at 2:44
@Billare: "Description 1 of a" and "Description 2 of a" aren't elements of $S$. Therefore typically (D1 of a, D2 of a) doesn't belong in $E$ since it doesn't even belong in $S\times S$. But this was what I meant that you mix the object with the description of the object: When I write $2+3=5$ what I mean is the object in $S$ that is described by $2+3$ is the same object that is described by $5$. I will edit my answer to try to make this more clear by giving some definitions about model theoretic truth. –  Apostolos Mar 2 '11 at 2:59
@Apostolos OK, I think I'm starting to get it. Let me make sure: Given $a, b \in S$, where $b$ is not "trivially" $a$, it is not a priori clear whether $(a, b) \in E$, is that correct? And: When you write something like $2 + 3 = 5$, to rigorously prove this, you would need to be presented with more information to demonstrate that the expression $2 + 3$ is in $S$; for example, the axioms of $\mathbb{N}$? And you would perform manipulations to show that the two expressions are really describing the same object, so $(2 + 3, 5) \in E$? –  Uticensis Mar 2 '11 at 3:24
Now when you're working with two numbers $a, b \in \mathbb{Z}$, you have a group operation $+:\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$. When you write $2 + 3 = 5$ you really mean $+(2, 3) = 5$, which can be read as 'the numbers $2$ and $3$ correspond to the number $5$ by the function $+$'. So $2 + 3$ is NOT itself an element in $\mathbb{Z}$, but its value as the function applied to two elements is, and the statement $(2 + 3, 5) \in E$ is as tautological as $(5, 5) \in E$. –  Alexei Averchenko Mar 2 '11 at 4:07
@Billare: More or less yes. Objects, relations and functions are labelled with symbols. In my example the word "stole" is a symbol for a binary relation that relates the thief with the object that he stole. Of course there are rules on how formulas are created. If you are interested and want to get the specifics on formations of sentences and truth you can read wikipedia's articles on well formed formulas and the T-schema. Also any introductory text to mathematical logic covers these. –  Apostolos Mar 2 '11 at 5:13

Consider $S=\{1,2,3\}$. The diagonal is $\{ (1,1), (2,2), (3,3) \}$. There is nothing trivial or tautological about it.

BTW, $(0, 6x + (-6)x)$ is the same ordered pair as $(0, 0)$ because $6x + (-6)x=0$ as polynomials. You need to recall the definition of equality of polynomials.

-
Yes, "the set of all polynomial expressions with integer coefficients" is not the same as "the set of all polynomials with integer coefficients"; we put an equivalence relation on the former to get the latter. –  Qiaochu Yuan Mar 1 '11 at 22:06
@Qiaochu Yuan I think I understand that. So the equivalence relation to go from the "expression" to the "equivalence" must be defined by saying the two expressions evaluate to the same number for all $x$ in their domain, is that correct? –  Uticensis Mar 1 '11 at 22:30
@Billare: no. That won't give you the correct equivalence relation over a finite field. A low-level definition is that the two expressions should have the same coefficients. –  Qiaochu Yuan Mar 1 '11 at 22:42

Writing a term, like $(-6)+6$, usually means that the term should be evaluated. $(-6)+6=0$ makes sense because of evaluating $(-6)+6$. If we compare written terms as strings, then terms on the left and right sides of equality will be always identical, which is uninteresting, as you pointed out.

As for polynomials, a term describing a polynomial is evaluated (simplified) to the canonical form. There are several, e.g. a partial function $f$ from natural numbers to $R$ (the set of coefficients in polynomials) which is everywhere $\neq 0$. $f(n)$ is a coefficient at n-th degree of the variable of the polynomial.

If we do not have an evaluation function but have an equivalence relation, we can construct an evaluation function as a quotient map.

-

The difference between the two is that on the left you start with a more general set(the set of all ordered pairs) and then reduce it to the one you want with an equivalence relation; while on the right you directly construct the set you want.

Your polynomial example isn't a counterexample because you're confusing set equality with polynomial equality. If the object $(0,6x + (-6)x)$ is considered different than $(0,0)$, then, yes, $(6x + (-6)x)$ is considered a different object than $0$.

To give another example, if you look at the integers modulo $7$, the number $0$ is equivalent to the number $7$ but as objects in the base system they are not equal.

-

I'd think about the answer to your question "What does it mean to write an expression like $x^2 = 2x$?" in terms of formal systems:

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

If you're given the additional "axiom" $x^2 = 2x$, you can then reason about this expression using the other axioms and rules of inference in the system.

When asked to "find $x$", you're being asked to derive a theorem stating that $x$ is equal to some other quantity.

If you're interested in reading more about formal languages; I'd recommend Kleene's "Introduction to Metamathematics", which is a classic.

-

The only point he is making is that "=" is the most fundamental of equivalence relations. In this case "=" means "is exactly the same as". In the most technical sense, "=" is useless. Two different segments of length 2 are not equal since I just said that they were different. The fractions $\frac{2}{4}$ and $\frac{1}{2}$ are not equal since they are obviously not the same thing. We could get around this by saying $\overline{AB} \equiv \overline{CD}$ and $\frac{2}{4} \equiv \frac{1}{2}$ Where equivalence is properly defined.

Similary, $6x + (-6x) = 0$ is incorrect and $6x + (-6x) \equiv 0$ is correct when defined properly. Because paying attention to details like this could quickly overwhelm mathematicians in a sea of frivolous notation, they are ignored.

We get away with this until we encounter $x^2 = 2x$ where the equal sign means something entirely different. They use the equal sign in both cases not because they mean the same thing but because you should be able to figure out their meaning from their context. It would be madness to have a separate notation for every single mathematical concept.

-
Technically you're wrong. The symbol $\equiv$ is not a standard symbol in logic, and so $6x+(-6x)=0$ is a well formed formula, asserting equality between two terms, whereas $6x+(-6x)\equiv0$ is not a well formed formula. –  Asaf Karagila Apr 23 at 15:50
@Asaf. So all of those foundations of mathematics classes I took were based on bad logic? Those two terms are not equal in the most fundamental sense of equality. You just have to look at them to see that they are not the exact same thing. –  Steven Gregory Apr 23 at 15:56
I have no idea when you took them, where you took them, who taught them, and what you'd learned. So I have no evidence to support one or another. It seems to me that you're thinking about interpreting the terms and then claiming they are equal, which is indeed rather an equivalence relation. But the statement that the terms are equal is still a true statement in your structure; whereas $\equiv$ is still not a part of first-order logic and to say the terms are equivalent is still not a well-formed formula without adding $\equiv$ to the language and requiring all the needed axioms for it. –  Asaf Karagila Apr 23 at 15:59
Fine. Explain equality between two terms to me without using equivalence. –  Steven Gregory Apr 23 at 23:04
There's nothing to explain. $x$ and $y$ are terms. $x=y$ is an atomic formula. $M\models_\sigma x=y$ means that under the assignment $\sigma$, the values of $x$ and $y$ are equal. In some cases we can prove that this equality does not depend on the assignment, e.g. $x+(-x)=0$. In which case we just write $M\models x+(-x)=0$. Or, when $M$ is clear enough from context (e.g. when working informally, from a foundational point of view), $x+(-x)=0$. –  Asaf Karagila Apr 23 at 23:11