1
$\begingroup$

Let us denote the set of equivalence relations $B$. So, the first direction is to say that the number of equivalent relations won't exceed the number of relations, that is $|P(A\times A)|=2^a$.

Now, for the other direction(inequality, $|B|\ge 2^a$) is a bit more complex for me. What I did in my exam is saying that from every subset $K$ of $A$ I can create the distribution $\{K,A\setminus K\}$ (Considering that the set of distributions of $A$ is isomorphic to the set of equivalence relations.). The problem is, I can't create an injection with it because for every image $H$ such that $H$ is a distribution of $A$, I have two sources. Since my teacher never defined $\left|{P(A)\over 2 }\right|$, how can I overcome it?

I would really appreciate your help.

$\endgroup$
3
  • 1
    $\begingroup$ Split $ A $ into two sets $ B, C $ of size $ a $, and count the equivalent relations with exactly two classes, one of them a subset of $ B $. Note that a modicum of the axiom of choice is used here and in your computation of an upper bound. Indeed, without choice it is consistent that for some infinite sets $ A $, the number of equivalence relations is not $2^{|A|} $. $\endgroup$ Mar 12 '15 at 18:04
  • $\begingroup$ How do you derive that one of the classes is in B? Suppose I take $D=B\cup \{x\}$ where $x\in C$. Then it's not in $B$. How can I know that $A\setminus D$ is in $B$? $\endgroup$ Mar 12 '15 at 18:27
  • $\begingroup$ I think what Andres is proposing is to only take those partitions where one of the classes is a subset of $B$ and ignore the rest, then the subsets of $B$ are in one-to-one correspondence with those partitions. Since $B$ is of size $a$, then there must be $2^a$ of those partitions. The size of $C$ is actually immaterial as long as it is not empty, to ensure that in any partition of $A$ at most one of the classes is a subset of $B$. $\endgroup$
    – askyle
    Mar 12 '15 at 19:24
1
$\begingroup$

We have that the cardinality of $\{A_0 \subseteq A \mid |A_0| > 1\}$ is $2^a$.

Now, for every $A_0$ in this set, define $\sim_{A_0}$ by:

$$a \sim a' \iff a = a' \lor \{a,a'\} \subseteq A_0 $$

Then $A_0 \mapsto \sim_{A_0}$ is an injection, so that $|B| \ge 2^a$ as desired.

$\endgroup$
1
$\begingroup$

Take some element from $A$, say $x$. Now let $A'=A\setminus\left\{x\right\}$; since $A$ is infinite there is a bijection between $A$ and $A'$, and therefore between their respective power sets. Now you can make an injection from $\mathcal{P}(A')$ to $B$ by mapping $C\subseteq A'$ to the partition $\left\{C, A\setminus C\right\}$. Note that $A\setminus C$ is not a subset of $A'$ so the ambiguity in your original argument does not happen; now you can proceed with it and complete the proof ☺

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.