What's the difference between a dense set and an uncountable set?

Question

I once called a dense set an uncountable set. I was told this was wrong, as the set was dense, and not uncountable. I didn't have the mathematical knowledge to find this confusing, and instead thought I was just mistaken. I still reckon I'm mistaken, but now I don't understand why.

A set $X$ is dense iff $\forall x,z \in X$ where $x <z, \ \exists y \in X$ s.t. $x < y <z$.

A set is uncountable if you can't ever count the members in any subset of it. So, let's take the set of naturals. I of course can't count all of the members within the naturals, but I can count all the members in any finite subset of the naturals (of course, since the subset is finite).

The problem with an uncountable set, like the set of real numbers, is that finite subsets (that include all members between the lower and upper limits) don't exist. $|[x,z]| = \infty \ \forall x,z \in \Bbb R$ There's an infinite number of members between any two members, and thus all subsets are infinite, which makes counting impossible (hence, uncountable).

Now, maybe there's way to achieve this uncountability without the set being dense. I just don't see how. Surely, a dense set is an uncountable set and vice versa?

EDIT:

I took user Pilcrow's adivce, and looked at a proof of the countability of the rationals. If I understand correctly, a set being countable means that there is a formula or algorithm for the next member in line. So, for the rationals, that algorithm could be expressed like this:

$\frac ab$ is a rational. $n(\frac ab)$ is the next rational (next defined by an ordering not of the greatness kind).

$$n(\frac ab) = \begin{cases} \frac{a+1}{b} & a+1 < b \\ \frac{1}{b+1} & a +1 = b \end{cases}$$

This would create a countable, ordered multiset, of which the rationals would be a subset. Thus, the rationals are countable (I assume it's impossible to have uncountable subsets of countable sets).

From this, I gather that if a poset is dense, it just means that there is no formula/algorithm for the next member, if one is enumerating using the ordering of which the density arises from. To be concrete, $n(\frac ab)$ is undefined if its ordering is so that it is the next number greater than $\frac ab$. There is no such number, because the rationals are dense when using the greatness ordering.

So, now my question is, is this new understanding correct?

Answer 1

What you write is seriously confused in many ways. I am not saying that to put you down, but rather to get you back on track.

1. The notion of density is only applicable to subsets of ordered sets, whereas for any set it makes sense to ask whether it is countable or uncountable. (More generally, there is a certain topological notion of density, but this is not directly relevant to your question.)

2. Your definition of density is incorrect. A subset $X$ of a given poset is dense if for each $x \in X$ and $z \in X$ such that $x < z$, there is some $y \in X$ with $x < y < z$. This is different from your proposed definition, according to which no non-empty set would be dense.

3. "A set is uncountable if you can't ever count the members in any subset of it." A set $X$ is countably infinite if there is a bijection between $X$ and the set $\mathbb{N}$ of all natural numbers. A set if uncountable if it is infinite but not countably infinite. It has nothing to do with subsets. Besides, every uncountable set contains a countable subset (for example, $\mathbb{R}$ contains $\mathbb{N}$ as a subset), so your definition is simply wrong.

4. "I of course can't count all of the members within the naturals, but I can count all the members in any finite subset of the naturals (of course, since the subset is finite)." You can count all the members of any finite subsets of any set, for example, you can count all the member of any finite subset of $\mathbb{R}$. That does not mean that $\mathbb{R}$ is countable.

5. "The problem with an uncountable set, like the set of real numbers, is that finite subsets don't exist." False, any set contains a finite subset. You seem to be confusing subsets with intervals.

6. The notation $\mathbb{R}_{x}^{z}$ does not mean anything unless you explain it further. My guess is that you mean either the open interval $(x, z)$ or the closed interval $[x, z]$.

7. The set $\mathbb{Q}$ of all rational numbers with the standard order is dense but it is countable. So you can have a dense but countable set. Conversely, you can have an uncountable set with an order on it which is not dense, such as the first uncountable ordinal $\omega_1$ or the so-called Cantor set (which is a certain subset of $\mathbb{R}$).

Answer 2

I am assuming that you are talking about subsets of $\Bbb R$ here. Then:

• $\Bbb Q$ is dense, but it is not uncountable.
• $[0,1]$ is not dense, but it is uncountable.

So, yes, these are distinct concepts.

Answer 3

A dense subset $S$ of a set $X$ is a set whose closure $\bar{X}$ is equal to the set $X$. A countable set is one for which there exists a bijection with the natural numbers. The rationals are countable and the argument is for constructing the bijection with the naturals is standard.

A related concept is that of a separable set $X$, $X$ is separable if it contains a countable dense subset.

Answer 4

I'm afraid there are a lot of misconceptions here. Let's see what we can do about straightening out at least some of them.

You have a correct definition of "dense" in an ordered space, such as $\Bbb R$. (A small quibble -- one generally speaks about one space being dense in another, but if we're specifically talking about ordered spaces, it makes sense to talk about the space simply being dense.) There is actually a more general definition of "dense" in topological spaces that doesn't require an order relationship, but for the moment we can work in an ordered space.

An infinite set $S$ is "countable" if there is a $1$-$1$ map $f: \Bbb N \to S$ that is surjective. In other words, it's countable if there is some way (not necessarily the obvious way) to use the natural numbers as an index that lists all possible elements of $S$. Note that this has nothing to do with whether they're "sprinkled" into your universe so thickly that a member of $S$ can always be found between any two elements.

The rational numbers $\Bbb Q$ are dense (either in themselves or in the real numbers $\Bbb R$) because there is always a rational number that is strictly between any two numbers (whether real or rational). But it's not hard to see that it's possible to list all possible rational numbers -- there are many standard proofs of that fact -- so the rationals are countable.

Conversely, there are lots of uncountable sets of real numbers that aren't dense. Just take pretty much any set of real numbers that includes a gap. There are even uncountable sets of real numbers that are "nowhere-dense" -- a famous example is called the Cantor set.