Do equivalence relations work in the "not" case?

53 Views Asked by At

I'm trying to write a proof involving equivalence relations. However, I'm not entirely sure my assumptions are valid.

We know for equivalence relations that $$A \sim B \implies B \sim A$$ $$A \sim B \text{ and } B \sim C \implies A \sim C$$

Does it follow that $$A \not \sim B \implies B \not \sim A$$ and $$A \not \sim C \implies A \not \sim B \text{ or } B \not \sim C?$$

I want to prove that

If $f: A \to B$ and the range of $f$ is uncountable, then the domain of $f$ is uncountable.

Two sets $A_0$ and $B_0$ are equivalent if there exists a bijection between them, which we define a set to be countable if there exists a bijection between the set and the natural numbers.

Here's what I tried:

PROOF: Suppose the domain of $f$, $A$ is countable. Then $A \sim \mathbb N$. Since the range of $f$ is uncountable and the range of $f$ is a subset of $B$, this implies that $B$ is also uncountable. Thus, we have $$A \sim \mathbb N \tag{$A$ is countable}$$ $$B \not \sim \mathbb N \tag{$B$ is not countable}$$ $$A \not \sim B,$$ because one is countable, and the other is not, so there does not exist a bijection between the two. $$A \not \sim B \not \sim \mathbb N$$ $$A \not \sim \mathbb N \not \sim B,$$ which is a contradiction since we assumed $A$ is countable $\implies A \sim \mathbb N$.

Are the last two steps valid? I feel like they contradict the contrapositive of the transitive property.