Showing the bijection between countable dense subset of a metric space $E×\mathbb{Q}→$neighborhoods of $E$ with rational radius

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

-
$N(p,q)$ is your notation for an open ball around $p$ of radius $q$? –  Martin Sleziak Aug 6 '12 at 9:08
@Martin yes, sir –  Katlus Aug 6 '12 at 9:10

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.

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

This can be done by induction, in the inductive step you choose $r_i < \min \{d(p_i,p_j); j<i\}$. (Note that $\{d(p_i,p_j); j<i\}$ 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<i$. Therefore any two sets $N(p_i,r_i)$ and $N(p_j,r_j)$, $i\ne j$, are different.)

-
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. –  Katlus Aug 6 '12 at 9:20
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$. –  Martin Sleziak Aug 6 '12 at 9:23
Perhaps related: this question and this question. –  Martin Sleziak Aug 6 '12 at 9:26
@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.) –  Martin Sleziak Aug 6 '12 at 9:39
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$?? –  Katlus Aug 6 '12 at 11:05