An uncountable countable set
muec...@rz.fh-augsburg.de
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
muec...@rz.fh-augsburg.de wrote:
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
muec...@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. 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.
muec...@rz.fh-augsburg.de
Virgil schrieb:
> In article <1150654604.3...@f6g2000cwb.googlegroups.com>,
> muec...@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
muec...@rz.fh-augsburg.de
Rupert schrieb:
> muec...@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.
> 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.
> 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
muec...@rz.fh-augsburg.de wrote:
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 g:|N --> M_f.
And that is enough to prove every M_f countable.
muec...@rz.fh-augsburg.de
Virgil schrieb:
> In article <1150703016.7...@h76g2000cwa.googlegroups.com>,
> muec...@rz.fh-augsburg.de wrote:
>
> > Virgil schrieb:
> >
> > > In article <1150654604.3...@f6g2000cwb.googlegroups.com>,
> > > muec...@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 ?
>
> Now for every f: |N --> M_f there is a bijection g:|N --> 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
> 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/
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> In article <1150654604.3...@f6g2000cwb.googlegroups.com> muec...@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
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.
Daryl McCullough
>> > 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
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> In article <1150718841.7...@g10g2000cwb.googlegroups.com> muec...@rz.fh-augsburg.de writes:
> >
> > Dik T. Winter schrieb:
> >
> > > In article <1150654604.3...@f6g2000cwb.googlegroups.com> muec...@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
muec...@rz.fh-augsburg.de
Daryl McCullough schrieb:
> muec...@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
Daryl McCullough
>> >> > 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)
Virgil
muec...@rz.fh-augsburg.de wrote:
> Rupert schrieb:
>
> > muec...@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.
Virgil
muec...@rz.fh-augsburg.de wrote:
> Virgil schrieb:
>
> > 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 ?
As soon as you tell us that M_f exists at all, YOU are telling us that
there must be such a set, K. The only other option is that there is no
such set K and no such set M_f and no such function f at all, in which
case the uncountable-countable-set becomes a non-existent
uncountable-countable-set.
Virgil
muec...@rz.fh-augsburg.de wrote:
Give us an example of such an f, K_f and M_f, to show that such an f,
K_f anf M_f can actually exist.
If they can exist at all, it is easy enough to show that there is a
bijection beween |N and M_f, and if they can't then there is no M_f to
worry about.
guenther vonKnakspot
Mueckenschleim wrote:
> Dik T. Winter schrieb:
>
> > In article <1150718841.7...@g10g2000cwb.googlegroups.com> muec...@rz.fh-augsburg.de writes:
> > >
> > > Dik T. Winter schrieb:
> > >
> > > > In article <1150654604.3...@f6g2000cwb.googlegroups.com> muec...@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.
guess your admirer Blumstin must be in rapture.
> > 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.
No, of course you don't. You can't even be consisten over a few lines
of text.
What is really disgusting is that this kook actually teaches at a
college and gets paid with the taxes earned by hard working people.
<snip crap>
Virgil
muec...@rz.fh-augsburg.de wrote:
> Dik T. Winter schrieb:
>
> > In article <1150718841.7...@g10g2000cwb.googlegroups.com>
> > muec...@rz.fh-augsburg.de writes:
> > >
> > > Dik T. Winter schrieb:
> > >
> > > > In article <1150654604.3...@f6g2000cwb.googlegroups.com>
> > > > muec...@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.
Wrong! Given any two large sets are many functions for one to the other
and equality of cardinality depends on whether any one of them is a
bijection. Given two sets to compare, you cannot restrict things to only
one allowable function between them but must allow all possible
functions between them to be considered.
>
> > 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.
Then there are other functions between N and M_f, one of which is a
bijection.
>
> > 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!
That you do not like it does not at all mean that it is impossible.
There are two issues here. The first is whether a function of the sort
Meucken tries to create can exist at all. He has given no example of
such a function, nor proof of existence.
However if we allow the assumption that such a function f exists, it is
not hard to show that there are bijections between |N and M_f, though f
need not be one of them.
Virgil
muec...@rz.fh-augsburg.de wrote:
That raises the question of whether such a set as M_f can exist at all.
If it cannot exist, then the issue of whether a non-existent set is
countable is irrelevant.
So that Meucken's first duty is to prove that a function having the sort
of codomain, M_f, he describes can exist at all.
If ever that is established, the construction of a bijection between it
and N is fairly trivial.
Tim Peters
>>> 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).
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.
[muec...@rz.fh-augsburg.de]
> 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.
And if Dik constructs g1, while I construct a distinct g2, the definition of
M frustrates both claimed bijections simultaneously? Cool ;-)
> ...
muec...@rz.fh-augsburg.de
Daryl McCullough schrieb:
> muec...@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
muec...@rz.fh-augsburg.de
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
Virgil
muec...@rz.fh-augsburg.de wrote:
> Daryl McCullough schrieb:
>
> > muec...@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.
Virgil
muec...@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.
Rupert
muec...@rz.fh-augsburg.de wrote:
> Rupert schrieb:
>
> > muec...@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.
muec...@rz.fh-augsburg.de
Tim Peters schrieb:
> [muec...@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
muec...@rz.fh-augsburg.de
Virgil schrieb:
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
Dik T. Winter
> Dik T. Winter schrieb:
...
> > > > > 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
...
> > [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.
Daryl McCullough
>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).
Virgil
muec...@rz.fh-augsburg.de wrote:
>
> > [muec...@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.
> 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.
f does not exist if it is required to be a bijection, but in that case
neither does K(f) of M(f) exist, so there no such set as M(f).
On the other hand, if f is not required to have K(f) in its image set,
then there is no problem with constructing any number of such functions,
and for each of them, there is a bijection (though not f) between N and
M(f).
>
> 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.
The problem only arises when one insists that there is some n in N such
that f(n) = K(f). If one does not make that requirement, then there is
no problem with the existence of K(f) or with functions f:N --> M(f).
Virgil
muec...@rz.fh-augsburg.de wrote:
If one claims that such an f is a bijection, then it cannot exist at
all, but neither can K_f or M_f exist, so the problem of whether such a
nonexistent set as M_f is countable is irrelevant.
If one does not require f to be bijective, in particular if one does not
require that there be any n in N for which f(n) = K_f, then K_f anf M_f
may quite easily exist.
And M_f is quite easily shown to be bijectable with N when it does
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.
There are two cases to consider:
(1) If one requires that there be some n in N for which f(n) = K_f, then
the function f does not exist, but then neither do K_f and M_f, so there
is no problem as there is no such thing as M_f.
(2) If f:N --> P(N) is such that there is no n in N for which f(n) =
K_f, then again there is no problem, since while K_f and M_f may exist,
it is easily shown that when they do, M_f and N biject.
>
> Regards WM
muec...@rz.fh-augsburg.de
Virgil schrieb:
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.
Why do you believe it could be capable of showing that |N --> P(|N)
does not exist?
Regards, WM
muec...@rz.fh-augsburg.de
Virgil schrieb:
>
> Give us an example of such an f, K_f and M_f, to show that such an f,
> K_f anf M_f can actually exist.
If the set {f, k, K} could actually exist, then M would be countable.
But it is not, isn't it?
>
> If they can exist at all, it is easy enough to show that there is a
> bijection beween |N and M_f, and if they can't then there is no M_f to
> worry about.
In order to define K_f you first have map all natural numbers n of |N
on the finite subsets of |N. Then consider K_f. But there is no element
k of |N remaining, which could be mapped on K. Hence the set M is
uncountable. It is about the same as Cantors diagonal proof. The
diagonal number depends on all numbers of his list. Moreover, after
constructing the diagonal number, it turns out to belong to a countable
set. My M remains uncountable in any instance.
Regards, WM
muec...@rz.fh-augsburg.de
Virgil schrieb:
> > M depends on f. And when you take g, then M depends on g. That is the
> > essence of M.
>
> Wrong! Given any two large sets are many functions for one to the other
> and equality of cardinality depends on whether any one of them is a
> bijection. Given two sets to compare, you cannot restrict things to only
> one allowable function between them but must allow all possible
> functions between them to be considered.
I allow for all functions, because I did not introduce any
restrictions.
> >
> > > 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.
>
> Then there are other functions between N and M_f, one of which is a
> bijection.
Could you prove that assertion please?
> There are two issues here. The first is whether a function of the sort
> Meucken tries to create can exist at all. He has given no example of
> such a function, nor proof of existence.
Of course there is no proof of existence. If it was, then M was
countable.
>
> However if we allow the assumption that such a function f exists, it is
> not hard to show that there are bijections between |N and M_f, though f
> need not be one of them.
There are many bijections between {numbers of Cantor's list plus
diagonal number}. Don't you know that? Here is one: Enumerate list
number n by n+1 and enumerate the diagonal number by 1.
Regards, WM
muec...@rz.fh-augsburg.de
Virgil schrieb:
> In article <1150728692.9...@h76g2000cwa.googlegroups.com>,
> muec...@rz.fh-augsburg.de wrote:
>
> > Daryl McCullough schrieb:
> >
> > > muec...@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?
>
> That raises the question of whether such a set as M_f can exist at all.
>
> If it cannot exist, then the issue of whether a non-existent set is
> countable is irrelevant.
Of course it exists. There are all finite subsets of |N. And there is,
for any function f, the set of all natural numbers, which are not
mapped on sets containing them. If |N exists, then K exists too. Maybe
|N does not exist completely?
> So that Meucken's first duty is to prove that a function having the sort
> of codomain, M_f, he describes can exist at all.
>
> If ever that is established, the construction of a bijection between it
> and N is fairly trivial.
If |N exists, then K exists too. Maybe |N does not exist completely?
Regards, WM
muec...@rz.fh-augsburg.de
Virgil schrieb:
> > The element K of M does not exist.
Excuse me. The set {f, k, 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, and equals N.
You are correct. Of course K_f does exist for any f (if all natural
numbers do exist). Nevertheless you see that the mapping is not a
bijection beause no f(n) = K.
> >
> > If it is proven impossible to set up a mapping between M and |N, then M
> > is uncountable.
>
> Wrong!
M is countable means: There is an enumeration of the elements of M,
i.e., a bijective mapping |N <--> M.
>
> 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,
If |N does exist, then each of its subsets must exist, including K.
What does not exist is the bijection |N <--> M.
Regards, WM
muec...@rz.fh-augsburg.de
Rupert schrieb:
> muec...@rz.fh-augsburg.de wrote:
> > Rupert schrieb:
> >
> > > muec...@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.
Could you say what you mean?
> > > 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.
f is not fixed by any specification. Therefore my arguing holds for any
f. K is that subset of |N which contains all natural numbers which are
not mapped under f on sets containing themselves.
>
> > > 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)?
No. K is that single set which belongs to the function f.
Regards, WM
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> In article <1150728187....@g10g2000cwb.googlegroups.com> muec...@rz.fh-augsburg.de writes:
> > Dik T. Winter schrieb:
> > > In article <1150718841.7...@g10g2000cwb.googlegroups.com> muec...@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.
Of course it is. It contains all finite subsets of |N and that set
which contains all natural numers wich under f are mapped on sets not
containing them. If |N is a set, then M is clearly a set too.
> And in order to tell whether that is
> uncountable or not you have to first define cardinality on such
> non-sets.
Cardinality is aleph_0 is there is a bijection with |N. If that is
impssible, then cardinality is larger.
>
> > > 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.
First you must find out what the set {f, k, K} is. *That* is
impossible, not K.
A bijection can be constructed from |N to the numbers of Cantors list
and the diagonal number. You only first have to construct the latter.
>
> > 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.
Who told you?
> The difference between this and your construction with M(f)
> is that the target M(f) depends on the bijection you are constructing.
The same holds in case of the proof of Cantor's theorem.
> P(N) is a properly defined set that does not depend on anything but N.
But the set of numbers which are mapped on sets not containing them is
not proerly defined.
> 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),
Of course it does. That is very obvious.
> 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.
Exactly the same holds in my example. Of course every subset K of |N
does exist. I is only the triple which does not. It is just this
contradiction that shows that f is not a bijection.
Regards, WM
Dik T. Winter
...
> 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. 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.
> 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. 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.
Dik T. Winter
...
> In order to define K_f you first have map all natural numbers n of |N
> on the finite subsets of |N. Then consider K_f. But there is no element
> k of |N remaining, which could be mapped on K. Hence the set M is
> uncountable.
Wrong. We can construct a bijection between N and M_f, but it will only
not be f. And do not tell me that M_f changes when I construct that other
mapping. Bijections are not done with moving targets.
> It is about the same as Cantors diagonal proof. The
> diagonal number depends on all numbers of his list. Moreover, after
> constructing the diagonal number, it turns out to belong to a countable
> set.
But that is a different list. You do not understand the proof. Given
*any* list it is possible to construct a real number that is not in that
particular list. That it is in a different list is irrelevant. That is
wat you always do. You move the target each time. The proof just shows
that there is *no* list that is complete. Otherwise, give me a *complete*
list. I can generate a number that is not in that list, so the list is
not *complete*. I think you have problems with proofs by contradiction.
Dik T. Winter
...
> > That raises the question of whether such a set as M_f can exist at all.
> >
> > If it cannot exist, then the issue of whether a non-existent set is
> > countable is irrelevant.
>
> Of course it exists. There are all finite subsets of |N. And there is,
> for any function f, the set of all natural numbers, which are not
> mapped on sets containing them. If |N exists, then K exists too. Maybe
> |N does not exist completely?
But K(f) depends on f, so M(f) depends on f. This does not preclude a
bijection between N and M(f). It only tells us that f is not a bijection.
Now construct a bijection between N and M(f) and call it g. It clearly
is a bijection between N and M(f), so M(f) is countable. You can not
add *now* to the conditions that it was not M(f) to which should be mapped
but M(g). That is cheating. g is a proper bijection between N and M(f).
Dik T. Winter
...
> M is countable means: There is an enumeration of the elements of M,
> i.e., a bijective mapping |N <--> M.
But there is *no* M. There is only a M(f). Pray remain a bit consistent.
M and K depend on a mapping f.
> If |N does exist, then each of its subsets must exist, including K.
> What does not exist is the bijection |N <--> M.
There is *no* M. You state here is no bijection between N and M(f).
The only thing you have proven is that *f* is not such a bijection.
Virgil
muec...@rz.fh-augsburg.de wrote:
> Virgil schrieb:
>
> > In article <1150710209.4...@i40g2000cwc.googlegroups.com>,
> > muec...@rz.fh-augsburg.de wrote:
> >
> > > Virgil schrieb:
> > >
> >
> > > > 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 ?
> >
> > As soon as you tell us that M_f exists at all, YOU are telling us that
> > there must be such a set, K. The only other option is that there is no
> > such set K and no such set M_f and no such function f at all, in which
> > case the uncountable-countable-set becomes a non-existent
> > uncountable-countable-set.
>
> Of course K exists for every mapping f (if |N exists). But the set {f,
> k, K} is a paradox set.
If K_f exists it is not paradoxical and if it is paradoxical, it does
not exist. The paradox occurs if one has any function f with domain N
and image some subset of P(N) containing K_f.
If the image of f is not required to contain K_f, there re no problems.
> It is not suitable to show that a bijection |N
> --> {all finite subsets of P(|N) plus one further set} does not exist.
> Why do you believe it could be capable of showing that |N --> P(|N)
> does not exist?
It is your example!
Work it out for yourself why f(n) = {m in N: m not in f(m)} doesn't work.
Dik T. Winter
> Dik T. Winter schrieb:
> > > 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.
>
> Of course it is. It contains all finite subsets of |N and that set
> which contains all natural numers wich under f are mapped on sets not
> containing them. If |N is a set, then M is clearly a set too.
Yes, M(f) is, for each and every f: N -> S (the set of finite subsets of N),
M is not. entier(x) is an integer for each real x, that does not mean that
entier is an integer, it is a function. And so your M is a function,
dependent on its argument.
> > And in order to tell whether that is
> > uncountable or not you have to first define cardinality on such
> > non-sets.
>
> Cardinality is aleph_0 is there is a bijection with |N. If that is
> impssible, then cardinality is larger.
Yes. But you first have to show that M is a set. Not that M(f) is a
set for each mapping f.
> > > 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.
>
> First you must find out what the set {f, k, K} is. *That* is
> impossible, not K.
>
> A bijection can be constructed from |N to the numbers of Cantors list
> and the diagonal number. You only first have to construct the latter.
You are putting it backwards. The proof is that *given any list* it is
possible to construct a number not on the list. But good luck at
constructing your bijection. When are you finished? And what if a
number is found not on your list (the proof shows that a number can
be constructed not on the list)?
> > > 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.
>
> Who told you?
Remember our discussion quite some time ago? I gave an explicit proof
of this.
However, this is neither here nor there. We start with a source and a
target. The source and target remain fixed (they are sets, you know).
Your discussion about M(f) and P(N)\K all do not disprove anything, you
are only moving the target. And bijections between sources and moving
targets are impossible.
> > The difference between this and your construction with M(f)
> > is that the target M(f) depends on the bijection you are constructing.
>
> The same holds in case of the proof of Cantor's theorem.
No, it is not.
> > P(N) is a properly defined set that does not depend on anything but N.
>
> But the set of numbers which are mapped on sets not containing them is
> not proerly defined.
See, the target is P(N), it does not depend on the bijection you are
constructing. It is fixed. The set of numbers which are mapped on sets
not containing them is properly defined. It is an existing set and
depends on the mapping.
> > 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),
>
> Of course it does. That is very obvious.
Do you think P(N) depends on f? The set K depends on f, agreed.
> > but it is not in the
> > image of f, which it should be if f is a bijection.
Why no remark on this?
> > 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.
>
> Exactly the same holds in my example. Of course every subset K of |N
> does exist. I is only the triple which does not. It is just this
> contradiction that shows that f is not a bijection.
Indeed, for f being a bijection it should exist. So f is not a bijection
between N and M(f). This does not state that there is no bijection
between N and M(f). There *are* bijections between N and M(f), for
each and every f you can construct such a bijection, it only is not f.
On the other hand, for every purported bijection between N and P(N) it
can be shown that it is not a bijection. You can not do that for every
purported bijection between N and M(f).
Virgil
muec...@rz.fh-augsburg.de wrote:
> Virgil schrieb:
>
>
> >
> > Give us an example of such an f, K_f and M_f, to show that such an f,
> > K_f anf M_f can actually exist.
>
> If the set {f, k, K} could actually exist, then M would be countable.
> But it is not, isn't it?
If M_f exists at all it is countable, and if it doesn't exist the
question of its countability is disappears.
> >
> > If they can exist at all, it is easy enough to show that there is a
> > bijection beween |N and M_f, and if they can't then there is no M_f to
> > worry about.
>
> In order to define K_f you first have map all natural numbers n of |N
> on the finite subsets of |N. Then consider K_f. But there is no element
> k of |N remaining, which could be mapped on K.
Then try a different mapping, say g:N --> M_f.
I have previously shown that if K_f and M_f exist for a non-bijective
f:N --> M_f, then M_f must be countable.
I have also shown that if f itself is required to be a bijection neither
it not K_f nor M_f even exist, so the question of countability of a
non-set is nonsense.
Virgil
muec...@rz.fh-augsburg.de wrote:
> Virgil schrieb:
>
> > > M depends on f. And when you take g, then M depends on g. That is the
> > > essence of M.
> >
> > Wrong! Given any two large sets are many functions for one to the other
> > and equality of cardinality depends on whether any one of them is a
> > bijection. Given two sets to compare, you cannot restrict things to only
> > one allowable function between them but must allow all possible
> > functions between them to be considered.
>
> I allow for all functions, because I did not introduce any
> restrictions.
You require that
(1) f be a bijection and
(2) its codomain contain {x in N: x not in f(x)} = K_f
These conditions are mutually contradictory, so that no such bijection
and no such K_f can co-exist.
However, it the function is not required t have K_f as a value, so that
IT is not bijection, then both f and K_f can exist and the codomain of
F, namely M_f, is countable.
> > >
> > > > 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.
> >
> > Then there are other functions between N and M_f, one of which is a
> > bijection.
>
> Could you prove that assertion please?
>
> > There are two issues here. The first is whether a function of the sort
> > Meucken tries to create can exist at all. He has given no example of
> > such a function, nor proof of existence.
>
> Of course there is no proof of existence. If it was, then M was
> countable.
Then the non-existent set M_f, if not countable, is not uncountable
either.
Virgil
muec...@rz.fh-augsburg.de wrote:
How can a function, f, from N to any subset of P(N) exist if it must be
the case that for some n in N, f(n) = {k in N: k not in f(k)} ?
If n were such that f(n) = K_f = {k in N: k not in f(k)}, would it be
the case that n IS a member of K_f or n IS NOT a member of K_f?
Assuming either establishes its negation, so neither can be the case.
>
> > So that Meucken's first duty is to prove that a function having the sort
> > of codomain, M_f, he describes can exist at all.
> >
> > If ever that is established, the construction of a bijection between it
> > and N is fairly trivial.
>
> If |N exists, then K exists too.
WRONG! Existence of N is quite simple in ZFC of NBG, but the existence
of K depends on the alleged properties of function f.
If f is requires to have K_f as a value then f, K_f and M_f are all
non-existant.
If f is allowed not to have K_f as a value, then f, though no longer a
bijection, can exist, as can K_f and M_f. But in this case there are
other functions between N and M_f which ARE bijections.
Virgil
muec...@rz.fh-augsburg.de wrote:
> Virgil schrieb:
>
>
> > > The element K of M does not exist.
>
> Excuse me. The set {f, k, 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, and equals N.
>
> You are correct. Of course K_f does exist for any f (if all natural
> numbers do exist).
Not so. {f,K_f,M_f} cannot exist if f is required to have K_f as a
value, but can and will, though not as a bijection, exist if that
requirement is voided.
> Nevertheless you see that the mapping is not a
> bijection beause no f(n) = K.
The failure of one function to be a bijection does no establish that
none exist.
> > >
> > > If it is proven impossible to set up a mapping between M and |N, then M
> > > is uncountable.
> >
> > Wrong!
>
> M is countable means: There is an enumeration of the elements of M,
> i.e., a bijective mapping |N <--> M.
> >
> > 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,
>
> If |N does exist, then each of its subsets must exist, including K.
K can only exist if the function, f, which defines it is not required
to have it for a value.
> What does not exist is the bijection |N <--> M.
If M_f exists at all (and it won't with Muecken's conditions on f) ,
then there are uncountably many bijections between N and M
Virgil
muec...@rz.fh-augsburg.de wrote:
> Rupert schrieb:
>
> > muec...@rz.fh-augsburg.de wrote:
> > > Rupert schrieb:
> > >
> > > > muec...@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.
>
> Could you say what you mean?
>
> > > > 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.
>
> f is not fixed by any specification.
its domain, codomain and range have been specified, but that codomain
and range have been define circularly in a way which prohibits the
existence of an F, K_f and M_f satisfying those conditions.
The easiest condition to relax is the one requiring that f be a
bijection, in particular that it have K_f as a value.
If this condition is dropped then, and only then, can an {f,K_f, M_f} as
described actually exist, and then M_f is easily countable.
> > 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)?
>
> No. K is that single set which belongs to the function f.
Thus you need to have that there to exist an n in N such that
f(n) = {x in N: x not in f(x)} = K_f
But if that n is in K_f then n is not in f(n) = K_f
and if it is not in K_f then it is automatically in f(n) = K_f
so that no such n can exist such that f(n) = K_f.
Virgil
muec...@rz.fh-augsburg.de wrote:
But given two different functions, say f and g,
one has M_f != M_g.
So "M" is not a set but the value of some function whose arguments are f
and g.
> Cardinality is aleph_0 is there is a bijection with |N. If that is
> impssible, then cardinality is larger.
Or smaller, or unknown.
> >
> > > > 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!
It is a good deal more possible that the garbage claims Meucken has been
making.
> >
> > A bijection can be constructed, you only can not name if f.
>
> First you must find out what the set {f, k, K} is. *That* is
> impossible, not K.
F and K and M are all impossible as long as Muecken requires that f have
K as a value.
Absent that requirement, it is all possible and the resulting M is
countable.
Rupert
muec...@rz.fh-augsburg.de wrote:
> Rupert schrieb:
>
> > muec...@rz.fh-augsburg.de wrote:
> > > Rupert schrieb:
> > >
> > > > muec...@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.
>
> Could you say what you mean?
>
Are you familiar with existential quantifiers and universal
quantifiers? You are making a statement of the form "There does not
exist an f such that...", or, alternatively "For all f it is not the
case that..." Then later on you use f to refer to a specific function.
You should use different letters on these two occasions.
> > > > 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.
>
> f is not fixed by any specification. Therefore my arguing holds for any
> f. K is that subset of |N which contains all natural numbers which are
> not mapped under f on sets containing themselves.
Okay. So let me have a shot in translating what you've said into
something coherent.
"Let f be an arbitrary function. There does not exist a bijective
mapping g:N->M, where M is the set consisting of all the finite subsets
of N together with the set K={k e N: k /e f(k)}."
This is false. There always will exist such a bijection g. It will of
course be different to f.
Rupert
muec...@rz.fh-augsburg.de wrote:
> Rupert schrieb:
>
> > muec...@rz.fh-augsburg.de wrote:
> > > Rupert schrieb:
> > >
> > > > muec...@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.
>
> Could you say what you mean?
>
> > > > 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.
>
> f is not fixed by any specification. Therefore my arguing holds for any
> f. K is that subset of |N which contains all natural numbers which are
> not mapped under f on sets containing themselves.
An alternative interpretation for what you're trying to say would be
"It is not the case that there exists a set M of subsets of N and a
bijection f:N->M, such that M consists of all the finite subsets of N
together with the set K={k e N: k /e f(k)}."
This is quite correct, but it does not amount to identifying an
uncountable countable set. What you've done is observe that there does
not exist a pair (M,f) with certain properties. To identify an
uncountable set you have to first identify a set M and then observe
that there does not exist an f with certain properties.
Virgil
"Rupert" <rupertm...@yahoo.com> wrote:
Except that if the function is require to have K as a value, the f and K
and M cannot exist:
if f(n) = K = {k e N: k /e f(k)} is n a member of K or not?
muec...@rz.fh-augsburg.de
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.
Then map g(n+1) = f(n) and g(1) = K(f). There is no proof that this
cannot be 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.
>
> 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.
Regards, WM
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> In article <1150835899.4...@g10g2000cwb.googlegroups.com> muec...@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.
> 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.
>
> > 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.
> 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.
Regards, WM
muec...@rz.fh-augsburg.de
Rupert schrieb:
> Are you familiar with existential quantifiers and universal
> quantifiers? You are making a statement of the form "There does not
> exist an f such that...", or, alternatively "For all f it is not the
> case that..." Then later on you use f to refer to a specific function.
> You should use different letters on these two occasions.
No. "For all f it is not the case" means the same as "there does not
exist any f for which it is the case". A f (f =/= surj) <==> ~E f (f =
sur).
And I let f be any function you like.
>
> "Let f be an arbitrary function. There does not exist a bijective
> mapping g:N->M, where M is the set consisting of all the finite subsets
> of N together with the set K={k e N: k /e f(k)}."
That is what I said.
>
> This is false. There always will exist such a bijection g. It will of
> course be different to f.
The same is true is you take Hessenberg's mapping of f:N --> P(N). It
is not surjective because of K(f). But if you define g(n+1) = f(n) and
g(1) = K(f), the proof is no longer a proof.
Regards, WM
Rupert
This is a perfectly good proof that K cannot be in the range of f. But
as far as I can tell, there would still be a bijection g:N->M, and K
would be in the range of g. g would of course be different from f. No?
Rupert
muec...@rz.fh-augsburg.de wrote:
> Rupert schrieb:
>
> > Are you familiar with existential quantifiers and universal
> > quantifiers? You are making a statement of the form "There does not
> > exist an f such that...", or, alternatively "For all f it is not the
> > case that..." Then later on you use f to refer to a specific function.
> > You should use different letters on these two occasions.
>
> No. "For all f it is not the case" means the same as "there does not
> exist any f for which it is the case". A f (f =/= surj) <==> ~E f (f =
> sur).
>
I know.
> And I let f be any function you like.
The question is, is the second occurrence of f within the scope of the
quantifier? I have given you two interpretations of what you said, one
on the assumption that the second occurrence of f is not within the
scope of the quantifier, and the other on the assumption that it is.
And I have responded to what you said on both interpretations.
> >
> > "Let f be an arbitrary function. There does not exist a bijective
> > mapping g:N->M, where M is the set consisting of all the finite subsets
> > of N together with the set K={k e N: k /e f(k)}."
>
> That is what I said.
> >
> > This is false. There always will exist such a bijection g. It will of
> > course be different to f.
>
> The same is true is you take Hessenberg's mapping of f:N --> P(N). It
> is not surjective because of K(f). But if you define g(n+1) = f(n) and
> g(1) = K(f), the proof is no longer a proof.
>
Yes, it is. For each mapping f:N->P(N), you have a bijection g:N->M. If
you change the mapping, you've got to change the bijection. But there
still is one. The proof still works.
> Regards, WM
muec...@rz.fh-augsburg.de
Rupert schrieb:
> > Except that if the function is require to have K as a value, the f and K
> > and M cannot exist:
> > if f(n) = K = {k e N: k /e f(k)} is n a member of K or not?
>
> This is a perfectly good proof that K cannot be in the range of f. But
> as far as I can tell, there would still be a bijection g:N->M, and K
> would be in the range of g. g would of course be different from f. No?
2) 0.12324389
3) 0.23123123
4) 0.85348714
..
1) 0.244...
This is a perfectly good proof, that a surjective mapping g: |N -->
[0,1] does exist, isn't it?
Regards, WM
Dik T. Winter
>
> 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
>
> Dik T. Winter schrieb:
>
> > In article <1150835899.4...@g10g2000cwb.googlegroups.com> muec...@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.
Jens Kruse Andersen
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
Virgil
muec...@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.
Virgil
muec...@rz.fh-augsburg.de wrote:
> Dik T. Winter schrieb:
>
> > In article <1150835899.4...@g10g2000cwb.googlegroups.com>
> > muec...@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).
Virgil
muec...@rz.fh-augsburg.de wrote:
> Rupert schrieb:
>
> > Are you familiar with existential quantifiers and universal
> > quantifiers? You are making a statement of the form "There does not
> > exist an f such that...", or, alternatively "For all f it is not the
> > case that..." Then later on you use f to refer to a specific function.
> > You should use different letters on these two occasions.
>
> No. "For all f it is not the case" means the same as "there does not
> exist any f for which it is the case". A f (f =/= surj) <==> ~E f (f =
> sur).
>
> And I let f be any function you like.
Let it be any function which does not have K_f as a value.
> >
> > "Let f be an arbitrary function. There does not exist a bijective
> > mapping g:N->M, where M is the set consisting of all the finite subsets
> > of N together with the set K={k e N: k /e f(k)}."
>
> That is what I said.
Then f is not arbitrary, since you insist on restricting the function f
to have some n in N such that f(n) = {x in n: x not in f(x)}.
With that restriction, no such f can exist, absent that restriction,
lots of them do.
Virgil
muec...@rz.fh-augsburg.de wrote:
No. And it totally ignores the fact that Muecken's alleged example of a
n uncountable countable set is fatally flawed, as is shown above.
Daryl McCullough
Daryl McCullough
>Rupert schrieb:
>> "Let f be an arbitrary function. There does not exist a bijective
>> mapping g:N->M, where M is the set consisting of all the finite subsets
>> of N together with the set K={k e N: k /e f(k)}."
>
>That is what I said.
>>
>> This is false. There always will exist such a bijection g. It will of
>> course be different to f.
>
>The same is true is you take Hessenberg's mapping of f:N --> P(N). It
>is not surjective because of K(f). But if you define g(n+1) = f(n) and
>g(1) = K(f), the proof is no longer a proof.
Sure it is. f is not a surjection from N -> P(N), because
K(f) is not in the image of f. Similarly, g is not a surjection
from N to P(N) because K(g) is not in the image of g.
Let's go through this one more time.
Let f be any function from N to P(N).
Let image(f) =
{ A in P(N) | exists x in N: f(x) = A }
Let K(f) =
{ x in N | x is not in f(x) }
Let M(f) =
{ A in P(N) | A is in image(f) or A = K(f) }
Finally, let g be defined by
g(0) = K(f)
g(x+1) = f(x)
Okay, so we have the following facts:
1. f is not a surjection from N to M(f)
2. f is not a surjection from N to P(N)
3. g is a surjection from N to M(f).
4. g is not a surjection from N to M(g).
5. g is not a surjection from N to P(N).
So, M(f) is countable, since there is a surjection g from
N to M(f). But there is no surjection from N to P(N). So
P(N) is *not* countable.
--
Daryl McCullough
Ithaca, NY
Rupert
No, that's absolute nonsense.
> Regards, WM
muec...@rz.fh-augsburg.de
Jens Kruse Andersen schrieb:
> By definition, an infinite set M is uncountable if and only if:
> There is no bijective mapping f from N to M.
Correct. What do you think, why this is so? My point is only to show
that the impossibility of a mapping involving Hessenberg's trick does
not prove anything about cardinalities of sets involved. It shows that
the sets |N and P(|N) do not exist.
>
> 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.
Oh, I see. Let's apply this new insight:
2) 0.12324389
3) 0.23123123
4) 0.85348714
5) 0.11133333
6) 0.31415161
..
1) 0.24446...
So this is the proof, that the proof that a surjective mapping f: |N
--> [0,1] does not exist, does not exist, isn't it?
>
> In the well-known proof that P(N) is uncountable, P(N) is a fixed given set
> before any function is even mentioned.
That is the question.
> The proof then shows that no matter
> which function f is chosen, f will not be a bijection from N to P(N).
And my proof shows that no matter what function f is chosen, there will
not be a bijection from N to M. You will have obtained from my sketch
of Cantor's diagonal proof above that it is *not* allowed to switch the
mapping after the set has been fixed.
Regards, WM
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> >
> > 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).
Like this one?:
2) 0.12324389
3) 0.23123123
4) 0.85348714
5) 0.11133333
6) 0.31415161
..
1) 0.24446...
This is the proof, that the proof that a surjective mapping f: |N -->
[0,1] does not exist, does not exist, isn't it?
Regards, WM
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> In article <1150875562.7...@g10g2000cwb.googlegroups.com> muec...@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.
but it is not possible to determine that K(f).
> > > 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,
But P(N) \ K(f) does. Map f : N --> P(N) \ K(f), and your proof
vanishes.
> > > so there is
> > > no mapping between N and P(N) that is a bijection.
Or there is no complete set |N and hence no complete set P(|N).
> >
> > Who told you?
>
> The proof above.
It does not disprove a surjection but the completeness of |N and P(|N).
Why do you think that non-dependence on f is a special feature? The set
K does exist for every mapping f. But for every mapping f there is no k
to be mapped on K.
The set K does not an cannot exist if f is required to be a surjection.
Why do you think, this can and must happen for a countable image set M
= S(|N) U {K(f)} ? Why do you think the reason is different from that
of P(|N) ?
>
> > 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.
The same is true for any M = S(|N) U {K(f)} defined by a *surjective*
mapping f. The set K then does not an cannot exist. Hence, there is no
helping g.
Regards, WM
Virgil
muec...@rz.fh-augsburg.de wrote:
> Jens Kruse Andersen schrieb:
>
> > By definition, an infinite set M is uncountable if and only if:
> > There is no bijective mapping f from N to M.
>
> Correct. What do you think, why this is so? My point is only to show
> that the impossibility of a mapping involving Hessenberg's trick does
> not prove anything about cardinalities of sets involved. It shows that
> the sets |N and P(|N) do not exist.
No more than it proves Muecken does not exist.
>
> >
> > 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.
>
> > In the well-known proof that P(N) is uncountable, P(N) is a fixed given set
> > before any function is even mentioned.
>
> That is the question.
>
> > The proof then shows that no matter
> > which function f is chosen, f will not be a bijection from N to P(N).
>
> And my proof shows that no matter what function f is chosen, there will
> not be a bijection from N to M. You will have obtained from my sketch
> of Cantor's diagonal proof above that it is *not* allowed to switch the
> mapping after the set has been fixed.
Actually in Cantor's proof, one is allowed to construct as many
functions as one likes between the fixed set N and the fixed set P(N),
as the general anti-diagonal rule works equally well on any of them.
Muecken insists on a function and codomain which can only exist if the
function is not a bijection, but which, in that case allow a diferent
fuction which is a bijection.
So that either neither of Muecken's f and M t exist at all and the issue
of bijection of N with a non-existent set is irrelevant.
Or if f and M do exist, it is because f is not required to be a
surjection, in particular K = {x in N: x not in f(x)} is not a value of
f, and then f, K and M all exist, and there are plenty of bijections
from N to M.
>
> Regards, WM
Virgil
Virgil
muec...@rz.fh-augsburg.de wrote:
The mapping f cannot exist if one requires, as Muecken does, that there
be some n for which f(n) = {x: x not in f(x)}.
That condition makes f an impossibility.
> > > Map f : N --> P(N) \ K(f). That has not been proven
> > > impossible.
Yes it has. Since there are bijections h: P(N) \ K(f) --> P(n),
any bijection f:N --> P(N) \ K(f) implies a bijection hof: N --> P(N)
Which cannot occur since function hof cannot map onto K(hof).
Dik T. Winter
This is plain nonsense.
Dik T. Winter
>
> Dik T. Winter schrieb:
>
> > In article <1150875562.7...@g10g2000cwb.googlegroups.com> muec...@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.
>
> but it is not possible to determine that K(f).
Why not?
> > > > 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,
>
> But P(N) \ K(f) does. Map f : N --> P(N) \ K(f), and your proof
> vanishes.
As I have shown already in a much earlier thread, the answer is *no*.
> > > > so there is
> > > > no mapping between N and P(N) that is a bijection.
>
> Or there is no complete set |N and hence no complete set P(|N).
That is altogether another theory. When you talk about current theory
there is a complete set N and a complete set P(N). You may of course
start your own version of set theory where that is not the case.
> > > Who told you?
> >
> > The proof above.
>
> It does not disprove a surjection but the completeness of |N and P(|N).
You are completely wrong. How does it prove that?
> Why do you think that non-dependence on f is a special feature? The set
> K does exist for every mapping f. But for every mapping f there is no k
> to be mapped on K.
>
> The set K does not an cannot exist if f is required to be a surjection.
> Why do you think, this can and must happen for a countable image set M
> = S(|N) U {K(f)} ? Why do you think the reason is different from that
> of P(|N) ?
Let's see. Let S be the set of finite subsets of N. And let us have
a bijection f: N -> S (they do exist). Now obviously f is not a
bijection from N to M(f), that is clear by the construction. On the
other hand, we can construct a bijection from N to M(f), as before:
g(0) = K(f)
g(i) = f(i - 1) when i > 0,
given that f is a bijection between N and S, it is easy to see that
g is a bijection between N and M(f).
Ah, I hear you mutter. But g is not a bijection between N and M(g).
No, of course not. g is not even a mapping from N to M(g).
> > > 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.
>
> The same is true for any M = S(|N) U {K(f)} defined by a *surjective*
> mapping f. The set K then does not an cannot exist. Hence, there is no
> helping g.
Note again: M depends on f, a fact that you leave out every time. M in
itself is not a set, but for every given f, M(f) is a set.
muec...@rz.fh-augsburg.de
Virgil schrieb:
> So the resolution is that either f, K_f and M_f are self-contradictory
> and do not exist at all
if f is defined to be a surjection. That is right. And why do you
believe that a self contradictory approach should prove anything (for
instance about the surjectivity of certain mappings)?
Regards, WM
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> In article <1150957437.4...@g10g2000cwb.googlegroups.com> muec...@rz.fh-augsburg.de writes:
> >
> > Dik T. Winter schrieb:
> >
> > > >
> > > > 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).
> >
> > Like this one?:
> >
> > 2) 0.12324389
> > 3) 0.23123123
> > 4) 0.85348714
> > 5) 0.11133333
> > 6) 0.31415161
> > ..
> >
> > 1) 0.24446...
> >
> > This is the proof, that the proof that a surjective mapping f: |N -->
> > [0,1] does not exist, does not exist, isn't it?
>
> This is plain nonsense.
Maybe. It is, however, the same approach as yours. If it is impossible
to find a direct surjective mapping, then first define the set and then
try to find a surjection. I can proudly declare in your words:
A *surjective* mapping does exist, but it is not f. There exists a
surjective mapping g -> M(f).
Regards, WM
muec...@rz.fh-augsburg.de
Dik T. Winter schrieb:
> > > > > 1. Given a mapping f: N -> P(N), the set K(f) constructed according to
> > > > > Hessenberg *does* exist.
> >
> > but it is not possible to determine that K(f).
>
> Why not?
Because, in case f should be surjective, a number k need be contained
in a set in which it must not be contained.
> > >
> > > The proof above.
> >
> > It does not disprove a surjection but the completeness of |N and P(|N).
>
> You are completely wrong. How does it prove that?
Because it is the only explanation of this and other paradoxes. At
least you cannot deny that it would resolve he problem.
Here is another one: Let {q_1, q_2, q_3, ...} the well-ordered set of
all rational numbers.
If you say that it exists, then I can prove that it can be ordered by
magnitude without destroying the well-order. Obviously that is
impossible. Hence {q_1, q_2, q_3, ...} does not exist.
> Let's see. Let S be the set of finite subsets of N. And let us have
> a bijection f: N -> S (they do exist). Now obviously f is not a
> bijection from N to M(f), that is clear by the construction.
Hence by constuction, the set M(f) does not exist, if f is required to
be surjective.
> Note again: M depends on f, a fact that you leave out every time. M in
> itself is not a set, but for every given f, M(f) is a set.
And for every given f, this set is not in bijection with |N.
Regards, WM
muec...@rz.fh-augsburg.de
Virgil schrieb:
> No more than it proves Muecken does not exist.
Please note: My name is Mueckenheim or short WM. It is fairly long,
but so much time must be for polite people. And I am not going to talk
to impolite people.
Regards, WM
Daryl McCullough
>Dik T. Winter schrieb:
>
>
>> > > > > 1. Given a mapping f: N -> P(N), the set K(f) constructed
according to Hessenberg *does* exist.
>> >
>> > but it is not possible to determine that K(f).
>>
>> Why not?
>
>Because, in case f should be surjective, a number k need be contained
>in a set in which it must not be contained.
That case is impossible. To prove a case impossible, you only
need to show that it leads to a logical contradiction.
>Here is another one: Let {q_1, q_2, q_3, ...} the well-ordered set of
>all rational numbers.
>If you say that it exists, then I can prove that it can be ordered by
>magnitude without destroying the well-order.
On the contrary, you cannot prove that. Here's a specific well-ordering:
Let r1 and r2 be two rational numbers. Then to figure out whether
r1 comes before r2 in the well-ordering:
Write r1 in the form p1/q1
where p1 and q1 are integers and q1 > 0 and there are no common
factors between p1 and q1. Similarly, write r2 in the form p2/q2.
1. If |p1| + q1 < |p2| + q2, then r1 comes before r2.
2. If |p1| + q1 > |p2| + q2, then r1 comes after r2.
3. If |p1| + q1 = |p2| + q2, and p1 < p2, then r1 comes before r2.
4. If |p1| + q1 = |p2| + q2, and p1 > p2, then r1 comes after r2.
This well-ordering gives the following first few terms of the sequence:
0/1,
-1/1, +1/1,
-2/1, -1/2, +1/2, +2/1
-3/1, -1/3, +1/3, +3/1
-4/1, -3/2, -2/3, -1/4, +2/3, +3/2, +4/1
-5/1, -1/5, +1/5, +5/1
etc.
(The first row has |p| + q = 1, the next row has |p| + q = 2, etc.)
But notice that this is not ordered by magnitude, since 1/2 < 1/1, but
1/1 comes before 1/2 in the ordering.
The ordering by magnitude in not a well-ordering.
Obviously that is
>impossible. Hence {q_1, q_2, q_3, ...} does not exist.
>
>> Let's see. Let S be the set of finite subsets of N. And let us have
>> a bijection f: N -> S (they do exist). Now obviously f is not a
>> bijection from N to M(f), that is clear by the construction.
>
>Hence by constuction, the set M(f) does not exist
No, that doesn't follow. What follows is that M(f) is *not* a subset
of S. Since S contains all finite subsets of N, it follows that M(f)
contains some element that is *not* a finite subset of N.
Daryl McCullough
muec...@rz.fh-augsburg.de says...
If an assumption leads to a contradiction, then that assumption must
be false. The assumption that there is a surjection from N to P(N) leads
to a contradiction. Therefore, it is false that there is a surjection
from N to P(N). Therefore, P(N) is uncountable.
Daryl McCullough
>Maybe. It is, however, the same approach as yours. If it is impossible
>to find a direct surjective mapping, then first define the set and then
>try to find a surjection. I can proudly declare in your words:
>
> A *surjective* mapping does exist, but it is not f. There exists a
>surjective mapping g -> M(f).
And those words are perfectly correct: f is not a surjective mapping
from N to M(f), but g *is* a surjective mapping from N to M(f). So
M(f) is countable.
In contrast, there is no surjection from N to P(N). So P(N) is *not*
countable.
--
Daryl McCullough
Ithaca, NY
Jens Kruse Andersen
> Jens Kruse Andersen schrieb:
>
> > By definition, an infinite set M is uncountable if and only if:
> > There is no bijective mapping f from N to M.
> >
> > exists for that M, with no other condition on f than it has to be
> > bijective.
>
> Oh, I see. Let's apply this new insight:
>
> 2) 0.12324389
> 3) 0.23123123
> 4) 0.85348714
> 5) 0.11133333
> 6) 0.31415161
> ..
>
> 1) 0.24446...
>
> So this is the proof, that the proof that a surjective mapping f: |N
> --> [0,1] does not exist, does not exist, isn't it?
As others have said: Nonsense. A small list of numbers with no definitions,
assumptioms, explanations or anything else is, well, a small list of numbers.
Your final claim is hard to parse but if you think your small list of numbers
with no comments proves that Cantor's diagonal proof is wrong, then: Nonsense.
After seeing your replies here and elsewhere, I have decided to not spend more
time on this discussion.
Others have already said several times what I would say but you appear to
ignore it. I suggest rereading the replies carefully.
> Please note: My name is Mueckenheim or short WM.
If you want to be referred to by some name then use it as poster name instead
of your e-mail address.
Many people reply with a program which automatically inserts your poster name.
--
Jens Kruse Andersen
muec...@rz.fh-augsburg.de
Jens Kruse Andersen schrieb:
> mueckenh wrote:
> > Jens Kruse Andersen schrieb:
> >
> > > 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.
> >
> > Oh, I see. Let's apply this new insight:
> >
> > 2) 0.12324389
> > 3) 0.23123123
> > 4) 0.85348714
> > 5) 0.11133333
> > 6) 0.31415161
> > ..
> >
> > 1) 0.24446...
> >
> > So this is the proof, that the proof that a surjective mapping f: |N
> > --> [0,1] does not exist, does not exist, isn't it?
>
> As others have said: Nonsense. A small list of numbers with no definitions,
> assumptioms, explanations or anything else is, well, a small list of numbers.
I think everyone her does know this list of numbers. It is not a small
list, but a countably infinte one. (One point was missing, it should
read "...".)
> Your final claim is hard to parse but if you think your small list of numbers
> with no comments proves that Cantor's diagonal proof is wrong, then: Nonsense.
Comment: The first mapping read f = 1), 2), 3), .... The second mapping
reads 2), 3), 4), ..., 1). Isn't that enough?
>
> After seeing your replies here and elsewhere, I have decided to not spend more
> time on this discussion.
> Others have already said several times what I would say but you appear to
> ignore it. I suggest rereading the replies carefully.
I have never stated the following problem. So you might be interested:
Cantor said: A well-ordered set remains well-ordered, if finitely many
or infinitely many transpositions are executed. Let's see what happens.
Let {q_1, q_2, q_3, ...} be the well-ordered set of all positive
rationals.
1) Consider for n e |N the rationals q_n and q_n+1. If q_n > q_n+1,
exchange q_n and q_n+1, otherwise let the succession unaltered. This
requires at most aleph_0 transpositions.
2) Consider for n e |N the rationals q_n+1 and q_n+2. If q_n+1 > q_n+2,
exchange q_n+1 and q_n+2, otherwise let the succession unaltered. This
requires at most aleph_0 transpositions.
3) Consider for n e |N the rationals q_n and q_n+1. If q_n > q_n+1,
exchange q_n and q_n+1, otherwise let the succession unaltered. This
requires at most aleph_0 transpositions.
4) Consider for n e |N the rationals q_n+1 and q_n+2. If q_n+1 > q_n+2,
exchange q_n+1 and q_n+2, otherwise let the succession unaltered. This
requires at most aleph_0 transpositions.
Of course, this all is defined in zero time, like the definition of
Cantor's diagonal.
After aleph_0 * aleph_0 = aleph_0 transpositions, the set {q_k_1,
q_k_2, q_k_3, ...} of all positive rationals is well-ordered and
simultaneously ordered by magnitude, starting with the smallest
positive rational and ending with the largest.
This can happen, if the well ordered set of all positive rational does
exist. But we know, it cannot happen. Hence, the well ordered set of
all positive rational does not exist.
Regards, WM
muec...@rz.fh-augsburg.de
Daryl McCullough schrieb:
>
> That case is impossible. To prove a case impossible, you only
> need to show that it leads to a logical contradiction.
>
1) Consider a bjective mapping from the set {a, 1} --> P({1}) = {{},
{1}}, where a is *not a natural number*. This mapping is arbitrary but
has to satisfy only one condition, namely that the set K = {k e |N & k
/e f(k)} is in the image. This mapping is impossible. (See my article
"On Cantor's Theorem", arXiv, math.GM/0505648, 30 May 2005.)
2) Consider a mapping |N --> P(|N) which need not be surjective but has
to satisfy only one condition, namely that the set K = {k e |N & k /e
f(k)} is in the image. This mapping is impossible.
In both cases there is this impredicable request {f, k, K} which is
impossible to satisfy. But in the proof by Hessenberg, you insist, it
would prove non-surjectivity?
In a bijective mapping |N --> P(|N) there is every element of |N and
every subset of |N. But no set is defined as K above, because this
very *definition* leads to an impossible result as can be seen by the
examples above.
> This well-ordering gives the following first few terms of the sequence:
It will be enough to use the positive rationals only.
>
> 0/1,
> -1/1, +1/1,
> -2/1, -1/2, +1/2, +2/1
> -3/1, -1/3, +1/3, +3/1
> -4/1, -3/2, -2/3, -1/4, +2/3, +3/2, +4/1
> -5/1, -1/5, +1/5, +5/1
> etc.
>
> (The first row has |p| + q = 1, the next row has |p| + q = 2, etc.)
>
> But notice that this is not ordered by magnitude, since 1/2 < 1/1, but
> 1/1 comes before 1/2 in the ordering.
>
> The ordering by magnitude in not a well-ordering.
>
Here is how we obtain it:
muec...@rz.fh-augsburg.de
Daryl McCullough schrieb:
Consider a mapping |N --> P(|N) which need not be surjective but has to
satisfy only one condition, namely that the set K = {k e |N & k /e
f(k)} is in the image. This mapping is impossible.
{f, k, K} is impossible to satisfy. But in the proof by Hessenberg,
you insist, it would prove non-surjectivity?
In a bijective mapping |N --> P(|N) there is every element of |N and
every subset of |N. But no set is defined as K above, because this very
*definition* leads to an impossible result as can be seen by the
examples above.
Regards, WM
muec...@rz.fh-augsburg.de
Daryl McCullough schrieb:
This is proven by three invalid proofs. Do you know Canto's first proof
of 1874? Probably not, so we need not discuss it. You certainly know
his second one. It is wrong, because all it shows is the construction
of a number of a set of countably many constructible numbers. It is
ridiculous to believe this to be a proof of uncountability. There are
simply not more than countably many constructible and individualizable
real numbers, because there are not more than countably many different
symbols or names in any language. And I pointed out already that your
arguing invalidates this proof completely:
> 2) 0.12324389
> 3) 0.23123123
> 4) 0.85348714
> ...
> 1) 0.244...
(I hope, you understand, what I mean.)
The third proof is that by Hessenberg, which utiizes an impredicable
definition. This set K does *exist*, if every subset of |N does exist,
but it cannot be *defined* as it is done. But I discussed that with you
in a previous posting.
Uncountably many sets, however, cannot be distinguished, because of
laking names.
Regards, WM
Virgil
muec...@rz.fh-augsburg.de wrote:
I believe that what does not exist cannot be used as an example of
something that does exist.
If one requires that f(n) = K(f) = {x : x not in f(x)} then
f:N --> M(f) does not even exist nor does K(f) or M(f).
if one does not require that f(n) = K(f) = {x : x not in f(x)} then
f:N --> M(f) exists, but is not a bijection.
However in that case, N and M are easily bijected, so that M is countable
Virgil
muec...@rz.fh-augsburg.de wrote:
If the function f and the set M(f) exist it is because there is no n in
N for which f(n) = K(f), and in that case, there are bijections between
N and M(f), but f is not one of them.
Virgil
muec...@rz.fh-augsburg.de wrote:
> Here is another one: Let {q_1, q_2, q_3, ...} the well-ordered set of
> all rational numbers.
> If you say that it exists, then I can prove that it can be ordered by
> magnitude without destroying the well-order. Obviously that is
> impossible. Hence {q_1, q_2, q_3, ...} does not exist.
I doubt that Muecken prove much of anything even when the thing is
provable, but I challenge him to provide a valid proof, based only on
what is deriveable from ZFC or NBG, of his claim that given any well
ordering of the rationals, Muecken can prove that the standard ordering
is also a well ordering.
If HMuecken could do this, it would make as big a splash as the proof of
FLT.
Virgil
muec...@rz.fh-augsburg.de wrote:
If your address is muec...@rz.fh-augsburg.de, I reserve the reight to
address you as mueckenh.
Virgil
muec...@rz.fh-augsburg.de wrote:
Source???
> Let's see what happens.
>
> Let {q_1, q_2, q_3, ...} be the well-ordered set of all positive
> rationals.
> 1) Consider for n e |N the rationals q_n and q_n+1. If q_n > q_n+1,
> exchange q_n and q_n+1, otherwise let the succession unaltered. This
> requires at most aleph_0 transpositions.
> 2) Consider for n e |N the rationals q_n+1 and q_n+2. If q_n+1 > q_n+2,
> exchange q_n+1 and q_n+2, otherwise let the succession unaltered. This
> requires at most aleph_0 transpositions.
> 3) Consider for n e |N the rationals q_n and q_n+1. If q_n > q_n+1,
> exchange q_n and q_n+1, otherwise let the succession unaltered. This
> requires at most aleph_0 transpositions.
> 4) Consider for n e |N the rationals q_n+1 and q_n+2. If q_n+1 > q_n+2,
> exchange q_n+1 and q_n+2, otherwise let the succession unaltered. This
> requires at most aleph_0 transpositions.
If each of the above steps is alleged to preserve the well-ordering, no
sequence of such operations can make an ordering in which a non-empty
set fails to have a smallest member according to its current ordering.
But for every real number x, the set of rationals greater than x in the
standard rational ordering is a non-empty set with no smallest member.
Thus there are uncountably many proofs that the set of positive
rationals in its standard order is not well-ordered.
>
> Of course, this all is defined in zero time, like the definition of
> Cantor's diagonal.
> After aleph_0 * aleph_0 = aleph_0 transpositions, the set {q_k_1,
> q_k_2, q_k_3, ...} of all positive rationals is well-ordered and
> simultaneously ordered by magnitude
Claimed but not proven.
Virgil
muec...@rz.fh-augsburg.de wrote:
> Daryl McCullough schrieb:
>
> > muec...@rz.fh-augsburg.de says...
> >
> > >Maybe. It is, however, the same approach as yours. If it is impossible
> > >to find a direct surjective mapping, then first define the set and then
> > >try to find a surjection. I can proudly declare in your words:
> > >
> > > A *surjective* mapping does exist, but it is not f. There exists a
> > >surjective mapping g -> M(f).
> >
> > And those words are perfectly correct: f is not a surjective mapping
> > from N to M(f), but g *is* a surjective mapping from N to M(f). So
> > M(f) is countable.
> >
> > In contrast, there is no surjection from N to P(N). So P(N) is *not*
> > countable.
>
> This is proven by three invalid proofs. Do you know Canto's first proof
> of 1874? Probably not, so we need not discuss it.
If you are to claim that the first proof is an invalid proof you must
either back up that claim or allow your claim to be called false and
the first prof valid.
And is that "first proof" for the theorem that there is no surjection
from N to P(N) or for the theorem that there is no surjection from N to
R, the set of all reals?
They are not quite the same.
> You certainly know
> his second one. It is wrong, because all it shows is the construction
> of a number of a set of countably many constructible numbers.
A slight modification to the "diagoal" proof allows for any given list
of reals, the constriction of one "anti-diagonal" real not listed for
each real in the open interval (0,1) = {x in R: 0 < x < 1}.
> It is ridiculous to believe this to be a proof of uncountability.
It is even more ridiculous to believe otherwise. At least within ZFC or
NBG.
Dik T. Winter
> Dik T. Winter schrieb:
> > In article <1150957437.4...@g10g2000cwb.googlegroups.com> muec...@rz.fh-augsburg.de writes:
> > > Dik T. Winter schrieb:
> > > > >
> > > > > 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).
> > >
> > > Like this one?:
> > >
> > > 2) 0.12324389
> > > 3) 0.23123123
> > > 4) 0.85348714
> > > 5) 0.11133333
> > > 6) 0.31415161
> > > ..
> > >
> > > 1) 0.24446...
> > >
> > > This is the proof, that the proof that a surjective mapping f: |N -->
> > > [0,1] does not exist, does not exist, isn't it?
> >
> > This is plain nonsense.
>
> Maybe. It is, however, the same approach as yours. If it is impossible
> to find a direct surjective mapping, then first define the set and then
> try to find a surjection. I can proudly declare in your words:
You are wrong again. Given the set S of finite subsets of N you can find
a surjective mapping from N to S. Name that mapping f. Obviously that is
not a surjective mapping from N to M(f), and it never claimed to be. But
given M(f) we can find a surjective mapping from N to M(f) (as has been
shown). Name that mapping g. Obviously it is not a surjective mapping from
N to M(g), and never claimed such, it is not even a mapping from N to M(g).
So I wonder where your problem is.
> A *surjective* mapping does exist, but it is not f. There exists a
> surjective mapping g -> M(f).
Indeed. But your short list does not show anything at all, I wonder what
I have to do with it. I think you intend to show something about the
diagonal number of a list of reals. But we were talking about a mapping
from N to P(N). So please keep to the subject.
Dik T. Winter
> Dik T. Winter schrieb:
> > > > > > 1. Given a mapping f: N -> P(N), the set K(f) constructed according to
> > > > > > Hessenberg *does* exist.
> > >
> > > but it is not possible to determine that K(f).
> >
> > Why not?
>
> Because, in case f should be surjective, a number k need be contained
> in a set in which it must not be contained.
Yes, and that shows that whatever mapping f you give, it is simply not
surjective. Given any mapping f, the proof shows that it is not
surjective. Based on f you can determine K(f) and show that it is not
in the image. See what I wrote. I did *not* say "given a surjective
mapping f: N -> P(N)".
> > > > The proof above.
> > >
> > > It does not disprove a surjection but the completeness of |N and P(|N).
> >
> > You are completely wrong. How does it prove that?
>
> Because it is the only explanation of this and other paradoxes. At
> least you cannot deny that it would resolve he problem.
That is opinion, not proof. And I do not see any paradoxes. You simply
do not understand that *in an abstract sense* infinite sets do exist, and
are indeed guaranteed by the axioms. If you do not like that that is your
problem. You might try to set up mathematics without the axiom of infinity.
> Here is another one: Let {q_1, q_2, q_3, ...} the well-ordered set of
> all rational numbers.
> If you say that it exists, then I can prove that it can be ordered by
> magnitude without destroying the well-order. Obviously that is
> impossible. Hence {q_1, q_2, q_3, ...} does not exist.
An interesting assertion.
> > Let's see. Let S be the set of finite subsets of N. And let us have
> > a bijection f: N -> S (they do exist). Now obviously f is not a
> > bijection from N to M(f), that is clear by the construction.
>
> Hence by constuction, the set M(f) does not exist, if f is required to
> be surjective.
Can you read plain English? Of course you can not construct a surjection
to a set which you do not know when you start constructing. The condition
"if f is required to be surjective" makes no sense at all in this context.
The f I have *is* surjective, it is a surjective map from N to S, as I
wrote. And so the set M(f) does exist. And f is not surjective to M(f),
that is also clear. This does *not* mean that there is another map from
N to M(f) that is surjective.
> > Note again: M depends on f, a fact that you leave out every time. M in
> > itself is not a set, but for every given f, M(f) is a set.
>
> And for every given f, this set is not in bijection with |N.
It is not in bijection with N by the function f, this does not preclude
other mappings.
Daryl McCullough
>Daryl McCullough schrieb:
>> And those words are perfectly correct: f is not a surjective mapping
>> from N to M(f), but g *is* a surjective mapping from N to M(f). So
>> M(f) is countable.
>>
>> In contrast, there is no surjection from N to P(N). So P(N) is *not*
>> countable.
>
>This is proven by three invalid proofs.
We're only discussing one right now: If f is any function from
N to P(N), then let K(f) = { x in N | x is not in f(x) }. Then
1. K(f) is a subset of N.
2. K(f) is an element of P(N).
3. K(f) is not in the image of f.
4. Therefore, f is not a surjection.
That's all there is to it: If f is any function from N to P(N),
then f is not a surjection from N to P(N). That is logically
equivalent to "There is no surjection from N to P(N)", which
is by definition what "P(N) is uncountable" means.
>It is wrong, because all it shows is the construction
>of a number of a set of countably many constructible numbers.
What it shows is that the assumption that f is a surjection
from N to P(N) leads to a contradiction. If something leads
to a contradiction, then it is provably false. Therefore it
is provably false that there exists a function f that is
a surjection from N to P(N).