0

The relation ~ is defined on P(N): A~B if |A| = |B|.

I need to prove that the cardinality of the equivalence classes is countable.

Any ideas??

Itay4
  • 2,166
  • I think that must use the continous hypotesis... – Martín Vacas Vignolo Jan 02 '17 at 20:24
  • 1
    Continuum hypothesis is definitely not required here. If $A\subset \mathbb{N}$ is infinite, then it is countably-infinite. The only remaining ones are the finite sets, so define a function $\mathbb{N} \to \mathcal{P}(\mathbb{N})/\sim$ by sending $0$ to $[\mathbb{N}]$, and $n$ to $[{1,\ldots, n-1}]$ for $n\geq 1$. – Hayden Jan 02 '17 at 20:30
  • Is there any more context? What is $P(N)$ here? – The Count Jan 02 '17 at 20:30
  • @Hayden I think I got it. Shouldn't the function be defined n to [(1,..,n}]? – Itay4 Jan 02 '17 at 20:43
  • In that case, you'd miss $[\emptyset]$, which was intended to be the image of $1$ (a notation like ${1,\ldots, n-1}$ is usually meant to denote the empty set when $n-1 < 1$). – Hayden Jan 02 '17 at 21:28
  • I see it now, thanks ! – Itay4 Jan 02 '17 at 21:44

1 Answers1

0

Hint: The cardinalities of the subsets of $\mathbb{N}$ are the natural numbers themselves and $\aleph_0$ ($=|\mathbb{N}|$), so this amounts to proving that the set $\mathbb{N} \cup \{ \aleph_0 \}$ is countable.

Clive Newstead
  • 64,925