FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
An uncountable countable set
Post new topic   Reply to topic Page 3 of 58 [858 Posts] View previous topic :: View next topic
Goto page:  Previous  1, 2, 3, 4, 5, ..., 56, 57, 58 Next
Author Message
Daryl McCullough
science forum Guru


Joined: 24 Mar 2005
Posts: 1167

PostPosted: Tue Jun 20, 2006 1:25 pm    Post subject: Re: An uncountable countable set Reply with quote

mueckenh@rz.fh-augsburg.de says...

Quote:
Daryl McCullough schrieb:

Okay, so M is not a fixed set, but is a function of f. So to make
this precise, let's put in the functional dependence:

K(f) = { k in N | k is not an element of f(k) }
M(f) = { A in P(N) | A is finite, or A = K(f) }

where P(N) means the set of all subsets of N.

Then what you are saying is that

forall f: N -> P(N),
f is not a bijection between N and M(f)

That's true. But that doesn't mean that M(f) is uncountable.

If it is proven impossible to set up a mapping between M and |N, then M
is uncountable.

Once again, M is not a fixed set. It is a *function* of f.
For each function f, there is a corresponding K_f and a
corresponding M_f.

Let's look at an example: Let f(x) be a mapping from N to P(N)
as follows:

f(0) = {}
f(1) = { 0 }
f(2^a_1 3^a_2 5^a_3 ... p_n^a_n)
= { x_1, x_2, ..., x_n }
where x_1 = a_1,
x_{n+1} = x_n + a_{n+1}

As I already pointed out, K(f) = { 0, 1, 2, ... } = N.
M(f) = { A | A is a finite subset of N, or A = K(f) }

M(f) is countable, since there is a bijection g:

g(0) = N
g(x+1) = f(x)

Quote:
That is the definition of uncountability.

By the definition of "uncountable" M(f) is countable.

Quote:
Cp. Cantor's diagonal proof:
There it is even possible to set up a bijektion between {numbers of the
list & diagonal number}, (after the diagonal number has been
constructed) and |N. Nevertheless uncountablilty is claimed.

The difference is that there is a proof that P(N) is uncountable,
but there is a proof that M(f) *is* countable.

What we can show is that for every f,

f is not a surjection from N to M(f).

But since M(f) is a subset of P(N), we have

f is not a surjection from N to M(f)
implies
f is not a surjection from N to P(N)

