|
|
 | | From: | ken quirici | | Subject: | Re: Infinite number of infinite coin flips | | Date: | 21 Jan 2005 07:26:21 -0800 |
|
|
 | Bill Smythe wrote:
> I wrote:
> > What if P and C are both uncountably infinite (say, to the same
degree of
> > aleph-whatever)? Is there a variation of the diagonal argument
which will
> > work in this case?
>
> I think I have answered my own question. If P and C are the same
degree of
> infinity (i.e. there is a bijection between P and C), then the
diagonal
> argument still works, almost without modification.
>
> For each element of P, simply look at the corresponding element in
the
> corresponding version of C, and reverse it. The set of all those
will be a
> new version of C which differs from each old one in at least one
spot, and
> there will be an obvious bijection between P and this new C.
>
> Bill Smythe
I think the diagonal argument requires countability because it requires
that you be able to enumerate the digits of the diagonal one at a time,
and be sure of getting all of them, which you can't do until someone
finds a well-ordering of the reals.
On the other hand, the Axiom of Choice implies you can select a
'diagonal' from any collection of sets even if it isn't the 'official'
diagonal. I don't think it needs to be the 'official' diagonal, as long
as each digit in the new 'diagonal' differs from a different member of
the uncountable sequence than any other digit in the new 'diagonal'.
So one can construct the 'anti-diagonal' for any uncountable list of
sets each with uncountable many 'digits'. But I'm very uneasy using
the Axiom of Choice here.
Thanks.
Ken
Thanks.
Ken
|
|
| | From: | Bill Smythe | | Subject: | Re: Infinite number of infinite coin flips | | Date: | Fri, 21 Jan 2005 21:29:58 -0600 |
|
|
| "ken quirici" wrote:
> I think the diagonal argument requires countability because it requires
> that you be able to enumerate the digits of the diagonal one at a time,
> and be sure of getting all of them, which you can't do until someone
> finds a well-ordering of the reals.
>
> On the other hand, the Axiom of Choice implies you can select a
> 'diagonal' from any collection of sets ....
> .... But I'm very uneasy using the Axiom of Choice here.
It seems to me that neither enumeration nor well-ordering has anything to do
with the problem, and that the Axiom of Choice is playing the same role, if
any, in the uncountable case as it is in the countable case.
The original problem spoke of (countably) infinitely many coin-toss sets,
which were referred to as "sequences". The word "sequence" implies not only
that each set is countABLE, but also that it has already been countED. In
other words, for each set there is an implied bijection between that set and
the natural numbers.
What, exactly, is a sequence of coin tosses? It is nothing more than a
mapping of the natural numbers to the two-element set { H, T } . If we
call such a mapping M, then we might have, for example, M(1)=H , M(2)=T ,
M(3)=T , M(4)=H , etc.
So the original problem can be restated as follows:
_____________________________________
Suppose we have a family F of mappings, one mapping C(x) for each
element x of the natural numbers, with each mapping C(x) being a mapping
from the natural numbers to the two-element set. Does there exist a new
mapping N , from the natural numbers to the two-element set, such that the
mapping N is different from the mapping C(x) for all natural numbers x
?
(Note: Each C(x) is a mapping. C(1) is a mapping, C(2) is a mapping,
etc. For example, if C(1) behaves like M above, then C(1)(1)=H ,
C(1)(2)=T , C(1)(3)=T , C(1)(4)=H , etc.)
The proof is by construction. Define the new mapping N as follows:
N(x) = NOT C(x)(x) for each natural number x.
(By NOT C(x)(x) I mean H if C(x)(x)=T , or T if C(x)(x)=H.)
That way, the mapping N differs from each mapping C(x) at element x .
_____________________________________
Now let's try the same thing with real numbers (or any other uncountable
set) instead of natural numbers:
_____________________________________
Suppose we have a family F of mappings, one mapping C(x) for each
element x of the real numbers, with each mapping C(x) being a mapping
from the real numbers to the two-element set. Does there exist a new
mapping N , from the real numbers to the two-element set, such that the
mapping N is different from the mapping C(x) for all real numbers x ?
The proof is the same. Define the new mapping N as follows:
N(x) = NOT C(x)(x) for each real number x.
That way, the mapping N differs from the mapping C(x) at element x .
_____________________________________
There you have it. No Axiom of Choice, as far as I can tell.
The Axiom of Choice may come in at the point where we make the leap from
"countable set of coin tosses" to "sequence of coin tosses", or,
analogously, from "uncountable set of coin tosses" to "mapping from the
reals to the two-element set". The second description in each pair implies
that we have not only a set, but also a bijection (to the natural numbers or
to the reals as the case may be) to go with it. If we start with just the
sets, we must create bijections to go with them, and this is where the Axiom
of Choice may be necessary, as we are "choosing" infinitely many bijections.
Bill Smythe
|
|
|
