Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
$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
add comment

1 Answer

up vote 0 down vote accepted

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

share|improve this answer
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
show 5 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.