So we conclude (Cantor's theorem)

forall f, f is not a surjection from N to P(N).

Quote:
We can prove

forall f: N -> P(N), exists g: N -> P(N)
g is a bijection between N and M(f)

No, it is not, because M(f) is incomplete without K. But K does not
exist.

On the contrary, for every f, there is a corresponding K(f), and
there is a corresponding M(f).

You give me an f, and I will show what the corresponding K(f) is.
We already saw one example: for the f defined explicitly above,
K(f) turns out to be all of N.

Quote:
The reason for its non-existence is not lacking number of
elements of |N but an impredicable definition.

Since K(f) *does* exist, it's a little silly to talk about the
reasons for its nonexistence.

Perhaps this would be easier for you if you start out
considering finite sets, instead of N.

Let N_1 = { 0 }. Then P(N_1) = { {}, {0} }.
Let f be any function from N_1 to P(N_1). There
are two such functions: f_1 and f_2 where

f_1(0) = {}
f_2(0) = {0}

Now consider K(f_1).

K(f_1) = { x in N_1 | x is not an element of f_1(x) }
= { 0 }

Clearly, K(f_1) is not in the image of f_1. So f_1 is not
a bijection between N_1 and P(N_1).

Now consider K(f_2).

K(f_2) = { x in N_1 | x is not an element of f_2(x) }
= {}

Clearly, K(f_2) is not in the image of f_2. So f_2 is not
a bijection between N_1 and P(N_1).

Note, K(f_1) is *not* equal to K(f_2).

Since f_1 and f_2 are all the functions from N_1 to P(N_1),
it is clear that there are no bijections from N_1 to P(N_1).

We can try the same thing using N_2 = { 0, 1}. We will find
that there is no bijection from N_2 to P(N_2). The same is
true for N_3 = { 0, 1, 2 } and N_4, and N_5, etc.

We can generalize: for *any* set A (finite or not), and for
any function f from A to P(A), we can define

K(f) = { x in A | x is not an element of f(x) }

It is clearly the case that K(f) is not in the image of f.
It is also clearly the case that K(f) is an element of P(A).
So we conclude:

f is not a bijection between A and P(A).

--
Daryl McCullough
Ithaca, NY
Back to top
Virgil
science forum Guru


Joined: 24 Mar 2005
Posts: 5536

PostPosted: Tue Jun 20, 2006 5:47 pm    Post subject: Re: An uncountable countable set Reply with quote

In article <1150796061.943937.27660@p79g2000cwp.googlegroups.com>,
mueckenh@rz.fh-augsburg.de wrote:


Quote:

[mueckenh@rz.fh-augsburg.de]
An uncountable countable set

There is no bijective mapping f : |N --> M,
where M contains the set of all finite subsets of |N
and, in addition, the set K = {k e |N : k /e f(k)} of all natural
numbers k which are mapped on subsets not containing k.

Of course f does not exist. But the reason has nothing at all to do
with cardinalities. This error, however, is the foundation of
Hessenberg's proof of Cantor's theorem.

f does not exist if it is required to be a bijection, but in that case
neither does K(f) of M(f) exist, so there no such set as M(f).

On the other hand, if f is not required to have K(f) in its image set,
then there is no problem with constructing any number of such functions,
and for each of them, there is a bijection (though not f) between N and
M(f).
Quote:

A set is required which is the image of k if it is not the image of k.
A barber is required who shaves himself if he does not.

IOW, I doubt this argument can be made in ZFC, just as it's not possible
under ZFC to prove that

F = {k e |N : k e F}
or
G = {k e |N : k /e G}

exist.

On the other hand, why should any mapping not exist? If you claim that
a surjective mapping |N --> P(|N) must contain the set K in any case,
then there is no arguing why my mapping should not exist.

The problem only arises when one insists that there is some n in N such
that f(n) = K(f). If one does not make that requirement, then there is
no problem with the existence of K(f) or with functions f:N --> M(f).
Back to top
Virgil
science forum Guru


Joined: 24 Mar 2005
Posts: 5536

PostPosted: Tue Jun 20, 2006 6:02 pm    Post subject: Re: An uncountable countable set Reply with quote

In article <1150796356.837197.53290@g10g2000cwb.googlegroups.com>,
mueckenh@rz.fh-augsburg.de wrote:

Quote:
Virgil schrieb:

In article <1150782120.872330.199120@c74g2000cwc.googlegroups.com>,
mueckenh@rz.fh-augsburg.de wrote:

Daryl McCullough schrieb:

mueckenh@rz.fh-augsburg.de says...

There is no bijective mapping f : |N --> M,
where M contains the set of all finite subsets of |N
and, in addition, the set K = {k e |N : k /e f(k)} of all
natural
numbers k which are mapped on subsets not containing k.

Above I spelled out clearly that M contains the set of all finite
subsets of |N and one more set K. What is unclear?

Okay, so M is not a fixed set, but is a function of f. So to make
this precise, let's put in the functional dependence:

K(f) = { k in N | k is not an element of f(k) }
M(f) = { A in P(N) | A is finite, or A = K(f) }

where P(N) means the set of all subsets of N.

Then what you are saying is that

forall f: N -> P(N),
f is not a bijection between N and M(f)

That's true. But that doesn't mean that M(f) is uncountable.

If it is proven impossible to set up a mapping between M and |N, then M
is uncountable.

But you have not proven it impossible, you merely argue that ONE
function between N and M(f) is not a bijection.



WE have some f: N --> P(N), which we know is not a surjection since
there is no n in N for which one can have f(n) = K(f).

But that does no mean that there is no surjection between M(f) and N.

In fact, given a function f for which K(f) exists, it is not difficult
to build a bijection between M(f) and N as follows:

For each S in M(F) define g: M(f) --> N by:
If K is finite then
if 0 e N
then g(S) = sum_{s e S} 2^s
else g(S) = sum_{s e S} 2^(s-1)
endif
else (K being infinite)
g(K) = the first natural
and
if 0 e N
then g(S) = sum_{s e S} 2^s+1
else g(S) = sum_{s e S} 2^(s-1)+1
endif
endif

In all these cases, g will be a bijection from M(f) to N.




We can prove

forall f: N -> P(N), exists g: N -> P(N)
g is a bijection between N and M(f)

No, it is not, because M(f) is incomplete without K. But K does not
exist.

But you have not proven it never exists, and for some functions, f, it
Does exist.

For example, let f(n) = {} for all n, then
K = {k in N : not k e f(k) } = N.

So that for SOME functions f, f, K(f) exists.

The reason that Meucken's argument fails here is that there is no
necessity for the function f to be a surjection onto M(f).

The desired bijection can be established by an entirely different
function between M(f) and N, as shown above.

Only if K(f) would exist.

If one claims that such an f is a bijection, then it cannot exist at
all, but neither can K_f or M_f exist, so the problem of whether such a
nonexistent set as M_f is countable is irrelevant.

If one does not require f to be bijective, in particular if one does not
require that there be any n in N for which f(n) = K_f, then K_f anf M_f
may quite easily exist.

And M_f is quite easily shown to be bijectable with N when it does
exist.

Quote:
The reason for its non-existence is not lacking number of
elements of |N but an impredicable definition.

Wrong, as shown by a specific example above.

Your example ist wrong because K(f) does not exist.

There are two cases to consider:

(1) If one requires that there be some n in N for which f(n) = K_f, then
the function f does not exist, but then neither do K_f and M_f, so there
is no problem as there is no such thing as M_f.
(2) If f:N --> P(N) is such that there is no n in N for which f(n) =
K_f, then again there is no problem, since while K_f and M_f may exist,
it is easily shown that when they do, M_f and N biject.
Quote:

Regards WM
Back to top
W. Mueckenheim
science forum Guru


Joined: 23 Apr 2005
Posts: 934

PostPosted: Tue Jun 20, 2006 8:38 pm    Post subject: Re: An uncountable countable set Reply with quote

Virgil schrieb:

Quote:
In article <1150710209.401911.130270@i40g2000cwc.googlegroups.com>,
mueckenh@rz.fh-augsburg.de wrote:

Virgil schrieb:


Note that M depends on the particular f that has been chosen.
We can indicate that dependence by writing M_f.

Oh, indeed? What is the number k mapped under f on the set K = {k e |N
: k /e f(k)} of this M_f ?

As soon as you tell us that M_f exists at all, YOU are telling us that
there must be such a set, K. The only other option is that there is no
such set K and no such set M_f and no such function f at all, in which
case the uncountable-countable-set becomes a non-existent
uncountable-countable-set.

Of course K exists for every mapping f (if |N exists). But the set {f,
k, K} is a paradox set. It is not suitable to show that a bijection |N
--> {all finite subsets of P(|N) plus one further set} does not exist.
Why do you believe it could be capable of showing that |N --> P(|N)
does not exist?

Regards, WM
Back to top
W. Mueckenheim
science forum Guru


Joined: 23 Apr 2005
Posts: 934

PostPosted: Tue Jun 20, 2006 8:41 pm    Post subject: Re: An uncountable countable set Reply with quote

Virgil schrieb:


Quote:

Give us an example of such an f, K_f and M_f, to show that such an f,
K_f anf M_f can actually exist.

If the set {f, k, K} could actually exist, then M would be countable.
But it is not, isn't it?
Quote:

If they can exist at all, it is easy enough to show that there is a
bijection beween |N and M_f, and if they can't then there is no M_f to
worry about.

In order to define K_f you first have map all natural numbers n of |N
on the finite subsets of |N. Then consider K_f. But there is no element
k of |N remaining, which could be mapped on K. Hence the set M is
uncountable. It is about the same as Cantors diagonal proof. The
diagonal number depends on all numbers of his list. Moreover, after
constructing the diagonal number, it turns out to belong to a countable
set. My M remains uncountable in any instance.

Regards, WM
Back to top
W. Mueckenheim
science forum Guru


Joined: 23 Apr 2005
Posts: 934

PostPosted: Tue Jun 20, 2006 8:44 pm    Post subject: Re: An uncountable countable set Reply with quote

Virgil schrieb:

Quote:
M depends on f. And when you take g, then M depends on g. That is the
essence of M.

Wrong! Given any two large sets are many functions for one to the other
and equality of cardinality depends on whether any one of them is a
bijection. Given two sets to compare, you cannot restrict things to only
one allowable function between them but must allow all possible
functions between them to be considered.

I allow for all functions, because I did not introduce any
restrictions.
Quote:

In order to show that
there is no bijection between N and M you are not allowed to change M
for each and every attempted mapping.

I do not change anything. I define K by exactly that mapping which is
assumed.

Then there are other functions between N and M_f, one of which is a
bijection.

Could you prove that assertion please?

Quote:
There are two issues here. The first is whether a function of the sort
Meucken tries to create can exist at all. He has given no example of
such a function, nor proof of existence.

Of course there is no proof of existence. If it was, then M was
countable.
Quote:

However if we allow the assumption that such a function f exists, it is
not hard to show that there are bijections between |N and M_f, though f
need not be one of them.

There are many bijections between {numbers of Cantor's list plus
diagonal number}. Don't you know that? Here is one: Enumerate list
number n by n+1 and enumerate the diagonal number by 1.

Regards, WM
Back to top
W. Mueckenheim
science forum Guru


Joined: 23 Apr 2005
Posts: 934

PostPosted: Tue Jun 20, 2006 8:46 pm    Post subject: Re: An uncountable countable set Reply with quote

Virgil schrieb:

Quote:
In article <1150728692.949790.258040@h76g2000cwa.googlegroups.com>,
mueckenh@rz.fh-augsburg.de wrote:

Daryl McCullough schrieb:

mueckenh@rz.fh-augsburg.de says...

There is no bijective mapping f : |N --> M,
where M contains the set of all finite subsets of |N
and, in addition, the set K = {k e |N : k /e f(k)} of all natural
numbers k which are mapped on subsets not containing k.

It's not exactly clear what you are talking about here. Do
you mean that M is the set of all finite subsets of N?

Above I spelled out clearly that M contains the set of all finite
subsets of |N and one more set K. What is unclear?

In
that case, there is definitely a bijection between M and N:

If M was the set of all finite subsets of N, that would be easy enough
to see.

If you let K = { k in N such that k is not an element of f(k) }
then we can see that

K = N

Such a mapping is possible with no doubt. There remains only one
question: what number is mapped on K?

That raises the question of whether such a set as M_f can exist at all.

If it cannot exist, then the issue of whether a non-existent set is
countable is irrelevant.

Of course it exists. There are all finite subsets of |N. And there is,
for any function f, the set of all natural numbers, which are not
mapped on sets containing them. If |N exists, then K exists too. Maybe
|N does not exist completely?

Quote:
So that Meucken's first duty is to prove that a function having the sort
of codomain, M_f, he describes can exist at all.

If ever that is established, the construction of a bijection between it
and N is fairly trivial.

If |N exists, then K exists too. Maybe |N does not exist completely?

Regards, WM
Back to top
W. Mueckenheim
science forum Guru


Joined: 23 Apr 2005
Posts: 934

PostPosted: Tue Jun 20, 2006 8:54 pm    Post subject: Re: An uncountable countable set Reply with quote

Virgil schrieb:


Quote:
The element K of M does not exist.

Excuse me. The set {f, k, K} does not exist.
Quote:

That requires proof, and is false in at least one case.
Let f(n) = {} for all n, then K_f is quite well defined, and equals N.

You are correct. Of course K_f does exist for any f (if all natural
numbers do exist). Nevertheless you see that the mapping is not a
bijection beause no f(n) = K.
Quote:

If it is proven impossible to set up a mapping between M and |N, then M
is uncountable.

Wrong!

M is countable means: There is an enumeration of the elements of M,
i.e., a bijective mapping |N <--> M.
Quote:

If it is impossible to set up an injection from N to M_F or a surjection
from M_f to N, and the axiom of choice is assumed, only then is M_f
uncountable.

And if K does not exist,

If |N does exist, then each of its subsets must exist, including K.
What does not exist is the bijection |N <--> M.

Regards, WM
Back to top
W. Mueckenheim
science forum Guru


Joined: 23 Apr 2005
Posts: 934

PostPosted: Tue Jun 20, 2006 8:58 pm    Post subject: Re: An uncountable countable set Reply with quote

Rupert schrieb:

Quote:
mueckenh@rz.fh-augsburg.de wrote:
Rupert schrieb:

mueckenh@rz.fh-augsburg.de wrote:
An uncountable countable set

There is no bijective mapping f : |N --> M,
where M contains the set of all finite subsets of |N
and, in addition, the set K = {k e |N : k /e f(k)} of all natural
numbers k which are mapped on subsets not containing k.


You're using the notation "f" in two ways.

No.

Yep. In one of the occurrences it occurs preceded by a universal
quantifier, in the other it occurs as a constant symbol.

Could you say what you mean?

Quote:
First you're denying that a
function f with certain properties exists, then you're defining M in
terms of some fixed function f,

f is not fixed by any prescription.


It doesn't make sense to talk about the set K={k e |N: k /e f(k)} unles
you've specified what f is.

f is not fixed by any specification. Therefore my arguing holds for any
f. K is that subset of |N which contains all natural numbers which are
not mapped under f on sets containing themselves.
Quote:

which it's not clear what it is. Use a
different letter for the two things, and the define the function

f is not restricted by any definition. Any mapping f: |N --> M is
allowed.


So you mean M is the set of all finite subsets of |N, together with all
sets of the form K={k e |N: k /e f(k)}, where f ranges over all
possible mappings |N->P(|N)?

No. K is that single set which belongs to the function f.

Regards, WM
Back to top
W. Mueckenheim
science forum Guru


Joined: 23 Apr 2005
Posts: 934

PostPosted: Tue Jun 20, 2006 9:09 pm    Post subject: Re: An uncountable countable set Reply with quote

Dik T. Winter schrieb:

Quote:
In article <1150728187.749465.36710@g10g2000cwb.googlegroups.com> mueckenh@rz.fh-augsburg.de writes:
Dik T. Winter schrieb:
In article <1150718841.726873.223390@g10g2000cwb.googlegroups.com> mueckenh@rz.fh-augsburg.de writes:
...
An uncountable countable set

There is no bijective mapping f : |N --> M,
where M contains the set of all finite subsets of |N
and, in addition, the set K = {k e |N : k /e f(k)} of all natural
numbers k which are mapped on subsets not containing k.

But is the set K in M? Pray give a proof.

Of course it is, by definition, for without K M would not be M.

Ah, I see. The set M is defined depending on f. Well in that case f
is clearly not a bijection between N and M.

That is correct.

This does not tell us that
there is *no* bijection (say g) between N and M.

M depends on f. And when you take g, then M depends on g. That is the
essence of M.

In that case M is not a set.

Of course it is. It contains all finite subsets of |N and that set
which contains all natural numers wich under f are mapped on sets not
containing them. If |N is a set, then M is clearly a set too.

Quote:
And in order to tell whether that is
uncountable or not you have to first define cardinality on such
non-sets.

Cardinality is aleph_0 is there is a bijection with |N. If that is
impssible, then cardinality is larger.
Quote:

So also M(f) is countable.

That is not at all the way a bijection has to be constructed between |N
and M. That is simply impossible!

A bijection can be constructed, you only can not name if f.

First you must find out what the set {f, k, K} is. *That* is
impossible, not K.

A bijection can be constructed from |N to the numbers of Cantors list
and the diagonal number. You only first have to construct the latter.
Quote:

But if you like tricks of this kind, then you can biject |N and its
power set P(|N) \ K. Subsequently take
1. g(0) = K(f)
2. g(n) = f(n - 1) when n > 0
and we see that Cantor's theorem is not proven by Hessenberg's proof,
because this proof makes use of the impredicable definition of a set
which does not and cannot exist, as well as the barber who shaves all
men of his village.

Sorry, this is plain nonsense. You can not construct a bijection between
P(N) \ K.

Who told you?

Quote:
The difference between this and your construction with M(f)
is that the target M(f) depends on the bijection you are constructing.

The same holds in case of the proof of Cantor's theorem.

Quote:
P(N) is a properly defined set that does not depend on anything but N.

But the set of numbers which are mapped on sets not containing them is
not proerly defined.

Quote:
But you are wrong. For every mapping f, the set K does exist (and is
an element of P(N), which does not depend on f),

Of course it does. That is very obvious.

Quote:
but it is not in the
image of f, which it should be if f is a bijection.

Of course, one may define a mapping from |N on P(|N), for instance n
--> {n}, where K is well defined. But the set {f, k, K}, essential for
Hessenberg's proof, does not exist. This shows that the customary
proof of Cantor's theorem makes use of a set which does not exist,
namely {f, k, K}. Therefore, its non-existence does not prove anything
about surjectivity of mappings.

The triple {f, k, K} does indeed not exist, but if f is a bijection it
should exist. It is just this contradiction that shows that f is not
a bijection.

Exactly the same holds in my example. Of course every subset K of |N
does exist. I is only the triple which does not. It is just this
contradiction that shows that f is not a bijection.

Regards, WM
Back to top
Dik T. Winter
science forum Guru


Joined: 25 Mar 2005
Posts: 1359

PostPosted: Wed Jun 21, 2006 12:07 am    Post subject: Re: An uncountable countable set Reply with quote

In article <1150835899.493068.116800@g10g2000cwb.googlegroups.com> mueckenh@rz.fh-augsburg.de writes:
....
Quote:
Of course K exists for every mapping f (if |N exists). But the set {f,
k, K} is a paradox set. It is not suitable to show that a bijection |N
--> {all finite subsets of P(|N) plus one further set} does not exist.

You do not show that. You show only that given a mapping f from N to the
set of finite subsets of N, the mapping f --> {all finite subsets of N
plus one additional subset conditioned by f} does not exist. This does
*not* prove that there is no bijection between N and {all finite subsets
of N plus one additional subset conditioned by f} does not exist.

Quote:
Why do you believe it could be capable of showing that |N --> P(|N)
does not exist?

Because P(N) does not depend on the mapping used. If you give as target
the set of all finite subsets of N plus one additional subset, I can
construct a bijection between N and that set. But your target is a
moving target.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Back to top
Dik T. Winter
science forum Guru


Joined: 25 Mar 2005
Posts: 1359

PostPosted: Wed Jun 21, 2006 12:19 am    Post subject: Re: An uncountable countable set Reply with quote

In article <1150836068.607034.205340@y41g2000cwy.googlegroups.com> mueckenh@rz.fh-augsburg.de writes:
....
Quote:
In order to define K_f you first have map all natural numbers n of |N
on the finite subsets of |N. Then consider K_f. But there is no element
k of |N remaining, which could be mapped on K. Hence the set M is
uncountable.

Wrong. We can construct a bijection between N and M_f, but it will only
not be f. And do not tell me that M_f changes when I construct that other
mapping. Bijections are not done with moving targets.

Quote:
It is about the same as Cantors diagonal proof. The
diagonal number depends on all numbers of his list. Moreover, after
constructing the diagonal number, it turns out to belong to a countable
set.

But that is a different list. You do not understand the proof. Given
*any* list it is possible to construct a real number that is not in that
particular list. That it is in a different list is irrelevant. That is
wat you always do. You move the target each time. The proof just shows
that there is *no* list that is complete. Otherwise, give me a *complete*
list. I can generate a number that is not in that list, so the list is
not *complete*. I think you have problems with proofs by contradiction.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Back to top
Dik T. Winter
science forum Guru


Joined: 25 Mar 2005
Posts: 1359

PostPosted: Wed Jun 21, 2006 12:30 am    Post subject: Re: An uncountable countable set Reply with quote

In article <1150836393.730055.231800@y41g2000cwy.googlegroups.com> mueckenh@rz.fh-augsburg.de writes:
....
Quote:
That raises the question of whether such a set as M_f can exist at all.

If it cannot exist, then the issue of whether a non-existent set is
countable is irrelevant.

Of course it exists. There are all finite subsets of |N. And there is,
for any function f, the set of all natural numbers, which are not
mapped on sets containing them. If |N exists, then K exists too. Maybe
|N does not exist completely?

But K(f) depends on f, so M(f) depends on f. This does not preclude a
bijection between N and M(f). It only tells us that f is not a bijection.
Now construct a bijection between N and M(f) and call it g. It clearly
is a bijection between N and M(f), so M(f) is countable. You can not
add *now* to the conditions that it was not M(f) to which should be mapped
but M(g). That is cheating. g is a proper bijection between N and M(f).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Back to top
Dik T. Winter
science forum Guru


Joined: 25 Mar 2005
Posts: 1359

PostPosted: Wed Jun 21, 2006 12:33 am    Post subject: Re: An uncountable countable set Reply with quote

In article <1150836884.833877.138440@c74g2000cwc.googlegroups.com> mueckenh@rz.fh-augsburg.de writes:
....
Quote:
M is countable means: There is an enumeration of the elements of M,
i.e., a bijective mapping |N <--> M.

But there is *no* M. There is only a M(f). Pray remain a bit consistent.
M and K depend on a mapping f.

Quote:
If |N does exist, then each of its subsets must exist, including K.
What does not exist is the bijection |N <--> M.

There is *no* M. You state here is no bijection between N and M(f).
The only thing you have proven is that *f* is not such a bijection.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Back to top
Dik T. Winter
science forum Guru


Joined: 25 Mar 2005
Posts: 1359

PostPosted: Wed Jun 21, 2006 1:10 am    Post subject: Re: An uncountable countable set Reply with quote

In article <1150837769.423770.307920@u72g2000cwu.googlegroups.com> mueckenh@rz.fh-augsburg.de writes:
Quote:
Dik T. Winter schrieb:
....
M depends on f. And when you take g, then M depends on g. That is the
essence of M.

In that case M is not a set.

Of course it is. It contains all finite subsets of |N and that set
which contains all natural numers wich under f are mapped on sets not
containing them. If |N is a set, then M is clearly a set too.

Yes, M(f) is, for each and every f: N -> S (the set of finite subsets of N),
M is not. entier(x) is an integer for each real x, that does not mean that
entier is an integer, it is a function. And so your M is a function,
dependent on its argument.

Quote:
And in order to tell whether that is
uncountable or not you have to first define cardinality on such
non-sets.

Cardinality is aleph_0 is there is a bijection with |N. If that is
impssible, then cardinality is larger.

Yes. But you first have to show that M is a set. Not that M(f) is a
set for each mapping f.

Quote:
That is not at all the way a bijection has to be constructed between |N
and M. That is simply impossible!

A bijection can be constructed, you only can not name if f.

First you must find out what the set {f, k, K} is. *That* is
impossible, not K.

A bijection can be constructed from |N to the numbers of Cantors list
and the diagonal number. You only first have to construct the latter.

You are putting it backwards. The proof is that *given any list* it is
possible to construct a number not on the list. But good luck at
constructing your bijection. When are you finished? And what if a
number is found not on your list (the proof shows that a number can
be constructed not on the list)?

Quote:
But if you like tricks of this kind, then you can biject |N and its
power set P(|N) \ K. Subsequently take
1. g(0) = K(f)
2. g(n) = f(n - 1) when n > 0
and we see that Cantor's theorem is not proven by Hessenberg's proof,
because this proof makes use of the impredicable definition of a set
which does not and cannot exist, as well as the barber who shaves all
men of his village.

Sorry, this is plain nonsense. You can not construct a bijection between
P(N) \ K.

Who told you?

Remember our discussion quite some time ago? I gave an explicit proof
of this.

However, this is neither here nor there. We start with a source and a
target. The source and target remain fixed (they are sets, you know).
Your discussion about M(f) and P(N)\K all do not disprove anything, you
are only moving the target. And bijections between sources and moving
targets are impossible.

Quote:
The difference between this and your construction with M(f)
is that the target M(f) depends on the bijection you are constructing.

The same holds in case of the proof of Cantor's theorem.

No, it is not.

Quote:
P(N) is a properly defined set that does not depend on anything but N.

But the set of numbers which are mapped on sets not containing them is
not proerly defined.

See, the target is P(N), it does not depend on the bijection you are
constructing. It is fixed. The set of numbers which are mapped on sets
not containing them is properly defined. It is an existing set and
depends on the mapping.

Quote:
But you are wrong. For every mapping f, the set K does exist (and is
an element of P(N), which does not depend on f),

Of course it does. That is very obvious.

Do you think P(N) depends on f? The set K depends on f, agreed.

Quote:
but it is not in the
image of f, which it should be if f is a bijection.

Why no remark on this?

Quote:
The triple {f, k, K} does indeed not exist, but if f is a bijection it
should exist. It is just this contradiction that shows that f is not
a bijection.

Exactly the same holds in my example. Of course every subset K of |N
does exist. I is only the triple which does not. It is just this
contradiction that shows that f is not a bijection.

Indeed, for f being a bijection it should exist. So f is not a bijection
between N and M(f). This does not state that there is no bijection
between N and M(f). There *are* bijections between N and M(f), for
each and every f you can construct such a bijection, it only is not f.
On the other hand, for every purported bijection between N and P(N) it
can be shown that it is not a bijection. You can not do that for every
purported bijection between N and M(f).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 3 of 58 [858 Posts] Goto page:  Previous  1, 2, 3, 4, 5, ..., 56, 57, 58 Next
View previous topic :: View next topic
The time now is Wed Aug 23, 2017 10:10 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Uncountable model of PA ashu_1559@rediffmail.com1 Math 4 Mon Jul 10, 2006 5:16 pm
No new posts vectors from l_2 and their difference isn't in l_1+uncoun... eugene Math 7 Fri Jun 23, 2006 10:52 pm
No new posts Is the set of infinite series of relational numers are co... TOMERDR Math 5 Mon May 15, 2006 4:24 pm
No new posts Countable sets [0,1] Kim Lee Math 4 Tue May 09, 2006 7:12 am
No new posts Countable set question Kim Lee Math 3 Tue May 09, 2006 1:50 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0454s ][ Queries: 16 (0.0045s) ][ GZIP on - Debug on ]