Herc and Russell's Paradox
Balthasar
"I'm not sure why you can't see this is Russel's Paradox."
First, it's called /Russell's/ paradox.
Second, mainly -I guess- because it isn't Russell's paradox.
B.
--
"For every line of Cantor's list it is true that this line does not
contain the diagonal number. Nevertheless the diagonal number may
be in the infinite list." (WM, sci.logic)
|-|erc
> Herc wrote:
>
> "I'm not sure why you can't see this is Russel's Paradox."
>
> First, it's called /Russell's/ paradox.
>
> Second, mainly -I guess- because it isn't Russell's paradox.
>
You prove the set of all subsets that don't contain their own index (don't contain themselves)
to be missing (from the set of all subsets).
sounds like Russell's to me.
Herc
Balthasar
"Russel's Paradox is: [Consider] the set of all sets that don't contain
themselves. if it is a member of itself, then it should not be a member
of itself, and vice versa.
You get the SAME PARADOX when you index subsets."
Ah really? Let's see.
"f(a) = {a,b} call this the ath subset then say 'a' contains itself."
I guess you meant to say: "then the a-th subset contains a." That's
right. Note: there's no set involved (potentially) containing itself
here.
Consider the following sequence of subsets of the set of natural
numbers:
{1}, {1, 2}, {1, 2, 3}, ...
Then the first element in this sequence is {1}, the second, {1, 2}, and
so on. Then we can index this sequence, let's call it S, with natural
numbers:
S_1 = S(1) = {1},
S_2 = S(2) = {1, 2}
S_3 = S(3) = {1, 2, 3}
:
Has nothing to do with Russell's paradox whatsoever. And right: we can
call S(i) the i-th element (subset of the natural numbers) in this
sequence. But certainly that does not mean that "i contains itself", nor
that S(i) contains itself.
"the paradox becomes:
which subset contains the indexes of the subsets [that are indexed]
that don't contain their own index"
Note that it doesn't make sense to talk of the /index of a
subset/ if it doesn't have one.
For the sake of the argumenet I'll asume that f -the
indexing function- is injective.
This is not a paradox, but a question. And the answer is: the set T,
defined with
T = {s e S : s !e f(s)}.
T c S is the set which contain all the indexes of the sets _that are
indexed_ and do not contain "their own" indexes, right.
But it might be clearer to state:
"T contains an index s iff it is not contained (as an element)
in the set indexed by s."
And where exactly do you see a PROBLEM here? I showed you a simple
example:
------------------------------------------
Let S = {a, b, c}. Then P(S) = {0, {a}, {b}, {c}, {a, b}, {a, c}, {b,
c}, {a, b, c}}. And let's consider an arbitrary function f: S --> P(S).
Say, f(a) = {a, b}, f(b) = {c}, f(c) = 0.
Now let's consider the set T = {s in S : s not in f(s)} in this case.
For s = a, s e f(s), since a e {a, b}. For s = b, s !e f(s), since b !e
{c}, and for s = c, s !e f(s), since 0 does not contain any element.
Hence a !e T, b e T and c e T. With other words, T = {b, c}.
And we see: T =/= f(a), T =/= f(b), T =/= f(c). With other words, T is
not an element of the image of f, though T e P(S). Hence f is not
surjective. qed.
------------------------------------------
What exactly do you not understand here?
>
> T = {s in S : s not in f(s)}
> this becomes
> T = {s in N : s not in P(N)_s}
> which becomes
> T = {s in N : s not in the sth subset of P(N)}
> which is:
> the subsets that don't contain their own index
>
> this logic is exactly the reasoning that determines Russel's
> set doesn't exist.
>
Right. There's a similarity in the FORM of the argument. (I already
wrote in this thread that Russell got the idea for his paradox from an
analyses of Cantor's proof.) BUT in contrast to Russell's paradox here's
nothing "paradoxical". :-) T is just a subset as any other. No
SELF-REFERENCE, or CIRCULARITY, or whatever is involved here.
Mr. Nobrain, we consider a set T consisting exactly of those elements s
which are in S and are not in f(s):
s e T <-> s e S & s !e f(s).
The existence of such a set is guaranteed in ZFC be the axiom schema of
specification. (And if you consider the simple example given above you
would see that there's nothing problematic with this set T, IF you had a
brain.)
MoeBlee
> You prove the set of all subsets that don't contain their own index
No, the antidiagonal in Cantor's argument is the set of all indexes
that are not a member of what they index.
> (don't contain themselves)
No, there's NOTHING about anything containing ITSELF.
> to be missing (from the set of all subsets).
No, the antidiagonal is missing from the range of the indexing
function, not missing from the set of all subsets of the index set.
> sounds like Russell's to me.
Because you are completely confused as to what Cantor's argument
actually is.
MoeBlee
Balthasar
>>
>> T = {s in S : s not in f(s)}
>> this becomes
>> T = {s in N : s not in P(N)_s}
>> which becomes
>> T = {s in N : s not in the sth subset of P(N)}
>> which is:
>> the subsets that don't contain their own index
>>
>> this logic is exactly the reasoning that determines Russel's
>> set doesn't exist.
>>
> Right. There's a similarity in the FORM of the argument. (I already
> wrote in this thread that Russell got the idea for his paradox from an
> analyses of Cantor's proof.) BUT in contrast to Russell's paradox here's
> nothing "paradoxical". :-) T is just a subset as any other. No
> SELF-REFERENCE, or CIRCULARITY, or whatever is involved here.
>
In fact, there's a variant of the Russell's "Barber paradox" which quite
closely mirrors the form of the argument (involved here):
"Barber pseudoparadox. The council of a certain village is said to have
given orders that the village's barber (supposedly unique and a man) was
to shave all the men in the village who did not shave themselves, and
only those men. Who shaved the barber?"
Well there's a simple solution: the barber does not live in the village;
and hence he might or might not shave himself.
Concerning the set T, we have: T is not indexed.
And hence f is not surjective. qed.
|-|erc
>
> Because you are completely confused as to what Cantor's argument
> actually is.
Cantor's argument is exactly analagous to asking : which box contains the
numbers of all the boxes that don't contain their own number.
Herc
Balthasar
>>
>> T = {s in S : s not in f(s)}
>> this becomes
>> T = {s in N : s not in P(N)_s}
>> which becomes
>> T = {s in N : s not in the sth subset of P(N)}
>> which is:
>> the subsets that don't contain their own index
>>
>> this logic is exactly the reasoning that determines Russel's
>> set doesn't exist.
>>
> Right. There's a similarity in the FORM of the argument. [...]
>
Ooops... Overlooked an inaccuracy in one of your statements. But Moe
caught it:
---------------------------------------------------
> T = {s in N : s not in the sth subset of P(N)}
Maybe you mean:
T = {s in N | s not in the sth MEMBER of PN}.
---------------------------------------------------
Sorry for that.
Balthasar
wrote:
It seems to me that he stumbles over is hidden assumption that _all_
subsets are indexed. That's of course NOT the case, and that's exactly
what Cantor's argument shows. OF COURSE the argument is screwed up if
this hidden argument is mixed in somehow. (And of course in this case
Cantor's argument may indeed be "linked" somehow to Russell's paradox.)
--------------------------
That this hidden assumption cannot (i.e. does not) hold in general is
quite obvious, since it does not hold for any concrete (and hence
finite) case. Yes, obvious one might think... :-)
Consider S = {a, b, c}. Hence P(S) = {0, {a}, {b}, {c}, {a, b}, {a, c},
{b, c}, {a, b, c}}.
So PLEASE Herc, show us a surjection from S onto P(S). :-)
In general, for any finite S with |S| = n: |P(S)| = 2^n. Hence clearly
no surjection is possible for any finite set S. Since 2^n > n for any n
e N.
Cantor's Argument just shows that this even holds for infinite sets, if
we consider their cardinality. With other words:
|P(X)| > X
for any set X.
|-|erc
There is a bijection r:S-->P(S) and T = {s in S : s not in r(s)}
are mutually exclusive.
If you allow all subsets of N to be countable, then T = {s in S : s not in r(s)}
is an invalid construction.
Herc
Balthasar
"Cantor's argument is exactly analogous to asking : which box contains
the numbers of all the boxes that don't contain their own number."
Not quite, rather:
"Cantor's argument is exactly analogous to asking: which box contains
the numbers of all the [numbered] boxes that don't contain their own
number."
Right. (Assuming for the sake of the argument that our index-function f
is injective.) And the answer is: The set T is just such a "box" (by
definition):
T = {s e S : s !e f(s)}.
There's nothing paradoxical about this. But we GET FROM THIS that T
itself is not indexed.
Proof: Consider an arbitrary indexed sets. If its index is contained in
it, it is not contained in T (by definition of T). Hence T cannot be
identical with this indexed set. If on the other hand its index is not
contained in it, it is (by definition of T) contained in T, Hence again
T cannot be identical with this indexed set. So in any case T is not
identical with this indexed set. But since this indexed set was just an
arbitrary indexed set, we get: T is not identical with any indexed set.
With other words, T is not indexed. qed.
|-|erc
the set of indexes of subsets that don't contain their own index
will not appear within any finite set of subsets.
fine, it works for finite subsets and its a valid set, that's why you're all convinced,
but WHY does it work? it basically says "show me a new subset that hasn't been indexed".
this contradicts the notion that ALL subsets have been listed, its not properly worded.
UTM(a, b) = 1 IFF b is a member of the ath member of P(N)
This will enumerate all computable subsets of N.
The set of indexes of subsets that don't contain their own index
is not computable.
It doesn't exist because it is not a valid construction, its self-contradictory.
Herc
MoeBlee
> There is a bijection r:S-->P(S) and T = {s in S : s not in r(s)}
> are mutually exclusive.
EtAs(s in t <-> (s in S & s not in r(s)}
contradicts
Er r is a bijection between S and PS,
YES, that's what we get from the proof of Cantor's theorem.
> If you allow all subsets of N to be countable, then T = {s in S : s not in r(s)}
> is an invalid construction.
All subsets of N ARE countable. Maybe you mean, if we assume that
there are only countably many subsets of N, then the construction is
"invalid".
(1) Anyway, that's just question begging, since to assume that there
are only countably many subsets is simply to assume something that
contradicts Cantor's theorem. I mean, no one denies that if we assume
that there are only countably many subsets of N then Cantor's theorem
is contradicted.
(2) There is nothing in the proof of Cantor's theorem that assumes it
is NOT the case that there are only countably many subsets of N. There
is nothing in the construction that is "invalid".
The proof of Cantor's theorem requires only:
Intuitionistic logic and the axiom schema of separation, which is
provably a CONSISTENT combination, with even a finite model. There is
no "invalid" step in the argument.
If you dispute the proof then you dispute the combination of
intuitionistic logic with the axiom schema of separation. Well, the
axiom schema of separation is impredicative, so that would be a
reasonable objection. However, then I'd ask you what alternative
axioms you propose.
MoeBlee
Balthasar
"There is a bijection f: S-->P(S) and T = {s in S : s not in f(s)}
are mutually exclusive."
Well, this "statement" sound's rather queer. I guess what you mean is
the following:
"f: S --> P(S), f bijective"
and
"There exists a set T such that
for all s: s e T <-> s in S : s not in f(s)"
are mutually exclusive.
Right. That's indeed the case. This way we can PROVE in ZFC (the axioms
of which guarantee the existence of the said set T) that f: S --> P(S)
is not a bijection.
"If you allow all subsets of N to be countable, then T = {s in S : s
not in f(s)} is an invalid construction."
Huh? By which axiom? In which system? Note Mr. Nobrain, things don't
become "invalid" in math just because you don't like them (or their
consequences). :-)
You realize that set theory was set up do deal with _infinite_ sets? :-o
MoeBlee
> "Balthasar" <nomail@invalid> wrote
> It doesn't exist because it is not a valid construction, its self-contradictory.
No, you've not shown that. All you have shown is that you are confused
as to what the construction actually is. The axiom schema of
separation has a FINITE model (and separation is all that is needed,
along with intutionistic logic, for the proof.)
But, yes IF you add the premise that all subsets of N are computable,
then, since there are only countably many computable subsets of N, we
get a contradiction. So what? That doesn't show that there is anything
invalid with Cantor's argument. It just reminds us that the axioms of
Z set theory are not consistent with the premise that all subsets of N
are computable. Yes, we know that. We AGREE with that.
MoeBlee
Balthasar
>
> Balthasar wrote:
>>
>> Let S = {a, b, c}. Then P(S) = {0, {a}, {b}, {c}, {a, b}, {a, c}, {b,
>> c}, {a, b, c}}. And let's consider an arbitrary function f: S --> P(S).
>> Say, f(a) = {a, b}, f(b) = {c}, f(c) = 0.
>>
>> Now let's consider the set T = {s in S : s not in f(s)} in this case.
>> For s = a, s e f(s), since a e {a, b}. For s = b, s !e f(s), since b !e
>> {c}, and for s = c, s !e f(s), since 0 does not contain any element.
>> Hence a !e T, b e T and c e T. With other words, T = {b, c}.
>>
>> And we see: T =/= f(a), T =/= f(b), T =/= f(c). With other words, T is
>> not an element of the image of f, though T e P(S). Hence f is not
>> surjective. qed.
>>
>> ------------------------------------------
>>
>> What exactly do you not understand here?
>>
> the set of indexes of subsets that don't contain their own index
> will not appear within any finite set of subsets.
>
Huh? You still didn't get it. (Well, no brain.)
The set of indexes of indexed subsets that don't contain their own index
is T in the example described above. T obviously is a subset of S. Hence
it's an element in P(S). Maybe you wanted to say: "it will not appear
within any finite set of _indexed_ subsets" - meaning: it's not itself
an indexed subset. Right: It's not an indexed subset. (By construction,
one might say.)
>
> fine, it works for finite subsets and its a valid set,
>
Right.
Note though that set theory (say ZFC, NBG, MK, NF, ...) does not "know"
about finite or infinite sets concerning its axioms (i.e. it does not
make any difference between finite and/or infinite sets at that level).
This means: the axioms (and hence the proof) holds for ANY sets, finite
or infinite.
"that's why you're all convinced,"
Since we can prove it for finite cases using simple arithmetic, we are
convinced that it holds for all finite cases, right. But that does NOT
mean that it will still hold for infinite sets. That has to be _proved_
(in a framework which allows for infinite sets). And that has been done
by Cantor and others (in several different systems).
"but WHY does it work?"
That's a GOOD question. (Why, oh why are they so rare from your side?)
"it basically says 'show me a new subset that hasn't been indexed'."
Exactly. That's the basic idea. And it's indeed possible to "construct"
such a set for any "index-function" f from S in P(S). For any index set
f we can come up with a set T which has not been indexed by f.
"this contradicts the [claim] that ALL subsets have been listed,"
Right. This contradicts that claim. In fact, it SHOWs (at least in ZFC
and other set theories similar to ZFC) that it's not possible to list
(i.e. "count") all subsets of the natural numbers. Hence we call P(N)
uncountable, btw.
>
> its not properly worded.
>
What is not properly worded? :-o Man, you just have a twist in your
brain. :-)
>
> UTM(a, b) = 1 IFF b is a member of the ath member of P(N)
>
> This will enumerate all computable subsets of N.
>
Well, this may very well be the case. But since there are uncountable
many subsets of N you will miss uncountable many (i.e. a lot of) subsets
this way.
>
> The set of indexes of subsets that don't contain their own index
> is not computable.
>
This may very well be the case. So what? Due to Turing we know that
there are uncomputable numbers (at least in the context of ZFC), so
what? :-o
>
> It doesn't exist because it is not a valid construction,
>
In which system? What are the axioms (i.e. principles) and definitions
of this system. PLEASE be more specific.
Note that in ZFC (and all set theories similar to ZFC) these
constructions ARE allowed, of course. (See Moe's posts!)
>
> its self-contradictory.
>
No, certainly not. This claim is COMPLETELY unsupported by what you have
written so far. Actually, it CAN'T be "self-contradictory": Moe showed
you that there are provable consistent systems which allows for this
construction. Get a grip (or even better a brain) man.
|-|erc
On Aug 6, 6:28 pm, "|-|erc" <h...@r.c> wrote:
> "Balthasar" <nomail@invalid> wrote
>> It doesn't exist because it is not a valid construction, its self-contradictory.
>
>No, you've not shown that.
If you say a UTM computes all the subsets of N.
UTM(a,b) = 1 IFF b is a member of the ath subset
then, "where are the subsets that don't contain their own index"
is a loaded question.
Perhaps there is some theory in which this holds.
Herc
MoeBlee
> "MoeBlee" <jazzm...@hotmail.com> wrote ...
> On Aug 6, 6:28 pm, "|-|erc" <h...@r.c> wrote:
>
> > "Balthasar" <nomail@invalid> wrote
> >> It doesn't exist because it is not a valid construction, its self-contradictory.
>
> >No, you've not shown that.
>
> If you say a UTM computes all the subsets of N.
But I don't say that. You can say it if you like. But then I'd like to
know your axioms and rules of inference by which you derived it.
> UTM(a,b) = 1 IFF b is a member of the ath subset
In ordinary set theory and mathematics, the subsets of N are not
enumerable, so there are subsets that don't have an index a to be used
for UTM(a b).
If you have a DIFFERENT theory in which the subsets of N are
enumerable, then, of course, every subset is indexed by a member of N.
> then, "where are the subsets that don't contain their own index"
> is a loaded question.
I don't know what you mean in this instance by "a loaded question".
> Perhaps there is some theory in which this holds.
Where what holds? That the subsets are enumerable because the only
subsets are the computable ones? You can research constructivist
mathematics for that kind of thing.
MoeBlee
Balthasar
wrote:
>>
>> If you say a UTM computes all the subsets of N.
>>
> But I don't say that.
>
That's the "hidden assumption" I was referring to. Well at least it's
not hidden any more. :-)
But WE don't say that. It's Herc's assumption.