I was in a discussion where I argued that the density of two sets of the same cardinality could be different in respect to the infinite range of non-negative integers. Does cardinality imply that any set of ${\aleph_0}$ has equal density to any other set of the same ${\aleph_0}$?

Also, does cardinality imply equivalence in set size? Or is a formal ranking of different tiers which cannot be compared?

Ok, got that so far. Expanding question now:

Densities can be different but the count is the same. Infinite == Infinite iff cardinality is equivalent. Why doesn't a different density imply infinite set != infinite set even if cardinality is equivalent?

  • 2
    $\begingroup$ You might want to give the definitions of "Cardinality" and "Density" you're familiar with, as your question seems to be answered directly from those definitions. $\endgroup$ – Gadi A May 20 '11 at 16:31
  • $\begingroup$ Well, I understand that cardinality asserts that any subset of non-negative integers can be mapped to the non-negative integers, implying that the cardinality is the same ${\aleph_0}$. However, the density (percentage of occurances over the range of 0 - f(n)) would be different. Such that the density of 2^n over 0 - 2^n would be less than the density of n over 0 - 2^n. Meaning there's less exponents of two than there are integers over any range, therefore there's less density of exponents of two over infinite range. $\endgroup$ – Lee Louviere May 20 '11 at 16:36
  • $\begingroup$ For example. 2^0 = 1, so over the interval 0-1, there are 2 non-negative integers, but only 1 2^n. Therefore 2^n is half as dense. Over a range of 0-infinity, there are infinite integers and infinite 2^n, however, 2^n is less dense. $\endgroup$ – Lee Louviere May 20 '11 at 16:40
  • $\begingroup$ The reason why I think this matters is if you take an infinite range, from a destination outward, and say you choose to teleport to a random integer, the probability of landing on an integer is 1, but the probability of landing on 2^n is far less. $\endgroup$ – Lee Louviere May 20 '11 at 16:43
  • 2
    $\begingroup$ Xaade: one cannot choose (teleport to, in your parlance) a random integer, that is, choose one uniformly over the integers. $\endgroup$ – Did May 20 '11 at 16:54

Let $\mathbb{N}$ refer to the positive integers. Usually we define the density of a subset $A\subset \mathbb{N}$ with respect to the integers to be $$\lim_{N\rightarrow\infty}\frac{|\{m\in A:m\leq N\}|}{N}.$$ For example, the set of even numbers $$\{2,4,6,\dots\}$$ has density $\frac{1}{2}$. From this, it is not hard to see that for any $c\in[0,1]$ you can find a set with density $c$.

Notice that if $c>0$ this automatically implies the set has cardinality $\aleph_0$, but it is also possible to have a set of density $0$ with cardinality $\aleph_0$. For example, the set of powers of $2$, or the set of prime numbers.

Hope that helps,

| cite | improve this answer | |
  • $\begingroup$ Ok, so densities can be different but the count is the same. Infinite == Infinite iff cardinality is equivalent. Because I don't understand how density doesn't play a part in count. $\endgroup$ – Lee Louviere May 20 '11 at 16:46
  • $\begingroup$ @Xaade: One this worth mentioning about density, (this is referring to your previous comments above) is that we always define it looking at the density up to $x$, and then taking a limit. For example, for the powers of two, we look at the density up to $x$ and see that there are about $\log_2 x$ powers of $2$ less then $x$, but a total of $x$ numbers. Since $\frac{\log_2 x}{x}$ goes to zero as $x\rightarrow \infty$ we see that the density is $0$. There are still infinitely many powers of two, and they have the same cardinality as the natural numbers because we can create a bijection) $\endgroup$ – Eric Naslund May 20 '11 at 16:54
  • $\begingroup$ Also worth noting is that somtimes this limit does not exist, and so some sets (e.g., the set of natural numbers whose first digit is 1) don't even have a density. $\endgroup$ – MartianInvader May 20 '11 at 18:32
  • 1
    $\begingroup$ @MartianInvader: Good point, and on top of that we could mention that logarithmic density, and how sometimes some sets have a logarithmic density but not a natural density. (Such as the numbers whose first digit is one) If the natural density exists, then so does the logarithmic, and they must equal. A great example of where the natural density does not exist is the set of natural numbers for which $li(x)>pi(x)$. It provably does not have a natural density, but under sufficient hypotheses (LI,RH) has a logarithmic density. $\endgroup$ – Eric Naslund May 20 '11 at 18:43
  • $\begingroup$ @Eric Naslund: LI? $\endgroup$ – Charles Jun 16 '11 at 16:41

I think that it is not completely clear to you what cardinality and density means.

Firstly cardinality is the "rawest" notion of size. For two sets to have the same cardinality they need only a bijection, which is to say "There exists a table with two columns, one for each set, and all the elements appear exactly once in that column."

The notion which you describe is called Dedekind infinite, which is to have the same cardinality as a proper subset.

As for density, this can be treated in several aspects:

  • A dense ordered set is a set such that for every $x,y$ there is $z$ which is strictly between them. The rationals are such set, the positive integers are not.
    If there is a first and/or last point (for example all the non-negative rationals which are less or equal to one) then it is customary to exclude the end points from the density criteria and say that there is a first/last point as well.
  • Topological dense sets: if $A$ is a topological space then $D\subseteq A$ is dense in $A$ if and only if its intersection with every open set is nonempty. The rationals are dense in the real numbers, in this sense, since every non empty interval contains a rational point inside it.

If the topological space is endowed with a linear order topology (e.g. the real numbers) then a dense set in the topological sense is a dense order as well (although not vice versa, consider all the real numbers versus the rationals between $-1$ to $1$)

The real numbers give example of a very large space (its cardinality is continuum) with a very small (countable) subset which is dense (topologically).

The third notion of size is measure, which roughly translates to volume. A large set is a set of positive measure (or equal measure to the measure of the entire space).

The Lebesgue measure is a way to determine the volume of subsets of the real numbers in the way we want it to work, that is if we just shift around the set it will not change its volume and if we stretch it the volume will increase as the factor we stretched by.

One can build a set which is of Lebesgue measure $0$ (i.e. has no volume at all), not dense at any point (that is if a point is outside the set then it has an open interval which does not intersect this set) and yet it is of the cardinality of the continuum. This can be generalized to have any volume that we want as well.

Therefore the notions are hardly related, if we have a very small (in cardinality) set which is dense (large topologically) and another set which is very large in cardinality but topologically speaking is very very small.

To sum up, there are many different ways to measure how big a set is and it gets more and more complex with every new technique you acquire (filters, cofinality, and more). They may or may not be related or correlated, but the case is usually that we want a new way of "sizing" up sets, mostly because the ones we have are insufficient or cumbersome for the task at hand.

| cite | improve this answer | |
  • $\begingroup$ Topology is hardly understandable. I need a visual interpretation, and there aren't many that describe what I need. $\endgroup$ – Lee Louviere May 20 '11 at 18:09
  • $\begingroup$ Xaade: I find it hard to describe how to visualize immense cardinalities and complicated mathematical structures. And personally I cannot really visualize "simple" things, I never really could tool. $\endgroup$ – Asaf Karagila May 20 '11 at 18:16
  • $\begingroup$ @Xaade: This tries to illustrate a nowhere-dense set with positive measure. $\endgroup$ – Henry May 20 '11 at 19:34

Subsets of the naturals can have different natural densties. If the natural density is greater than zero, the subset is countably infinite. Think of all the naturals (density 1) and the even numbers (density 1/2). But there are infinite subsets with natural density zero and infinite subsets for which the natural density cannot be defined.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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