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}$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 $X\to 2$
which takes $x\in X$ to $\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 />
