03-01-Predicativism.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{Predicativism}
\pmcreated{2013-03-22 18:32:45}
\pmmodified{2013-03-22 18:32:45}
\pmowner{gribskoff}{21395}
\pmmodifier{gribskoff}{21395}
\pmtitle{predicativism}
\pmrecord{8}{41265}
\pmprivacy{1}
\pmauthor{gribskoff}{21395}
\pmtype{Topic}
\pmcomment{trigger rebuild}
\pmclassification{msc}{03-01}
\pmclassification{msc}{03A05}
\pmsynonym{predicative set}{Predicativism}
%\pmkeywords{impredicative}
%\pmkeywords{vicious circle}
%\pmkeywords{type}
%\pmkeywords{order}
%\pmkeywords{axiom of reducibility}
\pmrelated{Logicism}
\pmrelated{FOUNDATIONSOFMATHEMATICSOVERVIEW}
\pmrelated{MathematicalPlatonism}
\pmdefines{impredicative definition}
\pmdefines{vicious circle principle}
\pmdefines{hierarchy of types}
\pmdefines{ramified theory}
\pmdefines{typical ambiguity}
\pmdefines{arithmetic predicate}

\endmetadata

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{graphicx}
%%\usepackage{xypic}
\usepackage{psfrag}
\usepackage{amsthm}
\usepackage[T1]{fontenc}
\usepackage{yfonts}

% define commands here
\begin{document}
\title{Predicativism}\Large 
\maketitle

\tableofcontents

\section{Initial definitions}\normalsize

In the literature on the foundations of mathematics the range of the concept predicativism is formulated in two divergent formulations.

In a rather broad sense predicativism is one of the (many) configurations of constructivism, which together with intuitionism disputes the so called classical or realist conception of mathematical knowledge.

But taken in a narrower sense predicativism is not a form of constructivism. It is rather a position in mathematical philosophy, the defining program of which is, \emph{in limine}, the categorical rejection of the use of \emph{impredicative definitions} or of the use of the \emph{vicious circle principle}. Both patterns, impredicative definition and the vicious circle principle, are used not only in classical but also in constructivist, v.g., intuitionistic mathematics. 

It is useful to divide the development of predicativism in essentially two periods.

The first to be called classical predicativism, includes Poincar\'{e}'s criticism of the use of the impredicative definition together with Bertrand Russell's pioneering work on the vicious circle principle and the ramified theory. 

The second to be called modern predicativism begins around 1960 and is essentially associated with the name of Georg Kreisel. The basic theme of Kreisel's predicativism has been the predicative reformulation of classical analysis and the attempt to define the limits of this reformulation.

\section{The vicious circle principle}\normalsize

The vicious circle principle was explained in \textbf{\emph{Principia mathematica}} essentially with the following content:

\begin{center}
\emph{No totality may contain elements definable  only in terms of the totality;} 

\emph{anything that can be defined only in terms of all the elements of a totality} 

\emph{can not be an element of the totality.}
\end{center}

\textbf{Example:}

In order to be allowed to speak predicatively of a set $\mathfrak{M}$ of natural numbers one has to have a predicate $\phi (\mathfrak{x})$ by means of which $\mathfrak{M}$ may be defined by the schema:

\begin{center}
$(\maltese)$ \qquad \qquad $(\forall \mathfrak{x}) [\mathfrak{x} \in \mathfrak{M} \leftrightarrow \phi (\mathfrak{x})].$
\end{center}

What is typical of the predicative conception is that the predicate $\phi (\mathfrak{x})$ has to have a \emph{meaning} which is independent of the knowledge about the existence of a set $\mathfrak{M}$ which satisfies $(\maltese)$. The argument is the following: 

Let us assume that a decision as to whether $\phi (\mathfrak{x})$ is satisfiable depends on \emph{knowledge} about which elements are members of $\mathfrak{M}$. In that case the question about a definition of an element $\kappa$ of $\mathfrak{M}$ could not be \emph{settled by appealing to} $\phi (\mathfrak{x})$, since that would be indeed a vicious circle. Recall that a sequence $\mathfrak{x}_1, \ldots, \mathfrak{x}_n$ of elements of $\mathfrak{M}$ satisfies $\phi (\mathfrak{x})$ if and only if when one inserts, for each $i$, a symbol representing $\mathfrak{x}_i$ for all free occurrences of $\mathfrak{x}_i$ in $\phi$, the resulting proposition is true in $\mathfrak{M}$.

