# Decide whether or not the relation is an equivalent relation. Help please?

• Mar 1st 2010, 06:04 AM
chocaholic
Decide whether or not the relation is an equivalence relation. Help please?
Equivalence relations are relations for which it is possible to see related elements as "similar" in some or other sense. Decide for each of the following relations whether or not it is an equivalent relation. Give full reasons. If it is an equivalence relation, give the equivalence classes. Also say if the equivalence classes are all infinite, whether some are finite or all are finite.

(a) Let A be all functions from N to N. Define f Rg if there exists a k is an element of N such that f(n)<=g(n) for all n>=k. (Where <= indicates bigger than or equal to etc)

(b) Let A = {x : x is an element of R;x >= 0}. Define a Rb if and only there exists a k is an element of N such that a = kb.

(c)Let A be the set of all finite sets of natural numbers. Define s Rt if and only if "s intersect t" = empty set.

(d) Let A = [0, 1]. Define a Rb if ab < min {a, b}. (e.g. (1/2 , 1/2) is an element of R but (3/4 , 1) is not an element of R.

I know that for a relation to be equivalent it needs to be reflexive, transitive and symmetric, but I'm not quite sure how to actually set up the relation in (a) and (b) and determine the properties of all of them.

Like for (b) if a=kb then b=a/k and not ka so this relation is not symmetric.I don't think my reasoning is correct here and I don't know how to show transitivity or symmetry.

Then for (c) if "s intersect t"=empty set then "t intersect s"=empty set so the relation is symmetric. Is this correct? But s intersect s = s so the relation is irreflexive? I'm having real trouble showing transitivity.

For (d) ab=ba so if aRb then bRa so it's symmetric but not reflexive because 1*1 is not smaller than 1? Once again what about transitivity.

I have no clue what to do about (a).

I know how to set up an equivalence class when I have all elements of R, but what if I don't as in the above?

Any input would be greatly appreciated

• Mar 1st 2010, 07:24 AM
Math Major
An equivalence relation is defined to be

1. Reflexive
IE given a relation, R, it is reflexive iff $\displaystyle \forall a \in A, aRa$

2. Symmetric

IE, given a relation R, it is symmetric iff $\displaystyle \forall a, b \in A, aRb \implies bRa$

3. Transitive

IE, given a relation R, it is transitive iff $\displaystyle \forall a, b, c \in A, aRb$ and $\displaystyle bRc \implies aRc$

Make sure these 3 properties hold. If one does not, it's not an equivalence relation.

so, say, the first one, for example.

$\displaystyle f R g \iff \exists k \in N$ such that $\displaystyle f(n) <= g(n) \forall n => k$

So f is in relation with g so that if f(n) is less than or equal to g(n) for all n bigger than some natural number, say, k.

Well, is it reflexive?

$\displaystyle f R f \iff \exists k \in N$ such that $\displaystyle f(n) <= f(n) \forall n => k$

It holds because f(n) = f(n) for all n, no matter what k you choose.