Search   Memberlist   Usergroups
 Page 1 of 58 [858 Posts] View previous topic :: View next topic Goto page:  1, 2, 3, ..., 56, 57, 58 Next
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
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

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

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

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 gN --> M_f.

And that is enough to prove every M_f countable.
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
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

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

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

Regards, WM
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
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
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

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.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 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 Sun Nov 18, 2018 4:41 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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