"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Tuesday, November 22, 2011

Constructing a set disjoint from, and equinumerous with any other set.

A while ago I needed (a lemma in a larger proof) to construct for any arbitrary set A, another set that is disjoint from A and of the same cardinality as A (without the use of higher machinery of ordinals). The task is harder than it may seem. One may choose to attempt a proof by contradiction. One of my friends has in fact proceeded that way. I came up with the following construction which I’m quite fond of.

First, let me state a theorem (which is a direct consequence of Russell’s paradox) that I helped myself to.

Theorem. For each set S, the set
Is not a member of S.
For if we assume otherwise, an immediate contradiction ensues, for
Now for the construction. Let’s take some set A, and construct a set B that is disjoint from it, and equinumerous with it. Consider the set
Theorem: For any set A the following set B is disjoint from A and equinumerous with it:
Less formally
It is clear that B has the same cardinality as A. (post-Clarification: just to be pedantic, it's not just the triple x, y, z that is in A, but rather I should have written "for x, y, z,... in A". I forgot the ellipsis.)

It is also clear that,
which is impossible by construction of RA . Hence B is equinumerous to, and disjoint from A. QED

1 comment:

Larry Daron said...

Hi, We have a new Calculus calculatorapplication.. And here you can see TI-83 and TI-84 application also..