[ 2 posts ] 
 Exercise [16.14] 
Author Message

Joined: 22 Apr 2010, 15:52
Posts: 43
Location: Olpe, Germany
Post Exercise [16.14]
My proposal:
Exercise_16_14.pdf [20.07 KiB]
Downloaded 162 times

28 Aug 2010, 10:00

Joined: 12 Jul 2010, 07:44
Posts: 154
Post Re: Exercise [16.14]
Your proposal might be stated even more simply:

A = "set of all sets"
B = 2^A = "set of all sets-of-sets"

Cantor: |B| > |A| (where |X| means "cardinality of set X")

However since B is composed of sets, it is clearly a subset of A: B is contained in A

Therefore |B| <= |A|

... contradiction with Cantor!


Interestingly, we can ask here, are A and B identical?
If there are set elements that are not themselves sets, then clearly they are not identical.
For example { {}, {3,4}, {{},{},{}} } contains elements that are themselves sets,
but { 1, 2, {3} } contains two elements that are just plain numbers.

...so *if* numbers aren't sets, { 1, 2, {3} } is not an element of B.

On the other hand, numbers, and all other mathematical objects can be defined in terms of sets;
for example on pages 64 and 365, the natural numbers are defined as the sets:

0 = {}, 1 = {0}, 2 = {0, {0} }, 3 = {0, {0}, {0, {0}}}, etc.

So, if everything in our "universe" is a set, then all set elements are sets;
every set is a "set of sets", and thus B is just the "set of all sets" - identical to A.

In that case, we necessarily have |A| = |B|, but also contradicting Cantor.


Alternatively, we could just note that there can be NO cardinality higher than the "set of all sets" A:

ANY set Z = {x, y, z, ...} has the same cardinality as Z' = {{x}, {y}, {z}, ... }, and Z' is a subset of A.

Hence A's cardinality is as high or higher that ANY set whatsoever.

...again contradicting Cantor: |B| > |A|


*** None of the above contradictions are the "Russell paradox", however, which is what the problem is asking for! ***

To recover the Russell paradox, you need to start with the Cantor proof that |A|<|2^A|, and proceed to the point where you construct

Q = {a: a not an element of S(a)}

for which we can prove that the statement "Q = S(a)" DOES NOT HOLD for any a in A, regardless of choice of S.

(In the book text, we first assumed S was a bijection from A to B and then derived a contradiction;
but in fact what the "diagonal argument" actually does is show that S cannot be a surjection, since Q isn't in it's range (or 'target', 'image').
See my answer to exercise [16.13] for more details).

So, there's NO surjection from A to B...
But B is contained in A ...?
It's reasonable to wonder, therefore: Surely the identity function on B, at least, must be a surjection!?

(A slight technical issue is that S maps A to B
As discussed above, if set elements don't necessarily have to be sets themselves, then A and B are not identical, as A then also contains all the sets with non-set elements.

In this case we can take S to be equal to the identity function only on a subset of A - specifically, on B.
We can then extend the domain of this identity function from S : B -> B onto the remainder of A in many different ways.

The easiest way is probably just to have the map "delete" the non-set elements, e.g.:

map {{x}, {y}, {z}} --> {{x}, {y}, {z}} ...identity mapping in this case, since all elements are sets

map {u, v, {w}, {z}} --> {{w}, {z}} ...removes non-sets "u" and "v" in the target

For our purpose below, setting S to be this particular "extended" identity function is just fine... although there are other similar extensions that would work just as well.)

So, if we choose S to be the (extended) identity function, the Cantor construction:

Q = {a: a not an element of S(a)}


Q = {a: a not an element of a}

(Note that any non-set elements of a play no role in the membership criterion for Q, which is why we can replace S(a) with a here even in the "exteneded identity" case.)

or in English:

Q = { "all sets that are not members of themselves" }

...which is of course the exact construction that leads to the Russell Paradox!

Since Q's elements are all sets themselves, Q is an element of B.
And S has been chosen to be the identity function on B, so trivially we would expect S(Q) = Q

But the Cantor proof refutes this "identity".

The only way this identity can fail to hold is if Q is contradictory by construction, and the Russell Paradox is simply a succinct statement of the inherent contradiction!


Note that the fact that Q, the "set of all sets that are not members of themselves" leads to a paradox, doesn't, in an of itself, tell us where the source of the trouble lies.

We might wonder, for example, if sets being members of themselves is somehow problematic?

However, looking closer at Russell's Paradox, to obtain the contradiction, we must show that Q is neither a member of itself, nor of its complement.

But the union of Q and it's complement is, once again, just the "set of all sets".

So it's safe to assume that this problematic idea of a "set of all sets" which causes contradictions with Cantor's theorems is also the culprit in the Russell Paradox case. (Or so I'd guess!)

07 May 2011, 21:01
   [ 2 posts ]