Author 
Message 
W. Mueckenheim science forum Guru
Joined: 23 Apr 2005
Posts: 934

Posted: Sun Jun 18, 2006 6:16 pm Post subject:
An uncountable countable set



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.
This shows M to be uncountable.
Regards, WM 

Back to top 


Virgil science forum Guru
Joined: 24 Mar 2005
Posts: 5536

Posted: Sun Jun 18, 2006 7:30 pm Post subject:
Re: An uncountable countable set



In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com>,
mueckenh@rz.fhaugsburg.de wrote:
Quote:  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.
This shows M to be uncountable.
Regards, WM

If M consists exactly of all finite subsets of }N, Meuckenh is wrong.
Using the 0 origin naturals for N, every finite subset, S, of N
bijects with a unique natural number under the mapping
g:M > N: g(S) = sum_{x in S} 2^s
so that the inverse of the f function is precisely the function that
Muecknh has declared not to exist.
If one uses the 1 origin naturals, the function is
g(S) = sum_{x in S} 2^(s1) 

Back to top 


Rupert science forum Guru
Joined: 18 May 2005
Posts: 372

Posted: Sun Jun 18, 2006 11:19 pm Post subject:
Re: An uncountable countable set



mueckenh@rz.fhaugsburg.de wrote:
Quote:  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. First you're denying that a
function f with certain properties exists, then you're defining M in
terms of some fixed function f, which it's not clear what it is. Use a
different letter for the two things, and the define the function in
terms of which you're defining M.
Quote:  This shows M to be uncountable.
Regards, WM 


Back to top 


W. Mueckenheim science forum Guru
Joined: 23 Apr 2005
Posts: 934

Posted: Mon Jun 19, 2006 7:43 am Post subject:
Re: An uncountable countable set



Virgil schrieb:
Quote:  In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com>,
mueckenh@rz.fhaugsburg.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.
This shows M to be uncountable.
Regards, WM
If M consists exactly of all finite subsets of }N, Meuckenh is wrong.

But it does not. The set M is uncountable while the set of all finite
subsets of N is countable.
Regards, WM 

Back to top 


W. Mueckenheim science forum Guru
Joined: 23 Apr 2005
Posts: 934

Posted: Mon Jun 19, 2006 7:49 am Post subject:
Re: An uncountable countable set



Rupert schrieb:
Quote:  mueckenh@rz.fhaugsburg.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.
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.
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.
Quote:  in
terms of which you're defining M.

Let p and q be two natural numbers and let sqrt(2) = p/q.
Regards, WM 

Back to top 


Virgil science forum Guru
Joined: 24 Mar 2005
Posts: 5536

Posted: Mon Jun 19, 2006 8:47 am Post subject:
Re: An uncountable countable set



In article <1150703016.762443.286860@h76g2000cwa.googlegroups.com>,
mueckenh@rz.fhaugsburg.de wrote:
Quote:  Virgil schrieb:
In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com>,
mueckenh@rz.fhaugsburg.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.
This shows M to be uncountable.
Regards, WM
If M consists exactly of all finite subsets of }N, Meuckenh is wrong.
But it does not. The set M is uncountable while the set of all finite
subsets of N is countable.
Regards, WM

Note that M depends on the particular f that has been chosen.
We can indicate that dependence by writing M_f.
Now for every f: N > M_f there is a bijection gN > M_f.
And that is enough to prove every M_f countable. 

Back to top 


W. Mueckenheim science forum Guru
Joined: 23 Apr 2005
Posts: 934

Posted: Mon Jun 19, 2006 9:43 am Post subject:
Re: An uncountable countable set



Virgil schrieb:
Quote:  In article <1150703016.762443.286860@h76g2000cwa.googlegroups.com>,
mueckenh@rz.fhaugsburg.de wrote:
Virgil schrieb:
In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com>,
mueckenh@rz.fhaugsburg.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.
This shows M to be uncountable.
Regards, WM
If M consists exactly of all finite subsets of }N, Meuckenh is wrong.
But it does not. The set M is uncountable while the set of all finite
subsets of N is countable.
Regards, WM
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 ?
Quote: 
Now for every f: N > M_f there is a bijection gN > M_f.
And that is enough to prove every M_f countable.

If you consider the mapping N > P(N), there is the same remedy by
showing that the mapping f : N > P(N) \ K cannot be used to prove
P(N) uncountable.
Regards, WM 

Back to top 


Dik T. Winter science forum Guru
Joined: 25 Mar 2005
Posts: 1359

Posted: Mon Jun 19, 2006 10:44 am Post subject:
Re: An uncountable countable set



In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com> mueckenh@rz.fhaugsburg.de writes:
Quote:  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.

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 


W. Mueckenheim science forum Guru
Joined: 23 Apr 2005
Posts: 934

Posted: Mon Jun 19, 2006 12:07 pm Post subject:
Re: An uncountable countable set



Dik T. Winter schrieb:
Quote:  In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com> mueckenh@rz.fhaugsburg.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.
Regards, WM 

Back to top 


Dik T. Winter science forum Guru
Joined: 25 Mar 2005
Posts: 1359

