Equivalence Relations and Counter Examples for Equinumerous Sets

[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 ?

 

[PeroK]

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

 

[issacnewton]

Thanks PeroK. Can you come up with simpler counterexample ?

 

[PeroK]

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$.

 

[issacnewton]

Yes, that's indeed very simple. Thanks