|
|
| 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.fh-augsburg.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^(s-1) |
|
| 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.fh-augsburg.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.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.
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.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.
| 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.fh-augsburg.de wrote:
| Quote: | Virgil schrieb:
In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com>,
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.
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 g N --> 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.fh-augsburg.de wrote:
Virgil schrieb:
In article <1150654604.323294.139860@f6g2000cwb.googlegroups.com>,
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.
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.fh-augsburg.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.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.
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.fh-augsburg.de writes:
| Quote: |
Dik T. Winter schrieb:
In article <1150654604.323294.139860@f6g2000cwb.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. 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.fh-augsburg.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.fh-augsburg.de writes:
Dik T. Winter schrieb:
In article <1150654604.323294.139860@f6g2000cwb.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.
| 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 non-existence 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.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?
| 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.fh-augsburg.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.fh-augsburg.de wrote:
| Quote: | 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.
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 Mar 14, 2010 6:06 pm | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
