Diagonal Arguments, and Paradoxes

"One of themselves, even a prophet of their own, said, the Cretians are always liars, evil beasts, slow bellies. This testimony is true."

Titus 1:12-14 (King James Version)

Definition:

A paradox is a statement or group of statements that lead to a logical self-contradiction. For example,

( $\QTR{Large}{A}$ ) The next bulleted statement is a lie.
( $\QTR{Large}{B}$ ) The previous bulleted statement is true.

Analysis:

__________________________________________________________________________________________________

Proposition:

There is a barber who lives on an island. The barber shaves all those men who live on the island who do not shave themselves, and only those men.

Question:

Does the barber shave himself?

Answer:

If the barber shaves himself then he is a man on the island who shaves himself hence he, the barber, does not shave himself. If the barber does not shave himself then he is a man on the island who does not shave himself hence he, the barber, shaves him(self).

Analysis:

This is not actually a paradox.

Consider the proposition Shave(x,y) which is true if x shaves y and false if x does not shave y. We can restate the proposition as:

$\QTR{bs}{\exists }$ x $\QTR{bs}{\forall }$ y (Shave(x,y) Shave(y,y))

There exists an x such that for every y, x shaves y iff y does not shave y.

Suppose this proposition were true. Let b be the x whose existance is hypothesized. thus

y (Shave(b,y) Shave(y,y))

Since this holds for all y it holds for y $\QTR{Large}{=}$ b. So

Shave(b,b) Shave(b,b)

Hence one may hypothesize that the proposition is false. It is worth checking that this hypothesis does not also lead to a contradiction.

Suppose

( $\QTR{bs}{\exists }$ x $\QTR{bs}{\forall }$ y (Shave(x,y) Shave(y,y)))

$\QTR{bs}{\forall }$ x(( $\QTR{bs}{\forall }$ y (Shave(x,y) Shave(y,y)))

$\QTR{bs}{\forall }$ x $\QTR{bs}{\exists }$ y (Shave(x,y) Shave(y,y))

Which is no problem since if for any x if we chose y $\QTR{Large}{=}$ x it is certainly the case that

(Shave(x,x) Shave(x,x))

For any meaning of Shave(x,x).

__________________________________________________________________________________________________________

Theorem:

Given any set $\QTR{Large}{S}$ ,there is no onto map .

Proof A:(A diagonal argument)

Let . Since $\QTR{Large}{f}$ is onto there is some with .

As usual, by definition if then and if then .

Proof B:( yet another diagonal argument. This is just a disguised version of A.)

Let $\QTR{Large}{B=\{}$ 0,1 $\QTR{Large}{\}}$ . Let be the set of all maps from $\QTR{Large}{S}$ to $\QTR{Large}{B.}$ . There is an obvious 1 to 1 onto map Specifically,

1 $\QTR{Large}{\}}$ . Hence we need to show that for any set $\QTR{Large}{S}$ ,there is no onto map .

Suppose there was such a map. Define by the formula

$\vspace{1pt}$ The rest of the proof is standard. Suppose there was some such that Compute

On the other hand, by definition

Proof C:( A fixed point theorem version of the same thing )

We first prove the following lemma, which is really a generalization of B.

Lemma : For sets $\QTR{Large}{S}$ and $\QTR{Large}{T}$ , suppose there exists an onto map , then every self-map has a fixed point.

Proof:

Consider the "evaluation" map defined by the formula

Like in B, above define by the formula

Again, since $\QTR{Large}{f}$ is onto there is some such that

We have

on the other hand, by definition,

Thus is a fixed point for $\QTR{Large}{h.}$

Now, to complete the proof of 9.4, Let 0,1 $\QTR{Large}{\}}$ and note that $\QTR{Large}{B}$ has a fixed point free self-map. In particular, let be define by the formula

$\QTR{Large}{h(}$ 0 $\QTR{Large}{)=}$ 1 and $\QTR{Large}{h(}$ 1 $\QTR{Large}{)=}$ 0 .