From: stephen on
Tony Orlow <aeo6(a)cornell.edu> wrote:
> stephen(a)nomail.com said:
>> Tony Orlow <aeo6(a)cornell.edu> wrote:
>> > stevendaryl3016(a)yahoo.com said:
>> >> albstorz(a)gmx.de says...
>> >>
>> >> >I don't know what you are talking about. The proof for finite sets
>> >> >needs just a complete induction. This will not hold for infinity I
>> >> >think.
>> >>
>> >> There is no induction involved in the finite case, and the
>> >> infinite case is *exactly* the same proof as the finite case.
>> >>
>> >> Here it is once again:
>> >>
>> >> Let A be any set whatsoever, finite or infinite, it doesn't matter.
>> >> Let f be any function from A to P(A).
>> >> Let w = { x in A | x is not an element of f(x) }.
>> >> Let x = any set in A.
>> >> Let u = f(x). We prove that u is not equal to w.
>> >>
>> >> By definition of w, we have x in w <-> x is not an element of f(x).
>> >> So x in w <-> x is not an element of u. That means that there are
>> >> two cases: Case 1: x in w, and x is not in u. In that case, u cannot
>> >> equal w. Case 2: x is not in w, and x is in u. In that case, u cannot
>> >> equal w.
>> >>
>> >> So what we have proved is that forall x, w is not equal to f(x). So
>> >> w is not in the image of f. So f is not a bijection between A and P(A).
>> >>
>> >> There's no induction. There's no assumption that A is finite.
>> > But there is an assumption that y is in S.
>>
>> Of course there is an assumption that y is in S. The
>> goal is to find a bijection f from S to P(S). That
>> means that for every element x in P(S), there must be
>> an element y in S such that f(y)=x. w is an element of P(S).
>> In order for f to be a bijection, there must exist an
>> element y in S such that f(y)=w.
>>
>> If y is not in S, then it is irrelevant to the question
>> of whether or not f is a bijection from S to P(S).
>>
>> Do you consider the following a bijection from S={a,b,c} to its
>> power set?
>>
>> f(a) = {}
>> f(b) = {a}
>> f(c) = {b}
>> f(d) = {c}
>> f(e) = {a,b}
>> f(g) = {a,c}
>> f(h) = {b,c}
>> f(i) = {a,b,c}
>>
>> If w= { x : x in S and x not in f(x) }
>> then w= {a,b,c}.
>>
>> Is there a y in S such that f(y) = {a,b,c}? No.
>>
>> Is there a y such that f(y) = {a,b,c}? Yes, f(i)={a,b,c}, but
>> i is not in S, and is not part of a bijection from S to P(S).
>>
>> The above function is a bijection from {a,b,c,d,e,g,h,i}
>> to P({a,b,c}). It is not a bijection from {a,b,c} to P({a,b,c}).
>>
>> Stephen
>>
> But, if this set went on forever, then i WOULD be in the set, and for any
> subset, you could identify an x such that it mapped to that set.

No it would not.

> that no bijection is possible in the finite case. In the proof, a last element
> of the set is assumed when we assume there is some string representing the
> entire set.

There is no mention of strings in the proof. Can't you
read a simple proof? There is no mention of strings or
last elements. Just read the proof. Stop making
up stuff.

The proof really only makes use of four things.
A set S, its power set P(S), a function f:S->P(S),
and the set w = { x : x not in f(x) }.

Given that P(S) is determined by S, and that w is
determined by f, the proof really only depends on
two things.

There are no strings. There is no largest element.

> However, to whatever extent we have considered the set, say to N
> elements, we can always consider it to N+1, or 2^N elements. If this is the set
> of all naturals, for instance, then N in the set implies 2^N in the set. There
> is no end to the bijection. The proof assumes one.

No. The proof does not assume an end to the bijection.
If you think it does, please point out where it makes
such an assumption.

Remember, the rest of us are talking about the entire set,
and the entire power set, not just an "extent" of it.

> So tell me, what rule of bijection did I break, and at what point does the
> mapping through the infinite binary strings break down. For lack of answers to
> thses questions, my bijection stands.

