Cardinality
Jimmy Wales
regarding issues of infinite numbers and cardinality... some things
about how I think that you *may* be talking past each other.
Joe writes:
>>Cantor demonstrated the reason I think there are for example more real #'s
>>than natural. oNe of his proofs follows:
Mike Huemer writes:
>Yes, I'm aware of the diagonalization argument, and I think it's a
>neat argument, but it doesn't show that there are "more real numbers".
>It just shows that the set of reals has a higher cardinality.
Like Joe, when I first read some things that Michael has written on
this topic, I thought that either he must not know about Cantor
diagonalization, or he must have some disagreement with it. But
that Isn't exactly right. Mike has no problem with the specialized
concept of 'cardinality'... he just thinks that it isn't the same,
conceptually, as the concept of 'size' or 'more than'.
The confusion may arise because for finite collections of objects,
a higher cardinality *is* the same as 'bigger'or 'more than'. Mike
just objects to carrying that over into a realm where it isn't
(or may not be) true. Since infinity is not a definite quantity,
then *even though* we can distinguish among different *kinds* of
infinity, it may not be appropriate to *also* apply concepts that
were devised to distinguish between finite quantities.
>Anyway, that didn't answer my question. My question to Olaf was
>whether *every* pair of infinities can be ordered. He already
>affirmed that some infinities are bigger than others. He also went
>further than Cantor does -- for instance, if I'm not mistaken, Olaf
>would also think that the set of integers is bigger than the set of
>even integers (right, Olaf?)
On Mike's view, Olaf would be *right* to say that some infinities have
a 'higher cardinality' than others, but *wrong* if he thought this meant
that they are 'bigger'. (Mike objects to using the concept 'bigger' with
respect to infinite things.)
On *any* view, I hope, it is not appropriate to say that the set of
integers is bigger than the set of even integers. I don't know if Olaf
said this, but if he did, then I don't understand what he means.
>Also, by the way, Cantor's argument certainly doesn't answer Galileo's
>argument. Paraphrasing Galileo, I gave a reason for thinking that the
>set of perfect squares is at least as big as the set of natural
>numbers, and a reason for thinking that the set of natural numbers is
>much bigger than the set of perfect squares. I've never heard an
>answer to either of these arguments.
Now here, I would suggest that I took you to mean that Galileo's argument
just shows that the ordinary concept of 'bigger' doesn't apply to
infinities. Is that right?
(Notice that I have not expressed any agreement or disagreement with
Mike's position here! I'm just trying to get a bit clearer on what
that position is. I'm _inclined_ to agree with him, so far as I
understand him, and this is a change of position on my part.)
--Jimbo
Olaf Weber
> I just wanted to try to point out some things to the disputants
> regarding issues of infinite numbers and cardinality... some things
> about how I think that you *may* be talking past each other.
I am inclined to agree that there is a certain amount of talking past
each other going on in the discussion. My apologies for the fact that
there is some duplication of content with other posts of mine, but I
hope that this presentation is an improvement.
> Mike Huemer writes:
>> Yes, I'm aware of the diagonalization argument, and I think it's a
>> neat argument, but it doesn't show that there are "more real
>> numbers". It just shows that the set of reals has a higher
>> cardinality.
As far as I know, the diagonalization argument _is_ interpreted by
mathematicians as implying that there are more real numbers than
natural numbers. In the same vein, the existence of a one-to-one
mapping of the integers to the natural numbers is taken to mean that
there are just as many integers as natural numbers. Cardinality, with
the comparison relation defined on it, captures this concept of
"more".
It is also true that there are integers that are not natural numbers,
while every natural number is an integer. Thus, the set of integers
is a proper superset of the set of natural numbers. This gives us
another way to characterize a "more than" relation: there are more
things of kind A than of kind B, if the set of As is a proper superset
of the set of Bs.
The problem with this definition is that set inclusion does not give
us a total ordering. That is, some sets are neither equal, nor proper
subsets of each other. (For example, {1,2} and {2,3}.) What we can
do about this is to take the subset relation, and "complete" it to a
total ordering by defining the cases where the subset ordering doesn't
give an answer. Doing this the "obvious" way, we get the comparison
relation for ordinal numbers. In that relation, the set of integers
is larger than the set of natural numbers.
And we have the odd situation that while the comparison of two finite
numbers gives the same result, irrespective of whether we compare them
as cardinals or ordinals, the results differ for infinite numbers,
some that are unequal when compared as ordinals, are equal when
compared as cardinals. The concept of more, when applied to
infinities, breaks into two related concepts: comparison of ordinals
and comparison of cardinals.
What may encourage some of the confusion is the fact that usually
ordinals are only briefly touched upon on the road to the introduction
of cardinals. After that, comparisons that are discussed are between
cardinals, and ordinals are more or less ignored. However, when
infinitesimals are introduced they are related to the reciprocal of
ordinals, and the ordering of ordinals is applicable. This artifact
of the way these things are taught may account for why a comparison
between ordinals "looks odd".
> Like Joe, when I first read some things that Michael has written on
> this topic, I thought that either he must not know about Cantor
> diagonalization, or he must have some disagreement with it. But
> that Isn't exactly right. Mike has no problem with the specialized
> concept of 'cardinality'... he just thinks that it isn't the same,
> conceptually, as the concept of 'size' or 'more than'.
> The confusion may arise because for finite collections of objects,
> a higher cardinality *is* the same as 'bigger'or 'more than'. Mike
> just objects to carrying that over into a realm where it isn't
> (or may not be) true. Since infinity is not a definite quantity,
> then *even though* we can distinguish among different *kinds* of
> infinity, it may not be appropriate to *also* apply concepts that
> were devised to distinguish between finite quantities.
The problem that I have with Michael's view is that I have been unable
to make out exactly what it _is_. He uses the concept of cardinality,
and apparently doesn't use (or accept) the concept of ordinality, even
though it's hard to learn about one withour learning about the other.
Moreover, he appeared to insist that we cannot (or should not try to)
say anything definite about infinities. But in mentioning the
ordinality or of an infinity we are saying something definite about
it.
And Michael appeared to argue that the infinity the characterizes the
number of real numbers is just as large as the infinity that
characterizes the number of natural numbers. But a difference in
cardinality is usually taken to be a _real_ difference in size, while
differences in ordinality are (arguably) _apparent_ differences in
size, and Michael seems to be well aware of this.
When I sum this all up, I am left confused.
>> Anyway, that didn't answer my question. My question to Olaf was
>> whether *every* pair of infinities can be ordered. He already
>> affirmed that some infinities are bigger than others. He also went
>> further than Cantor does -- for instance, if I'm not mistaken, Olaf
>> would also think that the set of integers is bigger than the set of
>> even integers (right, Olaf?)
> On Mike's view, Olaf would be *right* to say that some infinities
> have a 'higher cardinality' than others, but *wrong* if he thought
> this meant that they are 'bigger'. (Mike objects to using the
> concept 'bigger' with respect to infinite things.)
In my view, Michael would be engaging in a fairly pointless debate
about the meaning of a technical term if he objected to my use of
"bigger" in this case. OTOH, it would be perfectly fair to ask me
what I mean by "bigger" in that particular context. I hope I have
clarified this by now. If not, then I'm not sure what more I could
do.
> On *any* view, I hope, it is not appropriate to say that the set of
> integers is bigger than the set of even integers. I don't know if
> Olaf said this, but if he did, then I don't understand what he
> means.
When comparing the ordinality of the set of integers with the
ordinality of the set of even integers, it is perferctly proper to say
that the first is larger than the latter. And when comparing their
cardinalities it is equally proper to say that the sets have the same
size.
>> Also, by the way, Cantor's argument certainly doesn't answer
>> Galileo's argument. Paraphrasing Galileo, I gave a reason for
>> thinking that the set of perfect squares is at least as big as the
>> set of natural numbers, and a reason for thinking that the set of
>> natural numbers is much bigger than the set of perfect squares.
>> I've never heard an answer to either of these arguments.
> Now here, I would suggest that I took you to mean that Galileo's
> argument just shows that the ordinary concept of 'bigger' doesn't
> apply to infinities. Is that right?
As I've noted in another post as well, Galileo's argument is only
convincing if you do not realize that it equivocates on "bigger". The
resolution is to split the concept.
--
Olaf Weber
Michael Huemer
(I) TO JIMBO:
jwa...@MCS.COM (Jimmy Wales) writes:
>The confusion may arise because for finite collections of objects,
>a higher cardinality *is* the same as 'bigger'or 'more than'. Mike
>just objects to carrying that over into a realm where it isn't
>(or may not be) true. Since infinity is not a definite quantity,
>then *even though* we can distinguish among different *kinds* of
>infinity, it may not be appropriate to *also* apply concepts that
>were devised to distinguish between finite quantities.
Yes, that's exactly what I think.
>Now here, I would suggest that I took you to mean that Galileo's argument
>just shows that the ordinary concept of 'bigger' doesn't apply to
>infinities. Is that right?
Ditto.
(II) TO BRAD WILLIAMS:
What's relevant isn't whether there are an infinite number of things
in the world (e.g., infinitely many atoms), nor even whether there are
an infinite number of *states* of things. In the sort of example I
was considering (where probability is most applicable), there is only
*one*, *actual* state of things. That is, the random variable has one
actual value. So to that extent you're right. However, there *are*
infinitely many *possible* states. (Possible states, in this context,
are just states that your evidence doesn't rule out.)
(III) TO OLAF and maybe others:
I deny that the set of real numbers is actually, literally larger than
the set of natural numbers. You might make this argument (suggested
by your last post): "Well, you can interpret 'larger' either as
'higher cardinality' or as 'higher ordinal,' but *either way* the set
of reals comes out larger."
My answer to this is that I don't interpret 'larger' as being
synonymous with either of those. I think *both* conditions are
necessary for the 'greater than' or 'larger' relation to hold. I also
think that *another* necessary condition on the greater than relation
(this is the one that isn't satisfied) is that the relata be definite
quantities. I say that the # of natural numbers is not a definite
quantity because it cannot be compared in terms of greater or smaller
to certain other infinities (such as that of the set of perfect
squares) -- in other words, we have something like this:
(1) in order for set x to be bigger than y, x must have higher
cardinality than y.
(2) In order for x to be bigger than y, x must also have higher
ordinality. (I'm not sure I understand this notion, but anyway, x has
to not be a proper subset of y.)
(3) In order for x to be bigger than y, x and y must both contain a
definite number of elements.
(4) x contains a definite quantity of elements only if for every other
set, y, that contains a definite quantity of elements, x contains
either more than, less than, or the same # of elements as y.
(N.B. this is not intended as a definition, so don't complain of
circularity)
#1-4 are my intuitive premises about 'greater than'. I'm also
assuming
(5) Either the set of naturals and the set of perfect squares are both
definite quantities, or neither of them is.
Now we can argue:
(6) The set of naturals is neither greater than, nor smaller than, nor
the same size as, the set of perfect squares. (Galileo's argument,
with 1 + 2)
(7) Therefore, both sets can't be definite quantities. (from 4,6)
(8) Therefore, the set of naturals is not a definite quantity.
(from 6,7)
(9) Therefore, the set of reals #s is not bigger than the set of
natural numbers. (from 3,8)
Okay, I see that was complicated, but the reasoning is valid and the
premises are consistent. You might disagree with the premises, but
anyway, I think they're intuitive, which is the best thing you can say
for a premise (at least, in my philosophy).
--
^-----^
Michael Huemer <o...@rci.rutgers.edu> / O O \
http://www.rci.rutgers.edu/~owl | V |
\ /
Stephen Grossman
Jimmy Wales (jwa...@MCS.COM) wrote:
: I just wanted to try to point out some things to the disputants
: regarding issues of infinite numbers and cardinality... some things
: about how I think that you *may* be talking past each other.
Mr. Neutral. Peikoff is right. Kelley likes facts without values. Wales is
into polite argument rather than philosophy. Philosophy can can very
impolite in teaching wisdom to fools.
Ivan Ordonez
In article <4loisq$p...@amenti.rutgers.edu>, o...@amenti.rutgers.edu
(Michael Huemer) wrote:
> A few more notes about infinity:
[...]
>
> I deny that the set of real numbers is actually, literally larger than
> the set of natural numbers. You might make this argument (suggested
To deny that you first need to define what "larger" means. In Set Theory,
"larger" is interpreted as meaning having a higher cardinality.
> by your last post): "Well, you can interpret 'larger' either as
> 'higher cardinality' or as 'higher ordinal,' but *either way* the set
> of reals comes out larger."
>
> My answer to this is that I don't interpret 'larger' as being
> synonymous with either of those. I think *both* conditions are
> necessary for the 'greater than' or 'larger' relation to hold. I also
For any two sets A and B such that the cardinality of A is greater than
that of B, there are two ordinals a and b such that a is larger than b,
and such that A is equipollent with a and B is equipollent with b.
Whenever the first condition meets, the second does, too.
> think that *another* necessary condition on the greater than relation
> (this is the one that isn't satisfied) is that the relata be definite
What is a definite quantity? Here is where your argument collapses, since
you do not define what that is.
> quantities. I say that the # of natural numbers is not a definite
> quantity because it cannot be compared in terms of greater or smaller
> to certain other infinities (such as that of the set of perfect
> squares) -- in other words, we have something like this:
Of course it can be compared. Both sets have the same cardinality, but the
second is a proper subset of the first. See, this disturbing feature is
what characterizes infinite numbers. In fact, the axiom of infinity is
formally presented as saying "there is a set A such that A is equipollent
with a proper subset of itself." It is a simple thing to derive from ZF
that this is the same as saying "there is an infinite set."
> (1) in order for set x to be bigger than y, x must have higher
> cardinality than y.
OK.
> (2) In order for x to be bigger than y, x must also have higher
> ordinality. (I'm not sure I understand this notion, but anyway, x has
> to not be a proper subset of y.)
You don't understand the notion. There is no such thing as "ordinality."
OTOH, "x must not be equipollent with a proper subset of y" is a necessary
condition only for x to have a higher cardinality than y; it does not
forbid them to have the same cardinality.
Now, if you impose as a condition that if x is a proper subset of y (or
equipollent to a proper subset of y) then x must necessarily be smaller
than y, then you have restricted x and y to be finite sets. This is a very
simple theorem that follows from ZF.
> (3) In order for x to be bigger than y, x and y must both contain a
> definite number of elements.
Again, what is "definite?" From your condition above, it seems that your
"definite" actually means "finite."
> (4) x contains a definite quantity of elements only if for every other
> set, y, that contains a definite quantity of elements, x contains
> either more than, less than, or the same # of elements as y.
> (N.B. this is not intended as a definition, so don't complain of
> circularity)
If by "more, equal or less" you mean higher cardinality, equal cardinality
or lower cardinality, then the above is true of all sets, finite and
infinite, provided that we accept the axiom of choice.
> #1-4 are my intuitive premises about 'greater than'. I'm also
> assuming
>
> (5) Either the set of naturals and the set of perfect squares are both
> definite quantities, or neither of them is.
OK, let's say they both are.
> Now we can argue:
>
> (6) The set of naturals is neither greater than, nor smaller than, nor
> the same size as, the set of perfect squares. (Galileo's argument,
> with 1 + 2)
Wrong. Both sets have the same cardinality, but one is a proper subset of
the other. This is perfectly OK, as shown above.
> (7) Therefore, both sets can't be definite quantities. (from 4,6)
The only way I see to make sense of this is to translate it using the only
consistent interpretation I see of your arguments: Both sets are not
finite quantities."
> (8) Therefore, the set of naturals is not a definite quantity.
> (from 6,7)
"Therefore, the set of naturals is not finite."
> (9) Therefore, the set of reals #s is not bigger than the set of
> natural numbers. (from 3,8)
"Since, by definition, I restrict the concept of "bigger" or "equal" only
to finite quantities, I cannot compare the reals and the naturals."
> Okay, I see that was complicated, but the reasoning is valid and the
> premises are consistent. You might disagree with the premises, but
> anyway, I think they're intuitive, which is the best thing you can say
> for a premise (at least, in my philosophy).
The reasoning is not valid and the premises are not well defined. Your
arguments seems to boil down to "I don't understand infinite numbers, so I
forbid comparing them."
Why is it that people that know no math argue about math?
--
Ivan Ordonez
iord...@magnus.acs.ohio-state.edu (finger for PGP public key)
http://www.cis.ohio-state.edu/~iordonez
Cal Rice
Set A is bigger than set B if it is possible to match all elements
of B with a subset of A, but not possible to match all elements of
A with a subset of B.
illustrations:
The set of positive integers is not bigger than the set of even
positive integers, because you can match all of the elements of
each set with all of the elements of the other (1-2, 2-4, 3-6, ...).
The set of positive integers is not smaller than the set of positive
rational numbers because, if you lay out the set of positive rational
numbers like so,
1/1 1/2 1/3 . . .
2/1 2/2 2/3 . . .
3/1 3/2 3/3 . . .
. . . . . .
. . . . . . ,
you can then match the set of positive integers with the elements of
of this array by starting in the upper left corner and counting the
first two elements, then going down the diagonal toward the lower left
and counting two elements down the left column, then going up the
diagonal toward the right, counting each element that you encounter,
then two elements to the right, then back down the diagonal toward
the left, etc. All positive integers will then be matched with all
of the positive rational numbers, and then some, because the array
contains duplicated rationals.
There is no way to make a one-to-one correspondence between the set
of positive integers (natural numbers) and the set of real numbers,
however. There will always be some real numbers left over, no matter
how you pair the intergers with the reals. So the set of real numbers
is bigger than the set of natural numbers.
Michael Huemer
Cal Rice and Ivan Ordonez have recently joined the 'cardinality'
thread. Let me say a couple of things so that we don't have
unnecessary repetitions:
(a) Everybody here knows the diagonalization argument (I think).
Someone else previously posted it.
(b) We all also know the concept of 'cardinality' and that the
continuum has higher cardinality than the set of natural numbers.
It is not necessary to give any lessons in mathematics here. What is
going on, however, is a philosophical debate about, as it were, the
interpretation of the math.
iord...@magnus.acs.ohio-state.edu (Ivan Ordonez) writes:
>> I deny that the set of real numbers is actually, literally larger than
>> the set of natural numbers. You might make this argument (suggested
>To deny that you first need to define what "larger" means. In Set Theory,
>"larger" is interpreted as meaning having a higher cardinality.
Let's not play silly games here. I mean the sense in which you can
say that 7 is larger than 4, and things like that (or that a
collection of 7 things is larger than a collection of 4 things). If
you want to say, "But, gee, we can just *redefine* 'larger', give it
some technical sense completely unrelated to its ordinary English
meaning, and then the continuum *will be* 'larger' than the natural
numbers," if that makes you happy, go ahead. But that's really
philosophically uninteresting. The question is whether, in the same,
common sense sense in which you can say that 3 is bigger than 2, you
can also say that the set of reals is bigger than the set of natural
numbers. If you can only say the latter by redefining "bigger", then
I'm right.
(Note: I'm talking indifferently about sets being 'bigger' and about
numbers being 'bigger'. A set is 'bigger' just if it has more
elements, i.e. a bigger number of elements.)
Anyway, I do not see how there can be any confusion, since I very
explicitly stated the 3 necessary conditions on the 'larger than'
relation in the message that you are replying to.
>For any two sets A and B such that the cardinality of A is greater than
>that of B, there are two ordinals a and b such that a is larger than b,
Yes, I answered that lower in the message.
>and such that A is equipollent with a and B is equipollent with b.
I don't know what "equipollent" means, so I can't say whether I
answered that either, but I suspect I did. Just read through the rest
of the message before replying!
>What is a definite quantity? Here is where your argument collapses, since
>you do not define what that is.
I also stated very clearly a necessary condition on something's being
a definite quantity, and that condition is enough to support my
conclusion, so I don't see what your problem is. If you want to just
ask me to 'define this' and 'define that' arbitrarily, then I suspect
you of playing the usual usenet games of trying to shortcircuit
discussion, and then I will demand that you define "define" and define
"is" and so on.
>Of course it can be compared. Both sets have the same cardinality, but the
>second is a proper subset of the first. See, this disturbing feature is
Yes, I already dealt with this.
>> (2) In order for x to be bigger than y, x must also have higher
>> ordinality. (I'm not sure I understand this notion, but anyway, x has
>> to not be a proper subset of y.)
>You don't understand the notion. There is no such thing as "ordinality."
Take it up with Olaf. He says there is. Anyway, you can just take
the condition I said in parentheses. And stop being so condescending.
>Now, if you impose as a condition that if x is a proper subset of y (or
>equipollent to a proper subset of y) then x must necessarily be smaller
>than y, then you have restricted x and y to be finite sets. This is a very
Not necessarily, as Olaf pointed out -- this could just be a different
way (different from the use of cardinalities, that is) of ordering
infinite sets (he also pointed out that it doesn't give a total
ordering, but so what).
Anyway, I think I want to restate the second premise. To make it
relevant to Galileo's argument, I need something like this:
(2) x and y can't be of equal size if one is a proper subset of the
other.
Together with (1), that's what's going to get me that the set of
naturals is neither larger than, smaller than, nor the same size as
the set of perfect squares. (That's how Galileo's argument works.)
>Again, what is "definite?" From your condition above, it seems that your
>"definite" actually means "finite."
That's not just 'what it means.' But yes, a central thesis of mind is
that no infinity is a definite quantity. Only finite numbers are
definite (you can substitute "determinate" and "indeterminate" if you
like that better). Or you can even drop the qualifier and say my
thesis is that infinity isn't even a quantity; or, infinity isn't a
number. "Then what do we mean when we talk about infinity?" you ask.
As I mentioned in the past, I take the Aristotelian conception:
'infinity' is a purely negative concept -- i.e., it's used just to
deny limits.
>If by "more, equal or less" you mean higher cardinality, equal cardinality
>or lower cardinality, then the above is true of all sets, finite and
>infinite, provided that we accept the axiom of choice.
I thought it was pellucid by now that I *don't* "mean" higher
cardinality!!!! (Btw, I find most talk about 'what you mean by' this
or 'what I mean by...' annoying and probably seriously philosophically
confused. That's another debate.)
>Wrong. Both sets have the same cardinality, but one is a proper subset of
>the other. This is perfectly OK, as shown above.
This is exasperating. Instead of quoting back to me what you math
professor told you, why don't you *pay attention to what I wrote*?
You haven't addressed a single thing I said. You seem to be just bent
on telling me I'm stupid, and nothing more. Did you read the previous
message on Galileo's argument that I posted?
Given the argument I stated, it is not 'perfectly okay,' and you have
'shown' absolutely nothing. You've just repeated trivialities that I
was already aware of and that, in most cases, I already explicitly
stated in the same message you're allegedly responding to.
>The reasoning is not valid and the premises are not well defined. Your
>arguments seems to boil down to "I don't understand infinite numbers, so I
>forbid comparing them."
No. I suggest you read it again, and this time READ it, instead of
interpolating your own preconceptions about what I must be saying and
redefining the words I'm using.
>Why is it that people that know no math argue about math?
I don't know. Why is it that people who 'know' math are incapable of
listening to what others have to say? Why is it that they have no
philosophical curiosity but only show interest in insulting others
intellectually? Why is it that they have nothing to say that isn't
utterly trivial and irrelevant? Why do they assume that no one but
them knows what they're talking about? I have my own theories about
these things, but I will keep them to myself.
No, I should not so insult mathematicians. I am sure they are not all
so dogmatic and self-absorbed; hopefully, you are just a special case.
Olaf Weber
Michael Huemer writes:
> (1) in order for set x to be bigger than y, x must have higher
> cardinality than y.
> (2) In order for x to be bigger than y, x must also have higher
> ordinality.
If condition (1) is satisfied, then condition (2) is satsified, so (2)
is redundant. (And for finite sets, there is no difference between
these two anyway.)
In general, your argument boils down to saying that your intuitions
about "bigger" prevent it from being applicable to infinities, and
therefore we cannot say that the set of real numbers is bigger than
the set of natural numbers.
We can do the same for "smaller" and "same size". Thus we have that
(according to you) the set of real numbers is neither smaller than,
nor bigger than, nor equal sized to the set of natural numbers.
Sloganized: "Infinities cannot be compared."
My intuitions in this matter do allow for such comparisons.
--
Olaf Weber
Ivan Ordonez
In article <4lrae6$g...@amenti.rutgers.edu>, o...@amenti.rutgers.edu (Michael
Huemer) wrote:
[...]
> (b) We all also know the concept of 'cardinality' and that the
> continuum has higher cardinality than the set of natural numbers.
If you understand that, you just need to understand one more
thing: for finite sets, the concept of "higher cardinality"
corresponds accurately to the intuitive notion of "bigger."
Because of that, mathematicians generalize that notion to
encompass infinite sets as well, and for that they just make it
correspond to the concept of cardinality. There is no "right"
interpretation of such concepts, because there is nothing in
reality that is infinite. Not even the totality of states the
Universe could be on is infinite, despite what somebody else said
before; that number is actually something in the order of
10^300000.
> It is not necessary to give any lessons in mathematics here. What is
> going on, however, is a philosophical debate about, as it were, the
> interpretation of the math.
If you don't understand the math, then you DO need a math lesson.
How on earth can you argue about somithing you don't understand?
> iord...@magnus.acs.ohio-state.edu (Ivan Ordonez) writes:
>
> >> I deny that the set of real numbers is actually, literally larger than
> >> the set of natural numbers. You might make this argument (suggested
> >To deny that you first need to define what "larger" means. In Set Theory,
> >"larger" is interpreted as meaning having a higher cardinality.
>
> Let's not play silly games here. I mean the sense in which you can
> say that 7 is larger than 4, and things like that (or that a
> collection of 7 things is larger than a collection of 4 things). If
In other words, in the finite sense. That is the problem: that
sense does not generalize easily into infinite sets, unless we
use the concept of cardinality. Since you question the use of
cardinality as a measure of size, it is your burden to present an
alternative notion of "larger" that is applicable to infinite
sets.
> you want to say, "But, gee, we can just *redefine* 'larger', give it
> some technical sense completely unrelated to its ordinary English
> meaning, and then the continuum *will be* 'larger' than the natural
> numbers," if that makes you happy, go ahead. But that's really
Ordinary English does not deal with infinite sets, because such
objects are outside ordinary experience (outside all experience,
for that matter). Sets are just abstract objects, and to talk
about them we need to introduce new vocabulary. As I said before,
the concept of cardinality is a generalization of the concept of
size for finite objects. If you don't like it, please present an
alternative.
> philosophically uninteresting. The question is whether, in the same,
I have no clue about what you mean by "philosophically
interesting." You are trying to impose an interpretation on
something that, by its very nature, does not have an
interpretation.
> common sense sense in which you can say that 3 is bigger than 2, you
> can also say that the set of reals is bigger than the set of natural
> numbers. If you can only say the latter by redefining "bigger", then
> I'm right.
I will try to explain your "common sense" about finite sets, and
then explain how that corresponds to "cardinality." I know you do
not want math lessons, but you will need this in order to
understand what I'm saying.
The reason why we say that 3 is bigger than 2 is that, if we take
two sets, one with two things and another with three things, call
them A and B, and we try to pair up their elements, we will end
up with one element in B that cannot be paired with any element
in A, *no matter how we do the pairing.* In math terms, this
means that there is an injection from A to B, but there is no
injection from B to A. In other words, sets A and B are not
equipollent. By the way, an injection is a function that does not
repeat elements in the range; for example, in the reals, x -> 2x
is an injection, but x -> x^2 is not (because negative numbers
squared are the same as their corresponding positive numbers
squared).
Given the above fact, we *define* in math that B is "bigger" than
A if and only if there is no injection from B to A. In the case
of 3 and 2, any function from B to A will have to repeat at least
one element in the range (A), so it will not be an injection:
B A
* ----> *
* ----> |-> *
* ------|
I hope the diagram above is clear enough.
So this is the standard mathematical definition of "cardinality,"
which corresponts accurately to the common intuitive notion of
size for finite sets. It turns out that, for every finite set X,
every proper subset of X has lower cardinality than X. This is
just a property of finite sets, an NOT a property of the
mathematical definition of size. You just believe that this
proper-subset thingy is essential because you have never dealt
with infinite sets with enough depth, so you are making a flawed
generalization.
Now, you see why size is *the same* as cardinality in the
common-sensical sense of the word. If you disagree, I
challenge you to define "size" some other way.
[..]
> >For any two sets A and B such that the cardinality of A is greater than
> >that of B, there are two ordinals a and b such that a is larger than b,
>
> Yes, I answered that lower in the message.
>
> >and such that A is equipollent with a and B is equipollent with b.
>
> I don't know what "equipollent" means, so I can't say whether I
> answered that either, but I suspect I did. Just read through the rest
> of the message before replying!
A is equipollent to B if and only if there is an injection from A
to B and there is also an injection from B to A. For example, the
sets {3, 6, 7} and {1, 2, 100} are equipollent.
> >What is a definite quantity? Here is where your argument collapses, since
> >you do not define what that is.
>
> I also stated very clearly a necessary condition on something's being
> a definite quantity, and that condition is enough to support my
> conclusion, so I don't see what your problem is. If you want to just
> ask me to 'define this' and 'define that' arbitrarily, then I suspect
> you of playing the usual usenet games of trying to shortcircuit
> discussion, and then I will demand that you define "define" and define
> "is" and so on.
I don't want to play any games. I ask you for a definition
because I honestly have no clue about what you mean by "definite"
uless I accurately guessed that what you actually mean is
"finite."
[...]
> >Now, if you impose as a condition that if x is a proper subset of y (or
> >equipollent to a proper subset of y) then x must necessarily be smaller
> >than y, then you have restricted x and y to be finite sets. This is a very
>
> Not necessarily, as Olaf pointed out -- this could just be a different
> way (different from the use of cardinalities, that is) of ordering
> infinite sets (he also pointed out that it doesn't give a total
> ordering, but so what).
This is a non sequitur. We are dealing with the ordinary way of ordering
sets, which is, by their cardinality.
> Anyway, I think I want to restate the second premise. To make it
> relevant to Galileo's argument, I need something like this:
>
> (2) x and y can't be of equal size if one is a proper subset of the
> other.
You cannot say this unless you define size in general enough
terms to include infinite sets. The ordinary definition
(cardinality) implies that (2) is only true of finite sets. Your
"common sense" notion of size is the same as cardinality. So you
*must* define what size is, and how it is different from
cardinality.
You see, in ordinary set theory, the axiom of infinity is stated,
more or less, as "there is a set X such that X has the same size
as a subset of X." This is just an axiom. Axioms in math are not
intrinsically true nor false; they are just premises used to
build theories and models. It is absurd to say "the axiom of
infinity is wrong," because that implies that somehow we can
prove or disprive such axioms. We cannot.
Your argument seems to say "I reject the axiom of infinity." You
may well do that out of your arbitrary will, but it will only
allow you to produce uninteresting mathematics.
> Together with (1), that's what's going to get me that the set of
> naturals is neither larger than, smaller than, nor the same size as
> the set of perfect squares. (That's how Galileo's argument works.)
You must be aware that Galileo lived long before Cantor, Zermelo
and Fraenkel. The argument does not apply to infinite quantities.
> >Again, what is "definite?" From your condition above, it seems that your
> >"definite" actually means "finite."
>
> That's not just 'what it means.' But yes, a central thesis of mind is
> that no infinity is a definite quantity. Only finite numbers are
> definite (you can substitute "determinate" and "indeterminate" if you
> like that better). Or you can even drop the qualifier and say my
No, I don't like them, because I don't know what they are. Please
provide a definition of the form "a number X is definite if and
only if ..." (fill in the blanks). Otherwise your argument is
unacceptable.
If you claim that "definite" is not the same as "finite" please
exhibit a finite number that is not definite or an infinite
number that is definite. If you can't, provide a definition of
"definite" that does not make use of the concept of "finiteness."
If you cannot prove that "definite" and "finite" are not the
same, then you argument is circular: infinite numbers are not
finite because they are not finite.
> thesis is that infinity isn't even a quantity; or, infinity isn't a
> number. "Then what do we mean when we talk about infinity?" you ask.
What is a number? You keep throwing words without defining them.
Under the standard definition, infinites *are* numbers. If you
reject the definition, you *must* provide an alternate one.
> As I mentioned in the past, I take the Aristotelian conception:
> 'infinity' is a purely negative concept -- i.e., it's used just to
> deny limits.
Irrelevant. Aristotle lived thousands of years before Cantor.
[...]
> >Wrong. Both sets have the same cardinality, but one is a proper subset of
> >the other. This is perfectly OK, as shown above.
>
> This is exasperating. Instead of quoting back to me what you math
> professor told you, why don't you *pay attention to what I wrote*?
Big assumption here. I will not bother clarifying.
Besides, I read three times what you wrote in your previous
article, and twice what you wrote on this.
> You haven't addressed a single thing I said. You seem to be just bent
> on telling me I'm stupid, and nothing more. Did you read the previous
> message on Galileo's argument that I posted?
I hope you understand I have addressed everything you said. I
don't know whether you are stupid or not; all I know for sure is
that your argument does not have any soundness, and that it rests
on undefined concepts.
> Given the argument I stated, it is not 'perfectly okay,' and you have
> 'shown' absolutely nothing. You've just repeated trivialities that I
> was already aware of and that, in most cases, I already explicitly
> stated in the same message you're allegedly responding to.
I have shown that your relying on the "common sense" idea of
bigger lands you directly on the concept of cardinality. It is
your burden to show that this is not so.
Robert J. Kolker
o...@amenti.rutgers.edu (Michael Huemer) writes:
....snip....
>(1) in order for set x to be bigger than y, x must have higher
>cardinality than y.
>(2) In order for x to be bigger than y, x must also have higher
>ordinality. (I'm not sure I understand this notion, but anyway, x has
>to not be a proper subset of y.)
>(3) In order for x to be bigger than y, x and y must both contain a
>definite number of elements.
>(4) x contains a definite quantity of elements only if for every other
>set, y, that contains a definite quantity of elements, x contains
>either more than, less than, or the same # of elements as y.
>(N.B. this is not intended as a definition, so don't complain of
>circularity)
>#1-4 are my intuitive premises about 'greater than'. I'm also
>assuming
>(5) Either the set of naturals and the set of perfect squares are both
>definite quantities, or neither of them is.
>Now we can argue:
>(6) The set of naturals is neither greater than, nor smaller than, nor
>the same size as, the set of perfect squares. (Galileo's argument,
>with 1 + 2)
The set of natural integers has the same cardinality as the
set of squares of natural integers. The can be put in one to
one correspondence with each other.
Your statement is quite incorredt.
>(7) Therefore, both sets can't be definite quantities. (from 4,6)
>(8) Therefore, the set of naturals is not a definite quantity.
>(from 6,7)
you mean not a finite quantity. The cardinality of the
natural number is aleph_0. Any set that can be put in one
to one correspondence with the naturasl has cardinality
aleph_0.
>(9) Therefore, the set of reals #s is not bigger than the set of
>natural numbers. (from 3,8)
The naturals can be put in one to one correspondecne with
a proper subset of the reals, but the converse is not so.
Therefore the reals have a larger cardinality than the
naturals.
>Okay, I see that was complicated, but the reasoning is valid and the
>premises are consistent. You might disagree with the premises, but
>anyway, I think they're intuitive, which is the best thing you can say
>for a premise (at least, in my philosophy).
Go and study some set theory.
--
"Taxation is Theft, Jury Duty and the Draft are servitude"
"Those who *would* govern us are enemies"
"An armed society is a polite society""
Michael Huemer
To Ivan Ordonez:
All right, I'm going to follow up this thread again, hoping that it's
not about to degenerate into nastiness.
First, I don't see that your last message contains anything new --
anything that hasn't already been said before by you, me, and other
people on the group. Certainly you told me nothing I didn't know
before (except for the false things you said -- more below). You
seemed to be under the impression that you were telling me something
new. So, at the cost of repetition, let me repeat a few things that
it is not necessary to tell me or anyone else again (of course, I am
presently engaged in repetition, but only to forestall further future
repetition):
1. the definition of 'higher cardinality'
2. that some infinite sets have higher cardinality than others
3. that the set of reals has a higher cardinality than the set of
natural numbers.
4. that the set of natural #s has the same cardinality as the set of
perfect squares
5. that for finite sets, the larger always has a higher cardinality,
and vice versa
6. that Galileo lived a long time ago
7. that Aristotle lived a really, really long time ago
Rehashes of any of the above facts are just a waste of bandwidth,
besides being boring.
Second, you claimed that the common sense notion of "larger" just is
the notion of "higher cardinality". This is certainly not true (in
spite of fact 5 above). The common sense 'greater than' relation has
a number of properties (well, at least 2), among which ONE is that
when x is larger than y, you can't map the elements of x onto y
without reusing some of y's members. Yes, we're all in agreement that
that is ONE thing that is true about 'greater than' in the common
sense sense. Another thing that is true about the common sense
'greater than' relation is that x is always greater than a proper
subset of itself. There is no justification for just taking one of
the properties and identifying it with 'the' notion of greater than
that's applicable to finite sets and ignoring the other.
You may be under the impression that modern mathematics has somehow
answered Galileo's naive argument. No, modern mathematics just
chooses to latch on to one horn of Galileo's dilemma, accepting one
half of the reasoning for the paradox, and just simply ignore the
other half. You don't 'answer' a paradox by just saying, "Okay,
I'll just take the first line of reasoning, and not the second." (I'm
here assuming that you know which argument I'm talking about.)
Third, about the definition of "greater than": It's easy to define
"greater than" for sets: set X is larger than set Y iff the number of
elements in X is greater than the number of elements in Y (so the
notion of a larger set is parasitic on the notion of larger numbers).
It's easy to see (apart from the problem already discussed above) that
it's wrong to use cardinality to define "greater" since greater-than
is a general relation that applies to real numbers, and to natural
numbers as a special case. As to how to 'define' the notion of a
greater *number*, I don't think you can do that. It might be
possible, but I doubt it. Anyway, there doesn't seem to be any need
for that; it's not like some of us don't understand what it means for
one glass to have 'more' water in it than another.
Now some miscellaneous things (the most important part will come at
the end):
iord...@magnus.acs.ohio-state.edu (Ivan Ordonez) writes:
>reality that is infinite. Not even the totality of states the
>Universe could be on is infinite, despite what somebody else said
>before; that number is actually something in the order of
>10^300000.
I don't know what you have in mind, but surely this is wrong. The
number of possible positions of a single particle is already infinite.
And even if you want to talk about quantized properties, the range of
possible states of the wave function is still infinite (even when the
number of possible measurement-outcomes is finite).
>use the concept of cardinality. Since you question the use of
>cardinality as a measure of size, it is your burden to present an
>alternative notion of "larger" that is applicable to infinite
>sets.
No, because I'm saying the notion of "larger" *is not* applicable to
infinite sets. This really should be a pretty simple thing to
understand.
>> (2) x and y can't be of equal size if one is a proper subset of the
>> other.
>
>You cannot say this unless you define size in general enough
>terms to include infinite sets. The ordinary definition
>(cardinality) implies that (2) is only true of finite sets. Your
>"common sense" notion of size is the same as cardinality. So you
What? My thesis is that the notion of size *does not apply* to
infinite sets. So why should I 'define' (read, "redefine") size in
such a way that it would be applicable to infinite sets? That's
precisely what I should NOT do. As to the latter part, as I already
pointed out, no justification has been given for treating cardinality
as equivalent to the ordinary, common sense notion of size; all you're
doing is picking out one characteristic of that notion and ignoring
another one. Was this supposed to convince me?
>Your argument seems to say "I reject the axiom of infinity." You
Yep.
>may well do that out of your arbitrary will, but it will only
>allow you to produce uninteresting mathematics.
You haven't shown this, and in any case, my first interest is in *the
truth*. I reject the axiom of infinity because it's a mistake.
>You must be aware that Galileo lived long before Cantor, Zermelo
>and Fraenkel. The argument does not apply to infinite quantities.
...
>Irrelevant. Aristotle lived thousands of years before Cantor.
The argument *expressly* applies to infinite quantities; that's what
the whole thing is about. What are you talking about? As to the
other part, surely YOU are aware that temporal priority is not a
criterion of truth (there must be some name for this fallacy; it's
some form of argument ad hominem). I mean, "Aristotle has been dead
2000 years; therefore, nothing he said can be worthwhile" -- are you
serious?
>provide a definition of the form "a number X is definite if and
>only if ..." (fill in the blanks). Otherwise your argument is
>unacceptable.
YOU may well find it unacceptable, but I don't care about that. I'm
not going to state an incorrect definition of a term that probably
can't be defined just to satisfy someone else. What kind of arbitrary
standards on 'acceptable' arguments are you imposing here?
And suppose I ask YOU to define "set" for me, and I say if you do not,
then all of your previous statements and arguments about sets are
'unacceptable'?
=====================================
Now, finally, here is the philosophic dispute that's at the bottom of
all this, I think:
>as a subset of X." This is just an axiom. Axioms in math are not
>intrinsically true nor false; they are just premises used to
>build theories and models. It is absurd to say "the axiom of
>infinity is wrong," because that implies that somehow we can
>prove or disprive such axioms. We cannot.
I had a feeling this was going to come out eventually. Here is the
problem between us: I think that mathematics is directly about
*reality*. You think that mathematics is just an arbitrary symbol
game. We make up a bunch of meaningless squiggles and completely
arbitrary rules for moving them around, and then see what patterns of
squiggles we can produce by playing according to the rules. If that
were the case, I would think math was a pretty frivolous and stupid
pursuit.
*I* think mathematics, like all fields of knowledge, is a means of
*understanding* *reality*; and beyond that, it has no point. That
means there are some facts that mathematical concepts integrate. That
is why, when asked to explain what "larger" means, I will point you,
for example, to two buildings, and say, "THAT is larger than THIS";
and I will show you two groups of people and say, "You see this group
is larger than that group," and so on. This is what I think makes
math meaningful at all. But this is precisely why you're going to
keep insisting that my use of mathematical terms is not meaningful; as
long as I'm indicating things in the real world, you're going to
insist you don't understand me. You don't think you 'understand' any
mathematical concept until it's removed from the real world and put
into the realm of arbitrary symbol-manipulation, where the 'meaning'
of a concept is just the collection of (arbitrary) game rules we've
stipulated.
I can only say I most strongly, and profoundly disagree.
Ivan Ordonez Reinoso
In article <4lt1g9$d...@amenti.rutgers.edu>,
Michael Huemer <o...@amenti.rutgers.edu> wrote:
[..]
>Second, you claimed that the common sense notion of "larger" just is
>the notion of "higher cardinality". This is certainly not true (in
>spite of fact 5 above). The common sense 'greater than' relation has
>a number of properties (well, at least 2), among which ONE is that
>when x is larger than y, you can't map the elements of x onto y
>without reusing some of y's members. Yes, we're all in agreement that
>that is ONE thing that is true about 'greater than' in the common
>sense sense. Another thing that is true about the common sense
>'greater than' relation is that x is always greater than a proper
>subset of itself. There is no justification for just taking one of
>the properties and identifying it with 'the' notion of greater than
>that's applicable to finite sets and ignoring the other.
There is a clear justification. We can always use the first criterion, but
not always the second one. Consider the sets {1, 2} and {3, 4, 5}. Neither
is a subset of the other; however, we know that the second is larger than
the first, only through the use of the first criterion, i.e. the notion of
cardinality.
In fact, the first criterion, cardinality, is *sufficient* to establish the
"greater than" relationship among finite sets. We do not need need any other
criterion. However, when restricted to finite sets, the second criterion
follows from cardinality: if |A| < |B| and A is a subset of B, then A is a
proper subset of B. Because this is a logical conclusion of the concept of
cardinality, you add no new information to the concept of "bigger" when
applied to finite sets. Of course, you are free to keep both your criteria;
it will certainly forbid comparison among infinite sets.
However, if we drop your secon criterion, the subset thingy, we do not lose
anything as far as finite sets are concerned, but we gain a lot from a
different point of view: we achieve the ability to generalize to concept of
"bigger" into infinite sets.
Hence, you need a very good reason to include your second criterion by
itself, in spite of the fact that it follows from cardinality. This I do
not see you have done.
[..]
>Third, about the definition of "greater than": It's easy to define
>"greater than" for sets: set X is larger than set Y iff the number of
>elements in X is greater than the number of elements in Y (so the
>notion of a larger set is parasitic on the notion of larger numbers).
Actually, in set theory, it is the other way around: the concept of number
is based on the concept of set. Risking that you tell me again that you
already knew this, I will briefly explain the concept of ordinal, which
corresponds to the naive concept of number:
0 = The empty set, {}.
1 = {0}
2 = {0, 1}
...
omega = {0, 1, 2, ..... } (all the natural numbers)
omega + 1 = {0, 1, 2, ......., omega}
etc.
omega + 1 has the same cardinality as omega; hence not all ordinals are
cardinals (although all finite ordinals are cardinals).
Similarly, all reals, complex and any other kind of numbers are defined in
terms of sets. Set theory is considered the foundation of all mathematics.
Therefore we must first achieve a definition for "larger set," from which in
turn we can derive the definition of "larger number."
>It's easy to see (apart from the problem already discussed above) that
>it's wrong to use cardinality to define "greater" since greater-than
>is a general relation that applies to real numbers, and to natural
>numbers as a special case. As to how to 'define' the notion of a
The above is clearly wrong. See, *all* notions of "greater than" are based
on the concept of cardinality, even for real numbers, which are also sets.
>greater *number*, I don't think you can do that. It might be
>possible, but I doubt it. Anyway, there doesn't seem to be any need
>for that; it's not like some of us don't understand what it means for
>one glass to have 'more' water in it than another.
So yes, we can do that, and there is a need to do that. All math needs to be
based on a set of simple axioms. Set theory is just that, and it allows us
to define in very precise terms from the most simple things (such as "bigger
than" to the most complex ones, including calculus, topology, and several
others. ALL MATH is based on set theory.
I can explain to you very carefully, in terms of set theory and its axioms,
what it means for a glass to have more water than another. But that would be
boring.
[...]
>precisely what I should NOT do. As to the latter part, as I already
>pointed out, no justification has been given for treating cardinality
>as equivalent to the ordinary, common sense notion of size; all you're
>doing is picking out one characteristic of that notion and ignoring
>another one. Was this supposed to convince me?
So you do not see yet that there is not a single property of the common
sense notion of size that is not covered by the concept of cardinality when
applied to finite sets?
>>Your argument seems to say "I reject the axiom of infinity." You
>
>Yep.
>
>>may well do that out of your arbitrary will, but it will only
>>allow you to produce uninteresting mathematics.
>
>You haven't shown this, and in any case, my first interest is in *the
>truth*. I reject the axiom of infinity because it's a mistake.
Let's see. If you reject the axiom of infinity, you end up without real
numbers, integral and differential calculus, group theory, most set theory
itself, all theory of computation and all physics. Your caprice will return
us to the stone age.
The reason to keep that axiom is, as I said before, that it allow us to
provide a sound foundation for all mathematics.
[...]
>some form of argument ad hominem). I mean, "Aristotle has been dead
>2000 years; therefore, nothing he said can be worthwhile" -- are you
>serious?
Aristotle didn't know that it was possible to come up with a sound
axiomatization of set theory that could include infinite sets. This was not
known until the pioneering work of Cantor, Fraenkel, Zermelo, Skolem and
others was achieved.
>>provide a definition of the form "a number X is definite if and
>>only if ..." (fill in the blanks). Otherwise your argument is
>>unacceptable.
>
>YOU may well find it unacceptable, but I don't care about that. I'm
>not going to state an incorrect definition of a term that probably
>can't be defined just to satisfy someone else. What kind of arbitrary
>standards on 'acceptable' arguments are you imposing here?
"Standard" is very simple in this case: definable within the axioms of set
theory. For example, above I presented the conventional definition of
ordinal. See, there is not a single concept in mathematics that is not well
defined using the axioms of set theory.
>And suppose I ask YOU to define "set" for me, and I say if you do not,
>then all of your previous statements and arguments about sets are
>'unacceptable'?
Set theory is the background theory. We must start with something. It just
so happens that most mathematicians accept set theory as the foundation of
everything else. There is no particular reason to do so, except that it
makes things simpler and more elegant. For example, instead of defining
numbers in terms of sets you could do the reverse, but you'd end up with a
clumsy, unelegant theory, although probably equally sound than set theory.
>=====================================
>
>Now, finally, here is the philosophic dispute that's at the bottom of
>all this, I think:
>
>>as a subset of X." This is just an axiom. Axioms in math are not
>>intrinsically true nor false; they are just premises used to
>>build theories and models. It is absurd to say "the axiom of
>>infinity is wrong," because that implies that somehow we can
>>prove or disprive such axioms. We cannot.
>
>I had a feeling this was going to come out eventually. Here is the
>problem between us: I think that mathematics is directly about
>*reality*. You think that mathematics is just an arbitrary symbol
>game. We make up a bunch of meaningless squiggles and completely
I wouldn't call it a "symbol game" but the definition might be precise. See,
physics is about reality; so is history, sociology, biology, etc. Math is
not. It is about abstractions and mental constructions. Axioms in
mathematics (set theory) are considered true, but only by convention.
Consider, for example, the Continuum hypothesis: that the power set of the
naturals has the smallest cardinality that is greater than the cardinality
of the naturals. It was a mathematical mystery for many years, and people
broke their heads trying to prove or to disprove it. Finally, someone
provedf that the CH is completely independent of standard set theory (ZF).
Neither it nor its negation can be proved from ZF. Therefore, the question
"Is the CH true?" is vacuous: you have a sound theory if you say it is true,
but you also have a sound theory if you say it is not true.
In spite of my condescending tone in my first message, I don't really want
to demean you; however, it is very clear to me that you have never studied
math seriously. It is for that reason that you take that "naive realism"
approach to math. How can math be about reality, when nothing in math
refers to reality? See, what happens is that we observe certain structures
in reality that are isomorphic to certain mathematical objects; then we say
we use math to *model* those structures. On the other hand, there are
certain mathematical structures that bear absolutely no analogy to anything
real.
You might want to say "fine." Let's get rid of unreal mathematical objects,
and let's keep only those things that are 'real'". Unfortunately (for you)
there is no way to do that. To make useful models of real things you gotta
keep the nasties, including transfinite sets, cardinal numbers, etc. See,
although you can model reality using math, math is not intrinsically about
reality.
As somebody else said, "reality is just a special case."
>arbitrary rules for moving them around, and then see what patterns of
>squiggles we can produce by playing according to the rules. If that
>were the case, I would think math was a pretty frivolous and stupid
>pursuit.
Well, that frivolous and stupid pursuit is the foundation of all science.
And when it is not directly applicable to anything that you can touch, see
or smell, at least it is still fun.
--
Ivan Ordonez-Reinoso | If you have excess brainpower that
iord...@magnus.acs.ohio-state.edu | you don't want or need, then enjoy
iord...@cis.ohio-state.edu | smoking.
http://www.cis.ohio-state.edu/~iordonez/ | Pierce J. Howard
frank forman
The familiar proof, below, that the natural numbers and the rational
numbers have the same cardinality uses the Axiom of Choice. Would someone
please tell me *how* it is employed and whether the full axiom needs to
be used. Is there a theorem in Reverse Mathematics on this?
In article <4lqs0u$g...@larry.cc.emory.edu>,
Ian Sutherland
In article <formanDq...@netcom.com>,
frank forman <for...@netcom.com> wrote:
>The familiar proof, below, that the natural numbers and the rational
>numbers have the same cardinality uses the Axiom of Choice.
I don't believe it does.
--
Ian Sutherland
i...@eecs.nwu.edu
Sans Peur
Roger Bishop Jones
> The familiar proof, below, that the natural numbers and the rational
> numbers have the same cardinality uses the Axiom of Choice. Would someone
> please tell me *how* it is employed and whether the full axiom needs to
> be used. Is there a theorem in Reverse Mathematics on this?
My guess is:
The description gives an injection from rationals into the natural numbers.
i.e. the set of rationals is smaller than (or equal to) the set of naturals
(in cardinality).
Obviously the rationals are larger than the naturals since they contain them.
To get from there to "same cardinality" you need the Schroder Bernstein
theorem, which says that A<B and B<A => A=B.
To prove this theorem you need the axiom of choice.
I don't actually understand you second question.
Roger Jones http://www.rbjones.com/
at home r...@campion.demon.co.uk
Ian Sutherland
In article <830672...@campion.demon.co.uk>,
Roger Bishop Jones <r...@campion.demon.co.uk> wrote:
>The description gives an injection from rationals into the natural numbers.
>i.e. the set of rationals is smaller than (or equal to) the set of naturals
>(in cardinality).
>Obviously the rationals are larger than the naturals since they contain them.
>To get from there to "same cardinality" you need the Schroder Bernstein
>theorem, which says that A<B and B<A => A=B.
>To prove this theorem you need the axiom of choice.
I don't believe you need AC to prove Schroder-Bernstein.
Where does the usual proof with ancestrals need AC?
Cal Rice
: Cal Rice and Ivan Ordonez have recently joined the 'cardinality'
: thread. Let me say a couple of things so that we don't have
: unnecessary repetitions:
Sorry about the math lesson, and rather than try to jump into your
thread, I'll start a new thread about the power of the continuum.
frank forman
>
>> The familiar proof, below, that the natural numbers and the rational
>> numbers have the same cardinality uses the Axiom of Choice. Would someone
>> please tell me *how* it is employed and whether the full axiom needs to
>> be used. Is there a theorem in Reverse Mathematics on this?
>
>My guess is:
>
>i.e. the set of rationals is smaller than (or equal to) the set of naturals
>(in cardinality).
>Obviously the rationals are larger than the naturals since they contain them.
>To get from there to "same cardinality" you need the Schroder Bernstein
>theorem, which says that A<B and B<A => A=B.
>To prove this theorem you need the axiom of choice.
>
Reverse Mathematics just shows the *minimal* axioms of set theory needed
to prove one of the standard theorems in mathematics. In the above case,
I don't think we need the full axiom of choice, just the countable
version. In other words, *if* the rationals are countable, then for every
countable collection of non-empty sets, there is a choice function
picking out a member from each set. But I don't know that this is true,
which is why I'm posting the question.
P.S. I got an e-mail from someone who lives in England and has to pay for
*each* message. He is worried that readers on alt.philosophy.objectivism
will flood him with irrelevant political stuff. Well, I added sci.logic
to the Newsgroup list so that readers on a.p.o. could learn the answers
(or proposed answers) to my question, not to contribute themselves unless
they really had something to say about set theory.
Ian Sutherland
>I don't think we need the full axiom of choice, just the countable
>version. In other words, *if* the rationals are countable, then for every
>countable collection of non-empty sets, there is a choice function
>picking out a member from each set.
If I'm interpreting you correctly, this "axiom" is a
theorem of ZF! By "countable AC" you seem to mean
for all sets X, if X is countable, then for every
countable collection S of subsets of X, there is a
choice function on S.
You can prove something even stronger in ZF, namely
for all sets X, if X is countable, then there is a
choice function on the set of _all_ nonempty
subsets of X.
The proof is simple. Let x_1,x_2,... be an enumeration of
X (you _don't_ need the axiom of choice to get such an
enumeration). Define C on the nonempty subsets of X as
follows: C(S) is x_i where i is the smallest i such that
x_i is an element of S.
>But I don't know that this is true,
>which is why I'm posting the question.
Can you please tell me why you believe that the result you
quoted requires the axiom of choice? I'm really pretty
certain that it doesn't ...
ilias kastanas 08-14-90
In article <830672...@campion.demon.co.uk>,
Roger Bishop Jones <r...@campion.demon.co.uk> wrote:
>In article <formanDq...@netcom.com> for...@netcom.com "frank forman" writes:
>> The familiar proof, below, that the natural numbers and the rational
>> numbers have the same cardinality uses the Axiom of Choice. Would someone
>> please tell me *how* it is employed and whether the full axiom needs to
>> be used. Is there a theorem in Reverse Mathematics on this?
>My guess is:
>The description gives an injection from rationals into the natural numbers.
>i.e. the set of rationals is smaller than (or equal to) the set of naturals
>(in cardinality).
>Obviously the rationals are larger than the naturals since they contain them.
>To get from there to "same cardinality" you need the Schroder Bernstein
>theorem, which says that A<B and B<A => A=B.
>To prove this theorem you need the axiom of choice.
>I don't actually understand you second question.
On some matters of choice:
The Schroeder-Bernstein theorem does not need AC in its proof; that
is the whole point. In the presence of AC every set can be mapped 1-1 onto
an ordinal, and the theorem follows trivially.
A 1-1 and onto mapping between omega and Q does not need AC either.
There is no need for even a single choice; it is essentially a coding of
pairs, duly modified, obtainable in various ways as a primitive recursive
function.
As such, it can be constructed using no more than a fragment of Peano
Arithmetic... so it does not rise to the level of Reverse Mathematics (or
so I think).
Attempting to read between the lines, I would guess the posting's
"reason" is this. In proving a countable union of countable sets to be
countable, one usually enumerates the set A_i as a_i1, a_i2,..., at the
i-th row, and obtains an enumeration of U A_i by zig-zag, just like one
does for Q. Now this theorem _does_ need choice, albeit a weak form: one
needs to choose an enumeration for each A_i, and that's countably many
choices. There is no avoiding it; models of set theory without AC exist
where the theorem fails, and in fact the reals R are a countable union
of countable sets.
This does not carry over to Q; Q can be handled without AC. Each
"row" A_i, of pairs (i, j) has a natural, definable ordering via the j's,
obviating any need for choice.
Ilias
Roger Bishop Jones
In article <4m0l4p$3...@news.eecs.nwu.edu>
i...@eecs.nwu.edu "Ian Sutherland" writes:
> In article <830672...@campion.demon.co.uk>,
> Roger Bishop Jones <r...@campion.demon.co.uk> wrote:
> >The description gives an injection from rationals into the natural numbers.
> >i.e. the set of rationals is smaller than (or equal to) the set of naturals
> >(in cardinality).
> >Obviously the rationals are larger than the naturals since they contain them.
> >To get from there to "same cardinality" you need the Schroder Bernstein
> >theorem, which says that A<B and B<A => A=B.
> >To prove this theorem you need the axiom of choice.
>
> I don't believe you need AC to prove Schroder-Bernstein.
> Where does the usual proof with ancestrals need AC?
Well, I did say I was guessing!
The SB theorem was the bit that I understood badly enough for there
to be room for AC.
I think I will defer to your greater competence.
Ivan Ordonez Reinoso
>To get from there to "same cardinality" you need the Schroder Bernstein
>theorem, which says that A<B and B<A => A=B.
>To prove this theorem you need the axiom of choice.
No, Schroder-Bernstein does not require AC. As far as cardinality is
concerned, all AC buys you is the ability to compare all carinals; without
AC they are only a partial order.
Roger Bishop Jones
In article <4m21mb$4...@nuke.csu.net>
ika...@uranus.uucp "ilias kastanas 08-14-90" writes:
> In article <830672...@campion.demon.co.uk>,
> Roger Bishop Jones <r...@campion.demon.co.uk> wrote:
> >In article <formanDq...@netcom.com> for...@netcom.com "frank forman"
> writes:
>
> >> The familiar proof, below, that the natural numbers and the rational
> >> numbers have the same cardinality uses the Axiom of Choice. Would someone
> >> please tell me *how* it is employed and whether the full axiom needs to
> >> be used. Is there a theorem in Reverse Mathematics on this?
>
> >My guess is:
>
> >The description gives an injection from rationals into the natural numbers.
> >i.e. the set of rationals is smaller than (or equal to) the set of naturals
> >(in cardinality).
> >Obviously the rationals are larger than the naturals since they contain them.
> >To get from there to "same cardinality" you need the Schroder Bernstein
> >theorem, which says that A<B and B<A => A=B.
> >To prove this theorem you need the axiom of choice.
>
> >I don't actually understand you second question.
>
>
> On some matters of choice:
>
<snip>
> Attempting to read between the lines, I would guess the posting's
> "reason" is this. In proving a countable union of countable sets to be
> countable, one usually enumerates the set A_i as a_i1, a_i2,..., at the
> i-th row, and obtains an enumeration of U A_i by zig-zag, just like one
> does for Q. Now this theorem _does_ need choice, albeit a weak form: one
> needs to choose an enumeration for each A_i, and that's countably many
> choices. There is no avoiding it; models of set theory without AC exist
> where the theorem fails, and in fact the reals R are a countable union
> of countable sets.
Its very kind of you to attempt to reverse construct a rationale for my
posting, but this credits me with rather more depth than I can muster
on this topic.
The banal truth is that I was shooting from the hip on a topic which I
should have left to others. I think I managed at least two elementary
blunders. Firstly to believe that the Schroder Bernstein theorem is needed
to fill in the proof sketch, and secondly to guess that the axiom of
choice is necessary to prove the Schroder Bernstein theorem.
Better luck next time, maybe.
Robert Livermore
On Sun, 28 Apr 1996, Roger Bishop Jones wrote:
> In article <formanDq...@netcom.com> for...@netcom.com "frank forman" writes:
>
> > The familiar proof, below, that the natural numbers and the rational
> > numbers have the same cardinality uses the Axiom of Choice. Would someone
> > please tell me *how* it is employed and whether the full axiom needs to
> > be used. Is there a theorem in Reverse Mathematics on this?
>
> My guess is:
>
> The description gives an injection from rationals into the natural numbers.
> i.e. the set of rationals is smaller than (or equal to) the set of naturals
> (in cardinality).
> Obviously the rationals are larger than the naturals since they contain them.
> To get from there to "same cardinality" you need the Schroder Bernstein
> theorem, which says that A<B and B<A => A=B.
> To prove this theorem you need the axiom of choice.
>
> I don't actually understand you second question.
>
> Roger Jones http://www.rbjones.com/
> at home r...@campion.demon.co.uk
>
>
Guess again, Roger - you're wrong. The rationals and the naturals or the
integers are equal in cardinality. Transfinite arithmetic and finite
arithmetic are different. You show equivalence by showing that a one
to one function exists whose domain is one of the sets and whose range is
the other. The discussion above relying on diagonalizing showed how to find a
function of that sort between rationals - fractions - and integers - whole
numbers. This is another well known proof using a diagonalizing process
which shows in fact that no such function can be found whose domain is the
reals and whose range is the integers or anything equivalent to the
integers. This is Cantor's proof. Another way of seeing this is to
note that the reals are equivalent to the power set of the integers and
that the cardinality of the power set is greater than that of the set.
Robert Livermore
Michael Huemer
>In article <4m21mb$4...@nuke.csu.net>
> ika...@uranus.uucp "ilias kastanas 08-14-90" writes:
>> choices. There is no avoiding it; models of set theory without AC exist
>> where the theorem fails, and in fact the reals R are a countable union
>> of countable sets.
By the way, can you explain this? I don't see how the reals could be
a countable union of countable sets; it seems to me at the moment that
if this were true, it would be easily possible to construct a function
mapping the natural numbers onto the reals. Roughly, let's suppose
these countable sets you refer to are designated S1, S2, S3, ... It's
possible to so designate them, without leaving any out, because you've
said there are countably many of them.
And designate the elements of these sets like so:
S1 = {E11, E12, E13, . . .}
S2 = {E21, E22, E23, . . .}
S3 = {E31, E32, E33, . . .}
.
.
.
Again, it's possible to so designate the elements in each case because
you've said that each of S1, S2, S3, ... have countably many elements.
What you said above was that the set of real #s is the union of S1,
S2, S3, ...; i.e. all the real numbers would appear somewhere in the
little table I listed above -- every real number would appear as Enm,
for some natural numbers n and m. But then I think you can see how it
would be easy now to 'count' the real numbers. (Take E11, E12, E21,
E13, E22, E31, ...)
Where's the mistake in this?
Ian Sutherland
In article <4m6afm$n...@amenti.rutgers.edu>,
Michael Huemer <o...@amenti.rutgers.edu> wrote:
>And designate the elements of these sets like so:
>
>S1 = {E11, E12, E13, . . .}
>S2 = {E21, E22, E23, . . .}
>S3 = {E31, E32, E33, . . .}
>.
>.
>.
>
>Again, it's possible to so designate the elements in each case because
>you've said that each of S1, S2, S3, ... have countably many elements.
Let ENUMi be the collection of enumerations of Si, that is,
the collection of mappings from the natural numbers onto
Si. In order to constuct the function which you want to
construct which maps the natural numbers onto the reals,
you much choose an element of ENUMi for each i. In other
words, you much choose an element from each of a countably
infinite collection of sets. You cannot do this without
AC.
>What you said above was that the set of real #s is the union of S1,
>S2, S3, ...; i.e. all the real numbers would appear somewhere in the
>little table I listed above
Not so "little": it has an infinite number of rows and
columns!
Matthew Barsoum
In article <4m6dvj$2...@news.eecs.nwu.edu>,
Ian Sutherland <i...@eecs.nwu.edu> wrote:
>Let ENUMi be the collection of enumerations of Si, that is,
>the collection of mappings from the natural numbers onto
>Si. In order to constuct the function which you want to
>construct which maps the natural numbers onto the reals,
>you much choose an element of ENUMi for each i. In other
>words, you much choose an element from each of a countably
>infinite collection of sets. You cannot do this without
>AC.
...
This all becomes far more interesting if you ask mathematicians
why they do not need to postulate uncomputable reals (or sets)
in some manner. I'll have to ask the Pure Math prof I know.
Ever uncompromising,
Tom Koziol (c/o Matt).
Matthew P Wiener
In article <4m6afm$n...@amenti.rutgers.edu>, owl@amenti (Michael Huemer) writes:
>>In article <4m21mb$4...@nuke.csu.net>
>> ika...@uranus.uucp "ilias kastanas 08-14-90" writes:
>>> choices. There is no avoiding it; models of set theory without
>>> AC exist where the theorem fails, and in fact the reals R are a
>>> countable union of countable sets.
>By the way, can you explain this? I don't see how the reals could be
>a countable union of countable sets;
You need some form of choice to prove this.
> it seems to me at the moment that
>if this were true, it would be easily possible to construct a function
>mapping the natural numbers onto the reals.
Only if the countable sets were easily describable.
> Roughly, let's suppose
>these countable sets you refer to are designated S1, S2, S3, ... It's
>possible to so designate them, without leaving any out, because you've
>said there are countably many of them.
Correct.
>And designate the elements of these sets like so:
>S1 = {E11, E12, E13, . . .}
>S2 = {E21, E22, E23, . . .}
>S3 = {E31, E32, E33, . . .}
>.
>.
>Again, it's possible to so designate the elements in each case because
>you've said that each of S1, S2, S3, ... have countably many elements.
However, it is not a priori clear, without the axiom of choice, how to
_simultaneously_ pick countably many enumerations of structureless sets.
>What you said above was that the set of real #s is the union of S1,
>S2, S3, ...; i.e. all the real numbers would appear somewhere in the
>little table I listed above -- every real number would appear as Enm,
>for some natural numbers n and m. But then I think you can see how it
>would be easy now to 'count' the real numbers. (Take E11, E12, E21,
>E13, E22, E31, ...)
>Where's the mistake in this?
For each Si, let ESi denote the set of of enumerations N->Si. The
starting assumption is that each ESi is not empty. With choice, you
can pick a particular Eij for each i, and then combine them as you
indicate to enumerate the reals.
Ergo, assuming the axiom of choice, the reals are not a countable union
of countably many sets.
Otherwise, all bets are off. There are, as Ilias indicated, explicit
models of ZF such that the reals are a countable union of countable sets.
--
-Matthew P Wiener (wee...@sagi.wistar.upenn.edu)
Rob Arthan
In article <formanDq...@netcom.com>,
for...@netcom.com (frank forman) wrote:
>The familiar proof, below, that the natural numbers and the rational
>numbers have the same cardinality uses the Axiom of Choice.
>....
>>> The set of positive integers is not smaller than the set of positive
>> rational numbers because, if you lay out the set of positive rational
>> numbers like so,
>>
>> 1/1 1/2 1/3 . . .
>> 2/1 2/2 2/3 . . .
>> 3/1 3/2 3/3 . . .
>> . . . . . .
>> . . . . . . ,
>>
>> you can then match the set of positive integers with the elements of
>> of this array
>>...
>> All positive integers will then be matched with all
>> of the positive rational numbers, and then some, because the array
>> contains duplicated rationals.
I.e., at this point the argument as stated says that there is a surjection
from the positive integers (N+, say), onto the positive rationals, (Q+,
say)
(or, at least, that's how I read "matched ... and then some").
As lots of people have pointed out, if you use the diagram somewhat
differently to see it as showing an injection of Q+ into N+, then you can
appeal to the Schroeder-Bernstein theorem (which can be proved without AC)
to conclude that N+ and Q+ have the same cardinality.
Alternatively, you can grub around a bit harder and construct a bijection
from N+ to Q+ directly just using a bit of arithmetic. For example, beaver
away on the picture using induction to define a function from N+ onto the
pairs i/j with i and j coprime (essentially what Ilias kastanas suggested,
I think), or forget the picture and use the fundamental theorem of
arithmetic and a bijection between N+ and the integers.
So, with or without an appeal to S-B, you find that the fact to be proved
does not need AC. However, the argument *as stated* seems to be trying to
use a surjection from N+ onto Q+ (and the obvious injection of N+ into Q+)
to conclude that N+ and Q+ have equal cardinality - and S-B won't justify
that.
This raises some questions. There are two obvious ways of ordering sets by
cardinality: (1), use injections - say A <= B, iff. there as an injection
from A into B, or (2), use surjections - say A >= B, iff. there is a
surjection from A onto B. Both orderings are reflexive and transitive, and
(1) is the one which is generally used.
Given AC, the two orderings are the same and both are total: i.e., for any
sets A and B, A <= B or B <= A, and similarly for >=. Without AC, I don't
believe you can prove that either ordering is total, but S-B gives an
interesting property of the ordering by injections. However, the proofs of
S-B that I know don't seem to work for the ordering by surjections. So here
are the questions:
(a) Is the analogue of S-B for the ordering by surjections true?
(b) If (a) is false, is the analogue of S-B equivalent to AC? I.e., is AC
implied by the statement that, given any two sets A and B, the existence of
surjections from A onto B and from B onto A implies the existence of a
bijection between A and B?
(c) Is AC equivalent to the fact that the ordering by surjections is total?
I.e., is AC implied by the statement that, given any two sets A and B,
there is either a surjection of A onto B or of B onto A? (The analogous
result for injections is true.)
Sorry if this is off-topic for alt.philosophy.objectivism!
Rob Arthan (r...@trireme.demon.co.uk)
Ian Sutherland
In article <ADAD86B9...@trireme.demon.co.uk>,
Rob Arthan <r...@trireme.demon.co.uk> wrote:
>However, the argument *as stated* seems to be trying to
>use a surjection from N+ onto Q+ (and the obvious injection of N+ into Q+)
>to conclude that N+ and Q+ have equal cardinality - and S-B won't justify
>that.
True, but when the domain of the surjection is
well-orderable (as N+ is :-) you can turn the surjection
into an injection in the opposite direction trivially
without AC. You're right though, this step was not
included in the proposed proof.
>(c) Is AC equivalent to the fact that the ordering by surjections is total?
Yes. Assume ordering by surjections is total. Fix a set
X. We'll construct a well-ordering of X.
(1) It cannot be the case that X can be mapped onto every
ordinal. Assume not. In ZF we can prove that there exists
a set containing all pairs (E,<) where E is an equivalence
relation on X, < is a binary relation on X, and < is a
well-ordering of the equivalence classes of E. If X could
be mapped onto every ordinal, then every ordinal would be
isomorphic to the ordered set of equivalence classes for
some such (E,<), so by Replacement, the ordinals form a
set. This gives a contradiction by the Burali-Forti
paradox.
(2) Let O be an ordinal that X cannot be mapped onto; then
O can be mapped onto X. Let F be a function which maps O
onto X. Define G : X -> O by G(x) = the smallest C in O
such that F(C) = x. G is obviously 1-1, so we have a 1-1
mapping of X into a well-ordered set, which induces a
well-ordering on X.
Moses Klein
Followups restricted to sci.logic
In article <ADAD86B9...@trireme.demon.co.uk>,
Rob Arthan <r...@trireme.demon.co.uk> wrote:
>(a) Is the analogue of S-B for the ordering by surjections true?
>
>(b) If (a) is false, is the analogue of S-B equivalent to AC?
Offhand I don't know. I'll think about it some more.
>(c) Is AC equivalent to the fact that the ordering by surjections is total?
Yes, by essentially the same proof as for the ordering by injections.
Given a set S, there must be some ordinal a greater than S. Then we can
well-order S as follows: Fix a surjection from a onto S. For x in S define
f(x) as the least element of a which maps to x. Then f injects S into an
ordinal, thereby inducing a well-ordering.
Moses Klein (kl...@math.wisc.edu)
Fred Galvin
On Wed, 1 May 1996, Rob Arthan wrote:
[...]
> This raises some questions. There are two obvious ways of ordering sets by
> cardinality: (1), use injections - say A <= B, iff. there as an injection
> from A into B, or (2), use surjections - say A >= B, iff. there is a
> surjection from A onto B. Both orderings are reflexive and transitive, and
> (1) is the one which is generally used.
>
> Given AC, the two orderings are the same and both are total: i.e., for any
> sets A and B, A <= B or B <= A, and similarly for >=. Without AC, I don't
> believe you can prove that either ordering is total, but S-B gives an
> interesting property of the ordering by injections. However, the proofs of
> S-B that I know don't seem to work for the ordering by surjections. So here
> are the questions:
>
> (a) Is the analogue of S-B for the ordering by surjections true?
>
> (b) If (a) is false, is the analogue of S-B equivalent to AC? I.e., is AC
> implied by the statement that, given any two sets A and B, the existence of
> surjections from A onto B and from B onto A implies the existence of a
> bijection between A and B?
>
> (c) Is AC equivalent to the fact that the ordering by surjections is total?
> I.e., is AC implied by the statement that, given any two sets A and B,
> there is either a surjection of A onto B or of B onto A? (The analogous
> result for injections is true.)
[...]
> Rob Arthan (r...@trireme.demon.co.uk)
The first two questions are too hard for me; I'll leave those to the
set-theorists. The answer to question (c) is yes: assuming that the
surjective ordering is total, we can prove that an any set A can has a
well-ordering. Applying Hartogs' theorem to the power set P(A), we get a
well-orderable set W such that there is no injection from W to P(A). It
follows that there is no surjection from A to W, so there must be a
surjection from W to A. Given such a surjection, a well-ordering of W
induces a well-ordering of A.
By the way, there is a little discussion of the surjective ordering in
Waclaw Sierpinski, Cardinal and Ordinal Numbers, second edition, PWN
(Polish Scientific Publishers), 1965: see VIII.4, pp. 157-160, and XVI.3,
pp. 429-430. In fact, the latter section is titled "A. Lindenbaum's
theorem", and is precisely the answer to your question (c). Sierpinski
refers to some old papers by Tarski, Lindenbaum, and himself.
I just looked in the MathSci data base, using the keywords "surjective"
and "cardinals" and found this reference: J. K. Truss, Cancellative laws
for surjective cardinals, Ann. Pure Appl. Logic 27 (1984), 165-207.
ilias kastanas 08-14-90
[ . . . ]
:This raises some questions. There are two obvious ways of ordering sets by
:cardinality: (1), use injections - say A <= B, iff. there as an injection
:from A into B, or (2), use surjections - say A >= B, iff. there is a
:surjection from A onto B. Both orderings are reflexive and transitive, and
:(1) is the one which is generally used.
Maybe "because" an injection from A to B easily yields a surjection
the other way.
:Given AC, the two orderings are the same and both are total: i.e., for any
:sets A and B, A <= B or B <= A, and similarly for >=. Without AC, I don't
:believe you can prove that either ordering is total, but S-B gives an
:interesting property of the ordering by injections. However, the proofs of
:S-B that I know don't seem to work for the ordering by surjections. So here
:are the questions:
:
:(a) Is the analogue of S-B for the ordering by surjections true?
The answer is: no, it is not true. A construction can be based
on an infinite, Dedekind-finite set.
Ilias
Fred Galvin
On Thu, 2 May 1996, Fred Galvin wrote:
> On Wed, 1 May 1996, Rob Arthan wrote:
[...]
> > This raises some questions. There are two obvious ways of ordering sets by
> > cardinality: (1), use injections - say A <= B, iff. there as an injection
> > from A into B, or (2), use surjections - say A >= B, iff. there is a
> > surjection from A onto B. Both orderings are reflexive and transitive, and
> > (1) is the one which is generally used.
> >
> > Given AC, the two orderings are the same and both are total: i.e., for any
> > sets A and B, A <= B or B <= A, and similarly for >=. Without AC, I don't
> > believe you can prove that either ordering is total, but S-B gives an
> > interesting property of the ordering by injections. However, the proofs of
> > S-B that I know don't seem to work for the ordering by surjections. So here
> > are the questions:
> >
> > (a) Is the analogue of S-B for the ordering by surjections true?
[...]
> I just looked in the MathSci data base, using the keywords "surjective"
> and "cardinals" and found this reference: J. K. Truss, Cancellative laws
> for surjective cardinals, Ann. Pure Appl. Logic 27 (1984), 165-207.
Oops, the first word in that title is "Cancellation", not "Cancellative".
Truss's definition of "surjective cardinals" seems to indicate that there
is no Schroder-Bernstein theorem for surjections (in ZF), or at any rate,
if there is one, it was not known to Truss when he wrote that paper.
Inasmuch as the S-B theorem for surjections would be *stronger* than the
S-B theorem for injections (for nonempty sets, the existence of an
injection from A to B implies the existence of a surjection from B to A;
the converse is the axiom of choice), you'd think that, if there were
such a theorem, we would all have heard of it. So I guess the "surjective
S-B theorem" is not provable in ZF; maybe one of the set-theory experts
who reads this group will explain why. For the same reason, the following
intermediate S-B theorem is probably not a (known) theorem of ZF either:
"if there are maps f:A-->B and g:A-->B such that f is injective and g is
surjective, then there is a bijection between A and B".
Mike Oliver
In article <4mbl3q$j...@nuke.csu.net> ika...@uranus.uucp (ilias kastanas 08-14-90) writes:
>In article <ADAD86B9...@trireme.demon.co.uk>,
>Rob Arthan <r...@trireme.demon.co.uk> wrote:
>: Both orderings are reflexive and transitive, and
>:(1) is the one which is generally used.
> Maybe "because" an injection from A to B easily yields a surjection
> the other way.
Note that this uses excluded middle. For example, in Martin-L\"of's
Intuitionistic Type Theory (ITT), it *is* true that for every surjection
there's an injection (choice holds because, essentially, before you can
assert that something is surjective you have to have a way of finding
preimages) but it's *not* true that for every injection there's a
surjection (because you might not be able to tell whether or not a
given point is in the range of the injection).
>:(a) Is the analogue of S-B for the ordering by surjections true?
> The answer is: no, it is not true. A construction can be based
> on an infinite, Dedekind-finite set.
You don't need to go to something *that* strange. For example, if AD
holds then P(omega)/fin is strictly bigger (in cardinality based on
injections) than P(omega), but there is an obvious surjection from
P(omega) to P(omega)/fin (and the surjection the other way you get
from the injection).
You can even find A and B such that there are surjections both ways,
but no injection either way.
Fred Galvin
On Wed, 1 May 1996, Rob Arthan wrote:
[...]
> This raises some questions. There are two obvious ways of ordering sets by
> cardinality: (1), use injections - say A <= B, iff. there as an injection
> from A into B, or (2), use surjections - say A >= B, iff. there is a
> surjection from A onto B. Both orderings are reflexive and transitive, and
> (1) is the one which is generally used.
>
> Given AC, the two orderings are the same and both are total: i.e., for any
> sets A and B, A <= B or B <= A, and similarly for >=. Without AC, I don't
> believe you can prove that either ordering is total, but S-B gives an
> interesting property of the ordering by injections. However, the proofs of
> S-B that I know don't seem to work for the ordering by surjections. So here
> are the questions:
>
> (a) Is the analogue of S-B for the ordering by surjections true?
>
> (b) If (a) is false, is the analogue of S-B equivalent to AC? I.e., is AC
> implied by the statement that, given any two sets A and B, the existence of
> surjections from A onto B and from B onto A implies the existence of a
> bijection between A and B?
The answer to (a) is yes and no: the "Schroder-Bernstein theorem for
surjections" is "true" because AC is "true"; however, it is *not*
provable in ZF (which of course is what you meant) because it implies the
following statement, which is much weaker that AC (it follows from DC)
but is known to be independent of ZF: every infinite set has a countably
infinite subset. Here is a proof.
Let S be any infinite set. Let A be the set of all finite sequences (of
any length including 0) of *distinct* elements of S, i.e., nonrepeating
sequences. Let B be the set obtained from A by deleting the null
sequence. It is easy to define surjective maps f:A-->B and g:B-->A.
Namely, define f(X)=X if length(X) > 0, and f(the null sequence) = any
element of B; and define g(X) to be the sequence obtained from X by
dropping the last term. If we assume the "surjective analogue of the
Schroder-Bernstein theorem", there is an injective map h:A-->B. It
follows that there is an infinite sequence of *distinct* elements of A,
namely the sequence 0, h(0), h(h(0)), h(h(h(0))), ..., where 0 denotes
the null sequence. If we concatenate this infinite sequence of finite
sequences, we get an infinite sequence of elements of S, which may have
repetitions; the *range* of this sequence is a countably infinite subset
of S, Q.E.D.
Ilias Kastanas
In article <4mdkla$1b...@saba.info.ucla.edu>,
Mike Oliver <oli...@oak.math.ucla.edu> wrote:
>In article <4mbl3q$j...@nuke.csu.net> ika...@uranus.uucp (ilias kastanas 08-14-90) writes:
>>In article <ADAD86B9...@trireme.demon.co.uk>,
>>Rob Arthan <r...@trireme.demon.co.uk> wrote:
>
>>:(1) is the one which is generally used.
>
>> the other way.
>
Oh yes. I answered within classical mathematics. Thanks
for the Martin-Loef observation.
>>:(a) Is the analogue of S-B for the ordering by surjections true?
>
>> The answer is: no, it is not true. A construction can be based
>> on an infinite, Dedekind-finite set.
>
>You don't need to go to something *that* strange. For example, if AD
>holds [ . . . ]
Calling such a set "strange"... there is a _model_ with one, starting
from a model of ZF. Maybe I am missing something, but... how do we get a
model of AD!? You probably know, Mike, that I'm not ill-disposed towards
Determinacy; one can contemplate L[R], and so on. An actual model of AD,
though?
Ilias
Mike Oliver
ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
> Calling such a set [infinite but Dedekind finite] "strange"... there is
> a _model_ with one, starting from a model of ZF.
Really? This is a quibble but I assumed you would have to go to a generic
extension. Of course if all you want is a countable model of an arbitrarily
large finite fragment of ZF, you can get that inside your original model.
> Maybe I am missing something, but... how do we get a
> model of AD!? You probably know, Mike, that I'm not ill-disposed towards
> Determinacy; one can contemplate L[R], and so on. An actual model of AD,
> though?
Well, with a harmless little large-cardinal assumption (the sharp of an
iterable model for omega Woodin cardinals) you get that L(R) *is* a model
for AD.
But my point was not formal consistency strength; it was that I, personally,
find it very difficult to think about an infinite set that I can't pick omega
things from. Having DC around makes me happier.
Ilias Kastanas
In article <4mjbcs$l...@saba.info.ucla.edu>,
Mike Oliver <oli...@oak.math.ucla.edu> wrote:
>ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>
>> Calling such a set [infinite but Dedekind finite] "strange"... there is
>> a _model_ with one, starting from a model of ZF.
>Really? This is a quibble but I assumed you would have to go to a generic
>extension. Of course if all you want is a countable model of an arbitrarily
>large finite fragment of ZF, you can get that inside your original model.
From a model of ZF you do go to a generic extension... and eventu-
ally reach a model with an infinite set of reals that has no countable
subset. Hence ~ AC. I guess I said it elliptically above.
>> Maybe I am missing something, but... how do we get a
>> model of AD!? You probably know, Mike, that I'm not ill-disposed towards
>> Determinacy; one can contemplate L[R], and so on. An actual model of AD,
>> though?
>
>Well, with a harmless little large-cardinal assumption (the sharp of an
>iterable model for omega Woodin cardinals) you get that L(R) *is* a model
>for AD.
A minuscule, innocuous L.C. assumption!?
>But my point was not formal consistency strength; it was that I, personally,
>find it very difficult to think about an infinite set that I can't pick omega
>things from. Having DC around makes me happier.
No one will lay a hand on DC... Now, logical strength aside, _why_
would Product X_i, X_i =/= 0, trigger the intuition that it is non-0
if the X_i are countably many, but not if there are uncountably many?
Likewise for DC ... doesn't DC-kappa have just as good a claim? This
is vague, but it might be interesting.
Ilias
Mike Oliver
> No one will lay a hand on DC... Now, logical strength aside, _why_
> would Product X_i, X_i =/= 0, trigger the intuition that it is non-0
> if the X_i are countably many, but not if there are uncountably many?
Well, of course that intuition *is* triggered if there are uncountably
many. It's just that I know how to work around it in models where it
fails. I know not to expect to be able to choose uncountable wellordered
sequences from arbitrary sets, etc.
But not being able to choose even omega of them? Having a tree such
that I can go along it as long as I like and never get stuck, but
nevertheless there's no way through it? Then I just don't know *what*
to do.
> Likewise for DC ... doesn't DC-kappa have just as good a claim? This
> is vague, but it might be interesting.
Well, almost as good a claim. Then it's like the above situation, except
that I might be going through some limit stages on the tree.
That's the thing; limit stages are slightly less hardwired in my brain
than integer stages. I can accept weird things happening when you have
to go through limit steps more easily than when you don't. The failure
of DC_omega just brings the weirdness closer to home, to objects I
feel I should understand completely (even though I've argued that this
is an illusion, the feeling is still there).
Bill Taylor
oli...@oak.math.ucla.edu (Mike Oliver) writes:
|> if AD
|> holds then P(omega)/fin is strictly bigger (in cardinality based on
|> injections) than P(omega),
How does one get an injection from P(omega) to P(omega)/fin, using AD?
Is it easy enough to relate here? Be nice to see it.
|> You can even find A and B such that there are surjections both ways,
|> but no injection either way.
Right; this would be fun to see. In fact, whereas with AC there are only
two possible cardinality comparisons between two sets,
either A <------> B (bijection)
or A --in--> B (injection but not bi), [or vice versa of course];
there seem to be 6 possibilities, without any form of choice/determinacy:-
1. A <------> B
2. A --in--> B
3. A --on--> B
4. A --on-->
<--on-- B
5. A --on-->
--in--> B
6. A (none) B
where the injections and surjections shown are all there are, (taking account
that A --in--> B implies A <--on-- B of course).
Could you, Mike, or elseone, provide any simple (seeming-)examples of
cases 3,4,5 & 6, please?
Thanks.
==============================================================================
__ __ _________________ ||
/\ \ / \ / _______________/\ || M A C A W
\ \ \ / /\ \ / / ______ ______\/ || A D O R E
\ \ \ / /\ \ \ / /_/__ \ \ \ || C O M E T
\ \ \ / / \ \ \ / _____/\ \ \ \ || A R E N A
\ \ \ / / \ \ \ / /\____\/ \ \ \ || W E T A S
\ \ \/ / \ \ \/ / / \ \ \ ||
\ \__/ \ \__/ / \ \ \ ||===========================
\/_/ \/__\/ \_\/ || w...@math.canterbury.ac.nz
==============================================================================
Mike Oliver
>How does one get an injection from P(omega) to P(omega)/fin, using AD?
>Is it easy enough to relate here? Be nice to see it.
You don't need AD to get the injection. Just partition omega into
omega infinite pieces; call them C_0,C_1,.... Now for any subset S of
omega, let f(S) be
union{i \in S} C_i
It is clear then that if S != T, then f(S) and f(T) differ in infintely
many places, so they have different equivalence classes.
>there seem to be 6 possibilities, without any form of choice/determinacy:-
>Could you, Mike, or elseone, provide any simple (seeming-)examples of
>cases 3,4,5 & 6, please?
I think I can get them all. I'll try to figure it out and post.
Michael Abbott
Mike Oliver wrote:
>
> In article <4mbl3q$j...@nuke.csu.net> ika...@uranus.uucp (ilias kastanas 08-14-90) writes:
> >In article <ADAD86B9...@trireme.demon.co.uk>,
> >Rob Arthan <r...@trireme.demon.co.uk> wrote:
>
> >: Both orderings are reflexive and transitive, and
> >:(1) is the one which is generally used.
>
> > Maybe "because" an injection from A to B easily yields a surjection
> > the other way.
>
> Intuitionistic Type Theory (ITT), it *is* true that for every surjection
> there's an injection (choice holds because, essentially, before you can
> assert that something is surjective you have to have a way of finding
> preimages) but it's *not* true that for every injection there's a
> surjection (because you might not be able to tell whether or not a
> given point is in the range of the injection).
There's something I don't understand. I am not familiar with Martin-Loef type
theory but I frequently see it described as intuitionistic - but in my
understanding of Intuitionistic Type Theory (based I guess on Local Sets) the
Axiom of Choice is strictly NOT available because it forces decidability.
There is a simple proof that AC|-MP. Would somebody be willing to help
me to understand why this proof doesn't work in M-L type theory? Thanks very
much.
Michael
Ilias Kastanas
In article <4mo292$21...@saba.info.ucla.edu>,
Mike Oliver <oli...@oak.math.ucla.edu> wrote:
>In article <4mnk7l$q...@gap.cco.caltech.edu> ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>
>> No one will lay a hand on DC... Now, logical strength aside, _why_
>> would Product X_i, X_i =/= 0, trigger the intuition that it is non-0
>> if the X_i are countably many, but not if there are uncountably many?
>
>Well, of course that intuition *is* triggered if there are uncountably
>many. It's just that I know how to work around it in models where it
>fails. I know not to expect to be able to choose uncountable wellordered
>sequences from arbitrary sets, etc.
In fact, ways of "working around it" may be interesting in themselves,
and may say something about effectiveneess and definability. Still, as a
general property of sets it seems arbitrary and unnatural to restrict non-0
of Prod X to families of certain cardinalities only. What would be th
objective basis for such a thing?
>But not being able to choose even omega of them? Having a tree such
>that I can go along it as long as I like and never get stuck, but
>nevertheless there's no way through it? Then I just don't know *what*
>to do.
>
>> Likewise for DC ... doesn't DC-kappa have just as good a claim? This
>> is vague, but it might be interesting.
>
>Well, almost as good a claim. Then it's like the above situation, except
>that I might be going through some limit stages on the tree.
Right. So then, why some trees and not others?
>That's the thing; limit stages are slightly less hardwired in my brain
>than integer stages. I can accept weird things happening when you have
>to go through limit steps more easily than when you don't. The failure
>of DC_omega just brings the weirdness closer to home, to objects I
>feel I should understand completely (even though I've argued that this
>is an illusion, the feeling is still there).
Conquering the limit stages is one way of describing what set theory
does. We accept limits lambda, and lambda+1 for each one, and so on;
having crossed the threshold from individual n's to omega, this is inevi-
table. Well, once again it appears odd that "this" shouldn't be possible
for set A. We can choose {a1}, and go on to {a1, a2 ... an} for any n...
but we cannot put them together to form {a1, a2 ...} ?! (And go on to
a_w, etc)? That's AC in its WO form; we can "keep on choosing"!
Denying the latter, while having accepted the ordinals, again seems
strange and alien to sethood. No, there probably isn't a _rule_ for {a1,
a2, ...) ... Why, was there one for choosing a1?
Whether a definable selector exists is a valid question, but i don't
see it as an objection to AC. For one thing, even if each X_i is a pair,
not _all_ selectors can be definable! To answer the question you may need
the X_i to be somehow definable -- there is a whole field of study then,
one example being co-analytic (Pi-1-1) Uniformization, the Novikov-Kondo-
Addison Theorem.
Selectors might be recursive, hyp, measurable, polynomial-time,
continuous, or whatever -- challenging and interesting problems, but not
the subject-matter of AC; they are refinements.
Ilias
Mike Oliver
In article <4n40i8$s...@gap.cco.caltech.edu> ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>In article <4mo292$21...@saba.info.ucla.edu>,
>Mike Oliver <oli...@oak.math.ucla.edu> wrote:
>>In article <4mnk7l$q...@gap.cco.caltech.edu> ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>>> Likewise for DC ... doesn't DC-kappa have just as good a claim? This
>>> is vague, but it might be interesting.
>>Well, almost as good a claim. Then it's like the above situation, except
>>that I might be going through some limit stages on the tree.
> Right. So then, why some trees and not others?
You still seem to be under the impression that I'm arguing that DC is
somehow more *justified* than full AC. I'm not saying anything of
the kind.
What I said was that models of (not DC) are *stranger* than models
of AD+DC, not that either has a reasonable claim to be V.
And the reason that they're stranger is that certain very natural methods
are disallowed even in the case of very familiar structures that we
work with a lot. Thus I'm at a loss to figure out whether some statement
about, say, countable sets of reals, is true, whereas in a model
of AD+DC I would know.
Ilias Kastanas
In article <4n5iaj$r...@nexus2.cs.ucla.edu>,
Mike Oliver <oli...@nexus2.cs.ucla.edu> wrote:
>In article <4n40i8$s...@gap.cco.caltech.edu> ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>>In article <4mo292$21...@saba.info.ucla.edu>,
>>Mike Oliver <oli...@oak.math.ucla.edu> wrote:
>>>In article <4mnk7l$q...@gap.cco.caltech.edu> ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>
>>>> Likewise for DC ... doesn't DC-kappa have just as good a claim? This
>>>> is vague, but it might be interesting.
>
>>>Well, almost as good a claim. Then it's like the above situation, except
>>>that I might be going through some limit stages on the tree.
>
>> Right. So then, why some trees and not others?
>
>You still seem to be under the impression that I'm arguing that DC is
>somehow more *justified* than full AC. I'm not saying anything of
>the kind.
I'm not; the question restated a point, which you seemed to agree
with anyway. No AC here, just the matter of "different amounts of DC".
>What I said was that models of (not DC) are *stranger* than models
>of AD+DC, not that either has a reasonable claim to be V.
>
>And the reason that they're stranger is that certain very natural methods
>are disallowed even in the case of very familiar structures that we
>work with a lot. Thus I'm at a loss to figure out whether some statement
>about, say, countable sets of reals, is true, whereas in a model
>of AD+DC I would know.
Sure. And of course I am not suggesting that such models shouldn't
be studied.
Ilias
Hendrik Boom
Michael Abbott (mic...@rcp.co.uk) wrote:
I'm not sure what ACI-MP is. But I do know how true AC is
intuitionistically. In one sense, it is trivial:
(a) Given a collection of nonempty sets, it is possible to pich one
element from each of them.
Proof outline: They are nonempty. So each of them already has had an
element picked out when you showed it was nonempty.
In another sense, it is probably false:
(b) Given an indexed collection of nonempty sets, it is poossible to pick
one element from each of them so that when the same set appears several
times in the indexed collection, you pich the same element from it
each time you see it.
-- hendrik.
: Michael
Michael Abbott
Hendrik Boom wrote:
>
> Michael Abbott (mic...@rcp.co.uk) wrote: ...
> : There is a simple proof that AC|-MP. Would somebody be willing to help
> : me to understand why this proof doesn't work in M-L type theory? Thanks very
> : much.
> I'm not sure what ACI-MP is. But I do know how true AC is
Sorry, I wrote AC|-MP when I meant to write AC|-PEM, that is
Axiom of Choice entails Principle of Excluded Middle
(MP was a completely spurious mistake).
> intuitionistically. In one sense, it is trivial:
> (a) Given a collection of nonempty sets, it is possible to pich one
> element from each of them.
> Proof outline: They are nonempty. So each of them already has had an
> element picked out when you showed it was nonempty.
> In another sense, it is probably false:
> (b) Given an indexed collection of nonempty sets, it is poossible to pick
> one element from each of them so that when the same set appears several
> times in the indexed collection, you pich the same element from it
> each time you see it.
>
> -- hendrik.
>
> : Michael
Surely (intuitionistically) AC must be treated as generally false? After all,
even AC(N,N) can fail. And certainly AC(X,Y) for any Y with two distinguished
elements implies that X is decidable.