Re: HERC 97 SCI.MATH 0

From: ken quirici (kquirici_at_yahoo.com)
Date: 01/20/05


Date: 20 Jan 2005 07:49:23 -0800


|-|erc wrote:
> 3 more propositions, see if you can work out the truth value.
>
> THE PROBLEM
> (countable) infinite people each flip coins (countable) infinite
times each.
> Can you always come up with a new coin sequence?
>

I think there's something interesting here, which I will get to
presently, but first, to answer the above question:

Yes, clearly. Any countable list of countably many H's and T's has a
constructible 'diagonal' which is different from any member of the
list. So what? You haven't specified anything 'interesting' about this
list of infinite sequences of flips. For example, the list could be all

the same flipping sequence. If you mean the lists to be random, then
again, the lists have nothing 'interesting' about them. Sure, for some
random countable list of flip sequences I can generate the diagonal.
Again, so what?

> SCI.MATH SOLUTION
> Take the inverted diagonal of the flippers. Call this diagonal.
>
>
> PROPOSITION 1
> "Regarding the infinite set of people flipping coins,
> the diagonal coin sequence has been flipped only to some finite
amount of flips of the diagonal"
>
> PROPOSITION 2
> "Regarding the infinite set of people flipping coins,
> the diagonal coin sequence has been flipped to an infinite amount of
flips of the diagonal"
>
> PROPOSITION 3
> "Regarding the infinite set of people flipping coins,
> the diagonal coin sequence has been flipped some finite amount (or 0)
of flips per person"
>
> Herc

Let's assume we have a more interesting list of sequences - the list
of all possible flipping sequences. Then the diagonalization argument
shows that that list is not countable, by finding a list not in the
sequence. Given that there's a bijection between your flipping lists
and binary numbers and therefore with the integers, this is not
surprising. Interesting but not the Holy Grail, and not really
answering
your questions.

But now we come to your more interesting question of how much of any
diagonal constructed from some list purporting to be all possible
flipping sequences, match the same number of initial digits of some
one of the flipping lists. For example, is there some flipping
sequence whose first 17 digits match the first 17 digits of the
diagonal, say maybe sequence #1789723? And, what is the LARGEST number
of such digits for which we can find a matching element of the list of
flipping sequences?

I think that's a fair paraphrase of your 3-choice problem.

As far as an answer, I haven't the foggiest but I think it depends on
how you order your list of flipping sequences. If you choose a kind
of lexicographical order, where after 2, you have all possible 1-flip
sequences, and after another 4, you have all possible 2-flip sequences,

etc., then the answer would be, for any n however large, I can find
one of the flipping sequences that match the first n digits of the
diagonal.

My CLAIM is that Herc's questions, given an 'interesting' list of
flipping sequences, depend on the ordering of the list, and hence
go beyond the simpler question of denumerability. But I'm uneasy
with this conclusion, probably for good reason.

Thanks.

Ken



Relevant Pages

  • Re: HERC 97 SCI.MATH 0
    ... the lists have nothing 'interesting' about them. ... random countable list of flip sequences I can generate the diagonal. ... Then the diagonalization argument ... flipping sequences, match the same number of initial digits of some ...
    (sci.math)
  • Re: HERC 97 SCI.MATH 0
    ... the lists have nothing 'interesting' about them. ... random countable list of flip sequences I can generate the diagonal. ... Then the diagonalization argument ... flipping sequences, match the same number of initial digits of some ...
    (sci.logic)
  • Re: Problems I have with 1.999...=2
    ... we come to the problem of what these infinite decimal ... we know that rationals are dense on the real number ... infinite lists only contain rational numbers for our purposes here so ... As far as I understand these special sequences are ...
    (sci.math)
  • Re: Interface of the set classes
    ... >> Sequences have order, sets don't. ... neither in Python nor in C++ can you switch freely. ... You make claims, above, about the container templates in C++'s standard ... Python's lists, sets and dicts, and in what aspects precisely? ...
    (comp.lang.python)