\section{The scope of the vicious circle principle}\normalsize

Under these circumstances the vicious circle principle is essentially a negative principle, in the sense that it makes explicit which definition patterns have to be refused as illegitimate.

This negative character renders more difficult the \emph{an sich} more interesting task of making explicit the class of all definition patterns that the principle could reasonably justify.

In mathematical philosophy this last task is essential, in order to be able to formulate a decision as to which principles one can appeal to in order to \emph{assert the existence of classes}.

We can map two antagonic possibilities:

\begin{enumerate}
\item The exclusion of all definition patterns which violate the vicious circle principle;

\item The admission of all definition patterns which violate the vicious circle principle but whose legitimacy could be otherwise secured by universally accepted principles.
\end{enumerate}

It is immediately obvious that position 2. is not compatible with strict predicativism (see section 1 above) and we have to turn to the more positive component of Russell's work.

\section{Russell's threefold formulation in \emph{Principia mathematica}}\normalsize

We have learned from G\"{o}del the astonishing fact that already \emph{the formulation} of the vicious circle principle is a problem at least as difficult as the problem of its evaluation.

The evidence that supports G\"{o}del's insight is that in different passages of \emph{Principia mathematica} Russell provides different formulations of the principle, in spite of the fact that he means them to be equivalent, which is obviously not the case.

There are at least three different formulations of the principle and they lead to three not convergent evaluations:

\quad \textbf{Vicious circle principle I}:
\begin{center}
\emph{No totality can contain elements definable only in terms of the totality.}
\end{center}

                       
\quad \textbf{Vicious circle principle II}:
\begin{center}
\emph{Everything that involves all the elements of a totality can not be an element of the totality.}
\end{center}


\quad \textbf{Vicious circle principle III}:
\begin{center}
\emph{Everything that presupposes all the elements of a totality can not be an element of the totality.} 
\end{center}


Only the \textbf{\emph{vicious circle principle I}} makes it impossible the derivation of mathematics from logic required by the logicist program (see the PM entry Logicism for a report on this program) as this program was initially conceived by Dedekind and Frege.

But the profound significance of this trichotomy is that the vicious circle principle depends for its application on a previously adopted anti-realist position.

On the contrary if one assumes the realist point of view, according to which concepts and classes have an existence which is independent of the cognitive subject, then one can not exclude the definition of some of them by reference to all. 

In contrast impredicative definitions do not violate the \textbf{\emph{vicious circle principle II}} if one interprets "all" as an infinite conjunction.

In that case an impredicative definition that characterizes univocally one object does not involve the totality.

Impredicative definitions do not violate the \textbf{\emph{vicious circle principle IIII}} if one interprets "presuppose" as meaning an assumption for the existence of the totality and not as an assumption for knowledge about it, in the sense that one can reasonably say that a set presupposes its elements in order to exist but not in order to be known.

\section{Predicative reasoning in the ramified theory of types}\normalsize

The first contribution for a formal characterization of predicative reasoning was the \emph{ramified theory of types}, in which one combines the type of a variable with a classification of the predicates in orders.

In the \textbf{\emph{Introduction to mathematical philosophy}} for Russell a type is a domain of arguments for which a function can have values. A propositional function belongs to the totality of all propositional functions which use arguments of a given type and for Russell this totality can not be used in the definition of an argument of this type. 

This entails that the division in types builds an hierarchy in different levels, so that in each level a propositional function can only have arguments of a type lower than its own. The \emph{type hierarchy} builds a pattern according to the following rule:

\begin{enumerate}
\item Every individual (resp. individual variable) is of type $i$;

\item A predicate (resp. predicate variable)  

\begin{center}
$\mathfrak{A} (\mathfrak{x}_1, \ldots, \mathfrak{x}_n)$
\end{center}

with arguments $\mathfrak{x}_1, \ldots, \mathfrak{x}_n$ of types $\mathfrak{t}_1, \ldots, \mathfrak{t}_n$ is of type
                                
\begin{center}
$(\mathfrak{t}_1, \ldots, \mathfrak{t}_n).$
\end{center}
\end{enumerate}

\textbf{Examples:} 

\textbf{1.} Any binary predicate is of type:

\begin{center}
$(i, i);$
\end{center}

\textbf{2.} A predicate whose only argument is itself a predicate with two individual arguments is of type:

\begin{center}
$((i, i));$
\end{center}

\textbf{3.} A predicate $\mathfrak{R} (\mathfrak{x}, \mathfrak{y}, \mathfrak{F})$, whose arguments are two individuals and a binary function, is of type:

\begin{center}
$(i, i, (i, i)).$
\end{center}

Once the hierarchy of types is introduced one requires that bound variables always have to belong to some definite type. Every quantifier will range over the totality of all entities whose type equals that of the bound variable.

To get the ramified theory Russell (in \emph{Principia mathematica}) supplements the theory of types with the \emph{theory of orders}.

\begin{enumerate}

\item Propositions and propositional functions of \textbf{\emph{first order}} are those in which functions do not occur as free variables. They form a well defined totality which can occur as free variables in propositional functions of a higher order.

\item Propositional functions of \textbf{\emph{second order}} are those without occurrences of free variables of order higher than 1;

\item Propositional functions of \textbf{\emph{order $n$}} are those in which the free variables occurring as arguments are of order less or equal to $n-1.$
\end{enumerate}

\emph{A propositional function is said to be predicative when the highest order of some of its arguments is $n$ and the function is of order $n+1.$}

Finally only types higher than individuals are subject to the division by orders.

A concept related to the theory of types which is having a renaissance in the philosophical discussions of category theory is the concept of typical ambiguity.

It originates in the fact that many of the propositional functions and symbols of \emph{Principia mathematica} were conceived as having typical ambiguity.

A good example is identity.

In \emph{Principia mathematica} $x = y$ is a \emph{different} propositional function for each of the many types to which $x$ and $y$ may belong. What is regarded as essential is that all these separate identities \emph{share the same formal properties}, so that it is possible to overlook the distinction of type. It will be simply  understood that the symbol "=" will always denote the instantiation of "=" which is needed by the local context.

\section{Towards the predicative concept of set}\normalsize

Today with the benefit of hindsight we can separate in the ramified theory two component parts:

\begin{itemize}
\item \textbf{I.} A first partial representation of the predicative concept of set;

\item \textbf{II.} An instrument for the derivation of classical analysis.
\end{itemize}

The discussion of \textbf{II.} is best known in the literature because of the difficulties that it creates in the foundations of the theory of the classical continuum.

Here we have to show that every set $\mathfrak{D}$ of real numbers which has an upper bound has a least upper bound, so that a Dedekind cut in the real line always has a corresponding real number. But to prove this we have to use quantification over the elements of $\mathfrak{D}$.

Let us assume that the real numbers are identified with the lower classes of Dedekind cuts in the rational line. Then the least upper bound of $\mathfrak{D}$ is the union of its elements. But since this requires quantification over the real numbers in $\mathfrak{D}$, the propositional function that expresses this procedure is impredicative.

Since in this form the theory can not be used to prove the existence of the least upper bound, in \emph{Principia mathematica} one then assumes an additional axiom, the \textbf{\emph{axiom of reducibility}}, the content of which is that to each propositional function $f (x)$ there corresponds a coextensive, i.e., formally equivalent predicative function. 

In spite of its obvious \emph{ad hoc} character Russell and Whitehead still regarded the axiom of reducibility as a tenable, since it is still weaker than the assumption that to every propositional function there corresponds the class of all arguments that satisfy it. 

For our purpose \textbf{I.} is more promising and we report on a very interesting idea that goes back to Feferman. 

The \emph{natural numbers} are of type 0 and will be denoted by small roman letters $x, y, z, \ldots$

\emph{Sets of natural numbers} are of type 1 and are denoted by capital roman letters $M, N, \ldots$

To type 2 belong \emph{classes of sets of natural numbers} and are denoted by small Greek letters $\alpha, \beta, \ldots$

Under these circumstances one says that a \emph{predicate $\phi (x)$ is arithmetic if it only contains quantification of type 0.}

If one admits the natural numbers (see the qualification bellow) such predicates allow the construction of the class $\alpha_{0}$ of those sets $M$ defined by the schema:

\begin{center}
$(\forall x) [x \in M \leftrightarrow \phi (x)]$
\end{center}
 
where $\phi (x)$ is arithmetic.

So if we are given a predicate $\phi (x)$ we can build the set $M$ by means of the schema:

\begin{center}
$(\forall x) [x \in M \leftrightarrow \phi_{\alpha_{0}} (x)]$
\end{center}

The index in $\phi$ is to be interpreted as denoting the \emph{restriction} of all predicates of type 1 (occurring in $\phi$) to $\alpha_{0}$. The resulting sets are of order 1 and are denoted by $\phi_{1}.$ 

The general idea is to define $\Omega_{\alpha}$ as being formed by all sets $M$ such that for a predicate $\phi (x)$ one has the schema:

\begin{center}
$(\forall x) [x \in M \leftrightarrow \phi_{\alpha} (x)]$
\end{center}

Recall that Russell's thesis was that the class which corresponds to the enumeration of the classes of natural numbers of order $k$, (determined by well-formed formulas of the ramified theory of types), is of order $k+1$. Thus $\alpha_{0}$ corresponds to all definable arithmetic sets and $\Omega_{\alpha_{k}} = \alpha_{k+1}.$
 
If we denote the order as a superscript in a set variable, the general \textbf{axiom scheme of comprehension} has the notation:

\begin{center}
$(\exists M^{i}) (\forall x) [x \in M^{i} \leftrightarrow \phi (x)]$
\end{center}

The condition is that $M^{i}$ can not occur free in $\phi$. The definition of real numbers by means of predicates, such as the cut predicate, is thereby relativized to an order. In general if the numbers referred to in the definition are of order $k$, the order of the thereby created set of numbers is of order $k+1$. 

\section{Predicative philosophy of mathematics}\normalsize

As far as the philosophical content of the predicativist standpoint is concerned we will briefly mention two kinds of questions, the first on its epistemological significance and the second on the ontological aims of predicativism.

In epistemology the predicativist position can be seen as a form of foundationalism but it can also be seen as a form of nominalism.

In the first position \emph{das Gegebene} (the given) of the theory is the natural numbers as a totality. But in the nominalist position not even the totality of the natural numbers is accepted as an abstract object. 

A by-product of this nominalist position is its pragmatist bias, according to which sets can only be conceived as \emph{useful} abstractions, which are typically obtained from the extension of a predicate.

Of course in ontology the crucial question is the status of the power set of (the set of) the natural numbers. This totality is not considered as existing \emph{actualiter} but it is only thought of as a potential entity. In this sense the whole content of such a totality can not be known in advance of its construction.

However we can hope to attain a \emph{growing insight} of its content as we progress along the stages its construction. Of course this notion is not yet formal but we can already attain a perception of some of the axioms that it will eventually have to satisfy.

We denote the stages by ordinals and the constructed object by $\mathfrak{S}.$
 
\quad \textbf{Axiom 1:}

\begin{center}
\emph{There exists a primitive recursive relation $\mathfrak{S} (\alpha)$,} 

\emph{the meaning of which is "to build $\mathfrak{S}$ in $\alpha$".}
\end{center}

\quad \textbf{Axiom 2:}

\begin{center}
\emph{For every $\mathfrak{S}$ and every $\alpha$, $\mathfrak{S} (\alpha)$ is recursively decidable.}
\end{center}

\quad \textbf{Axiom 3:} 

\begin{center}
\emph{If $\alpha < \beta$ then $\mathfrak{S} (\alpha) \rightarrow \mathfrak{S} (\beta).$}  
\end{center}

\begin{thebibliography} {99}
\bibitem{SF} Feferman, S., "Systems of predicative analysis", \emph{Journal of Symbolic Logic}, 29, 1964.
\bibitem{KG} G\"{o}del, K., \emph{Collected works}, ed. S. Feferman, Oxford, 1987-2003.
\bibitem{GK1} Kreisel, G., "La predicativit\'{e}", \emph{Bulletin de la Societ\'{e} Mathematique de France}, vol. 88, 1960.
\bibitem{GK2} Kreisel, G., "Informal rigour and completeness proofs", \emph{Problems in the philosophy of mathematics}, North Holland, Amsterdam, 1967.
\bibitem{BR} Russell, B., \emph{Introduction to mathematical philosophy}, (1919) Routledge, London, 1956.
\bibitem{BRAW} Russell ,B., and Whitehead, A., \emph{Principia mathematica}, (1910-1913) Cambridge University Press, 1962.
\end{thebibliography}

\end{document}
%%%%%
%%%%%
\end{document}