The set of even naturals does not show up in your bijection.
You even admitted it. You can only account for the evens
that are less than some N, but that is not all the evens.

Stephen
From: Virgil on
In article <MPG.1dc1a7141d95b8b798a50a(a)newsstand.cit.cornell.edu>,
Tony Orlow <aeo6(a)cornell.edu> wrote:

> William Hughes said:
> > You have made exactly this mistake before.
> > For example
> > {peach, apple, plum, fiddle} is a set but not a number.

> Huh! I coulda swore that was 4!

To is often foresworn.
>
> > Just because you have a set does not mean you have a number.

> So, not every set has a size?

Not according to TO's definition of size.
From: Virgil on
In article <MPG.1dc1aa8cf0ac262998a50b(a)newsstand.cit.cornell.edu>,
Tony Orlow <aeo6(a)cornell.edu> wrote:

> Randy Poe said:
> >
> > Tony Orlow wrote:
> > > David R Tribble said:
> > > > Tony Orlow wrote:
> > > > >> I already showed you the bijection between binary *N and
> > > > >> P(*N). What didn't you like about it? It is valid.
> > > > >
> > > >
> > > > David R Tribble said:
> > > > >> No, you showed a mapping between *N and R, which is
> > > > >> equivalent to a mapping between *N and P(N). That's easy.
> > > > >
> > > >
> > > > Tony Orlow wrote:
> > > > >> No, it was specifically a bijection between two sets of
> > > > >> infinite binary strings representing, on the one hand, the
> > > > >> whole numbers in *N starting from 0, both finite and
> > > > >> infinite, in normal binary format, and on the other hand,
> > > > >> the specification of each subset of whole numbers in *N,
> > > > >> where each bit which, in the binary number, represents 2^n
> > > > >> denotes membership of n in the subset. This is a bijection
> > > > >> between the whole numbers in *N and P(*N), using an
> > > > >> intermediate bijection with a common set of infinite binary
> > > > >> strings.
> > > > >
> > > >
> > > > David R Tribble said:
> > > > >> But that's an incomplete mapping, because there are not
> > > > >> enough infinite binary strings in *N to enumerate all of the
> > > > >> subsets of *N. Try it, if you don't believe me.
> > > > >
> > > >
> > > > Tony Orlow wrote:
> > > > > Not enough infinite binary strings? How many in *N and in
> > > > > P(*N)? Are you saying that I cannot construct a bijection
> > > > > between the two on an element-by-element basis which
> > > > > continues infinitely through the set of binary strings?
> > > >
> > > > That's exactly what I'm saying.
> > > >
> > > > card(*N) = c, but card(P(*N)) = 2^c, and c < 2^c.
> > > At what point does the bijection break down?
> >
> > What is "the" bijection?
>
> "The" bijection I offered between *N and P(*N), using the
> intermediate set of infinite binary strings, remember? It's
> described, above, in this very post.
>
> > The proof that card(S) < card(P(S)) shows that no bijection exists.
> > That proof has been given a few times in this thread and I see
> > you're trying to get through it. Whether you believe the proof or
> > not yet, you do realize that the proposition is "Let f(S) be any
> > mapping from S to P(S). Then f can't be a bijection." Right?

> Yes, the proof purports to show no bijection can exist by positing a
> complete infinite set and deriving a contradiction from the fact that
> the element mapping to it is not in it.

What is this allegedly "complete infinite set" that TO claims the proof
requires?

In the proof that any f: S -> P(S) is not surjective, a certain set is
described, but there is no need for the certain set to be infintie, and
under certain circumstances, it can even be the empty set, for example
when f(x) = {x} for each x in S. then {x in S:x not in f(x)} = {}. But
it is still a subset of S and a member of P(S).

Perhaps if TO would learn to read at above kindergarten level, he
would make fewer of theses stupid mistakes.



> For any set, there exists a number mapping to it, and every number
> maps to a unique set. The fact that it has no end is no different
> from an y other infinite bijection. So, I ask again, what rule of
> bijection did I break, and where does this bijection break down,
> since it seems to hold for all finite cases?

