\documentclass[%
version=last,%
a5paper,
10pt,%
headings=small,%
bibliography=totoc,%
twoside,%
%titlepage=true,%
reqno,%
cleardoublepage=empty,%
parskip=half,%
draft=true,%
DIV=9,%
headinclude=true,%
pagesize]
{scrartcl}

\usepackage{verbatim}
%\begin{comment}
  

\usepackage[headsepline]{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\automark[section]{section} % this seems to be needed for \rightmark to work
%\manualmark
\rehead{Logical paradoxes}
\lohead{September, 2013}
\ohead{\pagemark}


%\end{comment}

\usepackage{multicol}
\setlength{\columnseprule}{0.4pt}

\usepackage{hfoldsty,url}

\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X

\usepackage{amsmath,amssymb,amsthm}

\newcommand{\gn}[1]{\ulcorner#1\urcorner}
\renewcommand{\phi}{\varphi}

\newcommand{\Forall}[1]{\forall{#1}\;}
\newcommand{\Exists}[1]{\exists{#1}\;}

\newtheorem{theorem}{Theorem}

\begin{document}
\title{Logical paradoxes}
\author{David Pierce}
\date{September 23, 2013}
\publishers{\relscale{0.9}Mathematics Department\\
Mimar Sinan Fine Arts University\\
\url{dpierce@msgsu.edu.tr}\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}

\maketitle  

%\begin{center}\relscale{0.9}
These notes were prepared in the fall of 2013
to distil the common essence of certain paradoxes,
from the Russell Paradox to G\"odel's Incompleteness Theorem.
Using the work of R. G. Collingwood (1889--1943),
the last section observes that a science purporting to study the whole world
must also study itself \emph{as} a science.
\LaTeX\ file last compiled, \today.
%\end{center}

%\begin{comment}
%\begin{multicols}2
\tableofcontents
%\end{multicols}
%\end{comment}

\section{Introduction}

The barber paradox is that there can be no male barber who shaves every man that does not shave himself.  If there were such a barber, he would shave himself if and only if he did not.

The Russell paradox, in its original form \cite{Russell-letter}, is that \emph{to be a predicate that cannot be predicated of itself} is not a predicate.  If it were a predicate, then it could be predicated of itself if and only if it could not.  Similarly there is no class consisting of the classes that do not belong to themselves.

These paradoxes are instances of the following.  

\begin{theorem}\label{thm:1}
Let $R$ be a binary relation on some domain of individuals.  Then there is no individual $a$ in that domain such that, for all individuals $x$ in the domain,
\begin{equation*}
a\mathrel Rx\iff \lnot\;x\mathrel Rx.
\end{equation*}
\end{theorem}

\begin{proof}
Replacing $x$ with $a$ yields a contradiction.
\end{proof}

\section{Tarski's Theorem}

Tarski's Undefinability Theorem \cite[Thm.~I, \S5, p.~247]{Tarski-truth} can now be understood as follows.  We take a \emph{logic} to be a formal way of studying some domain of individuals.  The logic has \emph{formulas,} each of which may have free variables.  The variables range over the domain being studied.  A formula with no free variables is a \emph{sentence.}  A sentence is true or false.  A formula with one free variable is a \emph{singulary} formula.  If $\phi$ is singulary, and $a$ is an individual, then $\phi(a)$ is a sentence: it is the result of replacing each free occurrence of the free variable of $\phi$ with a name for $a$.

We suppose each formula $\phi$ has a \emph{code,} denoted by $\gn{\phi}$.  This code is an individual in the domain of our logic.  In Theorem \ref{thm:1}, take $R$ to be relation that obtains between singulary formulas $\phi$ and $\psi$ just in case the sentence $\phi(\gn{\psi})$ is true.  That is,
\begin{equation*}
\phi\mathrel R\psi\iff\phi(\gn{\psi}).
\end{equation*}
Then there is no singulary formula $\theta$ such that, for all singulary formulas $\phi$,
\begin{equation*}
\theta(\gn{\phi})\iff\lnot\phi(\gn{\phi}).
\end{equation*}
Now suppose that, for every singulary formula $\psi$, there is a singulary formula $\psi^*$ such that, for all singulary formulas $\phi$,
\begin{equation}\label{eqn:*}
\psi^*(\gn{\phi})\iff\psi(\gn{\phi(\gn{\phi})}).
\end{equation}
Then there is no singulary formula $\rho$ such that, for all sentences $\sigma$,
\begin{equation}\label{eqn:truth}
\rho(\gn{\sigma})\iff\sigma.
\end{equation}
That is, there is no formula defining the collection of codes of true sentences.
For, if there were such a formula $\rho$, then
\begin{equation*}
\lnot\rho^*(\gn{\phi})
\iff\lnot\rho(\gn{\phi(\gn{\phi})})
\iff\lnot\phi(\gn{\phi}),
\end{equation*}
that is, $\lnot\rho^*$ would be a formula $\theta$ as above.  Here we understand $\lnot\rho^*$ to be $\lnot(\rho^*)$, although this is equivalent to $(\lnot\rho)^*$.

Another way to understand this is to note a special case of \eqref{eqn:*}:
\begin{equation*}
  \psi^*(\gn{\psi^*})\iff\psi(\gn{\psi^*(\gn{\psi^*})}).
\end{equation*}
Thus, for every singulary $\psi$, there is a sentence $\tilde{\psi}$ such that
\begin{equation*}
  \tilde{\psi}\iff\psi(\gn{\tilde{\psi}}).
\end{equation*}
This is the ``Diagonal Lemma'' (see the article of that name in Wiki\-pedia).
In particular, if \eqref{eqn:truth} holds, then
\begin{equation*}
  \rho(\gn{\widetilde{\lnot\rho}})\iff\widetilde{\lnot\rho}\iff\lnot\rho(\gn{\widetilde{\lnot\rho}}),
\end{equation*}
which is a contradiction.

\section{G\"odel's Theorem}

G\"odel's Incompleteness Theorem \cite{Goedel-incompl}, in its most basic form, relies on a variant of Theorem \ref{thm:1}.

\begin{theorem}\label{thm:2}
Suppose $Q$ and $R$ are binary relations on some domain, and $R$ includes $Q$, that is,
\begin{equation*}
x\mathrel Qy\implies x\mathrel Ry.
\end{equation*}
Suppose there is an individual $a$ such that
\begin{equation*}
%x\mathrel Qx\implies\lnot\;a\mathrel Rx.
a\mathrel Rx\iff\lnot\;x\mathrel Qx.
\end{equation*}
Then $Q$ and $R$ are not the same relation, and indeed
\begin{equation*}
\lnot\;a\mathrel Qa\And a\mathrel Ra.
\end{equation*}
\end{theorem}

\begin{proof}
Since
\begin{equation*}
a\mathrel Qa\implies a\mathrel Ra\implies\lnot\;a\mathrel Qa,
\end{equation*}
it follows that $\lnot\;a\mathrel Qa$ and therefore $a\mathrel Ra$.
\end{proof}

In the logic that we considered above, we now assume that there is a notion of \emph{provability} of sentences.  All provable sentences are true.  In addition to defining $R$ as before, we now let $Q$ be the relation on singulary formulas given by
\begin{equation*}
\phi\mathrel Q\psi\iff\text{$\phi(\gn{\psi})$ is provable.}
\end{equation*}
We assume there is a formula $\chi$ such that, for all sentences $\sigma$,
\begin{equation*}
\chi(\gn{\sigma})\iff\text{$\sigma$ is provable}.
\end{equation*}
Then we have
\begin{equation*}
\chi^*(\gn{\phi})
\iff\text{$\phi(\gn{\phi})$ is provable},
\end{equation*}
that is,
\begin{equation*}
\chi^*\mathrel R\phi
\iff\phi\mathrel Q\phi,
\end{equation*}
and hence
\begin{equation*}
(\lnot\chi^*)\mathrel R\phi\iff\lnot(\phi\mathrel Q\phi).
\end{equation*}
By Theorem \ref{thm:2}, the sentence $\lnot\chi^*(\gn{\lnot\chi^*})$ is true, but not provable.  Thus the notion of provability is incomplete in the sense of not establishing all truths.

\section{Criteriological science}

In Theorem \ref{thm:1}, let $R$ be the relation of studying, or examining, or criticizing, or giving an account of.  This is the relation that a science has to its objects.  But some things have this relation to themselves.  Thinking is an example: thinking is self-critical.  By the theorem, there is no science whose objects are precisely those things that are not self-critical.  Any science that studies all non-self-critical things must also study self-critical things.  Such a science must therefore be \emph{criteriological}: it must give an account of how this self-criticism is done.  

Collingwood defines criteriological science in \emph{An Essay on Metaphysics} of 1940~\cite[pp.~108--9]{Collingwood-EM}.  He mentions the traditional criteriological sciences of logic and ethics: the sciences of theoretical and practical thought, respectively.  Collingwood prefers the term \emph{criteriological} over the more usual term \emph{normative,} since the latter suggests a science that applies its own criteria or norms, rather than accounting for the criteria used by what it studies.  If I don't like what you do, it is not scientific just to declare that what you do violates my own ethical criteria; I should try to understand whether it violates your own criteria, and how you arrive at these criteria.  

By speaking about what I \emph{should} do as an ethicist, I demonstrate that the science of ethics applies also to itself.  Collingwood uses such an argument in his 1933 \emph{Essay on Philosophical Method} \cite[pp.~131-3]{Collingwood-EPM} to prove that philosophy is ``categorical'' in the sense that ``its subject-matter is no mere hypothesis, but something actually existing'' \cite[p.~127]{Collingwood-EPM}.  Ethics and logic are philosophical sciences.

Thus Collingwood gives an ``ontological proof'' in the \emph{Essay} of 1933.  Mathematics works with hypothetical objects; but philosophy must conceive of its objects as actually existing.
Collingwood makes it clearer in the \emph{Essay} of 1940 that the ontological proof of the existence of God is really a proof of belief, a proof that God is an ``absolute presupposition'' of anybody who believes in the unity of the world.  Thales is such a person: his argument that all is water is an introduction of monotheism to a polytheistic world.

\emph{Natural} sciences are not criteriological.  Psychology is supposed to be a natural science of thought.  But there can be no such science of thought as such.

Collingwood does not use the term ``criteriological'' in the earlier \emph{Essay.}  He does use it in the 1938 \emph{Principles of Art} \cite[p.~171 n.]{Collingwood-PA}.  He argues in the 1939 \emph{Autobiography} \cite[pp.~94--5]{Collingwood-Auto} that psychology cannot be a science of mind as such, because psychology is not criteriological; but he does not actually use this term.

\setbibpreamble{\relscale{0.9}}

\bibliographystyle{plain}
\bibliography{../references}


\end{document}