Prove $\langle P(\omega),\subseteq\rangle $ has chains with same cardinality as $P(\omega)$

214 Views Asked by At

This is solved in ZF btw.

So I had a go at this problem and used the fact that there is a bjjection between $\mathbb{N}\to\mathbb{Q}$. So now we know that $P(\omega)$ has the cardinality of the continuum so we are looking for a chain with the cardinality of the continuum.

We can now construc the sets for every $r \in \mathbb{R}$ we have $X = \{x\mid x\in \mathbb{Q}\text{ and }x \lt r\}$.

Then if we take the collection of all of those sets then for every $a,b \in \mathbb{R}$ if $a<b$ then $X_a \subseteq X_b$.We have a one to one mapping with $\mathbb{R}$ which is the cardinality of the continuum and the collection of all of those sets is a chain.

Is this somehow true?

What kind of stops me as well is how do we actually compare real and rational numbers in set theory?I looked over Dedekind cuts but still can't see how can I compare two elements by using them.

1

There are 1 best solutions below

1
On BEST ANSWER

It looks like you know how to solve the problem in the title, but that you have some confusion about how $\mathbb{R}$ is constructed from $\mathbb{Q}$ using Dedekind cuts, and how this allows us to compare rational numbers with real numbers. Perhaps you're also worried that the 'definition' $X_r = \{ x \in \mathbb{Q} \mid x < r \}$ is circular, since it uses a real number $r \in \mathbb{R}$ in the definition of the Dedekind cut.

...so I'm going to go through the Dedekind cut construction of $\mathbb{R}$ from $\mathbb{Q}$, use it to clarify how rational numbers and real numbers can be compared, and clarify what '$X_r$' actually means without being circular about it.

Here we go. Once you've constructed $\mathbb{Q}$, you can define $\mathbb{R}$ to be the set of subsets $D \subseteq \mathbb{Q}$ that are non-empty, bounded above and downward-closed. This is the Dedekind cut** construction. Thus the elements of $\mathbb{R}$ are particular subsets of $\mathbb{Q}$.

From this, we obtain an embedding $\mathbb{Q} \hookrightarrow \mathbb{R}$ defined by $$a \mapsto X_a := \{ x \in \mathbb{Q} \mid x<a \}$$ This defines what '$X_a$' means when $a \in \mathbb{Q}$.

The ordering on $\mathbb{R}$ is given by inclusion of subsets. We can therefore define the notation '$a \le r$', when $a \in \mathbb{Q}$ and $r \in \mathbb{R}$, to mean $X_a \subseteq r$.

This then allows us to define the notation '$X_r$' for arbitrary $r \in \mathbb{R}$ by $$X_r := \{ x \in \mathbb{Q} \mid x < r \} \subseteq \mathbb{Q}$$ This is kind of silly, since then we have $X_r = r$. But psychologically it makes sense to do this: we want to think about '$r$' as being a real number, but $X_r$ as being a set of rational numbers.

But now that we've gone through this, the map $\mathbb{R} \to \mathcal{P}(\mathbb{Q})$ given by $r \mapsto X_r$ is an order-preserving injection, and composing with the bijection $\mathcal{P}(\mathbb{Q}) \to \mathcal{P}(\mathbb{N})$ induced by your favourite bijection $\mathbb{Q} \to \mathbb{N}$ gives the desired result.


**Some people like their Dedekind cuts to be pairs $(A,B)$ where $(A,B)$ is a partition of $\mathbb{Q}$ and $A$ satisfies the properties I mentioned. I find this to be redundant, since we can just take $B = \mathbb{Q} \setminus A$, anyway.