An uncountable countable set
in [Math]
|
Prev: integral problem
Next: Prime numbers
From: mueckenh on 20 Jun 2006 05:34 Tim Peters schrieb: > [mueckenh(a)rz.fh-augsburg.de] > >>> 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. > > [Dik T. Winter] > >> 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. > > I'm not sure I'd be so generous here. K isn't a definite set before f is > specified (meaning that for K to provably exist by the axiom of separation, > f has to provably exist first), but to specify f K has to be a definite set > first (since K must be the image under f of some natural k, f can't be > proven to exist unless K can be proven to exist first). Of course f does not exist. But the reason has nothing at all to do with cardinalities. This error, however, is the foundation of Hessenberg's proof of Cantor's theorem. A set is required which is the image of k if it is not the image of k. A barber is required who shaves himself if he does not. > > IOW, I doubt this argument can be made in ZFC, just as it's not possible > under ZFC to prove that > > F = {k e |N : k e F} > or > G = {k e |N : k /e G} > > exist. On the other hand, why should any mapping not exist? If you claim that a surjective mapping |N --> P(|N) must contain the set K in any case, then there is no arguing why my mapping should not exist. Regards, WM
From: mueckenh on 20 Jun 2006 05:39 Virgil schrieb: > In article <1150782120.872330.199120(a)c74g2000cwc.googlegroups.com>, > mueckenh(a)rz.fh-augsburg.de wrote: > > > 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. > > > > > > >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. > > > > If it is proven impossible to set up a mapping between M and |N, then M > > is uncountable. > > But you have not proven it impossible, you merely argue that ONE > function between N and M(f) is not a bijection. > > > > WE have some f: N --> P(N), which we know is not a surjection since > there is no n in N for which one can have f(n) = K(f). > > But that does no mean that there is no surjection between M(f) and N. > > In fact, given a function f for which K(f) exists, it is not difficult > to build a bijection between M(f) and N as follows: > > For each S in M(F) define g: M(f) --> N by: > If K is finite then > if 0 e N > then g(S) = sum_{s e S} 2^s > else g(S) = sum_{s e S} 2^(s-1) > endif > else (K being infinite) > g(K) = the first natural > and > if 0 e N > then g(S) = sum_{s e S} 2^s+1 > else g(S) = sum_{s e S} 2^(s-1)+1 > endif > endif > > In all these cases, g will be a bijection from M(f) to N. > > > > > > > > We can prove > > > > > > forall f: N -> P(N), exists g: N -> P(N) > > > g is a bijection between N and M(f) > > > > No, it is not, because M(f) is incomplete without K. But K does not > > exist. > > But you have not proven it never exists, and for some functions, f, it > Does exist. > > For example, let f(n) = {} for all n, then > K = {k in N : not k e f(k) } = N. > > So that for SOME functions f, f, K(f) exists. > > The reason that Meucken's argument fails here is that there is no > necessity for the function f to be a surjection onto M(f). > > The desired bijection can be established by an entirely different > function between M(f) and N, as shown above. Only if K(f) would exist. > > > > > > > > > The reason for its non-existence is not lacking number of > > elements of |N but an impredicable definition. > > Wrong, as shown by a specific example above. Your example ist wrong because K(f) does not exist. Regards WM
From: Dik T. Winter on 20 Jun 2006 07:55 In article <1150728187.749465.36710(a)g10g2000cwb.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: > > In article <1150718841.726873.223390(a)g10g2000cwb.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 that case M is not a set. And in order to tell whether that is uncountable or not you have to first define cardinality on such non-sets. > > 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! A bijection can be constructed, you only can not name if f. > 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. Sorry, this is plain nonsense. You can not construct a bijection between P(N) \ K. The difference between this and your construction with M(f) is that the target M(f) depends on the bijection you are constructing. P(N) is a properly defined set that does not depend on anything but N. But you are wrong. For every mapping f, the set K does exist (and is an element of P(N), which does not depend on f), but it is not in the image of f, which it should be if f is a bijection. > 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. The triple {f, k, K} does indeed not exist, but if f is a bijection it should exist. It is just this contradiction that shows that f is not a bijection. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Dik T. Winter on 20 Jun 2006 08:16 In article <1150796061.943937.27660(a)p79g2000cwp.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: .... > > [Dik T. Winter] > > >> 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. > > > > I'm not sure I'd be so generous here. K isn't a definite set before f is > > specified (meaning that for K to provably exist by the axiom of separation, > > f has to provably exist first), but to specify f K has to be a definite set > > first (since K must be the image under f of some natural k, f can't be > > proven to exist unless K can be proven to exist first). > > Of course f does not exist. But the reason has nothing at all to do > with cardinalities. This error, however, is the foundation of > Hessenberg's proof of Cantor's theorem. Oh, but I think I disagree with Tim. Given any f: N -> S where S is the set of finite subsets of N, K(f) and M(f) do exist. > A set is required which is the image of k if it is not the image of k. > A barber is required who shaves himself if he does not. But here is your confusion. 1. Given a mapping f: N -> P(N), the set K(f) constructed according to Hessenberg *does* exist. If f were a bijection it is required (by the *definition* of bijection) that K(f) (because it is an element of P(N)) is the image of some element of N, but it is not, showing that f is not a bijection. P(N) does not depend on f, so there is no mapping between N and P(N) that is a bijection. 2. Given a mapping f: N -> S, the sets K(f) and M(f) do exist. If f were a bijection between N and M(f), K(f) should be in the image, it is not, so f is not a bijection. From this you can *not* conclude that M(f) is uncountable, because there can be a bijection g: N -> M(f). You can at most conclude that the union of *all* M(f)'s is uncountable. And that is easy, that union is just P(N). > On the other hand, why should any mapping not exist? If you claim that > a surjective mapping |N --> P(|N) must contain the set K in any case, > then there is no arguing why my mapping should not exist. You mapping does exist. See (2) above. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Daryl McCullough on 20 Jun 2006 09:25
mueckenh(a)rz.fh-augsburg.de says... >Daryl McCullough schrieb: >> 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. > >If it is proven impossible to set up a mapping between M and |N, then M >is uncountable. Once again, M is not a fixed set. It is a *function* of f. For each function f, there is a corresponding K_f and a corresponding M_f. Let's look at an example: Let f(x) be a mapping from N to P(N) as follows: f(0) = {} f(1) = { 0 } f(2^a_1 3^a_2 5^a_3 ... p_n^a_n) = { x_1, x_2, ..., x_n } where x_1 = a_1, x_{n+1} = x_n + a_{n+1} As I already pointed out, K(f) = { 0, 1, 2, ... } = N. M(f) = { A | A is a finite subset of N, or A = K(f) } M(f) is countable, since there is a bijection g: g(0) = N g(x+1) = f(x) >That is the definition of uncountability. By the definition of "uncountable" M(f) is countable. >Cp. Cantor's diagonal proof: >There it is even possible to set up a bijektion between {numbers of the >list & diagonal number}, (after the diagonal number has been >constructed) and |N. Nevertheless uncountablilty is claimed. The difference is that there is a proof that P(N) is uncountable, but there is a proof that M(f) *is* countable. What we can show is that for every f, f is not a surjection from N to M(f). But since M(f) is a subset of P(N), we have f is not a surjection from N to M(f) implies f is not a surjection from N to P(N) So we conclude (Cantor's theorem) forall f, f is not a surjection from N to P(N). >> We can prove >> >> forall f: N -> P(N), exists g: N -> P(N) >> g is a bijection between N and M(f) > >No, it is not, because M(f) is incomplete without K. But K does not >exist. On the contrary, for every f, there is a corresponding K(f), and there is a corresponding M(f). You give me an f, and I will show what the corresponding K(f) is. We already saw one example: for the f defined explicitly above, K(f) turns out to be all of N. >The reason for its non-existence is not lacking number of >elements of |N but an impredicable definition. Since K(f) *does* exist, it's a little silly to talk about the reasons for its nonexistence. Perhaps this would be easier for you if you start out considering finite sets, instead of N. Let N_1 = { 0 }. Then P(N_1) = { {}, {0} }. Let f be any function from N_1 to P(N_1). There are two such functions: f_1 and f_2 where f_1(0) = {} f_2(0) = {0} Now consider K(f_1). K(f_1) = { x in N_1 | x is not an element of f_1(x) } = { 0 } Clearly, K(f_1) is not in the image of f_1. So f_1 is not a bijection between N_1 and P(N_1). Now consider K(f_2). K(f_2) = { x in N_1 | x is not an element of f_2(x) } = {} Clearly, K(f_2) is not in the image of f_2. So f_2 is not a bijection between N_1 and P(N_1). Note, K(f_1) is *not* equal to K(f_2). Since f_1 and f_2 are all the functions from N_1 to P(N_1), it is clear that there are no bijections from N_1 to P(N_1). We can try the same thing using N_2 = { 0, 1}. We will find that there is no bijection from N_2 to P(N_2). The same is true for N_3 = { 0, 1, 2 } and N_4, and N_5, etc. We can generalize: for *any* set A (finite or not), and for any function f from A to P(A), we can define K(f) = { x in A | x is not an element of f(x) } It is clearly the case that K(f) is not in the image of f. It is also clearly the case that K(f) is an element of P(A). So we conclude: f is not a bijection between A and P(A). -- Daryl McCullough Ithaca, NY |