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 1 of 58 [858 Posts] View previous topic :: View next topic
Goto page:  1, 2, 3, ..., 56, 57, 58 Next
Author Message
Virgil
science forum Guru


Joined: 24 Mar 2005
Posts: 5536

PostPosted: Sun Jun 18, 2006 7:30 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Sun Jun 18, 2006 11:19 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 7:43 am    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 7:49 am    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 8:47 am    Post subject: Re: An uncountable countable set Reply with quote

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 gNeutralN --> 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

PostPosted: Mon Jun 19, 2006 9:43 am    Post subject: Re: An uncountable countable set Reply with quote

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 gNeutralN --> 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

PostPosted: Mon Jun 19, 2006 10:44 am    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 12:07 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 12:53 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 1:33 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 2:43 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 2:51 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 3:32 pm    Post subject: Re: An uncountable countable set Reply with quote

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

PostPosted: Mon Jun 19, 2006 6:34 pm    Post subject: Re: An uncountable countable set Reply with quote

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 fNeutralN --> 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
Virgil
science forum Guru


Joined: 24 Mar 2005
Posts: 5536

PostPosted: Mon Jun 19, 2006 6:43 pm    Post subject: Re: An uncountable countable set Reply with quote

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

Quote:
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.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 58 [858 Posts] Goto page:  1, 2, 3, ..., 56, 57, 58 Next
View previous topic :: View next topic
The time now is Mon Dec 18, 2017 2:47 pm | 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.0365s ][ Queries: 16 (0.0048s) ][ GZIP on - Debug on ]