# Prove that $|A|\ge |B|$, as $A = \{A_i \vert i \in \mathbb{N}\}, \forall b \in B: b \subseteq \mathbb{R}$

Prove that $$|A|\ge |B|$$, as $$A$$ and $$B$$ are two sets described as follows:

$$A=\{A_i \vert \ i \in \mathbb{N}\}$$, such that $$\forall i,j\in\mathbb{N}:i\neq j: \ A_i\neq A_j\land A_i\cap A_j=\emptyset$$,

$$B$$ is a set constructed of open intervals on $$\mathbb{R}$$,

such that for every $$b_1, b_2 \in B: b_1 \cap b_2 = \emptyset$$, $$\forall b\in B: \ b = (x,y)\subseteq \mathbb{R}$$ ($$x\neq y$$)

Prove: $$|A| \ge |B|$$, or in other words, Prove there exists a injective function $$f: B \to A$$.

My attempt:

As $$B$$ is a collection of open disjoint intervals on $$\mathbb{R}$$, then I'd like to define a partition over $$\mathbb{Q}$$ using the elements of $$B$$. Let this partition be called $$\pi_{B}$$.

By the definition of a partition, then $$|\pi_B| = |\mathbb{Q}| =\aleph_0$$

This allows me to know that there exists a bijection: $$g: \pi_{B} \to A$$, and as $$\pi_B$$ is defined using elements of $$B$$, then there exists an injective function $$h: \pi_{B} \to B$$.

I'd like to find a way to define a composition function of $$h$$ and $$g$$, such that this composition will be a one to one function: $$f: B \to A$$, and from that it will be possible to conclude that $$|A| \ge |B|$$.

But I don't know how to do such thing.

• Your description of the set $A$ has a type error. In your first sentence, you write $A \subset \mathbb N$, so $A$ is a subset of the natural numbers, hence each element of $A$ is a natural number. In your next sentence you write $A = \{A_i \mid i \in \mathbb N\}$, so each $A_i$ is an element of $A$, hence each $A_i$ is a natural number. But later in your second sentence you have the expression $A_i \cap A_j = \emptyset$; ordinarily it does not make much sense to intersect two natural numbers. – Lee Mosher Aug 27 '19 at 13:52
• I think you mean $A\subset P(\mathbb{N})$ and $B\subset P(\mathbb{R})$ – ZAF Aug 27 '19 at 14:17
• @LeeMosher - thankyou – Jneven Aug 27 '19 at 14:40
• We do not have $|B|=2^{\aleph_0}$..... $B$ is countable. – DanielWainfleet Aug 27 '19 at 15:32
• I don't see how it is possible to prove that $B$ is countable – Jneven Aug 27 '19 at 15:40

I will assume that $$B$$ contains no empty intervals.
Note that every interval $$b\in B$$ contains at least one rational number. This follows as $$b$$ is open and non-empty, hence we can find at least two elements in $$b$$, as a singleton set is closed. Since there is always a rational number between every two real numbers we can use the axiom of choice to find a map $$f:B\rightarrow\mathbb{Q}$$ such that $$f(b)\in b$$ for all $$b\in B$$. Note that this map is unique as the intervals in $$B$$ are pairwise disjoint. Let $$g:\mathbb{Q}\rightarrow\mathbb{N}$$ be an injection from $$\mathbb{Q}$$ to $$\mathbb{N}$$. Then $$h:B\rightarrow A,b\mapsto A_{g(f(b))}$$ is an injection.
To do this without the axiom of choice let $$(a,b)$$ be an open interval, Let $$n$$ be the smallest number such that $$2^{-n}\leq b-a$$. Then the set $$X_{(a,b)}=\{z2^{-n}\in (a,b):z\in\mathbb{Z}\}$$ is non-empty and we can define $$f((a,b))=\min X_{(a,b)}$$.
• I've expanded my answer with a possible explicit definition of $f$. – Floris Claassens Aug 27 '19 at 15:14
• Without AC we can define a well-order $<_W$ on $\Bbb Q$ that is order-isomorphic to $\Bbb N$. So for each non-empty $\beta \in B$ we can let $f(\beta)=\min_{<_W}(\beta\cap \Bbb Q).$ – DanielWainfleet Aug 27 '19 at 15:30