An uncountable countable set
in [Math]
|
Prev: integral problem
Next: Prime numbers
From: Daryl McCullough on 19 Jun 2006 09:33 mueckenh(a)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? 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
From: mueckenh on 19 Jun 2006 10:43 Dik T. Winter schrieb: > In article <1150718841.726873.223390(a)g10g2000cwb.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > > > Dik T. Winter schrieb: > > > > > In article <1150654604.323294.139860(a)f6g2000cwb.googlegroups.com> mueckenh(a)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 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. > 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
From: mueckenh on 19 Jun 2006 10:51 Daryl McCullough schrieb: > mueckenh(a)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? Regards, WM
From: Daryl McCullough on 19 Jun 2006 11:32 mueckenh(a)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. 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
From: Virgil on 19 Jun 2006 14:34
In article <1150703345.226815.319450(a)r2g2000cwb.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Rupert schrieb: > > > mueckenh(a)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 f:|N --> 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. |