Re: Distinct linear orderings on Z

From: Dave Rusin (rusin_at_vesuvius.math.niu.edu)
Date: 03/23/05 

Date: 23 Mar 2005 03:26:09 GMT

In article <PL20e.7048$JK1.428350@news20.bellglobal.com>,
Allan C Cybulskie <allan.c.cybulskie@yahoo.ca> wrote:

>I'm only going to say this once:

Let me take this opportunity to thank you for saying it clearly and
civilly.

>It seems to me that the history of this part of set theory
>likely ran something like this.
[Fine summary deleted.]
>And then at some point this led us to deciding that cardinality and
>bijection works really well as a notion of relative number of
>elements for finite sets.

OK so far. (For technical reasons, mathematicians would probably reserve
the adjective "relative" for something else. I might say "comparative".)

>And then we started looking at what it
>meant for an infinite set to have a certain number of elements.

Right. Well, we started to ask what "number of elements" meant when
we had run out of names for numbers. Or something like that. But yes,
we were thinking about what to say to try to extend the old concept
of "number" to the case of infinite sets.

> And
>mathematicians decided to apply cardinality as just being that as well ...

Yes.

>even though it contradicted the notion that obviously if one set contains
>everything in another set and more, it must have more elements.

Well, I would say, "even though it was sometimes unable to distinguish
between, for example, a set and a proper superset". Right. Cardinality
doesn't satisfy our "deepest desire" here. So? It's a size-like idea
that doesn't have _all_ the old features that natural numbers did. So?

>The problem is that cardinality is derived from our intuitions and notions
>about counting, not the other way around. To elevate it with no other
>argument is to cut it off from that which gave it its validity as a notion
>of "number of elements". Can it stand with its base cut out from under it?

How does a mathematical idea "stand"? I see no problem with your analysis
so far. We had an idea. We tried to extend it. It did work out quite
the way we might have naively hoped. That doesn't make it useless.
It still helps us e.g. distinguish the set of rational numbers from the
set of real numbers. Why throw away a perfectly good tool just because
it doesn't slice AND dice, if you occasionally have need for just a slicer?

>Personally, I would rather the mathematicians merely say "number of elements
>makes little sense for infinite sets"

I think you'll find ALL the mathematicians here telling you that the
phrase "number of elements" makes little sense for infinite sets!
It ain't us using that phrase, except when we try to help someone else
who insists on using the phrase!

>and then merely talk about cardinality
>and stoically ignore all talk of "number of elements" until something
>reasonable for mathematics comes along.

In practice mathematicians DON'T talk about "number of elements" in
sets (except finite ones of course). But when non-mathematicians come
and ask us questions about the "number of elements in an infinite set",
what would you have us do?
  (a) just walk away silently?
  (b) say "it makes no sense" and walk away?
  (c) say "it makes no sense, have you considered the alternative notion of
      cardinality"?
  (d) say "what do YOU mean by 'number of elements'?"

If you don't want to talk about cardinality, that's really fine, but
then what DO you want to talk about? You can wish that there were a
clear alternative, but you'd have to say what you want to be true.

Let me make a suggestion. Is this what you want?

  I would like to have an enlarged notion of "number" that can be
  used to measure infinite sets. That is, I want a collection X of
  "supernumbers" : objects with the property that for every set A we can
  pick out one of the x's to be the "size" of A -- in other words,
  I want a function f defined for all sets -- with the property that
     (1) when A is properly contained in B, then f(A) < f(B)
     (2) when A is finite, then f(A) is the number of elements in A.

Is that what you want? That's pretty clear. It actually contains a
few implicit points. Condition (1) forces it to be true that X is
not just a set, it's an _ordered_ set. (Not all sets are ordered; you
should see my sock drawer.) Condition (2) forces X to contain the
natural numbers.

You may want more things too, I don't know. Let me know what exactly
you're looking for. For example, do you want
     (3) whenever A and B are sets, then precisely one of the
         following is true: either f(A) < f(B), or f(B) < f(A),
         or else A and B are identical sets.

