Courtesy Georg Cantor and Jayadev Misra

Courtesy-Georg Cantor and Jayadev Misra

The purpose of Cantor's "Diagonal verfahren" was to show that any set $S$ is strictly smaller than its powerset $\mathcal{P}S$ (i.e. the set of all subsets of $S$ ). Because of the 1-1 correspondence between the elements of $S$ and its singleton subsets, which are elements of $\mathcal{P}S$ , $S$ is not larger than $\mathcal{P}S$ , and our proof can now be focussed on "strictly", i.e. we have to show that there exists no 1-1 correspondence between $S$ and $\mathcal{P}S$ . We can confine ourselves to the case of non-empty $S$ .

This note is devoted to two calculational proofs designed by Jayadev Misra, each interesting for its own reason. We shall use lower case letters to denote elements of $S$ and functions with such values, and upper case letters for elements of $P S$ and functions with such values. Consequently we distinguish between two identity functions, viz. id and $I D$ . Functions $F, g$ are of the types

(0) $F : S \rightarrow {PS}\;$ and $g : {PS} \rightarrow S$

Misra's first proof. We assume $g$ to be a 1-1 function and derive a contradiction.

For function $g$ being 1-1 we use in this

(1) $\left\langle {\forall Y,Z : Y = Z \equiv g \cdot Y = g \cdot Z}\right\rangle$ , and in order to formulate the contradiction we define set $X$ by $\left\langle {\forall y : y \in X \equiv \left\langle {32} : y = g.2 : y \notin Z}\right\rangle }\right\rangle$

and now we calculate

$$ \begin{array}{l} g. X \in X \ \equiv {(\mathrm {2}) \mathrm {w i t h} y := g. X } \ \langle \exists Z: g. X = g. Z: g. X \notin Z \rangle \ \equiv {1) \mathrm {w i t h} Y, Z := X, Z } \ \langle \exists Z: X = Z: g \cdot X \notin Z \rangle \ \equiv {\mathrm {1 - p o i n t r u l e} } \ g \cdot X \notin X, \ \end{array} $$

which yields the contradiction promised. (End of Misra's first proof.)

The disappointing thing about the above pre- sentation is that the introduction of $X$ by (2) comes as a great, big rabbit. (Misra's second proof admits a heuristically nicer presentation.) It is an interesting proof because in more than one way it shows the power of well-designed calculations. Firstly I ask you to enivisage the complications if we hadn't had the equivalence at our disposal, and had to rewrite

it a la Gentzen as mutual implication. Secondly I would like to point out that we could have replaced the existential quantifier E in (2) by the universal quantifier $\forall$ , for the 1-point rule works equally well for both: for someone used to the manipulation of uninterpreted formulae, the change is irrelevant, for some-one who insists on an awareness of what the formulae he manipulates "mean", the change would result in a totally new proof.

Misra's second proof. We shall show the absence of a 1-1 correspondence between S and PS by showing the absence of a pair of functions $F, g$ - typed as in (o) and such that $F$ and $g$ are the inverses of each other, and we shall do so by showing ${F}_{g} \neq {ID}$ for any $F,g$ of such types.

We can calculate for any $F, g$ typed as in (0)

$$ F o g \neq I D $$

$\equiv \left{ \begin{array}{l} \text{ definition of (in) equality of functions.} \ \end{array}\right.$

$$ \langle \exists X: (F o g). X \neq I D. X \rangle $$

[\text{d} = \left{ {\text{ definition }}_{1}\right} \text{ of }\text{ and }\text{ of }\text{ ID}} ]

$$ \langle \exists X: F _ {g. X} \neq X \rangle $$

[\left{ \begin{array}{ll} \text{ Leibniz, see Note below } \ \end{array}\right} ]

$$ \langle \exists X: g. X \in F (g. X) \neq g. X \in X \rangle $$

<3X: gX∈F.(gX)≠gX∈X>

$\Leftrightarrow \;z = g \cdot x}$

(X: : (Vz: z∈F.2≠z∈X))

[\left{ \begin{array}{ll} \text{ with } & X \mathrel{\text{:=}} { z|z \notin F,z} \text{ as witness}} \end{array}\right. ]

true

Note The usual form of Leibniz's Principle - "sub

$$ x = y \Rightarrow f _ {x} = f _ {y}, $$

but its contra-positive

$$ f \cdot x \neq f \cdot y \Rightarrow x \neq y $$

• "different values implies different arguments".

should be known as well, as it is a standard

way of concluding difference. Applying for some $z\left( {z \in S}\right)$ to both sides the operator "zε"

should not come as a surprise because some

where in the argument we have to take into account that the elements of $P{S}^{ - }$ are the sum

sets of $S$ . That in this case we have chosen

either because in the terminology available, $g \cdot X$ is the only element of ${S}^{ - }$ we can iden

ti fy. It could very well be this step that is responsible for the "surprise value" of Cantor's argument. If we wish to view the expression $\left( {z \in A}\right)$ as result of a function application,

the usual way of doing so is as (EA).z, i.e. applying A's membership function to z, but here we do it as $\left( {z\epsilon }\right) .A$ ,i.e. applying Z’s "containership function" to $A$ ,and the membership function is (for good reasons) much better known than the containership function. (End of Note.)

One can try to prove $g \circ F \neq i$ instead, but than one gets stuck.

Austin, 17 October 1999

prof. dr Edsger W.Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 USA