Posted: Mon Jun 19, 2006 12:53 pm Post subject:
Re: An uncountable countable set



In article <1150718841.726873.223390@g10g2000cwb.googlegroups.com> mueckenh@rz.fhaugsburg.de writes:
Quote: 
Dik T. Winter schrieb:
In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com> mueckenh@rz.fhaugsburg.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. This does not tell us that
there is *no* bijection (say g) between N and M. 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. Suppose f is a bijection between
N and S, where S is the set of finite subsets of N (such a bijection
does exist). Construct K(f) and next M(f). Clearly f is not a bijection
between N and M(f). However it is possible to construct a bijection
between N and M(f):
1. g(0) = K(f)
2. g(n) = f(n  1) when n > 0.
So also M(f) is countable.

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 


Daryl McCullough science forum Guru
Joined: 24 Mar 2005
Posts: 1167

Posted: Mon Jun 19, 2006 1:33 pm Post subject:
Re: An uncountable countable set



mueckenh@rz.fhaugsburg.de says...
Quote:  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? In
that case, there is definitely a bijection between M and N:
Here's how to compute f(x):
1. Let x be any natural number.
2. If x=0, then let f(x) = the empty set.
3. If x=1, then let f(x) = { 0 }.
4. Otherwise, factor x into products of primes:
x = 2^a_1 3^a_2 5^a_3 ...
where the last a_j is required to be greater than 0.
5. Then let f(x) = the set { a_1, a_2 + a_1 + 1, a_3 + a_2 + 1, ... }
If you let K = { k in N such that k is not an element of f(k) }
then we can see that
f(0) = the empty set
so 0 is not an element of f(0)
so 0 is an element of K
f(1) = { 0 }
so 1 is not an element of f(1)
so 1 is an element of K
f(2) = { 1 }
so 2 is not an element of f(2)
so 2 is an element of K
In general, we can prove that for every natural number x,
x is not an element of f(x)
so x is an element of K
So we have
K = N
K is therefore, not a finite set, and so is not an element of M.

Daryl McCullough
Ithaca, NY 

Back to top 


W. Mueckenheim science forum Guru
Joined: 23 Apr 2005
Posts: 934

Posted: Mon Jun 19, 2006 2:43 pm Post subject:
Re: An uncountable countable set



Dik T. Winter schrieb:
Quote:  In article <1150718841.726873.223390@g10g2000cwb.googlegroups.com> mueckenh@rz.fhaugsburg.de writes:
Dik T. Winter schrieb:
In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com> mueckenh@rz.fhaugsburg.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.
Quote:  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.
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.
Quote:  Suppose f is a bijection between
N and S, where S is the set of finite subsets of N (such a bijection
does exist). Construct K(f) and next M(f). Clearly f is not a bijection
between N and M(f). However it is possible to construct a bijection
between N and M(f):
1. g(0) = K(f)
2. g(n) = f(n  1) when n > 0.
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!
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.
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 nonexistence does not prove anything
about surjectivity of mappings.
Regards, WM 

Back to top 


W. Mueckenheim science forum Guru
Joined: 23 Apr 2005
Posts: 934

Posted: Mon Jun 19, 2006 2:51 pm Post subject:
Re: An uncountable countable set



Daryl McCullough schrieb:
Quote:  mueckenh@rz.fhaugsburg.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?
Quote:  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.
Quote:  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?
Regards, WM 

Back to top 


Daryl McCullough science forum Guru
Joined: 24 Mar 2005
Posts: 1167

Posted: Mon Jun 19, 2006 3:32 pm Post subject:
Re: An uncountable countable set



mueckenh@rz.fhaugsburg.de says...
Quote:  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.
We can prove
forall f: N > P(N), exists g: N > P(N)
g is a bijection between N and M(f)

Daryl McCullough
Ithaca, NY 

Back to top 


Virgil science forum Guru
Joined: 24 Mar 2005
Posts: 5536

Posted: Mon Jun 19, 2006 6:34 pm Post subject:
Re: An uncountable countable set



In article <1150703345.226815.319450@r2g2000cwb.googlegroups.com>,
mueckenh@rz.fhaugsburg.de wrote:
Quote:  Rupert schrieb:
mueckenh@rz.fhaugsburg.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.
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.

For any given fN > M_f there is a
h:M_f > N which is a bijection, and such an h is easy to constrruct.
Let N = {0,,1,2,...} be the von Neumann model of the naturals , and
let G be the set of all finite subsets of N, and
let sum_{n e {}} 2^n = 0, as is usual for empty sums,
then g:G > N defined by g(x) = sum_{y e x} 2^y
is a bijection from G to N corresponding to the binary representation
of the members of N.
Now for any f: N > M_f, of all finite subsets of N together with
K = {k e N : k /e f(k)} as members:
(1) either K is finite, in which case
G = M_f and h = g is a bijection between M_f and N
or
(2) K is not finite, in which case
we can define h so that h(K) = 0 and
for x in G h(x) = g(x) + 1.
Thus in any event, for every given f: N > M_f
there is an easily constricted bijection between N and M_f. 

Back to top 


Google


Back to top 



The time now is Sun Nov 18, 2018 4:41 pm  All times are GMT

