An uncountable countable set
in [Math]
|
Prev: integral problem
Next: Prime numbers
From: Dik T. Winter on 21 Jun 2006 10:58 In article <1150875562.782681.289070(a)g10g2000cwb.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > Dik T. Winter schrieb: > > > > > 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. > > (In case f should be surjective.) > > > 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. > > Who told you? The proof above. > Map f : N --> P(N) \ K(f). That has not been proven > impossible. > Then map g(n+1) = f(n) and g(1) = K(f). There is no proof that this > cannot be a bijection. Yes. See above. For *any* mapping it is shown that it is not a bijection. So g is also not a bijection. Construct K(g) according to Hessenberg (and that set *does* exist). If g were a bijection it is required (by the *definition* of bijection) that K(g) (because it is an element of P(n)) is the image of some element of N, but it is not, showing that g is not a bijection. P(N) does not depend on g, so there is no mapping between N and P(N) that is a bijoection. > > 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. > > > > Your mapping does exist. See (2) above. > > Of course. But only if f is not surjective. And g can be applied to > Hessenberg's proof in the same way. No, it can not. Because in the purported mapping N -> P(N) the target is independent of each attempted mapping. So when we start with an arbitrary mapping and show that it is not a bijection this implies that the proof goes on for every possible mapping. -- 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 21 Jun 2006 11:01 In article <1150875892.286170.29250(a)u72g2000cwu.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > Dik T. Winter schrieb: > > > In article <1150835899.493068.116800(a)g10g2000cwb.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > ... > > > Of course K exists for every mapping f (if |N exists). But the set {f, > > > k, K} is a paradox set. It is not suitable to show that a bijection |N > > > --> {all finite subsets of P(|N) plus one further set} does not exist. > > > > You do not show that. You show only that given a mapping f from N to the > > set of finite subsets of N, the mapping f --> {all finite subsets of N > > plus one additional subset conditioned by f} does not exist. > > A *surjective* mapping does not exist. The same does Hessenberg. A *surjective* mapping does exist, but it is not f. There exist a surjective mapping g -> M(f). > > This does > > *not* prove that there is no bijection between N and {all finite subsets > > of N plus one additional subset conditioned by f} does not exist. > > The same is with Hessenberg's. Nope. Try to do that with a purported mapping g -> M(f). (And please note, that I am talking about M(f), which is a set, not about M, which is *not* a set.) > > > Why do you believe it could be capable of showing that |N --> P(|N) > > > does not exist? > > > > Because P(N) does not depend on the mapping used. > > But Hessenberg's K(f) does depend on f. It is moving with f. And it can > be determined for any predicable definition of f. It cannot be > determined for the assumed surjection with its impredicable definition. Yes, so what? The *target* can be determined. That is sufficient. With your M(f) the target depends on f, and so is not a set. > > If you give as target > > the set of all finite subsets of N plus one additional subset, I can > > construct a bijection between N and that set. But your target is a > > moving target. > > Like that K(f) of Hessenberg's impredicable definition. But K(f) is not the target of the mapping. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Jens Kruse Andersen on 21 Jun 2006 11:44 I'll give it a shot, probably in vain. By definition, an infinite set M is uncountable if and only if: There is no bijective mapping f from N to M. Note that M is given first, and *then* it is said that no bijective f exists for that M, with no other condition on f than it has to be bijective. mueckenh 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. You are (correctly) saying: There is no bijective mapping f from N to a certain set M which depends on f in a certain way. In your case f apparently comes first (*), and *then* a specific set M is given, depending on f. The cited definition of uncountable does not apply to your situation, because you don't allow f to be chosen arbitrarily *after* M is given. You require a certain relationship (involving K) between M and f, where the uncountable definition *only* requires that f is a bijection from N to M. You are right that f is never a bijection for the specific M_f which depends on f, but for any non-bijective f there may be (and are) other functions which are bijections for that M_f (these bijections don't satisfy your condition about K). It may be a different function for different M_f but that's OK. The definition of countable always allows us to choose an arbitrary bijective function *after* the set is given. (*) Maybe you don't mean that f is selected first and then M, but just that f and M are given together with certain supposed properties, but if those properties require more than f being bijective, then the uncountable definition doesn't apply. In the well-known proof that P(N) is uncountable, P(N) is a fixed given set before any function is even mentioned. The proof then shows that no matter which function f is chosen, f will not be a bijection from N to P(N). The proof places no other condition on f than it has to be a bijection, so the definition of uncountable applies in that case: P(n) is uncountable. -- Jens Kruse Andersen
From: Virgil on 21 Jun 2006 15:44 In article <1150875562.782681.289070(a)g10g2000cwb.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Dik T. Winter schrieb: > > > > > 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. > > (In case f should be surjective.) > > > 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. > > Who told you? Map f : N --> P(N) \ K(f). That has not been proven > impossible. A bijection g: P(N) \ K(f) --> P(N) is necessarily possible, due to the infiniteness of P(N). Consider the composite mapping h = gof: N --> P(N) defined by h(x) = g(f(x)) and the set K(h) . That is also not in the image of f for the same reason so f is still not a bijection. Indeed, since there are infinitely many ( in fact uncountably many, but countably many is enough) different bijections g: P(N) \ K(f) --> P(N), one immediately has infinitely many K(h) not in the image of f.
From: Virgil on 21 Jun 2006 15:54
In article <1150875892.286170.29250(a)u72g2000cwu.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Dik T. Winter schrieb: > > > In article <1150835899.493068.116800(a)g10g2000cwb.googlegroups.com> > > mueckenh(a)rz.fh-augsburg.de writes: > > ... > > > Of course K exists for every mapping f (if |N exists). But the set {f, > > > k, K} is a paradox set. It is not suitable to show that a bijection |N > > > --> {all finite subsets of P(|N) plus one further set} does not exist. > > > > You do not show that. You show only that given a mapping f from N to the > > set of finite subsets of N, the mapping f --> {all finite subsets of N > > plus one additional subset conditioned by f} does not exist. > > A *surjective* mapping does not exist. While f itself cannot be surjective if any K_f and M_f are to exist, there are lots of non-surjective functions f, in fact any f not having K_f in its image. So the resolution is that either f, K_F and M_f are self-contradictory and do not exist at all or that they do exist and are numerous bijections between N and M_f (in fact uncountably many). |