3
$\begingroup$

Given $M=\{ A \in P( \mathbb{N} ) \mid A\text{ and } \overline{\rm A}\text{ are infinite} \}$

What is the cardinal of set $M$?

I thought to find the cardinal of $\{ A \in P( \mathbb{N} ) \mid A\text{ finite}\}$ and cardinal of $\{ A \in P( \mathbb{N} ) \mid \overline{\rm A}\text{ finite}\}$

But can't see how it helps.

Thanks

$\endgroup$
3
$\begingroup$

The set of finite sets, $\{A\in\mathcal{P}(\Bbb N)~:~A~\text{finite}\}$, is a countable set. To see this, consider ordering the sets by the sum of the elements in the set.

We have then the set can be written: $\{\{1\},\{2\},\{1,2\},\{3\},\{1,3\},\{4\},\{1,4\},\{2,3\},\{5\},\{1,2,3\},\{1,5\},\{2,4\},\{6\},\dots\}$ and it is clear that this pattern can continue, eventually getting any desired finite set.

It follows that the set of co-finite sets, $\{A\in\mathcal{P}(\Bbb N)~:~\overline{A}~\text{finite}\}$, is also countable as there is an obvious bijection between this set and the previous set.

Since it is known that $\mathcal{P}(\Bbb N)$ is uncountable, that $\mathcal{P}(\Bbb N)$ is equal to the disjoint union of the set of finite sets, the set of co-finite sets, and the set of infinite and co-infinite sets, and that the union of countably many countable sets is countable, it follows that the set of sets which are both infinite and coinfinite must be uncountable as well.

$\endgroup$
  • $\begingroup$ $\mathcal{P}( \mathbb{N}) $ is the union of all 3 sets the I wrote in my question? $\endgroup$ – Deb. U Dec 23 '19 at 18:49
  • $\begingroup$ @Deb.U yes, clearly. Note that it is impossible for both $A$ and $\overline{A}$ to simultaneously be finite as that would imply that $\Bbb N = A\cup \overline{A}$ to also be finite which we know to be false. $\endgroup$ – JMoravitz Dec 23 '19 at 18:54
4
$\begingroup$

The cardinality of this set $$ S=\big\{A\subset \mathbb N: |A|=|\mathbb N\setminus A|=|\mathbb N|\big\} $$ is equal to the cardinality of $\cal{P} (\mathbb N)$ or $\mathbb R$.

The see this, we write $\mathbb N=A_0\cup A_1\cup A_2$, where $A_i$ are the positive integers which leave remainder $i$ when divided by $3$.

Clearly, $\mathcal P(A_3)=\mathcal P(\mathbb N)$, and $$ S_1=\big\{A\subset \mathbb N: A=A_1\cup B\,\,\text{where}\,\,B\in\mathcal P(A_3)\big\}\subset S $$ and $|S_1|=|\mathcal P(A_3)|$.

$\endgroup$
3
$\begingroup$

The set is uncountable. For a proof consider the irrational numbers in the interval $[0,1]$. Each such number has infinite many zeros and infinite many ones in the binary expansion, hence every such number can be converted to a set with the desired property by defining $n\in A$ if and only if the $n$-th digit of the binary expansion is one.

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