# Equivalence Relations

• issacnewton

#### issacnewton

Homework Statement
(a) Suppose ##A\thicksim B## and ##A\times C \thicksim B\times D##. Must it be the case that ##C \thicksim D## ?
(b)Suppose ##A\thicksim B##, and ##A## and ##C## are disjoint, ##B## and ##D## are disjoint, and ##A \cup C \thicksim B \cup D ##. Must it be the case that ##C \thicksim D## ?
Relevant Equations
Definition of equinumerous sets
(a) I present the following counter example for this. Let ##A = \{0,1,2,\ldots \}## and ##B = \{ 2,4,6, \ldots \} ##. Also, let ##C = \{ 1, 2 \} ## and ##D = \{3 \}##. Now, we can form a bijection ##f: A \longrightarrow B## between ##A## and ##B## as follows. If ##f(x) = 2x + 2##, we can see that this is a bijection from ##A## to ##B##. So, ##A## and ##B## are equinumerous and so we have ##A \thicksim B ##. Now, we have the Cartesian products

$$A \times C =\big \{(0,1), (0,2), (1,1), (1,2), (2,1), (2,2), \ldots \big \}$$
$$B \times D = \big \{ (2,3), (4,3), (6,3), \ldots \big \}$$

Now, we can define a function from ##A \times C## to ##B \times D ## as follows. Let the mapping be defines as follows.

$$(0,1) \longrightarrow (2,3)$$
$$(0,2) \longrightarrow (4,3)$$
$$(1,1) \longrightarrow (6,3)$$
$$(1,2) \longrightarrow (8,3)$$

and so on. From this mapping, it can be seen that this mapping from ##A \times C## to ##B \times D ## is a bijection. So, we have ##A\times C \thicksim B\times D##. But ##C = \{ 1, 2 \} ## and ##D = \{3 \}## and since the cardinality is different for these finite sets, we can not have a bijection from ##C## to ##D##. So, its not true that ##C \thicksim D## .

(b) Here also, I will present the following counter example. Let ##A = \big \{ 0, 10, 20, \ldots \big \} ## , ##B = \big \{ 5, 15, 25, \ldots \big \}##, ##C = \big \{ 1,2 \big \}## and ## D = \big \{6 \big \} ##. Now we have a function ##g: A \longrightarrow B## defined as follows. ## g(x) = x+5##. We can see that this is a bijection, so we have ##A\thicksim B##. It can also be seen that ##A \bigcap C =\varnothing ## and ##B \bigcap D = \varnothing ##. Now, we also have following unions

$$A \bigcup C = \big \{ 0, 1, 2, 10, 20, \ldots \big \}$$
$$B \bigcup D = \big \{ 5, 6, 15, 25, \ldots \big \}$$

Let's define the following relation ##h## from ##A \bigcup C## to ##B \bigcup D ##.

$$h = \big \{ (0,5), (1,6), (2,15), (10, 25), \ldots \big \}$$

We can see that this is a bijection from ##A \bigcup C## to ##B \bigcup D ##. So, we have ## A \bigcup C \thicksim B \bigcup D ##. So, all the conditions given in the problem are satisfied. Now we have ##C = \{ 1, 2 \} ## and ##D = \{3 \}##. Again, these are finite sets with different cardinality. So, we can not have a bijection from ##C = \{ 1, 2 \} ## to ##D = \{3 \}##. So again, its not true that ##C \thicksim D##.
Do you think the reasoning is valid here ?

It looks good to me. I think, however, there are simpler counterexamples.

Thanks PeroK. Can you come up with simpler counterexample ?

Thanks PeroK. Can you come up with simpler counterexample ?

One idea is to use the transitivity of ##\thicksim## to show that your sets are both countable (equivalent to ##\mathbb{N}##, rather than directly to each other.

Also, using ##A = B## in both cases would simplify things.

For b), for example, you could have ##A = B = \{3, 4, 5 \dots \}##, ##C = \{1, 2 \}##, ##D = \{2 \}##.

Or, perhaps even simpler, ##C = \{1 \}##, ##D = \emptyset##.

Last edited:
Yes, that's indeed very simple. Thanks