6
$\begingroup$

I came across this long proof on this site:

Cardinality of relations set

But I would like to know whether my direction can work.

Say we want to find the cardinality of all equivalence relations in $\mathbb{N}$. Since it is a subset of all relations in $\mathbb{N}$, I conclude it has a cardinality smaller or equal to $\aleph$. Now, define an injective function from $P(\mathbb{N})$ to the set of equivalence relations by matching each subset of $\mathbb{N}$ with the identity relation (which is an equivalence relation in $\mathbb{N}$.

Therefore the cardinality of all equivalence relations in $\mathbb{N}$ is greater or equal to $\aleph$ and using CSB we get the desired result.

Seems legit?

$\endgroup$
6
  • 1
    $\begingroup$ Already wanted to upvote your previous question but was marked as duplicate. Was not too sure why to be honest. $\endgroup$ – Pedro Jun 3 '15 at 1:21
  • $\begingroup$ "subgroup of $\mathbb{N}$"? $\endgroup$ – mlbaker Jun 3 '15 at 1:22
  • $\begingroup$ Oops. In Hebrew the word for "group" is used to describe a "set". Quite confusing. Will edit. $\endgroup$ – Whyka Jun 3 '15 at 1:24
  • $\begingroup$ I don't think you're using $\aleph$ correctly (you seem to be using it for the cardinality of the powerset of $\mathbb{N}$). You may prefer to write: "I conclude it has cardinality smaller than or equal to $2^{|\mathbb{N}|^2},$ and hence cardinality smaller than or equal to $2^{\aleph_0}$." $\endgroup$ – goblin GONE Jun 3 '15 at 1:44
  • $\begingroup$ Isn't $2^{\aleph_0}$ equal to $\aleph$? $\endgroup$ – Whyka Jun 3 '15 at 1:48
3
$\begingroup$

Your approach is sound. I think you can choose a better injection from $P(\mathbb{N})$ into equivalence relations. Let us say $0 \in \Bbb N$ and we will inject $P(\Bbb N \setminus\{0\})$ into the equivalence relations on $\Bbb N$. I would suggest you take a subset of $\Bbb N \setminus\{0\}$ to the equivalence relation that groups all members of the subset and $0$ into an equivalence class and leaves all the rest of $\Bbb N$ under the identity.

If we don't do the trick with $0$, all singleton subsets will be mapped to the identity relation and you don't have an injection.

$\endgroup$
0

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.