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.

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.

share|improve this question
    
To make the question precise, you need to give a precise meaning for "more" for two arbitrary sets. Proper inclusion only works when you have a natural injection going exactly one way, which is the point you make. –  Arturo Magidin Nov 15 '10 at 1:25
1  
whether the "natural mapping" is available or not doesn't change the fact that Z and Q are countable. You mention the order, so you're clearly thinking about more structure than just the bare sets. If you take order into account then it's clear that Q is "thicker" than Z in the sense that its intervals are infinite. Is this the kind of thing you mean? –  Qiaochu Yuan Nov 15 '10 at 1:31
    
@Qiaochu Yuan: Yes. Or any other way you can think of; I'm hoping answers will include measures I haven't though of before. –  Charles Nov 15 '10 at 2:52

3 Answers 3

up vote 9 down vote accepted

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

share|improve this answer
1  
Nice point! On the other hand, N and -N are as small as possible among (infinite) countable, linearly ordered sets. If you want symmetry between < and >, then Z is as small as possible. –  Jonas Kibelbek Nov 16 '10 at 3:51
    
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. –  Arturo Magidin Nov 16 '10 at 4:04

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.

share|improve this answer
    
You can ask the same question about the ring structure as well: can we embed Z as a subring of Q? Can we embed Q as a subring of Z? –  Daniel McLaury Nov 15 '10 at 2:27
    
Great answer. But in this case, I do think there is something special about the natural orders on Z and Q (and I mention this in my question). It may be possible to show that Q is denser, somehow, using its order. For example: between any two distinct elements of Q there are infinitely many members, but between any two distinct members of Z there are only finitely many. But this is not entirely satisfactory, since Z U {-infty, +infty} has neither property and yet seems to be just as small as Z. –  Charles Nov 15 '10 at 2:56
1  
@Charles: Well, if you use the "order" among ordered sets I mention, then $\mathbb{Z}\cup\{-\infty,\infty\}$ is also strictly larger than $\mathbb{Z}$, not "just as small": there is no way to stick this set "inside" of $\mathbb{Z}$. It's somewhere between $\mathbb{Z}$ and $\mathbb{Q}$. If it "feels" just as small as $\mathbb{Z}$, then you aren't talking merely about "order-comparison", but something else. –  Arturo Magidin Nov 15 '10 at 3:53
1  
@user3296: Absolutely; you can always put "more structure", and as long as composition of appropriate embeddings is an appropriate embedding, you'll get a pre-order among the objects (symmetry may fail in some circumstances). Ring/group structures are one way, order is another, topology is yet a third, etc. But to have the question "Is $\mathbb{Z}$ smaller than $\mathbb{Q}$?" have a sensible answer of "yes", some extra-structure needs to be specified; otherwise the convention is that we are talking cardinalities, and there the answer is "no." –  Arturo Magidin Nov 15 '10 at 3:56
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}$! –  Jason DeVito Nov 15 '10 at 11:56

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.

share|improve this answer
    
How would you generalize natural density to subsets of Q? –  Charles Nov 16 '10 at 4:28
    
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. –  Ross Millikan Nov 16 '10 at 4:55

Your Answer

 
discard

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.