1
$\begingroup$

Let $X$ be a separable metric space. Let $E$ be a countable dense subset of $X$.

Let $p_i$ enumerate $E$ and $q_j$ enumerate $\mathbb{Q}$. Let $G=\{N(p_i,q_j) \subset X | i,j\in \omega\}$ Then $G$ is a base for $X$.

Can one show the bijection between $E×\mathbb{Q}$ and $G$ in ZF?

I want to show that $G$ is countable, and since $E×\mathbb{Q}$ is countable, if i can show the bijection, proof will be done. Help

I don't know whether $f:(p,q)→N(p,q)$ is a bijection and even if it is a bijection, i have no idea how to show that $f$ is injective..

  • 0
    $N(p,q)$ is your notation for an open ball around $p$ of radius $q$?2012-08-06
  • 0
    @Martin yes, sir2012-08-06

1 Answers 1

0

The map $(p,q)\mapsto N(p,q)$ is not necessarily bijection. Take $X=E=\mathbb Z$ as an example. (For any $z\in\mathbb Z$ the ordered pairs $(z,\frac1n)$ are mapped to the same set $N(z,\frac1n)=\{z\}$.)

However, you can take some well-ordering on $E\times\mathbb Q$ and define $$N(p,q)\mapsto \min\{(a,b)\in E\times\mathbb Q; N(a,b)=N(p,q)\}.$$ (If you prefer, you can get a well-ordering of order type $\omega$ on the set $E\times\mathbb Q$. This can be obtained using any bijection between $E\times\mathbb Q$ and $\omega$. Since you are given enumeration of $E$ and $\mathbb Q$, exhibiting such a bijection does not need axiom of choice.)

The image of this map is a subset of countable well-ordered set $E\times\mathbb Q$. Therefore it is again a countable well-ordered set. So it is in bijection with some countable ordinal.


Additional question in your comment:

How do I show that $G$ is not finite.

If $E$ is infinite, then $G$ cannot be finite.

Just show by induction on $i$ that for each $p_i$ you can find $r_i\in\mathbb Q$ such that $N(p_i,r_i)$ is different from $N(p_j,r_j)$ for each $j.

This can be done by induction, in the inductive step you choose $r_i < \min \{d(p_i,p_j); j. (Note that $ \{d(p_i,p_j); j is a finite set of positive real numbers, so the minimum of this set is a positive real number and there exists a rational number smaller than this minimum.)

Then $i\mapsto N(p_i,r_i)$ is an injective map $\omega\to G$. (The point $p_i$ is contained in $N(p_i,r_i)$, but it does not belong to any of the sets $N(p_j,r_j)$ for $j. Therefore any two sets $N(p_i,r_i)$ and $N(p_j,r_j)$, $i\ne j$, are different.)

  • 1
    you're right and i've tried this too! But my definition of 'countable' is cardinality of which is $\aleph_0$. How do i show that $G$ is not finite.2012-08-06
  • 0
    Then probably *at most countable* should be used at some places. (Finite discrete space is separable, in this case the set $E$ will be finite.) However, if you have an infinite subset of $\omega$, the order type of this set is again $\omega$.2012-08-06
  • 0
    Perhaps related: [this question](http://math.stackexchange.com/questions/107617/an-infinite-subset-of-a-countable-set-is-countable) and [this question](http://math.stackexchange.com/questions/168814/proving-every-infinite-subset-of-countable-set-is-countable).2012-08-06
  • 0
    @Katlus I've added some argument showing that $G$ is infinite whenever $E$ is infinite. (This seems to be more relevant for your question *"How do I show that $G$ is not finite"* then the two comments I wrote before.)2012-08-06
  • 0
    I tried to understand this for an hour and still i can't.. Would you give me some more explanation on induction? Plus, isn't choosing $q_i$ consequence of AC$_\omega$??2012-08-06
  • 0
    Now i got it. I think $q_i$ should be defined as min$\{d(p_i,p_j)|j instead. Anyway this proof is beautiful!2012-08-06
  • 0
    @You don't need AC to choose from system of non-empty subsets of $\mathbb Q$ since $\mathbb Q$ is well-ordered. (We can explicitly write down a [formula](http://en.wikipedia.org/wiki/Formula_%28mathematical_logic%29) in the language of [first order logic](http://en.wikipedia.org/wiki/First_order_logic) which describes a well-ordering of $\mathbb Q$.) It is discussed [this answer](http://math.stackexchange.com/a/146452/) and the comment following it. Choosing a rational number from a non-empty interval is also described in [this answer](http://math.stackexchange.com/a/98968/).2012-08-06
  • 0
    In addition to this, you have started with some given enumeration $\mathbb Q=\{q_i; i\in\omega\}$. If we have such an enumeration/bijection, we can transfer well-ordering from $\omega$ to $\mathbb Q$.2012-08-06
  • 0
    About you last comment: We want $q_i$ to be a rational number; we do not know whether $\{d(p_i,p_j)|j is rational. (BTW only now I've noticed that I am using $q_i$ in two meanings - the rationals from the inductive construction and the enumeration of $\mathbb Q$. I hope it is not too confusing. I'll edit the post to correct this, but I can't change it in the comments.)2012-08-06
  • 0
    You are absolutely right. I got it completely. Thank you.2012-08-06