This document is repetitive in places. Editing is planned.
We look at some ways to formalize some of the popular “paradoxes”.
This introduces some formalization techniques
in a, hopefully, enjoyable, easily understandable setting.
Note: There are two interplays at work here:
The interplay between (informal language) and (mathematical formalisms),
and, within mathematics, the interplay (in fact a bijection) between
(predicates on a set $U$) and (subsets of that set $U$).
$\def\sigmarel{\mathrel\sigma}$
$\def\Irr{ \text{Irr} } \def\To{\Rightarrow} \def\rtimes{\mathop {\rightadj\times}} \def\rtop{{\rightadj\top}} \def\lbot{{\leftadj\bot}} \def\rlnot{{\rightadj\lnot}} \def\lDelta{{\leftadj\Delta}} \def\su{{\source u}} \def\tv{{\target v}}$
$\def\S{\mathrel S}$ $\Newextarrow{\xLongrightarrow}{3,2}{0x21D2}$
For the mathematics, let us start with some recollections.
Given any set $\boxed U$,
there is a "diagonal function" (an example of what can be called a "comultiplication") $\boxed{ \lDelta_U : U \mathrel{\leftadj\to} U \rtimes U : u \mapsto \langle u,u \rangle }$.
In cases where $U$ is evident, the subscript $U$ can be omitted.
Also the set $\boxed{ \bftwo = \{\lbot, \rtop\} }$ has a "negation" endofunction $\boxed{ \rlnot : 2 \mathrel{ \rightadj\to } 2 : \lbot \mapsto \rtop, \rtop \mapsto \lbot }$) which interchanges $\lbot,\rtop$.
The negation endofunction $\rlnot$ is of course a permutation on a finite set,
and may be written using cycle notation as a 2-cycle, the transposition $(\lbot,\rtop)$.
It will later be of significance that this endofunction does not have a fixed point, i.e., is what combinatorists call "a derangement".
Given $\lDelta$ and $\rlnot$, for any relation $\boxed{ R: U\times U \to \bftwo }$,
we can postcompose with $\rlnot$, precompose with $\lDelta$, or both:
\[ \boxed{ \begin{array} {ccccc|l|c|l} R & : & U\times U & \to & \bftwo & \text{basic relation} & \homst u R v & \text{$\su$ is $R$-related to $\tv$} \\ R\rlnot & : & U\times U & \to & \bftwo & \text{negated relation} & \rlnot {\homst u R v} & \text{$\su$ is not $R$-related to $\tv$} \\ \lDelta R & : & U & \to & \bftwo & \text{diagonal of the basic relation} & \hom u R u & \text{$u$ is $R$-related to itself} \\ \lDelta R \rlnot & : & U & \to & \bftwo & \text{diagonal of the negated relation} = {} & \rlnot {\hom u R u} & \text{$u$ is not $R$-related to itself} \\ &&&&& \text{negation of the basic diagonal} \\ \end{array} } \]
The first two rows represent <I>relations</I> on $U$;
the last two rows represent <I>predicates</I> on $U$.
It is the last row, (the negated diagonal) or (the diagonal of the negated relation),
that is essential to the "diagonal arguments" to be discussed.
For want of a better name, I call it the "Irreflexivity" predicate for $R$, $\boxed{ \Irr_R = \lDelta R \rlnot }$.
This last plays such a large role in the development
that it is useful to show in detail how it acts on elements $u\in U$:
\[ \boxed{ \begin{array} {} \boxed{\Irr_R} & : & U & \xrightarrow[\kern3em]{\textstyle \lDelta}& U \rtimes U & \xrightarrow[\kern3em]{\textstyle \boxed{R}} & \bftwo & \xrightarrow[\kern3em]{\textstyle \rlnot} & \bftwo \\ && u & \mapsto & \langle u,u \rangle & \mapsto & \hom u R u & \mapsto & \rlnot \hom u R u \\ \end{array} } \]
This pre- and post- composition business can most perspicuously be presented as a tetrahedron,
where the triple composite $\lDelta R \rlnot$, the Irreflexivity predicate, needs to be imagined as a long northeast diagonal arrow.
\[ \boxed{ \begin{array} {} && U \rtimes U \rlap{ \xrightarrow [\kern9em] {\textstyle R \rlnot} } &&&& \bftwo \\ & \llap{ \lDelta } \nearrow && \searrow \rlap{R} && \nearrow \rlap{\rlnot} \\ U \rlap{ \xrightarrow [\textstyle \lDelta R] {\kern12em} } &&&& \bftwo \\ \end{array} } \]
Note that the two relations are the two arrows whose source is $U \rtimes U$,
while the two predicates are the lower two of the three arrows whose source is $U$.
The basic issue, which is the heart of many of the so-called "paradoxes",
can now be presented very cleanly and simply, using the Irreflexivity predicate.
<b>Theorem (Irreflexivity predicates are never representable)</b>
Given (any binary relation $\boxed {R : U \times U \to 2}$ (2.)) on (any set $\boxed U$ (1.)).
(its Irreflexivity predicate $\boxed{\Irr_R}$ (3.))
cannot be (represented (6) by $R$).
In other words, ($R$-irreflexivity (3.)) is not ($R$-representable (6.)).
(The numbers in parentheses will be used below.
They not only give a time sequence for constructing the argument
but also link together the various ways of presenting the argument.)
There is a well-defined framework within which all these so-called "diagonal arguments" can be placed.
Placing those arguments in this framework helps distinguish "the forest from the trees".
Here we give it in a series of numbered steps.
They assume we are working in the category of sets, but they apply in other suitable categories.
1. Consider a set $\boxed U$, the "universe".
2. Consider a binary relation, $\boxed{ R : U \rtimes U \to (2 = \{\lbot,\rtop\}) : \langle u,v \rangle \mapsto \hom u R v}$ on $U$.
3. Using (the diagonal map $\lDelta : U \leftadj\to U \rtimes U : u \mapsto \langle u,u \rangle$) and (the negation map $\rlnot : 2 \rightadj\to 2 : \lbot \mapsto \rtop, \rtop \mapsto \lbot$),
define (the <b>irreflexivity predicate</b> $\boxed{ \Irr_R = \lDelta R \rlnot : U \to 2 : u \mapsto \rlnot \hom u R u }\;$) on $U$.
4. The question now is, "Can $\Irr_R$ be represented by an element of $U$?".
Suppose it can.
Let $\boxed{ b\in U }$ be the putative representing element.
5. Form the predicate $\boxed{ \hom b R - : U \to 2 }$ on $U$.
6. We now expand the representability assertion.
The assertion that ($b$ represents $\Irr_R$) is
the assertion that (there exists an equality $\boxed{ {(\hom b R - = \Irr_R)} : U \to 2 }$ in $\hom U \Set 2$ ), which is defined to mean
the statement in first order logic ( $(\forall u\in U)(\hom b R u \iff \Irr_R u)$ ), which by the definition of $\Irr$ is
( $(\forall u\in U)(\hom b R u \iff \rlnot \hom u R u )$ ).
7. Instantiate that universal quantification at $b\in U$, getting $\boxed{ \hom b R b \iff \rlnot \hom b R b }$, i.e., $\hom b R b \in 2$ is a fixed point for $\rlnot$.
8. But (the negation $\rlnot : 2 \to 2$) does not have a fixed point ($\rlnot\lbot = \rtop$ and $\rlnot\rtop = \lbot$), so we have reached a contradiction. (In the familiar, concrete, and easily understandable "barber paradox", if we give the English language meaning of $\hom b R b$ in this case, (representability evaluated at $b$) becomes "if the barber shaves himself, then he doesn't shave himself, and if he doesn't shave himself, then he shaves himself".)
9. Therefore such a representing $b\in U$ cannot exist.
Here is a diagram in the category $\Set$ of sets which illustrates that framework:
\[ \boxed{ \begin{array} {} && 1 & \xrightarrow{\textstyle \boxed{b} \; (4.)} & U \\ && \big\uparrow && \big\uparrow \\ && 1 \rtimes U & \xrightarrow{ \smash{\textstyle b \rtimes U} } & U \rtimes U \rlap{ \xrightarrow [\smash{\kern15em}] { \smash{\textstyle \boxed{R} \; (2.)} } } &&&& \bftwo \\ && {\wr\Vert} && \Vert &&&& \Vert \\ && \llap{(1.) \;} U \rlap{ \xrightarrow[\kern27em]{\textstyle \hom b R - \; (5.) } } &&&&&& \bftwo \\ 1 & \xrightarrow { \smash{\textstyle \; \boxed{b} \; (7.) \;} } & \Vert & {} \rlap{ \kern-3.4em \text{? predicate $\Irr_R$ below $R$-representable by $b$ (6.)?} } &&&&& \Vert \\ && \llap{ \boxed{\Irr_R} \; (3.) : {} } U & \leftadj{ \xrightarrow[\textstyle \lDelta]{\kern3em} } & U \rtimes U & \xrightarrow[\textstyle \boxed{R} \; (2.)]{\kern3em} & \bftwo & \rightadj{ \xrightarrow[\textstyle \rlnot] {\kern3em} } & \bftwo \\ && u & \leftadj\mapsto & \langle u,u \rangle & \mapsto & \hom u R u & \rightadj\mapsto & \lnot {\hom u R u} \\ \end{array} } \]
(The numbers in parentheses show a time sequence for building this diagram.)
Now we apply that general result in some special cases.
First, the barber “paradox”, sometimes phrased as
(A town (1.)) has (a barber (4.))
who ((shaves (2.)) all those, and only those (6.))
(who do not shave themselves ("the irreflexives") (3)).
Does (the barber (7.)) shave himself?
We can formalize this situation as follows:
- Let $\boxed U$ (for “universe”) be the population in question.
- Define a binary relation $\boxed\S$ on $U$ by $u\S v \iff u \mathrel{\text{shaves}} v$.
- Form (the irreflexivity predicate $\boxed{\Irr_S(u)} = \rlnot(u\S u)$ on $U$), in words, "$u$ does not shave himself".
- Let $\exists \boxed b\in U$ (the barber), the putative barber.
- Form the predicate $\hom b S -$, which characterizes the people whom $b$ shaves.
- Suppose that $\hom b S -$ represents $\Irr_S$, i.e. $(\forall u\in U)\bigl(b\S u \iff \lnot(u\S u)\bigr)$ - we may say "$\Irr_S$ is $\S$-representable by $b$", or, in the English language, "the barber shaves precisely those who do not shave themselves".
- Instantiate the above universal quantification at $b\in U$, obtaining
$\boxed{ (b\S b) \iff \rlnot(b\S b) }$,
a contradiction, since $\rlnot$ does have a fixed point, in particular, $(b\S b)$ is not a fixed point for $\rlnot$.
- Conclusion: There cannot exist a $b\in U$ which $S$-represents $\Irr_S$.
In other words, such a barber cannot exist. - However, such a barber can exist, if we strike the requirement that the barber be <i>in the town</i>, and allow him to be outside of the town, i.e. in a larger metropolitan area. Such a $b$ would be outside the scope of applicability of the universal quantification. This is the origin of the large/small distinction which permeates logical studies.
At a "meta"-level, we may note that there are three levels of language being used to describe this situation.
There is the level of category theory, see the diagram above.
I call this the "1-D" level.
Then there is the level of first-order logic, exemplified by such formula as "$(\forall u\in U)\bigl(b\S u \iff \lnot(u\S u)\bigr)$".
I call that the "0-D" level.
Finally, there is the English language.
Examples of that appear above.
<hr / >
It is also worth noting that the problem is caused by the bidirectional nature of the "if and only if";
that is, if we replace the "iff" with a one-directional implication, in either direction,
that one-directional implication can be satisfied.
\[ \boxed{ \begin{array} {ccccc|cccccc} \kern2em & & {} \rlap{ \kern-7em \text{if you don't shave yourself,} } &&&&&& {} \rlap{ \kern-5em \text{if the barber shaves you,} } \\ & & {} \rlap{ \kern-7em \text{then the barber shaves you} } &&&&&& {} \rlap{ \kern-6em \text{then you didn't shave yourself} } \\ \hline & \lnot {(\hom x S x )} & \To & \hom b S x & \kern2em && \kern2em & \hom b S x & \To & \rlnot {(\hom x S x )} \\ \hline & \rlnot {(\hom b S b )} & \To & \hom b S b &&&& \hom b S b & \To & \rlnot {(\hom b S b )} & \kern2em & \red X \\ & \bot && \rtop &&&&& \bot \\ & & \rtop \\ \hline & && &&&&\rlnot {(\hom b S b )} & \To & \rlnot {(\hom b S b )} \\ & &&&&&& \rtop && \rtop \\ & &&&&&&& \rtop \\ \end{array} } \]
The range of possibilities, and their consequences, can be presented by a Venn diagram or an old-fashioned truth table:
Venn diagram (annotated) for $ \big( b S x \iff \rlnot (x S x) \big) $:
\[ \boxed{ \begin{array} {} \kern8em && \lbot \buildrel \rtop \over \Rightarrow \rtop && \kern8em \\ & & \lbot \buildrel \lbot \over \Leftarrow \rtop \\ && \boxed{ \lnot ( \hom b S b ) } \\ \\ & {} \rlap{ \kern-6em \boxed{ \begin{array} {} \\ \rtop \buildrel \rtop \over \Leftrightarrow \rtop \\ \rtop \To \hom b S x & \kern6em \\ \\ \end{array} } } & \begin{array} {} \rtop \buildrel \lbot \over \Rightarrow \lbot \\ \rtop \buildrel \rtop \over \Leftarrow \lbot \\ \boxed{ \hom b S b } \\ \end{array} & {} \rlap{ \kern-6em \boxed{ \begin{array} {} \kern6em \\ \\ & \lbot \buildrel \rtop \over \Leftrightarrow \lbot \\ & \rtop \To \hom x S x \\ \\ \\ \end{array} } } \\ \\ \end{array} } \]
Truth table:
\[ \boxed{ \begin{array} {cccc|cc|cc} \hom b S b & \hom b S x & \hom x S x & \rlnot {(\hom x S x )} & [ \hom b S x \Rightarrow \rlnot {(\hom x S x )} ] & [ \hom b S x \Leftarrow \rlnot {(\hom x S x )} ] & \hom b S x \Leftrightarrow \rlnot {(\hom x S x )} \\ \hline \rtop & \rtop & \rtop & \lbot & \leftadj{ \boxed\bot } & \rtop & \lbot \\ & \rtop & \lbot & \rtop & \rtop & \rtop & \rtop \\ & \lbot & \rtop & \lbot & \rtop & \rtop & \rtop \\ \lbot & \lbot & \lbot & \rtop & \rtop & \leftadj{ \boxed\bot } & \lbot \\ \end{array} } \]
The paradox can be understood in terms of that truth table.
There are three salient facts with regard to that table:
1) the truth values in the second and third columns are opposite,
2) the one-directional implications (in both directions) are between the first and third columns,
3) if we let $x=b$, then the truth values in the first two columns must be identical, thus only the first and last rows of the table are relevant, and for those cases (rows) the truth values in the first and third columns are opposite.
In those cases (rows), precisely one of the one-directional implications is satisfied, not both.
Thus in either case, the truth value of the if-and-only-if is $\lbot$, i.e., "false".
The above argument was presented in classical first-order logic terms.
The argument may also be presented (in terms of category theory), via (a diagram in the category of sets).
(This diagram precisely duplicates the above diagram, except that the letter $R$, for an arbitrary relation, is replaced by the letter $S$, for "shaves".)
\[ \boxed{ \begin{array} {} && 1 & \xrightarrow{\textstyle b \; (3.)} & U \\ && \big\uparrow && \big\uparrow \\ && 1 \times U & \xrightarrow{ \smash{\textstyle b \times U} } & U \times U \rlap{ \xrightarrow [\smash{\kern15em}] { \smash{\textstyle S \; (2.)} } } &&&& \bftwo \\ && {\wr\Vert} && \Vert &&&& \Vert \\ && U \rlap{ \xrightarrow[\kern27em]{\textstyle \hom b S -} } &&&&&& \bftwo \\ 1 & \xrightarrow { \smash{\textstyle \; b \; (4.) \;} } & \Vert & {} \rlap{ \kern-2.8em \Irr_S \text{ $\S$-representable by $b$ (3.) ???} } &&&&& \Vert \\ &\Irr_S \rlap{\; :} & U & \xrightarrow[\textstyle \lDelta]{\kern3em} & U \times U & \xrightarrow[\textstyle S]{\kern3em} & \bftwo & \xrightarrow[\textstyle \lnot] {\kern3em} & \bftwo \\ && u & \mapsto & \langle u,u \rangle & \mapsto & \hom u S u & \mapsto & \rlnot {\hom u S u} \\ \end{array} } \]
The (categorical) point is that
the hypothesized equality (3) that was questioned in "predicate below $\S$-representable by $b$ ???",
when evaluated (4) at $b$, instantly gives a contradiction.
(The paranthesized numbers refer to the text above.)
It is useful to state what we just proved abstractly and mathematically:
Theorem:
Given (any binary relation $\boxed S$ on any set $\boxed U$),
using $\lDelta$ and $\rlnot$ we may form (a predicate $\boxed{ (\text{Irr}_S = \lDelta S \rlnot) }$ on $U$)
which cannot be $S$-represented (i.e., represented by $S$).
<hr />
Leaving (our categorical aside) and (returning to the main text),
that is about as fast as it is possible to dispose of the original question.
It is instructive, however, to compare this proof that (such a barber cannot exist)
to the proof that (there cannot be a truly universal set, i.e., “the set of all sets”),
sometimes called “Russell’s paradox”.
Recall the proof that such a universal set cannot exist:
- Let $U$ ("the universe") be the set of all sets.
- Let $\text{Irr}_{\in} = \{u\in U \mid u \notin u \}$ (the irreflexives relative to ${\in}$) (axiom schema of separation).
- Assume $\text{Irr}_{\in} \in U$.
- Consider the proposition: $\text{Irr}_{\in} \in \text{Irr}_{\in}$. Assume it is either true or false. Consider each alternative:
$\text{Irr}_{\in} \in \text{Irr}_{\in} \xLongrightarrow{\text{defn $\text{Irr}_{\in}$}} \text{Irr}_{\in} \notin \text{Irr}_{\in}$.
$\text{Irr}_{\in} \notin \text{Irr}_{\in} \xLongrightarrow{\text{defn $\text{Irr}_{\in}$}} \text{Irr}_{\in} \in\text{Irr}_{\in} $.
Thus in either case we have a contradiction.
- Conclusion: $\text{Irr}_{\in}\subseteq U$, but $\text{Irr}_{\in} \notin U$.
- Thus the need for a larger universe, which includes both the members of the original universe $U$, and $\text{Irr}_{\in} = \{ u\in U \mathrel | u\notin u \}$.
As a slight variation, we can express the above argument as follows:
Let $U$ (for “universe”) be the population in question, the collection of all sets.
Consider the binary relation $\S$ on $U$ defined by $u\S v \iff u \in v$,
i.e., $S$ is just a name for the membership relation in $U$.
Assume (the predicate $\lnot(u\S u)$ on $U$) is $\S$-representable,
i.e., $\exists X \in U$ such that
$(\forall u\in U)\bigl(u\S X \iff \lnot(u\S u)\bigr)$
(this is (the comprehension scheme) applied to (the predicate $\lnot(u\S u)$ on $U$).
Instantiate the above universal at $X\in U$, obtaining
$\boxed{ \bigl(X\S X \iff \rlnot(X\S X)\bigr) }$,
a contradiction.
Conclusion: There cannot exist an $X\in U$ satisfying the condition asserted for $X$, i.e., $X= \{ u\in U | u\notin u \}$.
Thus, just as
the barber who shaved all those in a town who did not shave themselves
cannot himself be a member of that town,
so $\{ u\in U | u\notin u \}$ cannot itself be a member of $U$,.
Thus the need for another universe to which it can belong.
And if we want the new universe to include the original "universe", our new universe must perforce be a larger universe.
We can express in words parts of the above.
$X = \{u\in U | \rlnot (\hom u S u) \}$ is the set of $\{u\in U\}$ which do not self-$S$-relate, i.e., relate to themselves under $S$.
If that set $X = \{u\in U | \rlnot \hom u S u \}$ is $S$-representable,
then we have our contradiction as above.
<hr />
We can obtain a hybrid of those two proofs as follows:
- Let $U$ be the population in question.
- Define a binary relation $\S$ on $U$ by $u\S v \iff u \mathrel{\text{shaves}} v$.
- Let $X = \{u\in U \mid \rlnot(u\S u) \}$.
- Assume $X$ is representable by the relation $\S$, i.e.,
$(\exists b\in U)(u\in X \iff b\S u)$, i.e.,
$X = \{u\in U \mid b\S u\}$.
- Ask the equivalent questions:
Does $b\S b$? (This is the barber question.)
Is $b\in X$?
We have
$b\S b \iff b\in X \iff \rlnot(b\S b)$.
A contradiction.
- Conclusion: Such a $b$ cannot exist, i.e.,
$X = \{u\in U \mid \rlnot(u\S u)\}$ exists as a legitimate subset of $U$,
but it is not representable by $\S$.
All that is much more than is necessary merely to prove that the hypothesized barber cannot exist,
but contains reasoning, in this simple setting,
that occurs in more complex situations.
We can extend this argument to prove a key result in set theory,
that any set is strictly smaller than its power set (the set of subsets of the original set).
In fact, this is the application in which Georg Cantor originally introduced this argument,
now commonly known as the "Cantor diagonal argument."
Rather than proving the theorem in the form stated above,
we use the result that, given a set $X$,
the set of its subsets is in bijection with (so is of the same size as)
the set of functions from $X$ to $2$.
So we prove that,
for any set $X$, $|X| \lt |2^X|$,
where $2^X = \{\,\text{functions}\, X\to 2\}$.
This is proved by showing that there cannot be a surjection from $X$ to $2^X$,
because the existence of such a surjection would lead to a contradiction.
- Let $X$ be a set in $\Set$.
Let $2^X = \hom X \Set 2 = \{\,\text{functions}\, X\buildrel f \over \to 2\}$.
Let
\[\begin{array}{}
X \times 2^X & \xrightarrow{\text{eval}} & 2\\
\langle x, f \rangle & \mapsto & xf = (x)f\\
\end{array}\]
be the evaluation function.
- Suppose there exists a surjection $\boxed{X\buildrel \sigma \over \twoheadrightarrow 2^X}$.
(We will draw a contradiction from this assumption.)
- The exponential transpose of the function $X\buildrel \sigma \over \twoheadrightarrow 2^X$
is a relation, which we shall also call $\sigma$, $\boxed{X\times X \buildrel \sigma \over \to 2}$.
The hypothesis that (the original function $\sigma$ was a surjection)
is equivalent to (the following assertion about the relation $\sigma$):
- For each $X \buildrel f \over \to 2$, there exists an $x_0\in X$ such that
$f = - \mathrel\sigma x_0$ (using $-$ as a placeholder for the missing variable),
i.e., $\boxed{ xf \iff x \mathrel\sigma x_0 }$.
(We call this condition “$\sigma$-representability”.)
- Apply this to the function $\Irr_\sigma : X\to 2$
which takes $x\in X$ to $x\, \Irr_\sigma = \rlnot(x \mathrel\sigma x) \in 2$.
By $\sigma$-representability, there exists an $x_0\in X$ such that
$\rlnot (x \mathrel\sigma x) \iff x \mathrel\sigma x_0$.
Take $x=x_0$ to obtain the contradiction.
$\def\P{{\bf P}} \def\twotoP{{2^{\P}}} $
This argument, with a little extra work, show that the real numbers are not countable,
or as it sometimes said, "denumberable."
To get this result we apply the above with $X=\P$, the set of positive integers $\{1,2,3,\ldots\}$.
Applying the above directly we have $\P \lt \twotoP$.
We can embed (produce an injection) of $\twotoP$ in $\R$: $\twotoP \buildrel i \over \rightarrowtail \R$.
The idea is $\twotoP = \{ \text{functions} \; \P \to 2\}$,
so its elements, e.g. $\P \buildrel a \over \to 2$ may be written as
sequences, $a_1, a_2, a_3, \ldots$, indexed by $\{1,2,3,\ldots\}$, of elements of $2$.
Further, we now regard our handy-dandy set $2$ as consisting, not of truth values
but of the integers $0$ and $1$.
Given a sequence $a_1, a_2, a_3, \ldots$ we map it to
the real number $$.a_1a_2a_3\ldots = \sum_{n=1}^\infty a_n10^{-n} \in \R ,$$
so we have the injection
\[\begin{array}{}
\twotoP & \buildrel i \over \rightarrowtail & \R\\
\langle a_0, a_1, a_2, \ldots \rangle & \mapsto & .a_1a_2a_3\ldots = \displaystyle\sum_{n=1}^\infty a_n10^{-n}
\end{array}\]
Now, we know there cannot be a surjection of $\P$ onto $\twotoP$
and it would seem intuitive that then there cannot be a surjection from $\P$ onto $\R$,
which is even larger.
However it is worth giving a detailed proof of that,
as it illustrates several ideas which are generally useful and significant.
Suppose there were a surjection $\P \buildrel e \over \twoheadrightarrow \R$.
Then consider the diagram
\[\begin{array}{}
& & \P \\
& & \twoheaddownarrow \rlap e \\
\twotoP & \buildrel i \over \rightarrowtail & \R \\
\end{array}\]
Expand the diagram to:
\[\begin{array}{}
\twotoP \times_\R \P & \buildrel i' \over \rightarrowtail & \P \\
\llap{e'}\twoheaddownarrow & \raise8pt\hbox{$\lrcorner$}\qquad & \twoheaddownarrow \rlap e \\
\twotoP & \buildrel i \over \rightarrowtail & \R \\
\end{array}\]
where $\twotoP \times_\R \P$ is the pullback of $i$ and $e$,
thus $\twotoP \times_\R \P = \{ n\in\P \mid ne \in (\twotoP)i \}$.
(The small $\lrcorner$ is the standard categorial notation indicating that
what is "inside" the corner is a pullback.)
<hr />
We now apply the basic set-theoretical result that, for all sets $X$, $\boxed{ X \buildrel \scriptscriptstyle \text{Cantor} \over \lt \big( 2^X = [X,2] \big) }$ (<i>strictly</i> less than)
to obtain a basic result in the theory of categories:
<b>Theorem</b> (Mac Lane CWM Proposition V.2.3) $\def\bfA{{\mathbf A}}$
If a category $\bfA$ has <i>all</i> limits, no matter how large,
then $\bfA$ is a preorder (i.e., for all $a,b \in \bfA$, there is at most one arrow in $\hom a \bfA b$ ).
Proof:
We argue by contradiction.
Suppose not.
Suppose for some $a, \rightcat b \in \bfA$ there are two distinct arrows $\boxed{ h,k : a \to \rightcat b }$ in $\hom a \bfA {\rightcat b}$, so $2 \cong \{h,k\} \subseteq \hom a \bfA {\rightcat b}$.
Thus for any set $X$, we have
\[ \boxed{ \begin{array} {ccccccccccl} && 2 & \cong & \rightcat{ \{h,k\} } & \subseteq & \rightcat{ \hom {\leftcat a} \bfA b } &&&&&& \text{now apply} [X,-] : \Set\to\Set \\ && [X,2] & \cong & \rightcat{ [X,\{h,k\}] } &\subseteq & \rightcat{ [X, \hom {\leftcat a} \bfA {\rightcat b}] } & \rightadj{ \buildrel * \over \cong } & \leftcat{ \hom a \bfA { \rightadj{ (\prod_{\rightcat{x\in X}} {\rightcat b}) } } } & \subseteq & \text{Arr}(\bfA) & \kern1em & \text{so, taking cardinalities,} \\ |X| & \buildrel \text{Cantor} \over \lt & |[X,2]| & = & \rightcat{ |[X,\{h,k\}]| } &\le & \rightcat{ |[X, \hom {\leftcat a} \bfA {\rightcat b}]| } & \rightadj{ \buildrel * \over \cong } & \leftcat{ | \hom a \bfA { \rightadj{ (\prod_{\rightcat{x\in X}} {\rightcat b}) } } | } & \le & |\text{Arr}(\bfA)| && \text{now take } X = \text{Arr}(\bfA) \\ |{\text{Arr}(\bfA)}| & \buildrel \text{Cantor} \over \lt & |[{\text{Arr}(\bfA)},2]| & = & \rightcat{ |[{\text{Arr}(\bfA)},\{h,k\}]| } &\le & \rightcat{ |[\text{Arr}(\bfA), \hom {\leftcat a} \bfA {\rightcat b}]| } & \rightadj{ \buildrel * \over \cong } & \leftcat{ | \hom a \bfA { \rightadj{ (\prod_{\rightcat{f\in \text{Arr}(\bfA)}} {\rightcat b}) } } | } & \le & |\text{Arr}(\bfA)| \\ \end{array} } \]
Now recall the defining property of a categorical product, for $X$ a set (this is sometimes denoted $X \cotensor {\rightcat b}$, and called the <em>cotensor</em> of $X$ and $\rightcat b$, or <em>power</em> ${\rightcat b}^X$ of $\rightcat b$ by $X$):
$ \hom a \bfA { (\prod_{x\in X} {\rightcat b} ) } \cong [X, \hom a \bfA {\rightcat b} ]$.
Combining that property of the product with the above numerical inequality gives, for any set $X$,
$|X| \lt |\hom a \bfA { (\prod_{x\in X} {\rightcat b}) }|$.
Now let $X = {\text{Arr}(\bfA)} $, the collection of<em>all<em> arrows in $\bfA$.
The result:
$|\text{Arr}(\bfA)| \lt |\hom a \bfA { (\prod_{f \in \text{Arr}(\bfA)} {\rightcat b}) }|$,
But $|\hom a \bfA { (\prod_{f \in \text{Arr}(\bfA)} {\rightcat b}) }| \le |\text{Arr}(\bfA)|$,
so $|\text{Arr}(\bfA)| \lt |\text{Arr}(\bfA)|$, clearly impossible.
We may sharpen the conclusion as follows:
If $\bfA,a, \rightcat b, h,k,X$ are as above,
then a NECESSARY condition for $\prod_{x\in X} {\rightcat b} = {\rightcat b}^X$ to exist is that $|X| \lt |\text{Arr}(\bfA)|$.
The instance of the diagonal argument which is applicable here runs as follows:
If a function $\sigma : \text{Arr}(\bfA) \to [\text{Arr}(\bfA),2]$ is surjective, then there would have to exist an $f_0\in \text{Arr}(\bfA)$ such that \[ (\forall f \in \text{Arr}(\bfA)) \Big( (f_0 \sigmarel f) \iff \neg (f \sigmarel f) \Big) \, .\] Then, in analogy to the previous cases, instantiating at $f_0$ deliverers a contradiction.
<hr />
Lawvere has generalized this by generalizing the role of the endofunction $\rlnot : 2 \to 2$.
\[ \boxed{ \begin{array} {cccc|cc} 2 & \xrightarrow [\kern 3em] {\textstyle \rlnot} & 2 \\ \Omega & \xrightarrow [\kern 3em] {\textstyle \rlnot} & \Omega &&& (\forall \omega \in \Omega) (\rlnot\omega \not= \omega) \\ Y & \xrightarrow [\kern 3em] {\textstyle t} & Y &&& (\forall y \in Y) (yt \not= y) \\ \end{array} } \]
i.e., each of $\rlnot$ and $t$ lack a <b>fixed point</b>,
i.e., in the parlance of combinatorial mathematics, each is a <I>derangement</I>.
\[ \boxed{ \begin{array} {} && 1 & \xrightarrow{\textstyle \boxed{b} \; (3.)} & U \\ && \big\uparrow && \big\uparrow \\ && 1 \times U & \xrightarrow{ \smash{\textstyle b \times U} } & U \times U \rlap{ \xrightarrow [\smash{\kern20em}] { \smash{\textstyle \boxed{R} \; (2.)} } } &&&& (\bftwo = \Omega = Y) \\ && {\wr\Vert} && \Vert &&&& \Vert \\ && U \rlap{ \xrightarrow[\kern32em]{\textstyle \hom b R - \; (3.) } } &&&&&& (\bftwo = \Omega = Y) \\ 1 & \xrightarrow { \smash{\textstyle \; \boxed{b} \; (4.) \;} } & \Vert & {} \rlap{ \kern-3.4em \text{? predicate $\Irr_R$ below $R$-representable by $b$ (3.) ?} } &&&&& \Vert \\ && \llap{ \boxed{\Irr_R} : {} } U & \xrightarrow[\textstyle \lDelta]{\kern3em} & U \times U & \xrightarrow[\textstyle \boxed{R}]{\kern3em} & (\bftwo = \Omega = Y) & \xrightarrow[\textstyle \rlnot = t] {\kern3em} & (\bftwo = \Omega = Y) \\ && u & \mapsto & \langle u,u \rangle & \mapsto & \hom u R u & \mapsto & \rlnot {\hom u R u} = ({\hom u R u})t \\ \end{array} } \]
Consider $\Irr_R = \lDelta R \rlnot$, the bottom long left-to-right arrow, which starts at $U$.
The question is:
Can (that arrow) be $R$-represented by (an object $b$)?
If so, we have (an arrow $\hom b R -$ as above it),
and (an equality between those two arrows)
But then, precomposing (that pair of parallel arrows) with (the representing object $b$),
we find (a fixed point for $t$),
namely, ($\hom b R b \cong {(\hom b R b )} t$).
This is Theorem 6.5 of Noson S. Yanofsky, <I>Theoretical Computer Science for the Working Category Theorist</I>.
The earlier examples, the barber, Russell, and Cantor "paradoxes", use the contrapositive of this:
If $t: Y \to Y$ does not have a fixed point,
then $\Delta R t$ is not $R$-representable.
Specifically, they take $t: Y \to Y$ to be $\rlnot : 2 \to 2$.
Since $\rlnot \rtop = \lbot$ and $\rlnot \lbot = \rtop$,
$\rlnot$ does not have a fixed point.
<hr>
------------
Here are some useful references:
Yanofsky's excellent 23-page paper:
"A Universal Approach to Self-Referential Paradoxes Incompleteness and Fixed Points",
http://arxiv.org/abs/math/0305282
which is both introductory and comprehensive!
John Baez:
https://golem.ph.utexas.edu/category/2006/12/classical_vs_quantum_computati_8.html
Vishal Lama:
https://topologicalmusings.wordpress.com/2010/07/11/self-referential-paradoxes-incompleteness-and-fixed-points/
<hr>
-----------
What is below is an alternative approach to the paradoxes.
I have a choice on how to present this.
I could present the usual "paradox", which involves negation at two levels.
Or I could initially just present the kernel of the argument, the "positive version", which does not use negation, and replaces
the familiar truth-value set $2 = \{\lbot,\rtop\}$
(with its logical negation endofunction $\rlnot: 2\to 2$)
with an arbitrary set, say $\boxed Y$
(with an arbitrary endofunction on $Y$ called in various sources $\boxed{t:Y\to Y}$ or $\boxed{\alpha:Y\to Y}$ ).
Then, from that positive version, the usual version of the paradoxes can be derived,
by introducing negatives, in three steps, at two levels.
So let us begin with a diagram which illustrates the positive version.
\[ \boxed{ \begin{array} {} && \langle b,b \rangle && \hom b R b \\ && \langle x,x \rangle && \hom x R x \\ && X\times X & \xrightarrow {\textstyle R} & Y \\ && \llap \lDelta \Bigg\uparrow & \Big |\Big | \rlap{ \scriptstyle \kern-3.7em \text{representation} } & \Bigg\downarrow \rlap{t \text{ or } \alpha} \\ 1 & \xrightarrow [\textstyle x,b] {\kern3em} & X & \xrightarrow [\textstyle \hom b R -] {\kern3em} & Y \\ &&&&& \boxed{ \begin{array} {ccl} {\hom x R x}\alpha & \rightadj{ {\hom b R b}\alpha } & \text{top leg} \\ || & \rightadj{ || } \\ \hom b R x & \rightadj{ \hom b R b } & \text{bottom leg} \\ \text{representation at $x$} & \rightadj{ \text{representation at $b$} } \\ \end{array} } \\ \end{array} } \]
Thus we see that
IF $\hom b R -$ equals $\lDelta R \alpha$ (i.e., $b$ $R$-represents $\lDelta R \alpha$)
THEN $\rightadj{ \hom b R b}$ is a $\rightadj{ \text{fixed point} }$ for $\alpha$.
1. Now consider the case $ \alpha = \rlnot : 2\to2$. (This is internal to the category $\Set$.)
2. $\rlnot$ has NO fixed points. (This statement, and the next, are ABOUT the category $\Set$, not internal to it.)
3. Thus $\lDelta R \rlnot$ CANNOT be $R$-represented.
One now obtains the various diagonal "paradoxes",
e.g. the barber and Russell paradoxes,
by suitable selection of the set $X$ (or $U$), and the relation $R$ (or $S$) on it.
<hr />
