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

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

• This claim is untrue. Notably, consider $Y\subset X = \mathcal P(2\mathbb N)$. It is obvious that there is a bijection between $Y$ and $\mathcal P(\mathbb N)$, and $Y$ is a proper subset of $X$. ($Y$ is a subset of $X$ since any subset of $2\mathbb N$ has the property that its complement contains all the odds.) – Don Thousand Aug 10 '19 at 14:42
• so you're claiming that $|X| = \aleph_0$? – Jneven Aug 10 '19 at 14:43
• but that's what i'm claiming... – Jneven Aug 10 '19 at 14:44
• Just to make the result clear, the set $X$ defined at the beginning is uncountable, since every subset of the even integers is a element of $X$, and there are uncountable many subsets of the even integers (by the obvious bijection between P(N) and P(2N) ). – Ned Aug 10 '19 at 15:15
• @Jneven I meant {0,2,4,6, .... }, the even non-negative integers, sorry if my comment was confusing (not that the whole argument would be any different for Z and 2Z). The point is that X has a subset which is the power set of an infinite set (i.e. the power set of 2N is a subset of X) and so X must be uncountable since the power set of 2N is uncountable. – Ned Aug 11 '19 at 20:06

## 4 Answers

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.

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

• $|P(\mathbb N)| =\aleph$ is either wrong or really bad notation, depending on what the definition of $\aleph$ is. – spaceisdarkgreen Aug 14 '19 at 0:33
• Ok, the latter then. – spaceisdarkgreen Aug 14 '19 at 13:19
• @spaceisdarkgreen I mean of course $\aleph = 2^{{\aleph}_{0}}$ – Jneven Aug 14 '19 at 14:21
• @Jneven That's not a standard notation, though. – Noah Schweber Aug 17 '19 at 15:22
• @NoahSchweber I agree. therefore Decided to change it. – Jneven Aug 17 '19 at 15:48

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.

• I'm not sure what you mean. $A^c$ is $\mathbb N\setminus A$, that's it. – user524154 Aug 18 '19 at 20:52

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$$ ?

• You are misunderstanding the question; this does not actually address the problem at hand (and your second line has a left bracket that is never closed...) – Arturo Magidin Aug 13 '19 at 15:43
• "You are misunderstanding the question"- yes, you probably right. – cisco_guy Aug 13 '19 at 18:39