Re: infinity ...

Tony Orlow <aeo6@xxxxxxxxxxx> wrote:
> stephen@xxxxxxxxxx said:
>> Tony Orlow <aeo6@xxxxxxxxxxx> wrote:
>> > stephen@xxxxxxxxxx said:
>> >> Tony Orlow <aeo6@xxxxxxxxxxx> wrote:
>> >> > David R Tribble said:
>> >> >>
>> >> >> But you have not provided a mapping between any set and its powerset,
>> >> >> infinite or otherwise.
>> >> > Have too.
>> >>
>> >> No you have not Tony.
>>
>> > Have, too!
>>
>> >> The proof that there does not exist
>> >> a bijection between a set and its power set is quite short.
>> > Then it shouldn't take too much looking to see where it goes wrong....
>> >>
>> >> Let f be a function from S to P(S).
>> > Our proposed mapping bijection....
>> >>
>> >> Define the set w as follows:
>> >>
>> >> w= { x : x in S and x is not in f(x) }
>> > So, w is the set of all elements which are not members of the subsets which
>> > they map to through f(x)....
>> >>
>> >> Clearly w is a subset of S, and so w is an element of P(S).
>> > Clearly...but properly?
>>
>>
>> >>
>> >> We now show that w is not in the image of f. That is,
>> >> there does not exist a y such that f(y)=w.
>> > So, there can be no y such that it maps to the subset of all elements which do
>> > not map to subsets containing themselves? We'll see.....
>> >>
>> >> Suppose such a y exists. If such a y exists, it must
>> >> either be an element of w, or not.
>> > One or the other. I'll accept the excluded middle....
>>
>> >>
>> >> If y is an element of w, then y is in f(y), which means
>> >> it is not an element of w.
>> > If y is in w, this means y is a member of the set of elements which map to
>> > subsets which do not contain themselves. This means that y is in S but not in f
>> > (y). So, indeed, it IS a member of w. There is no reason why both x and y
>> > cannot map to subsets which do not contain themselves.
>>
>> If y is in w, then y is in f(y), because w=f(y). Remember,
>> we are assuming there exists a y such that f(y)=w. However
>> w is defined such that y can only be in w, if y is not in f(y).
> Okay, I hit this one at the end of the day, and got confused halfway through it
> and forgot that you're assuming y is mapped to w. Sorry about that. It is clear
> that no element in the set maps to a subset that contains itself, as I
> illustrated below. If f(y)=w, then y can't be in w, but then that means y IS in
> f(y), which means it's in w. Got it.

No, that is not clear at all. It is entirely possible that an
element maps to a set that contains itself. However no element
maps to w. You still do not get it.

Here is a simple mapping from N to P(N).

1 -> {1}
2 -> {1,2}
3 -> {1,2,3}
4 -> {1,2,3,4}
...

Every element is contained in the subset that it is mapped
to. For this mapping, w={}, and no element is mapped to {}.


> That certainly causes a bit of a contradiction, based on the largest-finite
> kind of argument, since you are noting that whatever subset you choose, it
> never contains the natural that maps to it,

No. Try again.

>> > If y is a member of w, then all you can say is that y does not map to any
>> > subset which contains itself. Y does not map to w. Neither does x.
>>
>> What is x? If y is a member of w, then y is in f(y), and
>> by the definition of w, w is not a member of w.
> Yes, there is no element y in any given set S which maps to S. That element
> would be element 2^|S|-1, outside the scope of S.
>>
>> >>
>> >> If y is not an element of w, then y is not in f(y), which
>> >> means it is an element of w.
>> > If y is not a member of w, then y maps to a subset which contains y as a
>> > member, and y IS in f(y). Is this possible? We'll see what you think.....
>>
>> >>
>> >> These are both contradictions. So y cannot be an element
>> >> of w, and it cannot not be an element of w. So y
>> >> cannot exist.
>> > Neither of those possibilities causes a contradiction. You are getting confused
>> > with your double negatives. If w is the set of all elements which do not map to
>> > subsets containing themselves, then being a member of w means simply that y
>> > does not map to a subset containing y, which is perfectly possible. Not being a
>> > member of w means that an element maps to a subset which DOES contain itself.
>> > Where is the contradiction?
>>
>> The contradiction is that if y is in w, then it is not in w,
>> and if y is not in w, then it is in w. That is a pretty
>> obvious contradiction.
> Well, y is in w, as are all the elements. y does not map to w. For any given
> set, there is no element in the set which maps this way to the set itself. And
> yet, when you have infinite sets such as this, can't I just map element 2^S-1
> to subset S?

What is element "2^S-1"? S is a set. Element "2^S-1" means
nothing to me.

>>
>> You apparently failed to grasp the very important fact that w=f(y).
>> So once again, is y in w?
> Not if w=f(y). If w=f(y), then y is not in S, and therefore not in w.