Does TO claim that there is some finite set (or even, gasp, a
Dedekind-finite set) that allows a surjection to its power set?

Please show us an example of such an anomalous object!

> > Did I break some
> specific bijection-forming rule?

Yes!


> > If the proof is correct (as it is), then ALL bijections break down.
> > The proof consists of showing that no matter what mapping you
> > choose, there's an unmapped element of P(S).

> >
> > > It certainly works for all finite cases, does it not?
> >
> > Absolutely not. Let S = {1,2,3}. Then P(S) has 8 elements: {}, {1},
> > {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}
> >
> > There is no bijection between the 3 elements of S and the 8
> > elements of P(S).

> You snipped what i was referring to as working. I believe it was that
> no element is a member of the set to which it maps. This is certainly
> the case here and for all finite cases.

let S = {1,2,3}, and f(x) = {x}, then EVERY element is a member of the
set to which it maps, but there are 5 sets in P({1,2,3}) which are not
values of f.
> >
> > > What makes you think it falls apart at some point?
> >
> > It falls apart for EVERY set.

> No, in the infinite case, the bijection exists for every natural and
> for every subset. It is a perfect 1-1 correspondence. Please name a
> natural or a subset which is left out of the mapping.

First give us the mapping, as the subsets left out depend critically on
which mapping is used. In general terms on subset left out by any
function f:S -> P(S) is {x in S: x not in f(x)}. As S gets larger,
there are more sets left out.
> >
> > > For which element is there not a corresponding subset?

For each element there is a subset, but not cconversely.
> >
> > It breaks apart in the other direction: there is (at least one)
> > subset for which there is no corresponding element.
> Name it please.

{x in S: x not in f(x)}

> >
> > First you have to define your mapping rule. Given any mapping rule,
> > a subset can be identified for which there is no corresponding
> > element.
>
> I gave the mapping rule: natural <-> binary string <-> subset,
> ordered naturally from 0.

The calling this mapping from *N to P(*N) by some name,
say f:*N -> P(*N), then {x in *N: x not in f(x)} is not in Image(f).
From: Virgil on
In article <MPG.1dc1abde3548019898a50c(a)newsstand.cit.cornell.edu>,
Tony Orlow <aeo6(a)cornell.edu> wrote:


> Did I not give what appears to be a valid bijection between the
> NUMBERS in *N and the SETS in P(*N)?

No! At least it does not have even the appearance of being valid outside
TOmatics.

> If the bijection is not valid,
> please state what mistake I made in constructing it.

If the mapping is called f, you did not show that there is some
*n in *N such that f(*n) = {x in *N: x not in f(x)}.
From: Virgil on
In article <MPG.1dc1b1d591e93a9a98a50e(a)newsstand.cit.cornell.edu>,
Tony Orlow <aeo6(a)cornell.edu> wrote:

> David R Tribble said:
> > Tony Orlow wrote:
> > >> I already showed you the bijection between binary *N and P(*N).
> > >> What didn't you like about it? It is valid.
> > >
> >
> > David R Tribble said:
> > >> No, you showed a mapping between *N and R, which is equivalent
> > >> to a mapping between *N and P(N). That's easy.
> > >
> >
> > Tony Orlow wrote:
> > >> What do you want me to try, anyway, and infinite mapping,
> > >> element-by-element? A bijection's a bijection, right?
> > >
> >
> > David R Tribble said:
> > >> Yes, that would be nice. Please show us your bijection.
> >
> > Tony Orlow wrote:
> > > f(0) = ...000 = {}
> > > f(1) = ...001 = {0}
> > > f(2) = ...010 = {1}
> > > f(3) = ...011 = {0,1}
> > > f(4) = ...100 = {2}
> > > f(5) = ...101 = {0,2}
> > > f(6) = ...110 = {1,2}
> > > f(7) = ...111 = {0,1,2}
> > >
> > > etc. Any questions?
> >
> > Where are the infinite subsets, such as the set of even numbers?
> >
> >
> Well, infinitely far down the list of course!

And where in that list is {x in *N: x not in f(x)}?
First  |  Prev  |  Next  |  Last
Pages: 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
Prev: math
Next: The proof of mass vector.