2
$\begingroup$

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?

$\endgroup$
9
  • 5
    $\begingroup$ "The problem with an uncountable set, like the set of real numbers, is that finite subsets don't exist." This is not true. $\endgroup$ Feb 28, 2022 at 23:05
  • 1
    $\begingroup$ $\{1,2,3\}$ is a finite subset of $\Bbb R$ $\endgroup$
    – pancini
    Feb 28, 2022 at 23:05
  • 1
    $\begingroup$ "Dense" means that there are no holes. "Uncountable" means just that, not enumerable or not able to be placed in an exhaustive list. You can find subsets of $\mathbb{R}$ that are just dense, just uncountable, neither, or both. For instance, the set of all real numbers with no "1"s in their ternary expansions is uncountable, but not dense; it has holes. $\endgroup$
    – mjqxxxx
    Feb 28, 2022 at 23:08
  • $\begingroup$ @TheoBendit See my edit. I was imprecise in my wording. $\endgroup$
    – user110391
    Feb 28, 2022 at 23:58
  • 1
    $\begingroup$ @user110391 density is a property one set can have in another set with a given topology. it doesn't inherently have anything to do with partial orderings or cardinality. $\endgroup$
    – pancini
    Mar 1, 2022 at 11:03

4 Answers 4

9
$\begingroup$

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

$\endgroup$
15
  • $\begingroup$ First of all, I have to correct my wording in the original post. I meant that there are no finite subsets of the reals of which all the members between the smallest and greatest members are included. Or in other words, all intervals have an infinite cardinality. As for 2., I agree, and I think maybe you brought it up because I didn't mention (in the OP) that $y$ too was a part of $X$. I didn't explicitly state that my $<$'s were of the greatness relation, so my definition was general enough to apply to any poset $X$. $\endgroup$
    – user110391
    Mar 1, 2022 at 0:12
  • $\begingroup$ The rest of the points seem to stem from my inadequate wording. If I'm correct, 7. is the point that adresses my question the most directly, but it's not enough for me to understand. I don't see how a dense set can have a bijection to the naturals. Thus, I don't see how a dense set can be countable. Thus, I don't see the difference between a dense and an uncountable set. $\endgroup$
    – user110391
    Mar 1, 2022 at 0:14
  • 1
    $\begingroup$ @user110391 Then you should look into the proof that the rationals are countable and ask a more specific question about whichever part of the proof it is that you find hard to follow. Again, you are bringing up order in contexts which have nothing to do with order. A set is countably infinite if it is in bijection with the natural numbers. This bijection is not required to preserve any order. $\endgroup$
    – Pilcrow
    Mar 1, 2022 at 0:17
  • 1
    $\begingroup$ Density is not only applicable to ordered sets. Neither $\mathbb{R}^2$ nor $\mathbb{Q}^2$ are ordered, yet $\mathbb{Q}^2$ is dense in $\mathbb{R}^2$. $\endgroup$
    – robjohn
    Mar 1, 2022 at 7:27
  • 1
    $\begingroup$ @Pilcrow: restricting density to ordered sets is going cause confusion as well. $\endgroup$
    – robjohn
    Mar 1, 2022 at 11:33
4
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ There are also uncountable sets which are nowhere dense, such a Cantor set $\endgroup$
    – Henry
    Feb 28, 2022 at 23:27
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .