3
$\begingroup$

The title is somewhat deceptive: I know that $|\mathbb{Q}|=|\mathbb{Z}|.$

But suppose I wanted to compare the sets, knowing that they are of the same cardinality but still wondering if there was some sense in which Q could be larger. There are two usual ways of thinking about this:

$\mathbb{Z}\subset\mathbb{Q}$ but $\mathbb{Q}\not\subset\mathbb{Z}$

(sorry, there's no \subsetneq symbol on math.stackexachange) and

'For any distinct integers m,n there are infinitely many rationals between m and n.'

These methods both rely on the natural mapping between integers and rationals, to wit: $n\mapsto\frac n1$. What if we didn't have this correspondence, or were working with an application where it wasn't sensible?

That is, we still have the usual order < on Q and Z, and the usual operations + and *, but we no longer have a reason to privilege the usual mapping over, say, $n\mapsto\frac2n$ or a diagonal mapping.

I'm much less concerned about the 'answer' part of the answers than I am of the 'question' part: the main point is 'how could this question be made precise?' rather than answering such question.

  • 0
    @Qiaochu Yuan: Yes. Or any other way you can think of; I'm hoping answers will include measures I haven't though of before.2010-11-15

3 Answers 3

10

As I mentioned in the comments section of Arturo's post, $\mathbb{Q}$ is as large as possible among countable linearly ordered sets.

Said another way, if $X$ is countable an linearly ordered, then there is an order preserving injection $X\rightarrow\mathbb{Q}$. So, if one (partially) orders the set of all countable linearly ordered sets by $X\leq Y$ iff there is a 1-1 order preserving map from $X$ to $Y$, then $\mathbb{Q}$ is the largest element of this set. (To be frank, I'm not positive this satisfies the antisymmetry condition of being a partial order, but whatever).

The proof is quite constructive. The key properties of $\mathbb{Q}$ are that it has no first or last element, and inbetween any two elements of $\mathbb{Q}$ there is another one.

Using these properties, the proof goes as follows:

X is countable so list the elements $X=\{x_1,x_2,...\}$. We will inductively define a function $f:X\rightarrow \mathbb{Q}$.

To start the induction, let $f(x_1)$ be any element of $\mathbb{Q}$. Next, assume $f$ has been defined on $\{x_1,...,x_n\}$ with $f$ injective and order preserving. We now define $f(x_{n+1})$. If $x_{n+1}$ is smaller than all of the previous $x_i$, define $f(x_{n+1}) = q$ where $q$ is any rational number smaller than all of $f(x_1),...,f(x_n)$. Such a $q$ certainly exists since the set $\{f(x_1),...,f(x_n)\}$ is finite. Likewise, if $x_{n+1}$ is bigger than all the previous $x_i$, choose $f(x_{n+1})$ bigger than all of the $f(x_i)$.

Finally, we assume $x_i < x_{n+1} < x_j$ for some previously some $x_i$ and $x_j$ in $\{x_1,...,x_n\}$. Further, we choose $x_i$ from $\{x_1,...,x_n\}$ as large as possible but still less than that $x_{n+1}$, and likewise, choose $x_j$ as small as possible. Then we define $f(x_{n+1})$ to be any rational number in between $f(x_i)$ and $f(x_j)$.

By induction, $f$ is defined for all $x_i$, and this $f$ is the desired injection.

With more care, one can show that if $X$ is dense in itself with no first or last element, then we can arrange for $f$ to be surjective, showing that these properties uniquely characterize $\mathbb{Q}$ up to isomorphism! (The "more care" is to well order $\mathbb{Q}$ and at any stage where a choice is made, to choose the minimal rational number satisfies whatever it has to).

  • 0
    de Vito: it's at least a pre-order, and you can then define a partial order on the set of equivalence classes determined by *forcing* reflexivity.2010-11-16
7

The two statements you give relate to two different issues; the first relates to the fact that there is a natural embedding of $\mathbb{Z}$ in $\mathbb{Q}$ arising from their constructions, and it makes sense to ask whether $\mathbb{Z}$ is a proper subset of $\mathbb{Q}$. This is certainly a sensible question whenever we have two sets $A$ and $B$ and $A$ is given as a subset of $B$. For arbitrary sets it does not make sense, as your comments about "other mappings" show.

The second statement has to do with order, but again with the natural or canonical ordering that both $\mathbb{Z}$ and $\mathbb{Q}$ inherit from the order in $\mathbb{N}$ (which is defined in terms of the successor function). The order of $\mathbb{Q}$ is dense, while the order of $\mathbb{Z}$ is not: $\mathbb{Z}$ is order-isomorphic to subsets of $\mathbb{Q}$, but not the other way around. If you "order" the linearly ordered sets by saying that $(P,\leq)$ is smaller than or equal to $(Q,\preceq)$ if and only if there is an order-preserving injection $P\to Q$, then you get equivalence classes of linearly ordered sets (much in the same way as with cardinals), and in that way of ordering linearly ordered sets, $\mathbb{Z}$ with its natural ordering is strictly smaller than $\mathbb{Q}$, also with its natural ordering. But if you think there is nothing special about the usual embedding $\mathbb{Z}\hookrightarrow \mathbb{Q}$, then presumably you also think there is nothing special about the natural ordering of $\mathbb{Z}$ or $\mathbb{Q}$, and then you can give them orderings that will make it come out "the other way".

So you can certainly make the question "precise" if you specify more information ("as ordered sets with their usual ordering"; "as subsets of $\mathbb{R}$"; etc). But that extra context needs to be explicit to make it make sense.

  • 2
    I also think it's worth pointing out that in the order sense, $\mathbb{Q}$ is as large as possible among countable things. That is, every countable linearly ordered set embeds into $\mathbb{Q}$!2010-11-15
1

I think the intuitive point here is captured in the idea that between -n and n there are only finitely many integers and infinitely many rationals. So over any finite range (and intuitively therefore over the entire range because it is uniform) the density of integers in the rationals is zero. The effort is to carry over the idea of natural density in the sense that there are fewer squares than naturals because the natural density of squares is zero. Natural density is a well defined operation, but may still not capture all the comparisons one would like to make.

In essence, this is captured in a remark on a previous post that cardinality is a coarse way to compare sets. Natural density is finer but demands an ordering. It allows more distinctions to be made, most (all?) of which are in line with our intuition.

  • 0
    I'm not sure there is a good answer in the spirit of your question. You could certainly ask whether there is a limiting density as the denominator of the reduced fraction goes to infinity, but that loses the order. You could make a product order between magnitude and denominator (using a pairing function). On the other hand, I think (but haven't proved) that a diagonal mapping inherently loses the order in the base set. Maybe the best thing to think about is what do you mean when you say "most rationals have this property?" I think natural density captures it for N.2010-11-16