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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Lee Mosher Aug 27 '19 at 13:52
  • 1
    $\begingroup$ I think you mean $A\subset P(\mathbb{N})$ and $B\subset P(\mathbb{R})$ $\endgroup$ – ZAF Aug 27 '19 at 14:17
  • $\begingroup$ @LeeMosher - thankyou $\endgroup$ – Jneven Aug 27 '19 at 14:40
  • $\begingroup$ We do not have $|B|=2^{\aleph_0}$..... $B$ is countable. $\endgroup$ – DanielWainfleet Aug 27 '19 at 15:32
  • $\begingroup$ I don't see how it is possible to prove that $B$ is countable $\endgroup$ – 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)}$.

  • $\begingroup$ Sidenote, you can do this without the axiom of choice, but it is a bit more work. $\endgroup$ – Floris Claassens Aug 27 '19 at 15:07
  • $\begingroup$ Unfortunately I am trying to this without AC. Do you have a suggestion on that case? $\endgroup$ – Jneven Aug 27 '19 at 15:09
  • $\begingroup$ I've expanded my answer with a possible explicit definition of $f$. $\endgroup$ – Floris Claassens Aug 27 '19 at 15:14
  • 1
    $\begingroup$ 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).$ $\endgroup$ – DanielWainfleet Aug 27 '19 at 15:30
  • $\begingroup$ @DanielWainfleet and also without well order theorem otherwise the exception of AC would be irrelevant $\endgroup$ – Jneven Aug 27 '19 at 15:56

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.