how to prove that: $|X| = 2^{\aleph_{0}}$, given $X = \{ A\in P(\mathbb{N}) \vert \ |A^{c}| = \aleph_{0} \}$

Question

Let $X = \{ A\in P(\mathbb{N}) | \ |A^{c}| = \aleph_{0} \}$

1. Prove\ Disprove that: $|X| = \aleph_{0}$

My attempt:

1. I'd like to disprove that: $|X|=\aleph_{0}$, By proving that $|X|=2^{\aleph_{0}}$.

For every $A\in X\to A\in P(\mathbb{N})$,then $X\subseteq P(\mathbb{N})\to|X|\leq|P(\mathbb{N})|=2^{\aleph_{0}}$.

Now I'd like to prove that there exists a set, $K$,

such that $|K|=2^{\aleph_{0}}$, and $K \subseteq X$, which will finish the proof.

Suppose by contradiction that there exists no set $K$ as described,

such that: $K\subseteq X$.

Now, let $A=2\mathbb{N}$, then $A^{c}=\mathbb{N}\setminus2\mathbb{N}=\mathbb{N}_{odd}$,

and $|A^{c}|=|\mathbb{N}_{odd}|=\aleph_{0}\to A\in X$.

Notice that for every set $i$, $\alpha_{i}\subseteq2\mathbb{N}:$ $\mathbb{N}_{odd}\subseteq\alpha_{i}^{c}\subseteq\mathbb{N}\to|\alpha_{i}^{c}|=\aleph_{0}$,

therefore for every $i$ and for every $\alpha_{i}$ as descirbed, $\alpha_{i}\in X $.

the collection of all $\alpha_{i}$ exists: $\{\alpha_{i}\vert\ \forall i\in\mathbb{N}:\alpha_{i}\subseteq2\mathbb{N}\}$,hence

$P(2\mathbb{N})=\{\alpha_{i}\vert\ \forall i\in\mathbb{N}:\alpha_{i}\subseteq2\mathbb{N}\}$

hence $P(2\mathbb{N})\subseteq X\Longrightarrow \ 2^{\aleph_{0}}=|P(2\mathbb{N})|\leq|X|$

and this contradicts the assumption,

that there exists no $K\subseteq X:|K|=2^{\aleph_{0}}$.

by Cantor Bernstein we get that $|X|=2^{\aleph_{0}}$.

Answer 1

I'd like to disprove that: $|X|=\aleph_{0}$, By proving that $|X|=2^{\aleph_{0}}$.

For every $A\in X\to A\in P(\mathbb{N})$,then $X\subseteq P(\mathbb{N})\to|X|\leq|P(\mathbb{N})|=2^{\aleph_{0}}$.

Now I'd like to prove that there exists a set, $K$,

such that $|K|=2^{\aleph_{0}}$, and $K \subseteq X$, which will finish the proof.

Suppose by contradiction that there exists no set $K$ as described,

such that: $K\subseteq X$.

Now, let $A=2\mathbb{N}$, then $A^{c}=\mathbb{N}\setminus2\mathbb{N}=\mathbb{N}_{odd}$,

and $|A^{c}|=|\mathbb{N}_{odd}|=\aleph_{0}\to A\in X$.

Notice that for every set $i$, $\alpha_{i}\subseteq2\mathbb{N}:$ $\mathbb{N}_{odd}\subseteq\alpha_{i}^{c}\subseteq\mathbb{N}\to|\alpha_{i}^{c}|=\aleph_{0}$,

therefore for every $i$ and for every $\alpha_{i}$ as descirbed, $\alpha_{i}\in X $.

the collection of all $\alpha_{i}$ exists: $\{\alpha \vert\ \alpha \subseteq2\mathbb{N}\}$,hence

$P(2\mathbb{N})=\{\alpha\vert\ \alpha \subseteq2\mathbb{N}\}$

hence $P(2\mathbb{N})\subseteq X\to \ 2^{\aleph_{0}}=|P(2\mathbb{N})|\leq|X|$

and this contradicts the assumption,

that there exists no $K\subseteq X:|K|=2^{\aleph_{0}}$.

