Take the 2-minute tour ×

I'm having a bit of trouble understanding exactly what this question is asking me in my Sets and Proofs homework:

If a polynomial p over $\mathbb{R}$ is an expression of the form $p(x) = a_nx^n + ... + a_1x+a_0$, is the relation $p\sim q \text{ if and only if } p(0) = q(0)$ an equivalence relation?

I know for a relation to be an equivalence relation, it must be reflexive symmetric and transitive, but I don't exactly understand how I can test/prove it in this situation.

Thank you!

EDIT: Ok, I think I've figured some of it out, but I'm not sure if my logic is right. So, it's symmetric because $q\sim p$ means $q(0) = p(0)$, and since $p(0) = q(0)$ we know this is true.
And it's reflexive because $p\sim q$ means $p(0) = p(0)$, which is trivially true. What I don't understand is how to prove it is transitive.

share|improve this question
Well, given a polynomial $p$ of any degree $n$ (i.e. the highest power of $x$), what is $p(0)$? Good, now that you figured that out, why don't you check these: is $p(0) = p(0)$? (this checks reflexivity). If $p(0) = q(0)$, does it follow that $q(0) = p(0)$? (what does this check for?). Finally, if $p(0) = q(0)$ and $q(0) = r(0)$, what does that say about a relation between $p(0)$ and $r(0)$? –  William Feb 15 '12 at 3:34
Well, the condition that $p\sim q$ if and only if $p(0)=q(0)$ implies $p$ and $q$ have the same constant term. Try starting from there. –  Holdsworth88 Feb 15 '12 at 3:34
So if I prove that p and q have the same constant term, and q and r have the same constant term, then I can say it's transitive because p must have the same constant term as r, making it the same polynomial and thus equal? –  roboguy12 Feb 15 '12 at 3:37
@roboguy12 exactly. –  Holdsworth88 Feb 15 '12 at 3:38
Yes, that's correct. –  William Feb 15 '12 at 3:38

3 Answers 3

up vote 3 down vote accepted

The condition $p\sim q$ if and only if $p(0)=q(0)$ implies $p$ and $q$ have the same constant term. As you have already shown reflexivity and symmetry, we have only transitivity to verify. Thus assume $p\sim q$ and $q \sim r$. Then $p(0)=q(0)$ and $q(0)=r(0)$, which implies $p(0)=r(0)$, finishing the result.

share|improve this answer

Let $P$ be the set of all polynomials over $\mathbb{R}$. You have the relation $\sim$ defined on $P$ by $$p\sim q\text{ if and only if }p(0)=q(0)\;.$$

The thing to notice about this definition is that it boils down to the relation of equality between things associated with $p$ and $q$, and equality is the prototypical equivalence relation. Checking reflexivity, symmetry, and transitivity is therefore very easy, because they all boil down to reflexivity, symmetry, and transitivity of equality. For instance, if $p\sim q$ and $q\sim r$, then $p(0)=q(0)$ and $q(0)=r(0)$, so by transitivity of equality we have $p(0)=r(0)$ and hence $p\sim r$. Similar arguments work for the other two properties.

Note that essentially the same argument would have worked equally well for the relation $p\sim q$ if and only if $p(5)=q(5)$, say; just replace $0$ by $5$ everywhere, and the argument goes through word for word.

Here’s another example. Suppose that $X$ is some set, and $f:X\to Y$ is some function. Define a relation $\sim$ on $X$ by $x\sim y$ iff $f(x)=f(y)$. Checking that $\sim$ is an equivalence relation on $X$ is again easy, because $x\sim y$ reduces to the equality of things associated with $x$ and $y$. For symmetry, for instance, if $x\sim y$, then $f(x)=f(y)$, so of course $f(y)=f(x)$ (since equality is symmetric), and therefore $y\sim x$. Transitivity is almost as easy: if $x\sim y$ and $y\sim z$, then $f(x)=f(y)$ and $f(y)=f(z)$, so $f(x)=f(z)$, and therefore $x\sim z$. Notice how very similar this is to the proof of transitivity of the relation in your problem.

Even when a relation $\sim$ is not defined in a way that easily reduces to equality, there is a standard way to approach the problem of proving that $\sim$ is transitive, say. You want to show that if $x\sim y$ and $y\sim z$, then $x\sim z$, so start by assuming that $x\sim y$ and $y\sim z$. Then translate these two assertions into more fundamental statements about $x,y$, and $z$ using the definition of $\sim$, as I did in my examples. Use those new statements to prove (somehow!) that $x$ and $z$ have the required relationship. In your problem this was easy, because you were basically working with equality; in other problems it might be harder, even a lot harder, but this is still the way to begin.

share|improve this answer

The idea of equivalence is the generalization of equality in the following sense. Once you manage to establish the given relation $\sim$ is actually an equivalence relation, then elements of the same equivalence class are 'equal' while elements of different classes are not. The quotes indicate they are not actually equal in the usual sense.

In your case, the usual equality of polynomials could have been defined as follows: For polynomials $p(x)=a_nx^n+\cdots+a_0$ and $q(x)=b_mx^m+\cdots+b_0,$ we say $p=q$ if $m=n$ and $a_k=b_k, \forall 0\leq k \leq n.$ The given relation, on the other hand, weakens the requirements on when we can say polynomials are 'equal'.

Now to answer your question, you have been asked to check if you can group polynomials into classes and talk of 'equality' at the level of classes. In order to show reflexivity, pick an arbitrary polynomial $p$ and check if $p \equiv p.$ For symmetry, pick arbitrary polynomials $p,q$ and check if $p\sim q$ then $q\sim p$. And so on.

share|improve this answer

Your Answer


