4
$\begingroup$

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.

  • 1
    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)$?2012-02-15
  • 1
    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.2012-02-15
  • 0
    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?2012-02-15
  • 0
    @roboguy12 exactly.2012-02-15
  • 0
    Yes, that's correct.2012-02-15
  • 0
    Thank you guys so much! I wish you guys wrote responses so I could accept your answers!2012-02-15
  • 0
    A useful, very general fact: if $S$ and $T$ are any sets and $f: S \to T$ is any function, then the relation $\sim$ on $S$ defined by declaring that $s \sim s'$ if and only if $f(s) = f(s')$ is an equivalence relation. It is no harder to prove in general than it is to prove in your case ($S$ is the set of all polynomials with real coefficients, $T = \mathbb{R}$, and $f$ the map sending $p(x)$ to $p(0)$). Often, given a relation on a set $S$, identifying a set $T$ and a function $f$ for which the relation has this form is the easiest way of showing that a relation is an equivalence relation.2012-02-15
  • 0
    Every relation defined via equality of the values of a function is an equivalence relation. See http://math.stackexchange.com/questions/92271/two-questions-about-equivalence-relations/92277#922772012-02-15

3 Answers 3

3

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.

3

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.

2

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.