by Cantor Bernstein we get that $|X|=2^{\aleph_{0}}$.

therefore for every $\alpha \subseteq P(2\mathbb{N}), \alpha \subseteq K$,

hence $P(2\mathbb{N}) \subseteq K \to |P(2\mathbb{N})| \leq |K|$, by using Cantor Bernstein theorem we conclude that $|K| = \aleph$.

Answer 2

take $A=\{1,2,3,4\}$

$A^c$={$\mathbb N$ $\setminus ${1,2,3,4}} $

$|A^c|=\aleph_0$ is $|\mathbb N $ $\setminus$ $A^c|$ = $\aleph_0$ ?

Answer 3

might be wrong, this is how I solved it

First I will define a function $ F:X \rightarrow \{{ (a_n)_{n \in \mathbb N } } : a_i = 0 $ infinitely often$, a_n \in \{0, 1\} $ for all $n\} $

Might be a little confusing but this is a function that goes from X to the set of all sequences of ones and zeroes such that 0 appears infinitely often.

The function can be defined as $F(A) = (a_n)_{n \in \mathbb N} : a_k = 1 \Leftarrow\Rightarrow k \in A$

In other words, we map each set to a sequence of ones and zeroes where the kth number is a one if the integer k is in the set A, or a zero otherwise. It is easy to see that the function is well defined, since the complement being infinite is the same as the image of a set having infinite zeroes.

I leave to you the proof that this function is bijective (which it might not be, but I feel like it is)

Once we have this function defined (let's call the codomain B) we have to prove that $|B| = c$, as in B has the same cardinality as the interval [0,1)

We know that $|B| \le c$ since B is a subset of the set of all infinite sequences of zeroes and ones, which has cardinality $2^ {\aleph_0} =c$

To prove that $|B| \ge c$ we can define a function that maps every sequence in $B$ to a number $x \in [0,1)$, knowing that every number in $[0,1)$ can be written in binary as $\sum_{n = 1}^{\infty} a_n2^{-n}$, or $0,a_0a_1a_3...$ where $a_i \in \{0,1\} \forall i \in \mathbb N$

This function is surjective, and so we have $|X| =|B| = c$.

---

Forgot to mention at the end, that every number in this interval (except for 0) can both be written with infinite ones or infinite zeroes. Since every number has this property, we can then prove surjectivity.

Answer 4

Alternatively, here's a different argument.

Let $X=\{A\subseteq\mathbb N:A^c\text{ is countably infinite}\}$, the cocountably infinite subsets of $\mathbb N$. What is this exactly? Well every subset of $\mathbb N$ has a finite complement (so is cofinite) or has a countably infinite complement (so is cocountably infinite), so $X$ is really $\mathcal P(\mathbb N)\setminus\operatorname{Cofin}_{\mathbb N}$.

Next, how big is $\operatorname{Cofin}_{\mathbb N}$? $\mathcal P_{\text{fin}}(\mathbb N)$ is countably infinite and there's a clear bijection from it to $\operatorname{Cofin}_{\mathbb N}$, so $\operatorname{Cofin}_{\mathbb N}$ is countably infinite as well. Hence $X=\mathcal P(\mathbb N)\setminus\operatorname{Cofin}_{\mathbb N}$ is uncountable.

But we're not done yet! How do we know $X$ doesn't have some cardinality strictly between $\mathbb N$ and $\mathcal P(\mathbb N)?$

---

For a bijection showing $\lvert X|=\lvert\mathcal P(\mathbb N)\rvert$, partition $X$ into $\mathcal P_{\text{fin}}(\mathbb N)\cup Y$ where $Y$ is the set of countably infinite, cococountably infinite subsets of $\mathbb N$.

Next, we match this with $\mathcal P(\mathbb N)=\mathcal P_{\text{fin}}(\mathbb N)\cup\operatorname{Cofin}_{\mathbb N}\cup Y$. Map $Y$ to $Y$, biject $\mathcal P_{\text{fin}}(\mathbb N)$ to $\mathcal P_{\text{fin}}(\mathbb N)\cup\operatorname{Cofin}_{\mathbb N}$ and we're done.