If y is not in S, then it is not part of the bijection.
f is function from S to P(S). It makes no sense to plug
in a value that is not in S into f.

>>
>> If y is in w, then y is in f(y), because w=f(y).
>> If y is in f(y), then y is not in w, because w is defined
>> as containing the elements x in S such that x is not in f(x).
>> w cannot contain y, because y is in f(y).
>>
>> If y is not in w, then y is not in f(y), because w=f(y).
>> If y is not in f(y), then y is in w, because w is defined
>> as containing the elements x in S such that x is not in f(x).
>> w must contain y, because y is not in f(y).
> Got it. y is not in S, and therefore not in w.

No. You still do not get it.
>>
>> >>
>> >> So there is at least one element in P(S) which is
>> >> not in the image of f, so f is not an onto function,
>> >> and it is not a bijection.
>> > Sorry, not so.
>>
>> Yes. The fact that you cannot understand a simple
>> proof does not make the proof invalid.
> I got a little confused, but you still haven't proven anything like the
> impossibility of a bijection with the power set. In other cases bijections are
> performed without regard to such discrepancies.

There is no bijection between a set and its powerset.
It does not matter what the set is, it does not matter
if it is finite, or infinite.
>>
>> >>
>> >> What is wrong with this proof in your opinion?
>> > You confused yourself with double negatives. If I misinterpreted any of what
>> > you said, please clarify.
>>
>> You apparently misintrepted all of it.
> not entirely.
>>
>> Do you understand that we are assuming that w=f(y)?
> No, I forgot that in figuring out what we were talking about specifically. I
> don;t see anything in it proving bijection impossible. If w=f(y) then y is not
> in S, assuming some limit to S. But, S goes on forever and ever, and we can
> always borrow for our bijection, having sets containing elements with at most
> the log2 of the value of the element that maps to it. As long as there's a 1-1
> correspondence, what's the problem?

If nothing in S maps to w, and w is in P(S), then f is not a bijection.
It is that simple. Nothing in S maps to w. If you think otherwise,
tell us what element of S is mapped to w.

You still do not understand the proof at all. It is a relatively
simple proof.

Here are some examples that might help you out. Although
you will likely snip them as "tedious nonsense."

First, look at the finite case. Let S={a,b,c}.

Lets look at
f(a) = { a }
f(b) = { a, c }
f(c) = { a, b, c }

w = { x : x not in f(x)}, so w={b}. {b} is not in the image of f.
We can try again.
f(a) = { a }
f(b) = { b }
f(c) = { a, b, c }
Now w={}, which is not in the range of f.
How about
f(a) = { }
f(b) = { a }
f(c) = { a, b }
Now w={a,b,c}. We can keep playing this game, but w will
never be in the image of f.

Of course in the finite case it is obvious that there
cannot be a bijection from S to P(S) because P(S) has
2^|S| elements, and when |S| is finite it is obvious that
2^|S| > |S|.

However the above proof makes no mention or use
of the set being finite, and it applies equally well
to finite and infinite sets.

Lets look at the natural numbers and the "bijection"
albstorz proposed:

1 -> N
2 -> {}
3 -> {1}
4 -> N\{1}
5 -> {2}
6 -> N\{2}
7 -> {1,2}
8 -> N\{1,2}
9 -> {3}
10 -> N\{3}
11 -> {1,3}
12 -> N\{1,3}
13 -> {4}
14 -> N\{4}
15 -> {1,4}
16 -> N\{1,4}
17 -> {2,3}
18 -> N\{2,3}
19 -> {5}
20 -> N\{5}
....

In this case
w={ 2,3,5,7,9,11,13,15,17,19 .... }

Where does this show up in teh above list? If you
claim it shows up in position y, then is y in w or not?

Stephen

.

Relevant Pages

  • Re: infinity ...
    ... What we want is to see a mapping from *N to Pwhich maps some member ... Anything less is irrelevant to the validity of TO's alleged bijection ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... If you claim that you have a bijection f from some set ... Of course you're going to get a contradiction. ... maps to A, the entire set. ... forall finite even naturals y, there exists a finite natural x such ...
    (sci.math)
  • Re: first attempt at cycling through London
    ... I'm a member of a couple of LCC local groups. ... were asked for any amendments/suggestions for the new update of the maps, ... I covered just some as they take a full day each, and I haven't got a spare ...
    (uk.rec.cycling)
  • Re: infinity ...
    ... >> Tony Orlow wrote: ... >>> Oh yeah, the entire set, last element and all. ... What we want is to see a mapping from *N to Pwhich maps some member ...
    (sci.math)
  • Re: infinity ...
    ... > any natural which maps to the entire set of naturals. ... That doesn't matter. ... But that does not establish anything like a bijection ... >> where z is NOT a member of your original set S. You don't ...
    (sci.math)