An uncountable countable set
in [Math]
|
Prev: integral problem
Next: Prime numbers
From: mueckenh on 20 Jun 2006 01:42 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. That is the definition of uncountability. 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. > 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. The reason for its non-existence is not lacking number of elements of |N but an impredicable definition. I only wanted to point out that the same impradicability is the reason Hessenberg' s proof (non-surjectivity of f: |N --> P(|N)) seems to hold. It does not. In fact, it has nothing to do with any number of elements of any set. Regards, WM
From: mueckenh on 20 Jun 2006 01:46 Virgil schrieb: > 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. No, it is not, because M_f is incomplete without K. But K does not exist. The reason for its non-existence is not a lacking number of elements of |N but an impredicable definition. I only wanted to point out that the same impradicability is the reason why Hessenberg' s proof (non-surjectivity of f: |N --> P(|N)) seems to hold. It does not. In fact, it has nothing to do with any number of elements of any set. > > 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. The element K of M does not exist. If it is proven impossible to set up a mapping between M and |N, then M is uncountable. That is the definition of uncountability. 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. Your arguing would establish countability for {numbers of the list & diagonal number}, because the diagonal number increases the set only by 1 element. Regards, WM
From: Virgil on 20 Jun 2006 03:04 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. > 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.
From: Virgil on 20 Jun 2006 03:12 In article <1150782414.064700.253320(a)p79g2000cwp.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > > > > 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. > > No, it is not, because M_f is incomplete without K. But K does not > exist. That requires proof, and is false in at least one case. Let f(n) = {} for all n, then K_f is quite well defined. > The reason for its non-existence is not a lacking number of > elements of |N but an impredicable definition. I only wanted to point > out that the same impradicability is the reason why Hessenberg' s proof > (non-surjectivity of f: |N --> P(|N)) seems to hold. It does not. In > fact, it has nothing to do with any number of elements of any set. > > > > > 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. > > The element K of M does not exist. That requires proof, and is false in at least one case. Let f(n) = {} for all n, then K_f is quite well defined, and equals N. > > If it is proven impossible to set up a mapping between M and |N, then M > is uncountable. Wrong! If it is impossible to set up an injection from N to M_F or a surjection from M_f to N, and the axiom of choice is assumed, only then is M_f uncountable. And if K does not exist, as Meucken asserts above, then neither does any set which is required to have it as a member, so that no such set as M_f nor any such function as f:N --> M_f exists either, and his whole argument collapses.
From: Rupert on 20 Jun 2006 04:24
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. Yep. In one of the occurrences it occurs preceded by a universal quantifier, in the other it occurs as a constant symbol. > > > 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. > It doesn't make sense to talk about the set K={k e |N: k /e f(k)} unles you've specified what f is. > > 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. > So you mean M is the set of all finite subsets of |N, together with all sets of the form K={k e |N: k /e f(k)}, where f ranges over all possible mappings |N->P(|N)? That set is clearly uncountable. There is no problem there. > > in > > terms of which you're defining M. > > Let p and q be two natural numbers and let sqrt(2) = p/q. > > Regards, WM |