Re: WWHHOOOOO YEEEEHHHHHH

From: The Ghost In The Machine (ewill_at_sirius.athghost7038suus.net)
Date: 01/31/05 

Date: Mon, 31 Jan 2005 04:00:10 GMT

In sci.logic, |-|erc
<H@r.c>
 wrote
on Mon, 31 Jan 2005 11:29:13 +1000
<365g21F4scdtfU1@individual.net>:
> "The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote
>> >> > 2 days running without having to read Will lying his ass off
>> >> > in his personal logico flatulant dialect.
>> >>
>> >> You can read me, instead. :-P
>> >>
>> >> Is 1/3 in {.3, .33, .333, ... }? Is 3 a multiple of 10? [*]
>> >
>> > no no
>>
>> Well, we're getting somewhere.
>>
>> >
>> >>
>> >> Does card(P(S)) > card(S) for any set S?
>> >
>> > no
>>
>> Prove it.
>
> S e { set:UTM(set, element) }

There you go into the computability realm again.

>
> let set = s, then S = UTM(s, element)
>
> P(S) = UTM(row,col) mod 2 AND S(col)
>
> AND is a row-wise bitmask logical and operation.
>
> For every element of P(S), (indexed by row, the binary
> UTM cartesian bitmask number) there is a corresponding
> element of S (indexed by its UTM element number)
>
>
>
>>
>> Here's a hint of what you're up against. Assume f : S ->
>> P(S) is 1-1 and onto. Construct the set X as a subset
>> of S:
>>
>> X = {s: s in S and s not in f(s)}.
>
> an example?

If S = {1,2,3}, then
P(S) = { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }.

Let's assume f(1) = {1,2}, f(2) = {3}, f(3) = {1}. Admittedly,
for such a trivial example this gets silly as it's obvious f
is not onto, but the set X is easily enough constructable;
it turns out to have the elements {2,3}, since 2 is not in f(2) = {3}
and 3 is not in f(3) = {1}.

Is there an x such that f(x) = {2,3}? Turns out there isn't.

The argument works equally well in the transfinite realm.
>
>
>>
>> Remember that f(s) is a member of P(S) therefore a subset of S.
>>
>> Since X is in the range of f (all subsets of S/elements of P(S) are),
>> there must be an element x in f's domain such that f(x) = X.
>>
>> Is x in X? If yes, then x is not in f(x), but f(x) = X. Contradiction.
>>
>> If no, then x is in f(x) = X.
>> (X and P(S)-X exhaustively partition P(S)),
>>
>> This is another contradiction. Hence f cannot exist as stated.
>>
>> 1-1 mappings are of course easy: g(s) = {s} : S -> P(S) is trivial.
>>
>> Hence there's at least one element in P(S) that is not in S,
>> and card(P(S)) > card(S).
>>
>>
>> >
>> >>
>> >> Is R countable?
>> >
>> > certainly, using the set of all computer programs,
>> > the Universal Turing Machine is designed especially to count programs.
>>
>> The number of programs is denumerable. R is not.
>>
>
> real(1) = UTM(1,0)
> real(2) = UTM(2,0)
>
> See? 1 to 1 mapping! Maybe I should have made this explicit 2 years ago.

It wouldn't have helped. How would you get around Cantor's
*first* uncountability proof?

http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof

>
> Herc
>
>
> 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.