Just 2 relations

Probability Level pending

Let A A and B B be 2 non-empty sets and let f f and g g be 2 mappings from A A to B B . Now we define relations R R and S S in A A as follows:

x R y xRy if f ( x ) = f ( y ) f(x)=f(y) and g ( x ) = g ( y ) g(x)=g(y)

x S y xSy if f ( x ) = f ( y ) f(x)=f(y) or g ( x ) = g ( y ) g(x)=g(y)

Which of the relation(s) must be (an) equivalence relation(s)?

S S only both R R and S S R R only none of them

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Brian Moehring
Jul 19, 2018

The following two facts are direct to prove:

  • f A × A \equiv_f \subset A \times A defined by x f y f ( x ) = f ( y ) x\equiv_fy \iff f(x)=f(y) is an equivalence relation.
  • If R 1 , R 2 R_1,R_2 are equivalence relations, then R 1 R 2 R_1\cap R_2 is an equivalence relation.

In fact, the first of these facts can be considered the main structure theorem for equivalence relations.


Then R = f g R = \equiv_f \cap \equiv_g is an equivalence relation, but S = f g S = \equiv_f \cup \equiv_g isn't necessarily. We can see this by setting f ( x ) = x + 1 , g ( x ) = x 1 2 f 0 g 2 ( 2 ) S 0 S 2 f(x) = |x+1|, g(x) = |x-1| \implies -2 \equiv_f 0 \equiv_g 2 \implies (-2) S 0 S 2 but 2 ̸ f 2 , 2 ̸ g 2 ( 2 , 2 ) ∉ S -2 \not\equiv_f 2, \quad -2 \not\equiv_g 2 \implies (-2,2) \not\in S so S S is not transitive, hence not an equivalence relation.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...