Well, you can't have that, not with condition (2) up there, since
f( {2} ) and f( {7} ) are supposed to be equal (to 1) but {2} and {7}
are not the same set. So I guess you don't want condition (3) phrased
exactly as I did. What DO you want it to say? I don't suppose you'd
accept this, would you?
     (3') whenever A and B are sets, then precisely one of the
         following is true: either f(A) < f(B), or f(B) < f(A),
         or else the elements of A and B can be paired off in a
         one to one manner.
Honest, I can't tell from everything you've written exactly what you
expect in this direction.

You mentioned "mathematical operations" once. Are you going to further
insist that
     (4) there is a binary operation "+" on X such that when
         A and B are disjoint, then f(A union B) = f(A) "+" f(B)
Will you further insist that there be another operation "*" on X?
What will you ask that it satisfy --- something like
     (5) f(A) * f(B) = f( something built from A and B )?
Must it be related to "+" somehow? That is, will you insist that e.g.
( x + y ) * z always be the same as ( x * z ) + ( y * z ) ?
Will you further insist that some kind of "^" be defined?
How must it be related to the corresponding sets? How must it be
related to "+" and "*" ? Must a "-" be defined too?

Next, do you really want to measure "size" of _all_ sets? Or will you
settle for just _sets of counting numbers_? That ought at least to
be a good first step, don't you think? We'd like to be able to speak
of the size of "the set of all primes", for example, right?

The reason I ask all these things is that these are precisely the
kinds of questions asked by the people who developed cardinal arithmetic,
except for the last line of condition (3), which they sacrificed because
they WERE able to concoct such a system with ALL those other properties
except for the existence of a subtraction operation. That's exactly
what cardinal arithmetic does. You ask for a new system with the
conditions (3), (4), (5), ... met -- but what if it can be proved that
no such system can exist? What are YOU willing to sacrifice? It
doesn't really matter to me (I like my slicer) but if you can't have
a slicer/dicer, then you'd better tell me just what you need the dicer
to do. (Don't say "dice". I'm serious.)

OK, with that long buildup, I am prepared to give you a partial answer
to the question, "Is there any other notion of 'number of elements'
than 'cardinality'?" My answer is Ye (I said it was a partial answer!)

It's actually very simple. I will use X to be the set of natural numbers
plus a copy of the interval (0,1] in the real line. (You can think of
this as saying I've got one "infinity" for every real number between 0 and 1,
but I won't use that terminology because as I said elsewhere I hate to
use the term "infinity" because it make people think there is this
weird twinkling hyperspace thingy beyond which Buzz Lightyear flies.)
Oh, I guess that means I have two different things called "1". Sorry
'bout that. Let me know if you can't tell which is which at any point.
There is a Helpful Picture below.

There is an ordering on X ; the natural numbers are ordered in the
usual way, and the real numbers are ordered in the real way, and we
declare all those real numbers to be larger than all those natural numbers.
    The function f that assigns one of these "sizes" to any subset A
of the counting numbers is the following:
    * If A is a finite set, then f(A) = |A| , the ordinary cardinality.
         (It's a member of the 'natural-number' part of X).
    * If A is an infinite set, then f(A) = sum 1/2^k, the sum
         taken over all the elements k of A. So for example the
         measure of N ={1,2,3,...} itself is f(N) = 1/2+1/4+1/8+... = 1.
         The even numbers are assigned a measure of 1/3, the odd numbers
         are assigned a measure of 2/3, and so on -- you can ask your
         local calculus student to work out more examples for you.

This process assigns a different "size" to every single infinite subset
of N. If you don't like these sizes to be expressed with small numbers
like fractions, you could multiply all the values of f by a thousand,
or do something like replace this number f(A) by f(A)/(1 - f(A))
for every set except A = N itself ; you'd have to get yet another symbol
for f(N), then -- obviously it's a "supernumber" (or whatever you want
to call these things) which is supposed to be bigger than every real number.

(Mathematically, X is only defined to be an ordered set, and I've just
given a couple of examples of ordered sets which are isomorphic; those
who study ordered sets would write these as X = N + (0,1] or something.
Actually I think the notation would be something like X =
"alpha + gamma + 0" or something -- I never did spend much time in
that particular branch of set theory.)

I should stress that this is actually very closely related to the
concept of cardinality which is to my mind simpler though as noted above
it does not differentiate among some distinct sets, but does generalize to
larger sets than the power set of N, and has the arithmetic properties too.
The connection is that "cardinality" is simply another mapping g
defined for (these) sets, in this case mapping into a different set X'
which consists of the natural numbers N together with just ONE more
element which we can call "Fred" (or "infinity" if you like). The
connection is that g is simply the composite g = h o f where
h : X --> X' collapses the interval (0,1] to the point "Fred" but
is the identity map on the rest of X. You can even draw a little picture:
       
     { cloud-like image containing each of the subsets of N goes here }
                              |
                              | this is the map f
                              V
     X = { 1 2 3 .... } [0 ... 1/pi ... 0.5 ... sqrt(2)/2 ... 1.0 ]
                              |
                              | this is the map h
                              V
     X' = { 1 2 3 .... } {"Fred"}

but the picture is merely intended to be suggestive, so if it doesn't
suggest anything to you then skip it. Anyway, cardinality maps all the
finite subsets of N to the left part of the last row, and maps
everything else to the right part. If you want a refined notion of size,
you're welcome to stop at the middle line; no two infinite sets have
gotten sent to the same point here.

(You can draw X and X' on the number line if you like; just put a
dot at the point -1/n labelled "n", for n = 1, 2, 3, ... , and leave
the interval (0,1] as is. As far as ordered sets go, that's
exactly the same object as the X shown. Or, you can draw X' differently
by putting the natural numbers on an ordinary number line, and then
putting a copy of the interval (0,1] sort of above it like a second
register on an organ. Again, as far as ordered sets go, these are all
isomorphic. Choose the model that works for you.)

The particular model I gave for X has the added benefit that the ordinary
addition of integers and the ordinary addition of real numbers is
reflected on the set-theoretic level: using these addition operations as
recipes for how to add certain pairs of elements of X, we can prove

   Theorem: If A and B are disjoint, then f( A union B ) = f(A) + f(B)
    if A and B are both finite, or if A and B are both infinite.

This particular model does NOT allow any such generalization to cover
the case where A is finite and B is not finite (nor the other way around),
even if you made up a very creative definition of what it means to "add"
one integer to one real number between (0,1] (necessarily to end up
with another number between 0 and 1). For example, how should be
define the new-fangled "sum" of the integer 2 and the real number 1/3 ?
Since 1/3 = f( the set of even numbers ) and 2 = f( {5, 7} ), we would
want 2 "+" 1/3 to be f( {2,4,5,6,7,8, 10, 12, 14, ...} ) which
works out to be 1/3 + 1/2^5 + 1/2^7. But at the same time we know
2 = f( {1, 3} ) so we should ALSO have 2 "+" 1/3 come out to be
f({1,2,3,4, 6, 8, 10 , ...}) which comes to 1/3 + 1/2^1 + 1/2^3, and
that's not the same number as before. So we can't extend the theorem
even to this simple case, no matter what definition of "+" we use
to "sum" elements from the two different parts of X.
    
I can't say this particular mapping "f" is very helpful. Indeed any
mathematician would say this is just the usual map which shows that
the power set of N has the same cardinality as the real line, i.e.
this is the proof that 2 ^ aleph0 = c [the cardinality of the continuum].
It's so transparently just a real-line encoding of the subsets of N
that there seems little point to it. But it meets the conditions you
APPEAR to have asked for: it refines the notion of cardinality in a
way that differentiates between a set and its proper subsets. You can
dress it up in different language if that make you happy (I don't know,
maybe paint the part of X other than N itself blue, and call those
elements the "un-natural numbers" or the "in-finite numbers".
It is you who say that they are. Oh, wait, that's a little messianic
of me, isn't it. Sorry.) So if that's what you always wanted as an
extension of the concept of "number of elements" to include infinite
sets, great. If it's not, you'll have to say why this is still not right.
Precise axioms, please, as above.

So there. Make a civil post, get a civil response.

dave

Relevant Pages

  • Re: Distinct linear orderings on Z
    ... I am not insisting that mathematicians cannot use cardinality to ... basic misunderstanding of infinite sets that it is hard to explain ... > capture what we feel is IMPORTANT about our counting. ...
    (sci.math)
  • Re: Epistemology 201: The Science of Science
    ... :> In sci.math Tony Orlow wrote: ... :>:> cardinality? ... Tony and others were claiming that the mathematicians ... didn't sound like it applied to infinite sets anyway. ...
    (sci.cognitive)
  • Re: Epistemology 201: The Science of Science
    ... :> In sci.math Tony Orlow wrote: ... :>:> cardinality? ... Tony and others were claiming that the mathematicians ... didn't sound like it applied to infinite sets anyway. ...
    (sci.physics)
  • Re: Epistemology 201: The Science of Science
    ... :> In sci.math Tony Orlow wrote: ... :>:> cardinality? ... Tony and others were claiming that the mathematicians ... didn't sound like it applied to infinite sets anyway. ...
    (sci.math)
  • Re: Galileos Paradox
    ... there are serious questions regarding the measure of infinite sets, as Six Letters points out. ... subset as always smaller than the superset, though that is clearly not how cardinality works for infinite sets. ... IFR only applies, if at all, only for order preserving functions from ordered sets to ordered sets, which leaves out all unordered sets and multiply ordered sets. ...
    (sci.math)
Loading