\documentclass[12pt]{report}
% These set up the correct dimensions for your thesis
\textwidth = 5.5 in \textheight = 8.5 in \oddsidemargin = 0.5 in
\evensidemargin = 0.5 in \topmargin = .5 in \headheight = 0.0 in
\headsep = 0.0 in \footskip = .5in
\parskip = 0.3mm
\parindent = 0.5in
\linespread{1.6} %gives the line spacing. the higher the number the larger the spacing.
%Use the following packages as needed.
\usepackage{amsmath,amssymb,url}
\usepackage{multicol}
\usepackage{color}
\usepackage{graphicx}
% A series of colours are defined if needed
% \definecolor{darkblue}{rgb}{0.0,0.250,1.000}
% \definecolor{lightblue}{rgb}{0.0,0.600,1.000}
% \definecolor{cyan}{rgb}{0.000,1.000,1.000}
% \definecolor{yellow}{rgb}{1.000,1.000,0.0}
% \definecolor{magenta}{rgb}{1.000,0.0,1.000}
% \definecolor{orange}{rgb}{1.000,.500,0.0}
% \definecolor{pink}{rgb}{1.000,0.200,0.500}
% \definecolor{grey}{rgb}{0.400,0.400,0.400}
% \definecolor{black}{rgb}{0.0,0.0,0.0}
% \definecolor{white}{rgb}{1.0,1.0,1.0}
% Define theorems as needed
\newtheorem{thm}{Theorem}[chapter] %notice how setting the numbering based on chapter or
\newtheorem{lm}{Lemma}[section]%section changes how things are numbered later
\newtheorem{cor}{Corollary}[thm]
\newtheorem{df}[thm]{Definition}%these are numbered in sequence with theorems.
\newtheorem{pr}{Proclamation}[thm]
\newtheorem{prop}{Proposition}[thm]
\newtheorem{ex}[thm]{Example}
\label{newcommands}
\newcommand{\AB}{\mathbb{A}}
\newcommand{\BB}{\mathbb{B}}
\newcommand{\RR}{\mathbb{R}} % the real numbers
\newcommand{\CC}{\mathbb{C}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\ZZ}{\mathbb{Z}} % the integers
\newcommand{\NN}{\mathbb{N}} % the natural numbers
\newcommand{\TT}{\mathbb{T}}
\newcommand{\SSS}{\mathbb{S}}
\newcommand{\UU}{\mathbb{U}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\WW}{\mathbb{W}}
\newcommand{\seq}[1]{\left\lbrace #1_n \right\rbrace} % a sequence
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\join}[2]{#1 \vee #2}
\newcommand{\Semd}[2]{#1 \rtimes_{\phi} #2}
\newcommand{\SES}[3]{#1 \stackrel{\Phi}{\longrightarrow} #2 \stackrel{\Psi}{\longrightarrow}#3}
\newcommand{\Klein}{\ZZ_2 \times \ZZ_2}
\newcommand{\Z}[1]{\ZZ_{#1}^{\ast}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\CA}{\mathcal{A}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\G}{\mathcal{G}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\CL}{\mathcal{L}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\CS}{\mathcal{S}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\ds}{\displaystyle}
\newcommand{\ls}{\hspace{0.5in}}
\newcommand{\SO}{\mathcal{O}}
\newcommand{\Aa}{\mathfrak{A}}
\newcommand{\Bb}{\mathfrak{B}}
\newcommand{\Cc}{\mathfrak{C}}
\newcommand{\Ff}{\mathfrak{F}}
\newcommand{\Gg}{\mathfrak{G}}
\newcommand{\Kk}{\mathfrak{K}}
\newcommand{\Nn}{\mathfrak{N}}
\newcommand{\Pp}{\mathfrak{P}}
\newcommand{\Rr}{\mathfrak{R}}
\newcommand{\Ss}{\mathfrak{S}}
\newcommand{\Uu}{\mathfrak{U}}
\newcommand{\Ww}{\mathfrak{W}}
\newcommand{\TF}{\{T,F\}}
\newcommand{\B}[1]{\textbf{#1}}
\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\ora}[1]{\overrightarrow{#1}}
\newcommand{\eval}{\big \vert}
\newcommand{\tequiv}{{|\!\!\!=\!=\!\!\!|}\hspace{0.02in}}
\newcommand{\Part}[4]{\{#1 = #2_0, #2_1,\ldots , #2_{#3} = #4\}}
\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\fa}{\forall}
\newcommand{\es}{\exists}
\newcommand{\napprox}{ \ \slash \hspace{-0.17in} \approx}
\newcommand{\nmodels}{ \ \slash \hspace{-0.17in} \models}
\newcommand{\dfem}[1]{\em\textbf{#1}\em}
\newcommand{\Th}[1]{\text{Th } #1}
\newcommand{\Cn}[1]{\text{Cn } #1}
\newcommand{\Mod}[1]{\text{Mod } #1}
\newcommand{\suc}[1]{\bs{S}^{#1}\bs{0}}
\newcommand{\wh}[1]{\widehat{#1}}
\newcommand{\Ast}[2]{\begin{Huge} $\ast$ \end{Huge}}
\newcommand{\pf}{{\bf Proof: }}
\newcommand{\qed}{\hfill\rule[-1pt]{4pt}{8pt}}
\newcommand{\edf}{\hfill$\diamondsuit$\end{df}}
\newcommand{\eex}{\hfill\framebox[1.2\width]{\ }\par\end{ex}}
% Vertical and horizontal space
\newcommand{\vsc}[1]{\vspace{#1cm}}
\newcommand{\hsc}[1]{\hspace{#1cm}}
% Math black board bold
\newcommand{\bb}[1]{\mathbb{#1}}
%These set up the correct title pages
% Insert the name of your thesis in CAPITALS in the space indicated.
\newcommand{\ThesisTitle}{{\Large G\"ODEL'S INCOMPLETENESS THEOREM}}
% Put your name in the space indicated (note that in the second it is all CAPITALS}
\newcommand{\Name}{Christopher Mullins}
\newcommand{\NAME}{CHRISTOPHER MULLINS}
% Put the appropriate term and year here
\newcommand{\Term}{Spring 2013}
% Put the appropriate Committee members here
\newcommand{\CHAIR}{W. DALE GARRAWAY, GRADUATE STUDY COMMITTEE}
\newcommand{\MEMBERa}{RONALD GENTLE, GRADUATE STUDY COMMITTEE}
\newcommand{\MEMBERb}{PARTHA SIRCAR, GRADUATE STUDY COMMITTEE}
% this sets up the first pages of the thesis.
\newcommand{\Thesis}{
\ \
\begin{center}
\ThesisTitle
\underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ }
A Thesis
Presented To
Eastern Washington University
Cheney, Washington
\underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ }
In Partial Fulfillment of the Requirements
for the Degree
Master of Science
\underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ }
By
\Name
\Term
\end{center}
\newpage
% \thispagestyle{empty}
\vspace*{1cm}
\begin{center}
THESIS OF \NAME\ APPROVED BY
\end{center}
\vspace{8cm}
\hspace{-1.75cm}\begin{tabular}{ll}
\underline{\hspace{11.5cm}}&DATE:\underline{\hspace{1.75cm}}\\
\multicolumn{2}{l} \CHAIR \\
&\\
\underline{\hspace{11.5cm}}&DATE:\underline{\hspace{1.75cm}}\\
\multicolumn{2}{l} \MEMBERa \\
&\\
\underline{\hspace{11.5cm}}&DATE:\underline{\hspace{1.75cm}}\\
\multicolumn{2}{l} \MEMBERb \\
\end{tabular}}
\newpage\newpage
\begin{document}
\thispagestyle{empty}
\pagenumbering {roman}
\Thesis
\newpage %Next is the Abstract
\addcontentsline{toc}{section}{\bf Abstract}
\begin{center}
{\bf Abstract}
\end{center}
\begin{minipage}{4.5in}
\hspace{0.375in} This thesis gives a rigorous development of sentential logic and first-order logic as mathematical models of humanity's deductive thought processes. Important properties of each of these models are stated and proved including Compactness results (the ability to prove a statement from a finite set of assumptions), Soundness results (a proof given a set of assumptions will always be true given that set of assumptions), and Completeness results (a statement that is true given a set of assumptions must have a proof from that set of assumptions). Mathematical theories and axiomatizations or theories are discussed in a first-order logical setting. The ultimate aim of the thesis is to state and prove G\"odel's Incompleteness Theorem for number theory.
\end{minipage}
\newpage%Next is the optional Acknowledgements page
\addcontentsline{toc}{section}{\bf Acknowledgements}
\begin{center}
{\bf Acknowledgements}
\end{center}
\begin{minipage}{4.5in}
\hspace{0.375in} First and foremost, I would like to acknowledge the one true God of the Bible for His great grace and mercy for the insight, understanding, wisdom, speed, and accuracy in writing this thesis. I have asked for His help throughout this project, and He has given His help in abundance beyond what I could imagine or deserve. All truth is God's truth.
\hspace{0.375in}Second, I would like to thank my loving and supportive parents Bill and Tammy Mullins who sacrificed so much to give me such a superb educational foundation by homeschooling me. I owe any and all academic success to them.
\hspace{0.375in} Third, I would like to thank the love of my life,\\ Ashley Murray (soon to be Mullins) for her unconditional support and encouragement in this massive and time-consuming project. Thank you Love for being so understanding and patient and for being my continual cheerleader and supporter. We first started dating after I had chosen the topic for this thesis, and you have stuck by me as my best friend throughout the whole process. Thank you so much! I love you!
\hspace{0.375in} Lastly, I would like to thank Dr. Dale Garraway for his critical role as my thesis advisor. There were many times when I thought that I would not be able to get this thesis done on time, but you always encouraged me and gave me helpful feedback and helpful perspectives from which to analyze things. Thank you so much!
\end{minipage}
\newpage%Next is the table of contents.
\tableofcontents
\newpage%next comes the list of table, figures etc. (optional)
\chapter{Introduction}
\pagenumbering {arabic} %We now change from roman numerals to arabic numerals
\setcounter{page}{1} % We start over at page 1
\hspace{0.5in} Statements that are true yet unprovable? Such a notion seems to be self-contradictory and yet that is exactly what G\"odel's Incompleteness Theorem asserts.\\
\noindent\textbf{G\"odel's Incompleteness Theorem}\textit{ Given a decidable set of first-order sentences that are true in number theory, then there is a statement true in number theory that is not provable from our decidable set.}\\
Of course there are terms in this statement that have as yet to be defined, but this statement gives the reader a first sense of the result that this thesis seeks to prove. Think of the set of sentences that the theorem mentions as the center of a circle in the plane. Think of the radius of that circle being associated with the extent of what can be proven from those sentences. Finally think of the entire plane representing the totality of all statements true of number theory. Then what G\"odel's Theorem says is that the radius of the circle must be less than infinity.
It is clear that Kurt G\"odel's Incompleteness Theorem states not only a mathematical result but also touches on meta-mathematics. It raises deep philosophical questions. How do we know mathematical truth? How do we know that we can prove true statements? Is mathematics realism or formalism?
Kurt G\"odel went to university in Europe in the interim period between World Wars I and II. The philosophical air of logical positivism, whose foundational axiom is ``Man is the measure of all things," abounded in Europe during this period. Hence, it is no surprise that mathematicians themselves were mostly formalists who believed that all of mathematics can be reduced to rule following. There is no objective reality of mathematical objects. There is no need to appeal to intuition.
David Hilbert was one of formalism's most vocal proponents in mathematics, and his desire was to spur his colleagues to the systematic formalizing of all mathematical branches. Among his 10 problems that he submitted to the mathematical community in 1900 was the goal of proving arithmetic consistent. This proof would basically demonstrate that arithmetic could be treated as a self-contained formal system without reference to anything else. Kurt G\"odel's Incompleteness Theorem destroyed Hilbert's dream.
G\"odel himself did not share the mathematical mainstream view. Instead Kurt G\"odel was a Platonist believing that mathematical objects exist in reality with the mathematical project a project of discovery and not a meaningless exercise in reasoning and rule following. G\"odel first announced that he had a proof of a version of the Incompleteness Theorem in 1930 in a conference in K\"onigsberg (a conference at which Hilbert was present). Many at the conference paid no heed to the meek G\"odel's understated announcement. One person of interest who did take a great deal of notice was John von Neumann, one of the patriarchs of computability theory. Von Neumann saw the application of G\"odel's Theorem quite quickly.
Although one of the corollaries to the Incompleteness Theorem says that the consistency of arithmetic cannot be proved within arithmetic, solving in the negative one of Hilbert's problems and smashing the formalist enterprise, many took very little heed. In a strange twist, the logical positivists and post-modernists usurped G\"odel's result as supporting their positions of relative knowledge and meaning. This conception continues to this day. G\"odel believed that his work supported just the opposite view: that objective mathematical truth exists. (Note the author obtained much of the historical information given above from \textit{Incompleteness--the Proof and Paradox of Kurt G\"odel} by Rebecca Goldstein.)
Many have cited astonishing philosophical consequences of G\"odel's Theorem including an intriguing argument that the mind must be more than a computer. To fully understand what G\"odel's Incompleteness Theorem says and to judge the soundness of such claims we proceed on a journey through mathematical logic to prove this weighty theorem.
G\"odel's Theorem is a statement about the mathematical model of logic called ``first-order logic." In this thesis, we seek to establish a rigorous mathematical development of sentential and first-order logic as models of humanity's deductive thought processes.
As we proceed through the development of these two mathematical models of logic, we will state, prove, and discuss several important results, important not only for G\"odel's Theorem but also powerful results in their own right. Among these results are soundness, completeness, and compactness results for both models.
After developing the model of first-order logic, we will discuss what formal theories are and what the formal axiomatization of a theory means. We will give concrete examples of these concepts with familiar mathematical structures on our journey to prove G\"odel's Incompleteness Theorem.
Finally, as the main goal of this thesis, we will give a proof of G\"odel's Incompleteness Theorem, discussing the concepts of G\"odel numbering and representability within number theory which are necessary to prove the theorem. The development of this thesis closely follows that of Herbert Enderton in \textit{A Mathematical Introduction to Logic}. Because this is the case, citation is suppressed for ease in reading.
\chapter{Sentential Logic: The Language and Truth Values}
\hspace{0.5in}In our journey to prove G\"odel's famous theorem, we must rigorously establish the mathematical system, first-order logic, in which it is proved. As a prototype to first-order logic, in this chapter we rigorously develop the mathematical system of sentential logic.
\section{Intuition Behind the Sentential Language}
\hspace{0.5in}Our goal behind creating a formal language is to create a model for humanity's deductive thought processes. In the real world, as reasoners, we may put forward the following arguments:
\begin{center}
If Socrates is a man, then he is mortal.\\ Socrates is a man.\\ Therefore, Socrates is mortal.\\ \vspace{0.25in}
\newpage
If Gertrude is a purple oliphant, then it eats grapes.\\ Gertrude is a purple oliphant.\\ Therefore Gertrude eats grapes.\\ \vspace{0.25in}
If it is not the case that you are reading this sentence and you are confused, then you should re-read it.\\ I am confused and I am no longer reading the former sentence.\\ Therefore, I should re-read the first sentence.
\end{center}
Now, as reasoners we can see that the first two arguments make sense \textit{regardless} of whether men exist, Socrates, or purple oliphants named Gertrude. What makes the first two arguments understandable is the inherent structure of the propositions. In a very real way, what it \textit{means} to be Socrates, a man, or a purple oliphant named Gertrude are inconsequential and merely cloud our thinking when we attempt to decide whether the argument is reasonable. Thus, it would be handy to have a formal system, with all the rigor of mathematics, that can capture the essential structure of arguments that we may make.
For instance $\{\bs{(A \rightarrow B)}, \bs{A}\}\vDash \bs{B}$ captures the essential structure of the first two arguments where we accept the two expressions in the set as ``true" and where ``$\vDash$" has an intended meaning of ``therefore." So, we can interpret the symbolism to say that given the statements $\bs{(A \rightarrow B)}$ and $\bs{A}$ the conclusion $\bs{B}$ follows. Whether we translate ``Socrates is a man" and "Man is mortal" as $\bs{A}$ and $\bs{B}$ respectively or whether we translate ``Gertrude is a purple oliphant" and ``Gertrude eats grapes" as $\bs{A}$ and $\bs{B}$ respectively, we have captured in just a few symbols the inherent structure in both arguments above.
In addition to capturing the essential structure of human reasoning with no frills, such a formal language to model human deductive thought processes also avoids the ambiguities of natural languages (languages spoken by humans to express thought). In the third argument, understanding the first premise is the key to knowing whether the argument makes sense. We need to know the conditions for re-reading the first sentence, and the stated condition is it not being the case that you are reading the first sentence and you are confused. Now, the problem is, there is ambiguity in the sentence. Does the ``not" refer to \textit{both} reading the first sentence and being confused or does the ``not" refer to just reading the first sentence. Given how the sentence is written in our natural language (English in this case)--and in a perfectly acceptable way--it could be read with either emphasis. In the first case, either not reading the sentence or not being confused would be a sufficient condition for re-reading the sentence. In the second case, only by not reading the sentence and being confused will be sufficient for re-reading the sentence. Whether we take the intended meaning to be one or the other, the argument still makes sense, since the second premise was that I was no longer reading the sentence, and I was confused, and this premise will be sufficient for both cases. (So, since you, the reader, are no longer reading the first sentence in that argument--you are reading this one!--and you are probably still confused, you should go re-read the first sentence!) The point is that this ambiguity in the natural language clouds the analysis of whether the argument was reasonable.
Now, if we translate ``you are reading this sentence" as $\bs{S}$ and ``you are confused" as $\bs{C}$, and if we have ``$\bs{\neg}$" represent the idea of ``not" and ``$\bs{\wedge}$" represent the idea of ``and", then the ambiguity we have described above is whether ``it is not the case that you are reading this sentence and you are confused" should be translated as $\bs{(\neg(S \wedge C))}$ or as $\bs{((\neg S) \wedge C)}$. Having even the power to \textit{describe} the ambiguity with just these few symbols indicates in and of itself the ability to also \textit{avoid} such ambiguity if we use such a formal language to model deduction.
How would we analyze the reasonableness of arguments if we have such a nice formal language with which to work? The reader is probably already familiar with symbology we have already used and also the notion of truth tables. I can substitute values of true or false in for each symbol, and for all values that cause the premise expressions to be true, the conclusion expression should also be true. The truth table for the first two arguments above would be
\begin{figure}[!h]
\begin{tabular}{|c|c|c|}
\hline
$\bs{A}$ & $\bs{B}$ & $\bs{(A \rightarrow B)}$\\
\hline
$T$ & $T$ &$T$\\
\hline
$T$ & $F$ & $F$\\
\hline
$F$ & $T$ & $T$\\
\hline
$F$ & $F$ & $T$\\
\hline
\end{tabular}
\end{figure}
The only line in the truth table for which both premises $\bs{A}$ and $\bs{(A\rightarrow B)}$ are true is the first, and we see that the conclusion, $\bs{B}$, is also true in this case. So, we would say that our argument is reasonable. All of the foregoing should be familiar to the reader from a mathematical foundations course.
\section{The Need for Formalizing the Intuition}
\hspace{0.5in}Since we will want to use the mathematical structure of our formal language to prove mathematical results about logic (ultimately, G\"odel's Incompleteness Theorem), we need to develop the intuitive, foundations level ideas in a mathematically rigorous way. Above, we have simply thrown around symbols and ideas without any justification whatsoever. However, to establish our intuitive ideas rigorously, we may ask questions like, ``What constitutes a valid formula in our language?", ``How do we know that our valid formulas may be read unambiguously?", and ``Do we (or will we) have sufficient structure in our language to express any proposition?". We will answer these and other such questions in the next couple of chapters. Note that throughout this thesis, to denote formal language symbols we put all such symbols in a bold typeface.
\section{Valid Formulas}
\hspace{0.5in} We begin by establishing the language of sentential logic and precisely describing what a valid formula or grammatically correct statement in that language will be. Note that we assume knowledge of basic set theory which we will use extensively in developing the language.
First, we assume that we are given a countably infinite number (cardinality $\aleph_0$) of symbols to use in the alphabet of our formal language. These symbols are listed in the following table.\\
\begin{figure}[!h]
\begin{tabular}{|c|c|c|}
\hline
\textbf{Symbol} & \textbf{Type} & \textbf{Intended Meaning}\\
\hline
$\bs{(}$ & Logical Grouping Symbol &\\
$\bs{)}$ & Logical Grouping Symbol &\\
$\bs{\neg}$& Logical Connective & ``not"\\
$\bs{\wedge}$ & Logical Connective & ``and"\\
$\bs{\vee}$ & Logical Connective & ``or"\\
$\bs{\rightarrow}$ & Logical Connective& ``implies"\\
$\bs{\leftrightarrow}$ & Logical Connective & ``is equivalent to"\\
$\bs{A_i}$ for each $i \in \NN$ & Sentence Symbol &\\
\hline
\end{tabular}
\end{figure}
\newpage
\noindent We assume that none of these symbols is a finite sequence of the others e.g. $\bs{A_{1989}} \neq \bs{\neg)(\wedge\vee}$.
\begin{df}
An \dfem{expression} in the sentential language is a finite sequence of symbols from the sentential alphabet.
\end{df}
\begin{ex}
Any symbol from the sentential alphabet is an expression. Each of the following are sentential expressions
$$\bs{\rightarrow))))A_{1989}},$$ $$\bs{\rightarrow)))\leftrightarrow(((\neg}, \text{ and}$$ $$\bs{((\neg A_1) \rightarrow (A_2 \wedge (A_3 \vee A_4)))}$$
\end{ex}
Of course, in our language we only want to consider expressions that have the appropriate structure to translate our natural language propositions. So, for instance, $\bs{\rightarrow))))A_{1989}}$ cannot translate any meaningful English proposition whereas $\bs{(\neg(A_1 \wedge A_2))}$ can meaningfully translate the proposition ``It is not the case that I am both reading this sentence and am confused," if we let $\bs{A_1}$ translate the statement ``I am reading this sentence," and let $\bs{A_2}$ translate the statement ``I am confused." So, in our language we want to be able to identify ``grammatically correct" expressions (ones that can meaningful translate a natural language proposition). We will call these grammatically correct expressions \textit{well-formed formulas} or \textit{wffs} for short. There are two primary ways to define wffs.
We start with a top-down approach. Let $\Ss$ be the family of all sets $S$ of expressions in the sentential language that fulfill the following properties: (i): every sentence symbol is in $S$, and (ii): if expressions $\bs{\alpha}$ and $\bs{\beta}$ are in $S$, then so are the expressions $\bs{(\neg \alpha )}, \ \bs{(\alpha \wedge \beta)}, \ \bs{(\alpha \vee \beta), (\alpha \rightarrow \beta)}, \text{ and } \bs{(\alpha \leftrightarrow \beta)} \in S$.
\begin{df}\label{def1Wff}
An expression is a \dfem{well-formed formula (wff)} if it is an expression in the set $\ds \bigcap_{S \in \Ss} S$
\end{df}
\begin{ex}
$\bs{((\neg A_1) \rightarrow (A_2 \wedge (A_3 \vee A_4)))}$ is a wff under this definition. Since all of the sentence symbols are in every $S$ (by property (i) of the family), this means that $\bs{(\neg A_1)}$ and $\bs{(A_3 \vee A_4)}$ are also in every $S$ (by property (ii)). Thus, $\bs{(A_2 \wedge(A_3 \vee A_4))}$ is also in every $S$, and so \\$\bs{((\neg A_1) \rightarrow (A_2 \wedge (A_3 \vee A_4)))}$ is in every $S$, hence in the intersection, hence a wff under the definition.
\end{ex}
The idea with this definition is that we should include all expressions that take the form that we think our wffs should have, either a stand alone sentence symbol or one of the five other forms mentioned above, each of which uses one of our logical connective symbols. But, by including any set of expressions with these properties, we have more expressions than we want. For instance, if $\bs{\rightarrow A_1 \neg}$ happens to be in one such $S$ that has the two properties mentioned above, then we get infinitely many garbage expressions like $\bs{(A_2 \wedge \rightarrow A_1 \neg)}$. We can eliminate such garbage expressions by using the intersection over all such sets to whiddle down to the smallest set that will have the two properties of each set in the family (that the intersection has the two properties of the family may be quickly verified by the reader).
Now for a bottom-up approach. Let $\EE$ designate the set of all expressions using the sentential alphabet. We define several formula building operations on $\EE$ and on $\EE \times \EE$ as follows (note that the bolded parentheses are part of the definition):
$$\F_{\neg}(\bs{\alpha}) = \bs{(\neg \alpha)}$$ $$\F_\wedge(\bs{\alpha},\bs{\beta}) = \bs{(\alpha \wedge \beta)}$$ $$\F_\vee(\bs{\alpha},\bs{\beta}) = \bs{(\alpha \vee \beta)}$$ $$\F_\rightarrow(\bs{\alpha}, \bs{\beta}) = \bs{(\alpha \rightarrow \beta)}$$ $$\F_\leftrightarrow(\bs{\alpha}, \bs{\beta}) = \bs{(\alpha \leftrightarrow \beta)}$$
\begin{df}\label{def2Wff}
An expression is a \dfem{wff} if there is a finite sequence of expressions $$\langle \bs{\alpha_0},\bs{\alpha_1},\ldots,\bs{\alpha_n}\rangle$$ where each $\bs{\alpha_i}$ is a sentence symbol, $\bs{\alpha_i} = F_\neg(\bs{\alpha_j})$ for $j*m$. Then for all $1\leq i \leq m$, $\bs{a_i} = \bs{g_i}$, and $\bs{a_{m+1}} = \bs{\flat}$. So, $\langle \bs{a_1},\bs{a_2},\ldots,\bs{a_m}\rangle = \bs{\gamma}$, a wff. However, since $\langle \bs{a_1},\bs{a_2},\ldots,\bs{a_m}\rangle$ is a proper initial segment of $\bs{\alpha}$, a wff, it must be left-heavy by the preceding lemma, and cannot be a wff, a contradiction. Hence, $m = n$ ($\bs{\alpha} = \bs{\gamma}$), implying that $\bs{\sharp} = \bs{\flat}$. Since the lengths of the wffs we assumed to be equal must be the same we must have $\bs{\beta} = \bs{\delta}$. We have not only shown that the images of $\F_\sharp$ and $\F_\flat$ must be pairwise disjoint, but also (if we replace $\bs{\flat}$ with $\bs{\sharp}$ in our initial assumption of equality), that $\F_\sharp$ is one-to-one for each $\bs{\sharp} \in \{\bs{\wedge, \vee, \rightarrow, \leftrightarrow} \}$. It is clear that $\F_\neg$ will also be one-to-one.
Suppose that $\F_\sharp\eval_{\W^2}(\bs{\alpha}, \bs{\beta}) = \F_\neg\eval_\W(\bs{\gamma})$ where $\bs{\sharp}$ is as above. Then we have $\bs{(\alpha \sharp \beta)} = \bs{(\neg \gamma)}$. Thus, $\bs{\alpha \sharp \beta)} = \bs{\neg \gamma)}$. This cannot happen by the second of the two notes we made before the start of the proof. In fact then, $\F_\sharp\eval_{\W^2}(\bs{\alpha}, \bs{\beta}) \neq \F_\neg\eval_\W(\bs{\gamma})$ for any $(\bs{\alpha},\bs{\beta}) \in \W \times \W$ and $\bs{\gamma} \in \W$.
By the first note before the start of the proof, the images of the formula-building operations together with the set of sentence symbols are all pairwise disjoint since a formula-building operation always adds a left parenthesis. Hence we have shown that $\W$ is freely generated from the set of sentence symbols by the five formula-building operations.\qed
\end{pf}
Essentially the wffs being freely generated from the set of sentence symbols by the five formula building operations says that given a wff, it can be uniquely deconstructed back into its constituent wffs i.e. there is one and only one way to build that particular wff using the formula-building operations. This result will be crucial in developing the notion of truth assignments, which we now do.
\section{Truth Assignments}
\hspace{0.5in}Now that we have developed our alphabet, defined what grammatically correct statements in the sentential language are, and shown that there is no ambiguity in reading these statements, we want to talk about how one wff will follow logically from another wff. Remember that with sentential logic, we're modeling deductive thought. If we think of a wff as providing the structure into which we can translate an English statement or proposition, we want to be able to model what a deduction in English would look like in our language. A deduction in English happens when given a statement, if we know the statement is true, it must also be true that another statement is true. We deduce the second statement from the first. So, in our formal language, we may think of one wff being deducible from another if when the first wff is true, the second wff \textit{must} also be true. For example, if the wff $\bs{(A_1 \wedge A_2)}$ is a translation from English into our formal sentential language of a true proposition, we should be able to deduce $\bs{A_1}$ from our initial wff. Notice that \textit{what} proposition we are translating into the wff $\bs{(A_1 \wedge A_2)}$ is inconsequential but merely the \textit{truth value} of that proposition.
In a mathematics foundations course, we are taught to assign truth values (usually symbolized with $T$ or $F$) to each of the sentence symbols involved in the wffs at hand and then calculate the truth values of the constituent wffs that make up the wff or wffs under consideration. This process can be achieved by filling out a row in a truth table, and we may fill out such a row for each possible combination of truth values for the sentence symbols involved. We then say that wff $\bs{\alpha}$ implies wff $\bs{\beta}$ if whenever there is a row in the truth table where $\bs{\alpha}$ is true, in the same row the wff $\bs{\beta}$ is also true. Since we are attempting to mathematically model deductive thought, we must rigorously develop these notions. First, we need to mathematically develop how to assign truth values to wffs, formalizing our more intuitive foundations notions. To do this, we develop more general notions of recursive functions.
\subsection{Recursion}
\hspace{0.5in} Our idea of assigning truth values to our wffs is a recursive idea. To figure out the truth value of the current wff under consideration, we need to look at the truth value of the wff last in line. In a more general setting we have a set $\UU$ (like the set of all expressions), a subset $B$ of $\UU$ (like the set of all sentence symbols) and two functions $f:\UU\times \UU \longrightarrow \UU$ and $g:\UU\longrightarrow \UU$ where $C \subseteq \UU$ is the set generated from $B$ by $f$ and $g$ ($C$ would correspond to the set of all wffs). Our goal is to define a function on $C$ recursively, that is we want a function $\ol{h}$ with domain $C$ such that\\
\begin{itemize}
\item[1.] We have rules for computing $\ol{h}(x)$ for $x \in B$
\item[2a.] We have rules for computing $\ol{h}(f(x,y))$ based on $\ol{h}(x)$ and $\ol{h}(y)$
\item[2b.] We have rules for computing $\ol{h}(g(x))$ based on $\ol{h}(x)$.
\end{itemize}
These will be our only three cases we need to explore since $C$ is generated from $B$ and thus elements in $C$ take the form, $x \in B$, $f(x,y)$ for $x,y \in C$, or $g(x)$ for $x \in C$. The idea is that given some $c \in C$ and if we desire to compute $\ol{h}(c)$, then we merely need to see how $c$ is generated by $f$ and $g$ and reverse engineer that construction until we eventually reach the ``bottom" where we see what $\ol{h}$ does to the elements of $B$ from which $c$ is generated.
\begin{ex}
Let $\UU = \RR$, $B = \{0\}$, $S(x) = x+1$, and $C = \NN$ as discussed above. Now define $$\ol{h}(0) = 0$$ $$\ol{h}(S(x)) = S(x) + \ol{h}(x)$$ So,\\ $ \begin{array}{lll}
\ol{h}(4)&= &\ol{h}(S(3))\\ &= &S(3) + \ol{h}(3)\\ &=& 4 + \ol{h}(S(2))\\ &= &4 + (S(2) + \ol{h}(2))\\ &=& 4+3 + \ol{h}(S(1))\\ &=& 4+3+S(1) + \ol{h}(1)\\& = &4+3+2+S(0) + \ol{h}(0)\\& =& 4+3+2+1+0\\ \end{array}$\\ So, $\ol{h}(x) = \ds\frac{x(x+1)}{2}$
\end{ex}
The question arises as to whether such a function always exists that fulfils the rules given? It does not.
\begin{ex}
Let $U = \RR$, $B = \{0\}$, $f(x,y) = x\cdot y$, and $g(x) = x+1$. Then $C = \NN$. We attempt to define $\ol{h}$ as a function as follows:
\begin{itemize}
\item[1.] $\ol{h}(0) = 0$
\item[2a.] $\ol{h}(f(x,y)) = f(\ol{h}(x),\ol{h}(y))$
\item[2b.] $\ol{h}(g(x)) = \ol{h}(x) + 2$
\end{itemize}
On one hand $$\begin{array}{lcl}\ol{h}(1)& = &\ol{h}(f(g(0),g(0)))\\& =& f(\ol{h}(g(0)),\ol{h}(g(0)))\\& = &f(\ol{h}(0) + 2,\ol{h}(0)+2)\\ & = &f(2,2) = 4\\\end{array}$$ On the other hand $\ol{h}(1) = \ol{h}(g(0)) = \ol{h}(0) + 2 = 2$. Thus, $\ol{h}$ cannot be a function. The main problem here is that 1 is not uniquely generated from $f$ and $g$ since $Im(g) \cap Im(f) \neq \emptyset$.
\end{ex}
Since it will not always be the case that such a recursive function exists, we seek to establish conditions for when such a recursive function will exist. These conditions are given by the following Theorem.
\begin{thm}[The Recursion Theorem]
Assume that the subset $C$ of $\UU$ is freely generated from $B$ by $f$ and $g$, where $$f:\UU \times \UU \longrightarrow \UU \hspace{0.25in} g:\UU \longrightarrow \UU.$$ Further assume that $V$ is a set and that $F$, $G$, and $h$ are functions such that $$h:B\longrightarrow V \hspace{0.25in}
F:V \times V \longrightarrow V \hspace{0.25in} G:V\longrightarrow V.$$ Then there is a unique function $$\ol{h}:C \longrightarrow V$$ such that
\begin{itemize}
\item[(i)] For $x \in B$, $\ol{h}(x) = h(x)$.
\item[(ii)] For $x,y \in C$,
\end{itemize}
$$\ol{h}(f(x,y)) = F(\ol{h}(x),\ol{h}(y)) \hspace{.25in} \ol{h}(g(x)) = G(\ol{h}(x)).$$
\end{thm}
Viewed algebraically, the conclusion of this theorem says that any map $h$ of $B$ into $V$ can be extended to a homomorphism $\ol{h}$ from $C$ (with operations $f$ and $g$) into $V$ (with operations $F$ and $G$). The idea behind the theorem is that we can assign values from a new set $V$ to our basis elements in $B$ and then compute the value of my input into $\ol{h}$ using operations on the new set $V$ following the same structure for how my input into $\ol{h}$ was uniquely constructed in $C$. For us, the $h$ function will be a truth assignment for the sentence symbols, and then $\ol{h}$ will give us the ability to calculate the truth value of any sentential wff given this truth assignment.
\begin{pf}
We will call a function $v$ \textit{acceptable} if the following statements hold for $v$:
\begin{itemize}
\item[1.] $Dom(v)\subseteq C$ and $Im(v)\subseteq V$.
\item[2.] $x \in B\cap Dom(v)$ implies that $v(x) = h(x)$
\item[3.] $f(x,y),g(x)\in Dom(v)$ implies that $x,y \in Dom(v)$ and $$v(f(x,y)) = F(v(x),v(y)) \text{ and } v(g(x)) = G(v(x))$$
\end{itemize}
Let $K$ be the set of all acceptable functions. We must first show that $K$ is non-empty. Consider $h:B \longrightarrow V$. Property (1) is certainly fulfilled as is (2). Since $C$ is freely generated from $B$, $B$, $Im(f\eval_{C^2})$, and $Im(g\eval_C)$ are pairwise disjoint. Thus, no element of $B$ can take the form $f(x,y)$ or $g(x)$ where $x,y \in C$. Hence, (3) is vacuously true. Hence, $h$ is an acceptable function, and hence, $K \neq \emptyset$.
Now let $\ds \ol{h} = \bigcup_{v \in K}v$. So $(x,y) \in \ol{h}$ if and only if $v(x) = y$ for some $v \in K$. We seek to verify that $\ol{h}$ is acceptable. First we must show that it is indeed a function. Certainly we may say that it is a relation, that is $\ol{h} \subseteq C \times V$. Let $S = \{x \in C:$ For at most one $y$, $(x,y) \in \ol{h}\}$. We seek to show that $S$ is inductive. Let $x \in B$. Suppose $(x,y) \in \ol{h}$. Then there is $v \in K$ such that $v(x) = y$. Since $x \in B$ and $v$ is acceptable, $y = h(x)$. Thus, there is at most one $y$ such that $(x,y) \in \ol{h}$ for $x \in B$. Thus, $B \subseteq S$. Now let $x_1, x_2$ in $S$ Suppose $(f(x_1,x_2),y) \in \ol{h}$. Then there exists $v \in K$ such that\\ $v(f(x_1,x_2)) = y$. Since $v$ is acceptable it fulfils (2) above. Thus we have $$y =v(f(x_1,x_2)) = F(v(x_1),v(x_2)).$$ So, $x_1,x_2 \in Dom(v)$ i.e. there exist $y_1,y_2 \in V$ such that $v(x_1) = y_1$ and $v(x_2) = y_2$. Thus $(x_1,y_1), (x_2,y_2) \in \ol{h}$ and since $x_1,x_2 \in S$, $y_1$ and $y_2$ are the only values paired with $x_1$ and $x_2$ respectively. Now if $v' \in K$ such that $v'(f(x_1,x_2)) = y'$ (in which case $(f(x_1,x_2),y') \in \ol{h}$), we have $$F(v(x_1),v(x_2)) = y'$$ which implies that $F(y_1,y_2) = y = y'$ since $F$ is assumed to be a function. Thus, for at most one $y$ we have $(f(x_1,x_2),y) \in \ol{h}$. Hence, $f(x_1,x_2) \in S$. Similarly for $g(x_1)$. So, $S$ is closed under $f$ and $g$, and by the Induction Principle, we must have $S = C$. Since $Dom(\ol{h}) \subseteq C$, we may say that for every $x \in Dom(\ol{h})$ there exists a unique $y$ such that $(x,y) \in \ol{h}$. Thus, $\ol{h}$ is by definition, a function.
We next, seek to show that $\ol{h}$ is acceptable. Property (1) certainly holds. For property (2), let $x \in Dom(\ol{h})\cap B$. Then $(x,y) \in \ol{h}$ for some unique $y \in V$. By the definition of $\ol{h}$, there exists $v \in K$ such that $(x,y) \in v$. Since $x \in Dom(v)\cap B$ and $v$ is acceptable, $y = v(x) = h(x)$. Thus, $\ol{h}(x) = h(x)$ for $x \in Dom(\ol{h})\cap B$, and property (2) holds.
For property (3), let $f(x_1,x_2) \in Dom(\ol{h})$ for $x_1, x_2 \in C$. Thus, there is a unique $y \in V$ such that $(f(x_1,x_2),y) \in \ol{h}$, and by definition of $\ol{h}$, there is $v \in K$ such that $v(f(x_1,x_2)) = y$. Since $v$ is acceptable, $x_1,x_2 \in Dom(v)\subseteq Dom(\ol{h})$, and $$v(f(x_1,x_2)) = F(v(x_1),v(x_2)) = y.$$ So $(x_1,v(x_1)), (x_2, v(x_2))\in v \subseteq \ol{h}$. Hence $\ol{h}(x_1) = v(x_1)$ and $\ol{h}(x_2) = v(x_2)$. Thus $\ol{h}(f(x_1,x_2)) = y = v(f(x_1,x_2)) = F(v(x_1),v(x_2)) = F(\ol{h}(x_1),\ol{h}(x_2))$. Similarly, if $g(x_1) \in Dom(\ol{h})$ for $x_1 \in C$, then $x_1 \in Dom(\ol{h})$ and \\$\ol{h}(g(x_1)) = G(\ol{h}(x_1))$. So, property (3) holds, and $\ol{h}$ is acceptable.
Now we show that $Dom(\ol{h})$ is $C$. To do this, we show that $Dom(\ol{h})$ is inductive. As shown earlier, $h$ is acceptable with $B = Dom(h)\subseteq Dom(\ol{h})$. Now let $x_1, x_2 \in Dom(\ol{h})$. Our goal is to demonstrate that both $f(x_1,x_2)$ and $g(x_1)$ are in $Dom(\ol{h})$. We do this by creating a new function that has $f(x_1,x_2)$ in its domain and then show that this new function is a subset of the old function.
Let $\ol{h}' = \ol{h} \cup \{(f(x_1,x_2),F(\ol{h}(x_1), \ol{h}(x_2))\}$. We show that $\ol{h}'$ is an acceptable function. It will be a function since $\ol{h}$ is a function and by Property (3) applied to $\ol{h}$.
Property (1) of acceptable functions clearly holds for $\ol{h}'$ as does property (2) since $Im(f\eval_{C^2}) \cap B = \emptyset$, so that $f(x_1,x_2) \notin B$. Hence, $\ol{h}'(x) = \ol{h}(x) = h(x)$ for $x \in B$. It is also clear that property (3) of acceptable functions holds for $\ol{h}'$ since the property holds for all $(x,y) \in \ol{h} \subseteq \ol{h}'$ and $$\ol{h}'(f(x_1,x_2)) = F(\ol{h}'(x_1), \ol{h}'(x_2)).$$ Hence, $\ol{h}'$ is acceptable, and is in $K$. But then, $\ol{h}' \subseteq \ol{h}$, and we have \\$f(x_1,x_2) \in Dom(\ol{h})$. Similarly, $g(x_1) \in Dom(\ol{h})$. Thus, by the Induction Principle, $Dom(\ol{h}) = C$.
At this point we have shown that we have a function $\ol{h}:C\longrightarrow V$ that is an acceptable function. We now must show that this function is unique. Suppose we have $\ol{h}':C\longrightarrow V$ that is also acceptable. Let $S$ be the set on which $\ol{h}$ and $\ol{h}'$ agree. $B \subseteq S$ since for all $x \in B$, $\ol{h} = h(x)= \ol{h}'$. Let $x_1, x_2 \in S$, then $f(x_1,x_2) \in C = Dom(\ol{h}) = Dom(\ol{h}')$, and $$\ol{h}(f(x_1,x_2)) = F(\ol{h}(x_1),\ol{h}(x_2)) = F(\ol{h}'(x_1),\ol{h}'(x_2)) = \ol{h}'(f(x_1,x_2))$$ since $\ol{h}(x_i) = \ol{h}'(x_i)$ for $i = 1,2$ by assumption. Hence $f(x_1,x_2) \in S$. Similarly, $g(x_1) \in S$. Thus, by the Induction Principle $S = C$, and hence $\ol{h} = \ol{h}'$. Thus, we have proved the Recursion Theorem.\qed
\end{pf}
We have proved the Recursion Theorem for free generation by two functions $f$ and $g$, but of course the results may be extended to free generation by any finite number of functions. To get a sense of what the Recursion Theorem gives us, we consider the following examples.
\begin{ex}
Recall that $\NN$ is generated from $\{0\}$ by the successor function $S$. Since $S$ is one-to-one and $Im(S)\cap\{0\} = \emptyset$, then we may say that $\NN$ is freely generated from $\{0\}$ by $S$. So, by the Recursion Theorem, for any set V, any $a\in V$, and any $F:V\longrightarrow V$ with $h(0) = a$, there will exist a unique $\ol{h}$ such that $\ol{h}(0) = a$ and for $n \in \NN$, $\ol{h}(S(n)) = F(\ol{h}(n))$
As a specific case, take $V$ to be the set of prime numbers, and let $$h(0) = p_0 = 2.$$ Let $F(p_i) = p_{i+1}$ ($p_i$ is the $i$th prime number). Then, $$\ol{h}(4) = \ol{h}(S(3)) = F(\ol{h}(3)) = F(F(F(F(h(0))))) = F(F(F(F(2))))=p_5 = 11.$$
\end{ex}
\begin{ex}
The wffs are freely generated from the set of sentence symbols by the five formula building operations. Let $\CS$ denote the set of sentence symbols, $\W$ the set of wffs, and $V = \ZZ^+$. Let $h:\CS\longrightarrow \ZZ^+$ defined by $h(\bs{A}) = 1$ for $\bs{A} \in \CS$. Let $G_\neg: \ZZ^+ \longrightarrow\ZZ^+$ $G_\sharp:\ZZ^+\times \ZZ^+ \longrightarrow \ZZ^+$ be defined by $G_{\neg}(n) = 3 + n$ and $G_\sharp(n,m) = 3 + n + m$ for $\bs{\sharp} \in \{\bs{\vee, \wedge, \rightarrow, \leftrightarrow}\}$. The Recursion Theorem then states that there exists a unique $\ol{h}:\W\longrightarrow \ZZ^+$ such that $\ol{h}(\bs{A}) = 1$ for each $\bs{A} \in \CS$ and $\ol{h}(\bs{(\neg\alpha)}) = \ol{h}(\F_\neg(\bs{\alpha)})= G_\neg(\ol{h}(\bs{\alpha})) = 3 + \ol{h}(\bs{\alpha})$ and $\ol{h}(\bs{(\alpha\sharp \beta)}) = \ol{h}(\F_\sharp(\bs{\alpha},\bs{\beta})) = G_\sharp(\ol{h}(\bs{\alpha}),\ol{h}(\bs{\beta})) = 3 + \ol{h}(\bs{\alpha}) + \ol{h}(\bs{\beta})$. $\ol{h}$ simply gives the length of each wff, finding the length by ``peeling" off and counting symbols until it reaches the sentence symbols.
\end{ex}
Having now established some general recursion results, we now return to our primary discussion of formalizing the notion of truth assignments for wffs in the sentential language.
We will consider the set $\TF$ where $T$ is thought of as \textit{truth} and $F$ is thought of as \textit{falsity}. We could just as easily think of this set as $\{1,0\}$, the way a computer ``thinks" of truth and falsity. Let $\CS$ be the set of sentence symbols, and suppose we are given $v:\CS\longrightarrow \{T,F\}$. Such a function will be what we mean when we use the term \textit{truth assignment}.
We of course have the set of wffs $\W$ being freely generated by the five formula building operations: $\F_\neg, \F_\sharp$ where $\bs{\sharp} \in \{\bs{\vee, \wedge, \rightarrow, \leftrightarrow}\}$. Let $\G_\neg: \TF \longrightarrow \TF$ and $\G_\sharp:\TF \times \TF \longrightarrow \TF$ for $\bs{\sharp} \in \{\bs{\vee, \wedge, \rightarrow, \leftrightarrow}\}$ where $$ \G_\neg(V) =\left\lbrace \begin{array}{cl} T & \hbox{if }V = F\\ F & \hbox{if } V = T\\ \end{array} \right.$$
$$\G_\vee (V_1 , V_2) = \left\lbrace \begin{array}{cl} F & \hbox{if }V_1 = F \hbox{ and } V_2 = F\\ T & \hbox{otherwise}\\ \end{array} \right.$$
$$\G_\wedge (V_1 , V_2) = \left\lbrace \begin{array}{cl} T & \hbox{if }V_1 = T \hbox{ and } V_2 = T\\ F & \hbox{otherwise}\\ \end{array} \right.$$
$$\G_\rightarrow (V_1 , V_2) = \left\lbrace \begin{array}{cl} F & \hbox{if }V_1 = T \hbox{ and } V_2 = F\\ T & \hbox{otherwise}\\ \end{array} \right.$$
$$\G_\leftrightarrow (V_1 , V_2) = \left\lbrace \begin{array}{cl} T & \hbox{if }V_1 = V_2\\ F & \hbox{otherwise}\\ \end{array} \right.$$
These are the natural truth value operations for ``not", ``and", etc. Applying the Recursion Theorem, we are guaranteed the existence of unique $\ol{v}: \W \longrightarrow \TF$ where $\ol{v}(\bs{A}) = v(\bs{A})$ for $\bs{A} \in \CS$, and where \\$\ol{v}(\F_\neg(\bs{\alpha})) = \G_\neg(\ol{v}(\bs{\alpha}))$ and $\ol{v}(\F_\sharp(\bs{\alpha},\bs{\beta})) = \G_\sharp(\ol{v}(\bs{\alpha}),\ol{v}(\bs{\beta}))$ for ${\bs{\sharp} \in \{\bs{\vee, \wedge, \rightarrow, \leftrightarrow}\}}$. Equivalently, $\ol{v}(\bs{(\neg \alpha)}) = \G_\neg(\ol{v}(\bs{\alpha}))$ and $\ol{v}(\bs{(\alpha \sharp \beta)}) = \G_\sharp(\ol{v}(\bs{\alpha}),\ol{v}(\bs{\beta}))$.
The moral of the story is that given a wff, and a given assignment of truth and falsity to each of the sentence symbols involved in the wff, we can compute a unique truth value of the wff by looking at the truth value of its pieces. The existence of a unique truth value for any wff given truth assignments for each of its sentence symbols comes as a consequence of the wffs being freely generated from the sentence symbols i.e. the Unique Readability Theorem. We can only read each wff in one way and so when we assign truth values to each of its sentence symbols, we can only obtain one truth value for the wff.
\begin{ex}
Consider the wff $\bs{(A_1 \wedge A_2)}$ and let $v: \CS \longrightarrow \TF$ where $v(\bs{A_1}) = T$, $v(\bs{A_2}) = F$, and $v(\bs{A_i}) = T$ for $i >2$. By the Recursion Theorem, we have $\ol{v}:\W \longrightarrow \TF$, and $$\ol{v}(\bs{(A_1 \wedge A_2)}) = \G_\wedge(\ol{v}(\bs{A_1}),\ol{v}(\bs{A_2})) = \G_\wedge(v(\bs{A_1}),v(\bs{A_2}))= \G_\wedge(T,F) = F$$
\end{ex}
\begin{ex}
Consider the wff $$\begin{array}{ll}\bs{(((\neg(A_1 \wedge A_2)) \rightarrow ((\neg A_1) \vee (\neg A_2)))\leftrightarrow ( ((\neg A_1) \vee (\neg A_2))\rightarrow} &\\ \bs{ (\neg(A_1 \wedge A_2))))} &\\ \end{array}$$ We use the same $v$ as in the previous example. To speed computation, instead of writing, say $\G_\neg(T) = F$ or $\G_\wedge(T,F) = F$ we will write $\bs{(\neg} T\bs{)} = F$ and\\ $\bs{(}T\bs{\wedge} F\bs{)} = F$. So with the wff at hand $$\begin{array}{ll}&\ol{v}(\bs{(((\neg(A_1 \wedge A_2)) \rightarrow ((\neg A_1) \vee (\neg A_2)))\leftrightarrow ( ((\neg A_1) \vee (\neg A_2))\rightarrow}\\ &\bs{ (\neg(A_1 \wedge A_2))))})\\ = &\bs{(((\neg(}T \bs{\wedge} F\bs{)) \rightarrow ((\neg} T\bs{) \vee (\neg} F\bs{)))\leftrightarrow ( ((\neg} T\bs{) \vee (\neg }F\bs{))\rightarrow} \\ &\bs{ (\neg(}T \bs{\wedge} F\bs{))))}\\
= & \bs{(((\neg }F\bs{) \rightarrow (}F \bs{ \vee }T\bs{))\leftrightarrow ( (}F \bs{\vee} T\bs{)\rightarrow (\neg} F\bs{)))}\\
= & \bs{((}T \bs{\rightarrow} T\bs{)\leftrightarrow (} T\bs{ \rightarrow }T\bs{))}\\
= & \bs{(}T\bs{\leftrightarrow} T\bs{)}\\
= & T\\
\end{array} $$
\end{ex}
Given these examples we see at once that each row of a truth table represents a truth assignment from the sentence symbols to the set $\TF$.
\begin{ex}\label{deMorgan}
The following table lists all possible truth assignments for the wff in the bottom column.\\
\begin{figure}[!h]
\begin{scriptsize}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\bs{A_1}$ & $\bs{A_2}$ & $\bs{(\neg A_1)}$ & $\bs{(\neg A_2)}$ & $\bs{(A_1 \wedge A_2)}$ & $\bs{(\neg (A_1 \wedge A_2))}$ & $\bs{((\neg A_1) \vee (\neg A_2))}$ \\
\hline
$T$ & $F$ & $F$ & $T$ & $F$ & $T$ &$T$ \\
\hline
$T$ & $T$ & $F$ & $F$ & $T$ & $F$ &$F$ \\
\hline
$F$ & $F$ & $T$ & $T$ & $F$ & $T$ &$T$ \\
\hline
$F$ & $T$ & $T$ & $F$ & $F$ & $T$ &$T$ \\
\hline
\end{tabular}
\begin{tabular}{|c|}
\hline
$\bs{((\neg (A_1 \wedge A_2))}$ $\bs{ \leftrightarrow ((\neg A_1) \vee (\neg A_2))}$\\
\hline
$T$\\
\hline
$T$\\
\hline
$T$\\
\hline
$T$\\
\hline
\end{tabular}\\
\end{scriptsize}
\end{figure}\\
Each row corresponds to a truth assignment from $\CS$ to $\TF$ with the values in the first two columns giving the assignment on the sentence symbols of interest. As we move from left to right in this particular truth table, we are computing the truth value of larger and larger constituent pieces of the wff in the top row of the bottom column. Row 1 corresponds to $v$ in the previous two examples, and our computations from columns 3 to 6 are via $\ol{v}$ given to us by the Recursion Theorem.
\end{ex}
Of course, the truth table above indicates that no matter what truth assignment we make for the sentence symbols in the wff $$\bs{((\neg (A_1 \wedge A_2)) \leftrightarrow ((\neg A_1) \vee (\neg A_2))},$$ the wff will always be true. Analyzing the truth value of wffs given a truth assignments for the sentence symbols involved is at the heart of our design of modeling human deductive thought processes. We have characterized a deduction as occurring when the truth of one statement guarantees the truth of another statement. The deduction comes from the inherent structure of the statement. Thus, in the case above, no matter what natural language (English) statements the sentence symbols $\bs{A_1}$ and $\bs{A_2}$ are intended to translate, the wff $\bs{((\neg (A_1 \wedge A_2)) \leftrightarrow ((\neg A_1) \vee (\neg A_2))}$ will always be a truism. Truth assignments give us the tool for modeling and analyzing the raw logical structure in statements and hence the deducibility of one statement from another. We now formalize the notion of deducibility within our sentential language.
\section{Tautological Implication}
We begin with some definitions which will aid our discussion.
\begin{df}\label{sentSatis}
We say that $v: \CS \longrightarrow \TF$ \dfem{satisfies} wff $\bs{\varphi}$ if $\ol{v}(\bs{\varphi}) = T$.
\end{df}
\begin{df}
The set of wffs $\Sigma$ \dfem{tautologically implies} the wff $\bs{\tau}$ and we write $\Sigma \vDash \bs{\tau}$ if every truth assignment on the set of sentence symbols that satisfies every wff in $\Sigma$ also satisfies the wff $\bs{\tau}$.
\end{df}
Notice, as we have implicitly done in the truth table in Example 2.37, we need only consider what a particular truth assignment will do to the sentence symbols in the wffs in question. There will of course be infinitely many truth assignments on the set of \textit{all} sentence symbols such that $v(\bs{A_1}) = T$ and $v(\bs{A_2}) = T$, but we only really care about what these truth assignments will do to the sentence symbols $\bs{A_1}$ and $\bs{A_2}$.
\label{edit progress}
More formally, we could define an equivalence relation between truth assignments. Let $\K$ denote the set of all sentence symbols in $\Sigma$ and $\bs{\tau}$. Then say that truth assignments $v_1$ and $v_2$ are equivalent $(v_1 \sim v_2)$ if and only if $v_1\eval_\K = v_2\eval_\K$. This will clearly be an equivalence relation. We see then that if we take a representative from each equivalence class and compute the truth value for each wff in $\Sigma \cup \{\bs{\tau}\}$ with each representative truth assignment, we will have computed the truth value of each wff in question for \textit{all} truth assignments.
So in our truth table above, although we really only computed the truth value of $\bs{((\neg (A_1 \wedge A_2)) \leftrightarrow ((\neg A_1) \vee (\neg A_2))}$ under finitely many truth assignments, this is sufficient since the truth assignments chosen and represented in the table are each representatives of the equivalence classes under the equivalence relation discussed above.
Tautological implication in sentential logic is our model for a logical deduction. It models our intuitive idea that if the premises (the set $\Sigma$) of a valid implication are true, then the conclusion of the implication we are trying to establish ($\bs{\tau}$) cannot fail to be true.
\begin{ex}
Consider $\Sigma = \{\bs{A_1}, \bs{(A_1\rightarrow A_2)}\}$ and $\bs{\tau} = \bs{A_2}$.\\
\begin{figure}[!h]
\begin{scriptsize}
\begin{tabular}{|c|c|c|}
\hline
$\bs{A_1}$ & $\bs{A_2}$ & $\bs{(A_1 \rightarrow A_2)}$\\
\hline
$T$ & $T$ &$T$\\
\hline
$T$ & $F$ & $F$\\
\hline
$F$ & $T$ & $T$\\
\hline
$F$ & $F$ & $T$\\
\hline
\end{tabular}
\end{scriptsize}
\end{figure}\\
We see here that only for row 1 in the truth table are all of the elements in $\Sigma$ satisfied, and we have that $\bs{\tau}$ is also satisfied. We never have a situation where the elements of $\Sigma$ are true but $\bs{\tau}$ is false. Thus, we may say that $\{\bs{A_1}, \bs{(A_1\rightarrow A_2)}\} \vDash \bs{A_2}$. This is the logical rule ``modus ponens."
\end{ex}
\begin{ex}
Consider $\Sigma = \{\bs{(\neg A_1)}, \bs{(A_1\rightarrow A_2)}\}$ and $\bs{\tau} = \bs{(\neg A_2)}$.\\
\begin{figure}[!h]
\begin{scriptsize}
\begin{tabular}{|c|c|c|c|c|}
\hline
$\bs{A_1}$ & $\bs{A_2}$ & $\bs{(\neg A_1)}$ & $\bs{(\neg A_2)}$ & $\bs{(A_1 \rightarrow A_2)}$\\
\hline
$T$ & $T$ & $F$ & $F$ & $T$\\
\hline
$T$ & $F$ & $F$ & $T$ & $F$\\
\hline
$F$ & $T$ & $T$ & $F$ & $T$\\
\hline
$F$ & $F$ & $T$ & $T$ & $T$\\
\hline
\end{tabular}
\end{scriptsize}
\end{figure}\\
Now we have two rows where the elements of $\Sigma$ are satisfied, rows 3 and 4. Notice however that $\bs{(\neg A_2)}$ is not satisfied in row 3. So $\Sigma$ does not tautologically imply $\bs{\tau}$ in this case. This represents the fallacy of denying the consequent.
\end{ex}
\begin{ex}
Consider $\Sigma = \{\bs{(\neg A_2)}, \bs{(A_1\rightarrow A_2)}\}$ and $\bs{\tau} = \bs{(\neg A_1)}$. \\
\begin{figure}[!h]
\begin{scriptsize}
\begin{tabular}{|c|c|c|c|c|}
\hline
$\bs{A_1}$ & $\bs{A_2}$ & $\bs{(\neg A_1)}$ & $\bs{(\neg A_2)}$ & $\bs{(A_1 \rightarrow A_2)}$\\
\hline
$T$ & $T$ & $F$ & $F$ & $T$\\
\hline
$T$ & $F$ & $F$ & $T$ & $F$\\
\hline
$F$ & $T$ & $T$ & $F$ & $T$\\
\hline
$F$ & $F$ & $T$ & $T$ & $T$\\
\hline
\end{tabular}
\end{scriptsize}
\end{figure}\\
Row 4 is the only row of the truth table for which the elements of $\Sigma$ are satisfied. For this row, $\bs{(\neg A_1)}$ is also satisfied and so $$\{\bs{(\neg A_2)}, \bs{(A_1\rightarrow A_2)}\} \vDash \bs{(\neg A_1)}.$$This is contraposition.
\end{ex}
Having given a few examples that give a sense of what tautological implication is, we now consider a few special cases.\\
\noindent \textbf{Case 1:} What if $\Sigma$ is empty? It is then a vacuously true statement to say that every truth assignment $v$ satisfies every member of $\Sigma$ (i.e the implication ``If $\bs{\varphi} \in \Sigma$, then $v$ satisfies $\bs{\varphi}$" can never be false since the antecedent is false, and thus the statement holds true for any truth assignment $v$). So, we may say ``$\emptyset \vDash \bs{\tau}$" if and only if every truth assignment satisfies $\bs{\tau}$ since every truth assignment satisfies the elements of $\emptyset$. In this case we write $\vDash \bs{\tau}$ and say that $\bs{\tau}$ is a \textit{tautology}, a statement that is always true.
\begin{ex}\label{tautDeMorgan}
$\bs{((\neg (A_1 \wedge A_2)) \leftrightarrow ((\neg A_1) \vee (\neg A_2))}$ is a tautology since it is always true, no matter what truth assignment we use i.e. no matter what row of the truth table (see Example $\ref{deMorgan}$) we are considering. Of course this is one of DeMorgan's Laws. We may verify all of the standard tautologies presented in a mathematics foundations course in a similar fashion using truth tables.
\end{ex}
\noindent \textbf{Case 2:} What if the wffs in $\Sigma$ cannot be satisfied? If this is the case, then \textit{any} wff $\bs{\tau}$ is tautologically implied by $\Sigma$. This is so because of our definition of tautological implication. For $\bs{\tau}$ to be tautologically implied by $\Sigma$, \textit{if} a truth assignment $v$ satisfies every wff in $\Sigma$, then $v$ must also satisfy $\bs{\tau}$. So if a truth assignment \textit{cannot} satisfy all the elements of $\Sigma$ it is vacuously true that $\bs{\tau}$ is tautologically implied by $\Sigma$.
\begin{ex}
$\{\bs{A_1}, \bs{(\neg A_1)}\}\vDash \bs{A_2}$ since no truth assignment can satisfy both $\bs{(\neg A_1)}$ and $\bs{A_1}$. Therefore, every truth assignment which satisfies all the elements of $\{\bs{A_1}, \bs{(\neg A_1)}\}$ (there are none) will also satisfy $\bs{A_2}$. The idea is that any statement follows from a contradiction.
\end{ex}
\noindent \textbf{Case 3:} What if $\Sigma$ is a singleton i.e. $\Sigma = \{\bs{\sigma}\}$? Instead of writing $\{\bs{\sigma}\} \vDash \bs{\tau}$, we write $\bs{\sigma} \vDash \bs{\tau}$. If $\bs{\sigma} \vDash \bs{\tau}$ and $\bs{\tau} \vDash \bs{\sigma}$ we say that $\bs{\sigma}$ and $\bs{\tau}$ are \textit{tautologically equivalent}, and we write $\bs{\sigma} \tequiv \bs{\tau}$. For sentential logic, this gives us our notion of logical equivalence.
\begin{ex}
From Example $\ref{deMorgan}$, it is clear that $$\bs{((\neg (A_1 \wedge A_2))} \vDash \bs{((\neg A_1) \vee (\neg A_2))} \text{ and}$$ $$\bs{((\neg A_1) \vee (\neg A_2))}\vDash \bs{((\neg (A_1 \wedge A_2))}.$$ Thus, $\bs{((\neg A_1) \vee (\neg A_2))}\tequiv \bs{((\neg (A_1 \wedge A_2))}$.
\end{ex}
We also saw in Example $\ref{tautDeMorgan}$ that $$\bs{((\neg (A_1 \wedge A_2)) \leftrightarrow ((\neg A_1) \vee (\neg A_2))}$$ was a tautology. Our examples with one of DeMorgan's Laws suggest the following results.
\begin{thm}\label{tautImplForm}
$\bs{\alpha} \vDash \bs{\beta}$ iff $\vDash \bs{(\alpha \rightarrow \beta)}$
\end{thm}
\begin{pf}
$$\begin{array}{lcl}
\bs{\alpha} \vDash \bs{\beta}& \text{iff} & \ol{v}(\bs{\alpha}) = T \text{ implies } \ol{v}(\bs{\beta}) = T\\
& \text{iff} & \ol{v}(\bs{\alpha}) = T \text{ and } \ol{v}(\bs{\beta}) = F \text{ cannot both happen.}\\
& \text{iff} & \ol{v}(\bs{(\alpha \rightarrow \beta)}) = T \text{ for every truth assignment.}\\
& \text{iff} & \vDash \bs{(\alpha \rightarrow \beta)}\\ \end{array}$$\qed
\end{pf}
\begin{cor}\label{tautEquivform}
$\bs{\alpha} \tequiv \bs{\beta}$ iff $\vDash \bs{(\alpha \leftrightarrow \beta)}$
\end{cor}
\begin{pf}
$$\begin{array}{lcl}
\bs{\alpha} \tequiv \bs{\beta} & \text{iff} & \bs{\alpha} \vDash \bs{\beta} \text{ and } \bs{\beta} \vDash \bs{\alpha}\\
& \text{iff} & \vDash \bs{(\alpha \rightarrow \beta)} \text{ and } \vDash \bs{(\beta \rightarrow \alpha)}\\
& \text{iff} & \text{neither } \ol{v}(\bs{\alpha}) = T \text{ and } \ol{v}(\bs{\beta}) = F \text{ nor } \ol{v}(\bs{\beta}) = T \text{ and } \ol{v}(\bs{\alpha}) = F\\
&\text{iff} & \ol{v}(\bs{\alpha}) = \ol{v}(\bs{\beta}) \text{ for every truth assignment.}\\
&\text{iff} & \vDash \bs{(\alpha \leftrightarrow \beta)}\\ \end{array}$$\qed
\end{pf}
\begin{thm}\label{impliesTaut}
$\Sigma \cup \{\bs{\alpha}\} \vDash \bs{\beta}$ iff $\Sigma \vDash \bs{(\alpha \rightarrow \beta)}$
\end{thm}
\begin{pf}
Since this proof should follow easily from the appropriate definitions, it is left to the reader.\qed
\end{pf}
The interesting thing about these theorems and their proofs is the perspective they yield about talking in a logical mathematical way about the mathematical topic of logic. In Theorem $\ref{tautEquivform}$, the statement on the left is a statement about the sentential model of logical equivalence existing between $\bs{\alpha}$ and $\bs{\beta}$ in the formal language, but this statement exists \textit{outside} of the formal sentential language. However, the statement on the right gives a statement about it always being true that $\bs{\alpha}$ and $\bs{\beta}$ are equivalent \textit{within} the formal language. (The intended meaning of $\bs{\leftrightarrow}$ being logical equivalence). The theorem thus indicates that logical equivalence (in the sentential model) between two statements in the formal sentential language, can be translated into the formal language itself where the logical symbol $\bs{\leftrightarrow}$ is the formal language symbol for equivalence.
Perhaps even more of a mind-bender is the fact that this theorem \textit{itself} which is a statement about logical equivalence can be translated into the formal language. We will let $\bs{A_1}$ translate the statement ``There are two wffs $\bs{\alpha}$ and $\bs{\beta}$ that are tautologically equivalent" (i.e. ``$\bs{\alpha} \tequiv \bs{\beta}$"). Now we will let $\bs{A_2}$ translate the statement ``The wff $\bs{(\alpha \leftrightarrow \beta)}$ is a tautology" (i.e. ``$\vDash \bs{(\alpha \leftrightarrow \beta)}$"). The theorem above says that $\bs{A_1} \vDash \bs{A_2}$ and $\bs{A_2} \vDash \bs{A_1}$ (or the same thing $\bs{A_1} \tequiv \bs{A_2}$). But then the theorem says that this is logically equivalent to $\vDash \bs{(A_1 \leftrightarrow A_2)}$. So our theorem can be modeled in the formal sentential language. At this point the infinite ``hall of mirrors" effect is beginning to set in. To combat the disorientation, we must recognize that we are operating at two levels, a meta-level and the formal level. When we say, ``The theorem above says $\bs{A_1} \tequiv \bs{A_2}$," we are thinking at the formal level \textit{within} our sentential model. Any formal satisfaction of the wff $\bs{A_1}$ will also formally satisfy the wff $\bs{A_2}$. When we say ``But then the theorem says that this is logically equivalent to $\vDash \bs{(A_1 \leftrightarrow A_2)}$," we are stepping \textit{outside} of the formal model of sentential logic to the meta-level of us being rational beings who understand logical equivalence and what that \textit{means}. In this case, we understand that the statement ``$\bs{A_1} \tequiv \bs{A_2}$" is logically equivalent (this equivalence is at the meta-level) to the statement ``$\vDash \bs{(A_1 \leftrightarrow A_2)}$" given the theorem we proved. At the meta-level, we are deducing things about our model of deduction (in this case, sentential logic). At the formal level, we are modeling within a formal language the deduction about our model of deduction. We as the readers and mathematicians stand in the real world making real deductions about the models of our real deductions.
This self-reference is the sort that comes about from studying logic mathematically when mathematics itself is based on logic. It is also just this sort of self-reference that is the very key to proving G\"odel's Incompleteness Theorem.
We have established the basics of sentential logic as a model for humanity's deductive thought processes. We are now in a position to explore some of the properties of this model.
\newpage
\chapter{Properties of Sentential Logic}
\hspace{0.5in} Having developed sentential logic as a model of humanity's deductive thought processes, we are in a position to ask about what nice properties sentential logic has. Recall that our goal is to develop mathematically rigorous models of deduction, and like other mathematical constructs, we would like to ask what nice properties a particular model has and what properties it lacks. Really, what we are asking is how well does sentential logic model humanity's deductive thought processes?
\section{The Compactness Theorem}
\hspace{0.5in} We recall first that saying ``$\Sigma \vDash \bs{\tau}$" is our model for saying ``If the hypotheses of the statements (wffs) in $\Sigma$ are satisfied, then the statement (wff) $\bs{\tau}$ must also be satisfied." Now, nothing was said about the cardinality of the set $\Sigma$. By assumption, we have a countable alphabet of logical symbols and sentence symbols, and expressions are finite sequences of indecomposable alphabet symbols. Hence there are countably many possible wffs, and the set $\Sigma$ of wffs is countable.
The question becomes, if it is the case that $\Sigma \vDash \bs{\tau}$ where $\Sigma$ is countably infinite, is it possible to give a \textit{proof} that $\Sigma \vDash \bs{\tau}$?
It is instructive at this point to consider what we mean by the term \textit{proof}. Remember that at our current sentential level, we are thinking of \\``$\Sigma \vDash \bs{\tau}$" as a model for saying that the statements or premises of $\Sigma$ logically imply the statement $\bs{\tau}$. To give a proof of ``$\Sigma \vDash \bs{\tau}$", we use the properties of sentential logic that we have developed as part of it being a mathematical structure to fulfill the definition for what it means to say ``$\Sigma \vDash \bs{\tau}$." Here, our proof consists of finitely many statements at the meta-level discussed at the end of Chapter 2. What we are doing as reasoners in the real world (the meta-level) is examining a statement in a mathematical structure (sentential logic) and giving sufficient meta-reasons to be able to say ``$\Sigma \vDash \bs{\tau}$" in our mathematical structure. This is no different than if we were working in number theory seeking to establish a proof of the statement ``There are infinitely many prime numbers." Our proof of ``$\Sigma \vDash \bs{\tau}$" is not a statement within the formal sentential logic structure, just as our proof of there being infinitely many prime numbers does not take place in the formal system of number theory itself. We only use the \textit{structure} of number theory to carry out a reasonable proof.
The question then arises, if we carry out proofs as part of our deductive thought processes as humans, can we model our proofs in the sentential structure itself? What is characteristic about a proof is a \textit{demonstration} of \textit{how} the truth of finitely many premises guarantees the truth of a conclusion. At the sentential logic level we can handle the truth of finitely many premises guaranteeing the truth of a conclusion. This structure we can express in the sentential model of deduction as ``$\Sigma_f \vDash \bs{\tau}$" where $\Sigma_f = \{\bs{\sigma_0}, \bs{\sigma_1},\ldots, \bs{\sigma_n}\}$ (a finite set of wffs that translates our finitely many premises as $\bs{\sigma_0}$ through $\bs{\sigma_n}$). We may even express our tautological implication in the symbolism of the sentential language as $\bs{(\sigma_0 \rightarrow (\sigma_1 \rightarrow( \ldots \rightarrow \sigma_n))\ldots) \rightarrow \tau}$ since this wff will be a tautology using Theorem $\ref{impliesTaut}$ finitely many times.
This representation of a proof is the best we can do with sentential logic. Given the \textit{meaning} we have intended for the symbols involved, the above wff definitely models the guarantee of the truth of the statement $\bs{\tau}$ given the truth of the premises of $\Sigma_f$. Analysing the wff via truth table will show that given any truth assignment $v$, $\ol{v}$ will always return an output of $T$ given the wff as an input. Or from the computer science perspective, if we program a computer to return $F$ for an always false wff, $T$ for an always true wff, or ``inconclusive" for a sometimes true and sometimes false wff, given our wff $\bs{(\sigma_0 \rightarrow (\sigma_1 \rightarrow( \ldots \rightarrow \sigma_n))\ldots) \rightarrow \tau}$ as an input into the computer, the computer would return $T$.
We now measure against our intuitions whether our model for a proof in the sentential realm is a good one. Our model seems limited. A proof should clearly demonstrate the \textit{how} and the \textit{why} behind the guarantees of truth. In other words the ultimate \textit{``why"} behind writing $\bs{\rightarrow}$ in $\bs{(\alpha \rightarrow \beta)}$ where this wff is a tautology. Any hints as to this ``why" within the formal language itself must come from the very structure of the symbolism being used and interaction of truth values of the wffs. So, perhaps at the most rudimentary level, our model for a proof in sentential approaches what a proof actually is, but it seems unsatisfying.
However, at this point we recall that sentential logic is a \textit{model} for the deductive process that human beings use. Of course any mathematical model will have limitations since it is just that: a model. It is an approximation to the real world where we compress the real world's complexities into something simpler and easier to think about. The properties we then derive from the model may give us some useful information to use in the real world. We also recall that sentential logic, is only our \textit{first} model for humanity's deductive thought processes. We see that refinements of the model may be in order. We now return to our original discussion.
Again, the question is, if it is the case that ``$\Sigma \vDash \bs{\tau}$" where can we \textit{always} give a proof (at the real world level) of this fact? The interesting case occurs when $\Sigma$ is countably infinite. Our main tool at this point for establishing a statement of this kind is to use the definition; i.e. if an arbitrary truth assignment satisfies the wffs in $\Sigma$, then it must also satisfy the wff $\bs{\tau}$. Proving this statement becomes a problem if $\Sigma$ is infinite for then we necessarily have infinitely many sentence symbols $\bs{A_i}$ and thus infinitely many truth assignments to check (or equivalently, infinitely many rows in our truth table). Thus, if $\Sigma$ is infinite, we can never prove $\Sigma \vDash \bs{\tau}$ directly from the definition+. We need other results which we now develop.
First, recall that we say that truth assignment $v: \CS \longrightarrow \TF$ \textit{satisfies} wff $\bs{\varphi}$ if and only if $\ol{v}(\bs{\varphi}) = T$.
\begin{df}
A set $\Sigma$ of wffs is \dfem{satisfiable} if there is a truth assignment which satisfies every member of $\Sigma$.
\end{df}
\begin{lm}\label{Lem1Comp}
If every finite subset of a set of wffs $\Sigma$ is satisfiable, then the same is true of at least one of the sets $\Sigma \cup \{\bs{\alpha}\}$ and $\Sigma \cup \{\bs{(\neg \alpha)}\}$ for any wff $\bs{\alpha}$.
\end{lm}
\begin{pf}
If either $\bs{\alpha}$ or $\bs{(\neg \alpha)}$ is in $\Sigma$, the result holds trivially. We assume then that neither $\bs{\alpha}$ nor $\bs{(\neg \alpha)}$ are in $\Sigma$, and thus $\bs{(\neg \alpha)} \notin \Sigma \cup \{\bs{\alpha}\}$ and $\bs{\alpha} \notin \Sigma \cup \{\bs{(\neg \alpha)}\}$. Suppose, by way of contradiction that there are finite sets $F_1$ and $F_2$ with $F_1 \subseteq \Sigma \cup \{\bs{\alpha}\}$ and $F_2 \subseteq \Sigma \cup \{\bs{(\neg \alpha)}\}$ such that no truth assignments satisfy either $F_1$ or $F_2$. Note that since $F_1$ and $F_2$ are finite, $F_1 \cup F_2$ will also be finite as will $F_1\cup F_2 - \{\bs{\alpha}, \bs{(\neg \alpha)}\}$. This set is a subset of $\Sigma$. Since $\Sigma$ has the property that every finite subset of $\Sigma$ is satisfiable, there is a truth assignment $v$ satisfying every member of $F_1\cup F_2 - \{\bs{\alpha}, \bs{(\neg \alpha)}\}$. In particular, $v$ satisfies every member of $F_1 - \{\bs{\alpha}, \bs{(\neg \alpha)}\}$ and of $F_2 - \{\bs{\alpha}, \bs{(\neg \alpha)}\}$ which are each subsets of $F_1\cup F_2 - \{\bs{\alpha}, \bs{(\neg \alpha)}\}$. Since $\bs{(\neg \alpha)}\notin F_1 \subseteq \Sigma \cup \{\bs{\alpha}\}$ and $\bs{\alpha} \notin F_2 \subseteq \Sigma \cup \{\bs{(\neg \alpha)}\}$, $F_1 - \{\bs{\alpha}, \bs{(\neg \alpha)}\} = F_1 - \{\bs{\alpha}\}$, and $F_2 - \{\bs{\alpha}, \bs{(\neg \alpha)}\} = F_2 -\{\bs{(\neg \alpha)}\}$.
Now, either $\ol{v}(\bs{\alpha}) = T$ or $\ol{v}(\bs{\alpha}) = F$. In the first case, $F_1$ would have to be satisfiable since $(F_1 - \{\bs{\alpha}\}) \cup \{\bs{\alpha}\} = F_1$. This contradicts our assumption of $F_1$ not being satisfiable, and we conclude that $\ol{v}(\bs{\alpha}) = F$. But by properties of $\ol{v}$ established in Chapter 2, this must mean that $\ol{v}(\bs{(\neg \alpha)}) = T$. In this case $F_2$ must be satisfiable by similar reasoning to that in the previous case. But this is another contradiction to what we have assumed. We thus conclude that what we have supposed is false and every finite subset is satisfiable for at least one of $\Sigma \cup \{\bs{\alpha}\}$ and $\Sigma \cup \{\bs{(\neg \alpha)}\}$. \qed
\end{pf}
We need one more lemma before we prove a result that will help us to answer our question under consideration.
\begin{lm}
Let $\Delta$ be a set of wffs such that (i) every finite subset of $\Delta$ is satisfiable, and (ii) for every wff $\bs{\alpha}$, either $\bs{\alpha} \in \Delta$ or $\bs{(\neg \alpha)} \in \Delta$ (this will be an exclusive ``or" since $\{\bs{\alpha},\bs{(\neg \alpha)}\}$ would not be a satisfiable subset of $\Delta$). Define the truth assignment $v$ by
$$v(\bs{A}) = \left\lbrace \begin{array}{ll} T & \hbox{if } \bs{A} \in \Delta\\ F & \hbox{if } \bs{A} \notin \Delta\\ \end{array}\right.$$
for each sentence symbol $\bs{A}$. Then for every wff $\bs{\varphi}$, $\ol{v}(\bs{\varphi}) = T$ iff $\bs{\varphi} \in \Delta$.
\end{lm}
\begin{pf}
Recall that for sentential logic, we let $\CS$ denote the set of sentence symbols and $\W$ denote the set of wffs. Let $${I = \{\bs{\varphi} \in \W|\bs{\varphi} \in \Delta \text{ iff }\ol{v}(\bs{\varphi}) = T\}}$$ ($v$ is the truth assignment defined above). We wish to use induction, that is, the Induction Principle, to prove that $I = \W$.
Note that $\CS\subseteq I$ since for every sentence symbol $\bs{A}$, $\ol{v}(\bs{A}) = v(\bs{A}) = T$ if and only if $\bs{A} \in \Delta$ by how $v$ was defined. If we can demonstrate that $I$ is closed under the formula building operations, we will have fulfilled the Induction Principle.
Let $\bs{\alpha}, \bs{\beta} \in I$. Note that this means that $\ol{v}(\bs{\alpha}) = T$ iff $\bs{\alpha} \in \Delta$ and $\ol{v}(\bs{\beta}) = T$ iff $\bs{\beta} \in \Delta$. We show that $\bs{(\neg \alpha)} \in I$. We know from our results using the Recursion Theorem with truth assignments that $\ol{v}(\bs{(\neg \alpha)}) = T$ iff $\ol{v}(\bs{\alpha}) = F$ iff $\bs{\alpha} \notin \Delta$. We show that $\bs{\alpha} \notin \Delta$ iff $\bs{(\neg \alpha)} \in \Delta$. By property (ii) of $\Delta$, we have that $\bs{\alpha} \notin \Delta$ implies that $\bs{(\neg \alpha)} \in \Delta$. Conversely, if $\bs{(\neg \alpha}) \in \Delta$, then $\bs{\alpha} \notin \Delta$. Thus, we have that $\bs{(\neg \alpha)} \in \Delta$ iff $\bs{\alpha} \notin \Delta$. So, we have that $\ol{v}(\bs{(\neg \alpha)}) = T$ iff $\bs{\alpha} \notin \Delta$ iff $\bs{(\neg \alpha)} \in \Delta$. Hence $\bs{(\neg \alpha)} \in I$ by definition, and $I$ is closed under $\F_\neg$.
The same reasoning used here to show that $I$ is closed under $\F_\neg$ may be used in the remaining cases of the formula building operations. The demonstration of all of these cases is very tedious. We will illustrate the proofs for the remaining formula building operations with one two-variable formula building operation, and then we leave it to the reader to establish the remaining cases.
We seek to demonstrate that $\bs{(\alpha \vee \beta)} \in I$. By the Recursion Theorem, we note that $\ol{v}(\bs{(\alpha \vee \beta)}) = T$ iff $\ol{v}(\bs{\alpha}) \bs{\vee} \ol{v}(\bs{\beta}) = T$ iff $\ol{v}(\bs{\alpha}) = T$ or $\ol{v}(\bs{\beta}) = T$ iff $\bs{\alpha} \in \Delta$ or $\bs{\beta} \in \Delta$, since $\bs{\alpha}, \bs{\beta} \in I$. The following piece of a truth table will be helpful in establishing the claim that $\bs{\alpha} \in \Delta$ or $\bs{\beta} \in \Delta$ iff $\bs{(\alpha \vee \beta)} \in \Delta$.
\begin{scriptsize}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\bs{\alpha}$ & $\bs{\beta}$ & $\bs{(\neg \alpha)}$ & $\bs{(\neg \beta)}$ & $\bs{(\alpha \vee \beta)}$ & $\bs{(\neg (\alpha \vee \beta))}$\\
\hline
$T$ & $T$ & $F$ & $F$ & $T$ & $F$\\
\hline
$T$ & $F$ & $F$ & $T$ & $T$ & $F$\\
\hline
$F$ & $T$ & $T$ & $F$ & $T$ & $F$\\
\hline
$F$ & $F$ & $T$ & $T$ & $F$ & $T$\\
\hline
\end{tabular}\\
\end{scriptsize}
We see from the Recursion Theorem that all possibilities for the truth values for the key wffs $\bs{\alpha}$ and $\bs{\beta}$ have been exhausted under any truth assignment. We see immediately from the truth table that the finite sets $$\{\bs{\alpha}, \bs{(\neg(\alpha \vee \beta))}\} \text{ and }\{\bs{\beta}, \bs{(\neg(\alpha \vee \beta))}\}$$ are each not satisfiable under any possible truth assignment since the sets' two wffs never have the value of truth under the same truth assignment. If we assume that either $\bs{\alpha} \in \Delta$ or $\bs{\beta} \in \Delta$, then we must conclude by property (i) of $\Delta$ that $\bs{(\neg(\alpha \vee \beta))} \notin \Delta$, otherwise one of the above sets would be satisfiable. So, by property (ii) of $\Delta$, $\bs{(\alpha \vee \beta)} \in \Delta$. Conversely, if we suppose that $\bs{(\alpha \vee \beta)} \in \Delta$, then we note that $\{\bs{(\neg \alpha)}, \bs{(\neg \beta)}, \bs{(\alpha \vee \beta)}\}$ is not satisfiable as seen by the truth table above. Since we are assuming that $\bs{(\alpha \vee \beta)} \in \Delta$, by property (i), we have that either $\bs{(\neg \alpha)} \notin \Delta$ (in which case $\bs{\alpha} \in \Delta$ by property (ii)) or $\bs{(\neg \beta)} \notin \Delta$ (in which case $\bs{\beta} \in \Delta$ by property (ii)). So $\bs{(\alpha \vee \beta)} \in \Delta$ implies that $\bs{\alpha} \in \Delta$ or that $\bs{\beta} \in \Delta$. Thus, $\bs{(\alpha \vee \beta)} \in \Delta$ iff $\bs{\alpha} \in \Delta$ or $\bs{\beta} \in \Delta$. So, we conclude that $\ol{v}(\bs{(\alpha \vee \beta)}) = T$ iff $\bs{\alpha} \in \Delta$ or $\bs{\beta} \in \Delta$ iff $\bs{(\alpha \vee \beta)} \in \Delta$. Hence, $\bs{(\alpha \vee \beta)} \in I$ by definition and $I$ is closed under $\F_\vee$. The cases with the other formula building operations are similar and are left to the reader.
Since $I$ contains $\CS$ and is closed under the formula building operations, we conclude by the Induction Principle that $I = \W$. So, for any wff $\bs{\varphi}$, $\ol{v}(\bs{\varphi}) = T$ iff $\bs{\varphi} \in \Delta$. We thus accept this lemma as proved.\qed
\end{pf}
We are now in position to prove the result that will answer our question at hand.
\begin{thm}[The Compactness Theorem for Sentential Logic]$\text{}$\\
A set of wffs is satisfiable if and only if every finite subset is satisfiable.
\end{thm}
\begin{pf}
Let $\Sigma$ be a set of wffs. If $\Sigma$ is satisfiable, then of course, every finite subset will be satisfiable. Just take the truth assignment that satisfies $\Sigma$ and this will satisfy all of $\Sigma$'s subsets, finite or not. Conversely, suppose that every finite subset of $\Sigma$ is satisfiable. If $\Sigma$ is itself finite, we are done since $\Sigma$ is a subset of itself, and being finite, is satisfiable by assumption. So, we suppose that $\Sigma$ is infinite and that every finite subset of $\Sigma$ is satisfiable. The idea is to construct a maximal set of wffs which contains $\Sigma$ and define a truth assignment which satisfies every member of this maximal set. Such a truth assignment will of course satisfy $\Sigma$ as well. We proceed.
Let $\bs{\alpha_1}, \ \bs{\alpha_2},\ \bs{\alpha_3},\ldots$ be an enumeration of the wffs (the set of wffs is countable). Define the following: $$\Delta_0 = \Sigma$$ $$\Delta_{n+1} = \left\lbrace\begin{array}{ll} \Delta_n \cup \{\bs{\alpha_{n+1}}\} & \text{if every finite subset of this set is satisfiable}\\
\Delta_n \cup \{\bs{(\neg \alpha_{n +1})}\} & \text{otherwise}\\ \end{array} \right.$$
Using a simple induction argument and the Lemma $\ref{Lem1Comp}$, we know that every finite subset of $\Delta_n$ for each natural number $n$ is satisfiable. Every finite subset of $\Delta_0 = \Sigma$ is satisfiable by assumption. If every finite subset of $\Delta_{n-1}$ for $n\geq 1$ is satisfiable, then the same holds true for at least one of $\Delta_{n-1}\cup\{\bs{\alpha_n}\}$ and $\Delta_{n-1}\cup\{\bs{(\neg \alpha_n)}\}$ by the lemma. Let $\ds \Delta = \bigcup_{n=0}^\infty \Delta_n$. First, it is clear that $\Sigma = \Delta_0 \subseteq \Delta$. Let $F$ be a finite subset of $\Delta$. Now, $F \subseteq \Delta_n$ for some $n \in \NN$. Since every finite subset of $\Delta_n$ is satisfiable, then $F$ is satisfiable. Since our choice for $F$ as a finite subset of $\Delta$ was arbitrary, then we know that every finite subset of $\Delta$ is satisfiable.
Now let $\bs{\varphi}$ be a wff. By our enumeration of the set of wffs, $\bs{\varphi} = \bs{\alpha_i}$ for some natural number $i$. By construction either $\bs{\varphi} = \bs{\alpha_i} \in \Delta_i$ or\\ $\bs{(\neg \varphi)}=\bs{(\neg \alpha_i)} \in \Delta_i$. In either case, we have that either $\bs{\varphi} \in \Delta$ or $\bs{(\neg \varphi)} \in \Delta$. Since our choice for $\bs{\varphi}$ was arbitrary, this is true for any wff $\bs{\varphi}$. We define the truth assignment $v$ as in Lemma 3.1.2, and using the lemma we find that for any wff $\bs{\varphi}$, $\ol{v}(\bs{\varphi}) = T$ if and only if $\bs{\varphi} \in \Delta$. Since for every wff $\bs{\varphi} \in \Sigma$, $\bs{\varphi} \in \Delta$, we see that $\ol{v}(\bs{\varphi}) = T$ for every $\bs{\varphi} \in \Sigma$. Hence, the truth assignment $v$ satisfies $\Sigma$ by definition. Therefore, the assertion of the Compactness Theorem holds. \qed
\end{pf}
Note that there are two alternative proofs to the Compactness Theorem to the one given above that may be of interest to the reader. The first uses Zorn's Lemma (equivalent to the Axiom of Choice), and in this case the Compactness Theorem can be shown to hold for an uncountable alphabet of sentential symbols. The second alternative uses general topological concepts. The compactness theorem asserts the compactness of a particular topological space called a Stone Space. The interested reader may wish to do some research on this line.
\begin{cor}
If $\Sigma \vDash \bs{\tau}$, then there is a finite $\Sigma_f \subseteq \Sigma$ such that $\Sigma_f \vDash \bs{\tau}$.
\end{cor}
\begin{pf}
Assume that $\Sigma \vDash \bs{\tau}$. A moment's reflection shows that $\Sigma \vDash \bs{\tau}$ if and only if $\Sigma \cup \{\bs{(\neg \tau)}\}$ is unsatisfiable. Suppose by way of contradiction that for every finite $\Sigma_f \subseteq \Sigma$ it is not the case that $\Sigma_f \vDash \bs{\tau}$. By our first observation then $\Sigma_f \cup \{\bs{(\neg \tau)}\}$ is satisfiable for every finite $\Sigma_f \subseteq \Sigma$. Note that a finite subset of $\Sigma \cup \{\bs{(\neg \tau)}\}$ will either be of the form $\Sigma_f$ or $\Sigma_f \cup \{\bs{(\neg \tau)}\}$ for finite $\Sigma_f \subseteq \Sigma$. Since $\Sigma_f \cup \{\bs{(\neg \tau)}\}$ is satisfiable for any finite $\Sigma_f \subseteq \Sigma$ and $\Sigma_f \subseteq \Sigma_f \cup \{\bs{(\neg \tau)}\}$, we see that every finite subset of $\Sigma \cup \{\bs{(\neg \tau)}\}$ is satisfiable. By the Compactness Theorem then, $\Sigma \cup \{\bs{(\neg \tau)}\}$ is itself satisfiable. But, by our initial observation, this is so if and only if it is not the case that $\Sigma \vDash \bs{\tau}$, a contradiction. So, in fact it must be the case that $\Sigma_f \vDash \bs{\tau}$ for some finite $\Sigma_f \subseteq \Sigma$. \qed
\end{pf}
Thus, we are guaranteed that if $\Sigma \vDash \bs{\tau}$, we should be able to find finite $\Sigma_f \subseteq \Sigma$ to establish $\Sigma_f \vDash \bs{\tau}$. Hence, we are always able to establish $\Sigma \vDash \bs{\tau}$ using our truth table method in the meta-realm. Since $\Sigma \vDash \bs{\tau}$ is our model in the sentential language for the truth of the statements of $\Sigma$ guaranteeing the statements of $\bs{\tau}$, the above theorem also guarantees that we need only finitely many premises ($\Sigma_f$) to make this guarantee. That is, this corollary to the Compactness Theorem guarantees that our intuitive notion that a proof of a true statement should be finite in length (and thus physically doable) is matched in the sentential model for deductive thought.
Hence our sentential does a decent job at mirroring our intuitive notions of proof construction. We now ponder another desirable property.
\section{Expressibility in Sentential Logic}
\hspace{0.5in} Another question we wish to ask about our model for humanity's deductive thought processes is ``How do we know that we can't enrich the sentential language by adding more connectives?" Have we included enough sentential connectives (our current connective symbols are $\bs{\neg}, \ \bs{\vee}, \ \bs{\wedge}, \ \bs{\rightarrow}, \text{ and } \bs{\leftrightarrow}$) to express all possible logical constructions that could occur given our intended meanings for our connectives?
An example clarifies exactly what we mean by this question. Suppose we enrich our sentential language with a connective symbol $\bs{\nabla}$. That is, we have a new ternary formula building operation $\F_\nabla$ which we define on the set of expressions in the enriched sentential language by $\F_\nabla(\bs{\alpha}, \bs{\beta}, \bs{\gamma}) = \bs{(\nabla\alpha\beta\gamma)}$. So in our new language, $\bs{(\nabla\alpha\beta\gamma)}$ is now an expression for expressions $\bs{\alpha}$, $\bs{\beta}$, and $\bs{\gamma}$. Now, we also must have an intended meaning for $\bs{\nabla}$ as we do with our original connectives (i.e. the intended meaning for $\bs{\wedge}$ is ``and", the intended meaning for $\bs{\rightarrow}$ is ``implies", etc.). We will call $\bs{\nabla}$ the ``too good to be true" operator. To understand our intended meaning, let us define $\G_\nabla \TF^3 \longrightarrow \TF$ as follows: $$\G_\nabla(V_1,V_2,V_2)= \left\lbrace \begin{array}{ll} F & \text{if } V_i = V_j = T \text{ where } i\neq j\\
T & \text{if } V_i = V_j = F \text{ where } i\neq j\\ \end{array}\right.$$ (This function is well defined since the truth value of two of the inputs must match.) So, for instance $\bs{(\nabla} TTT\bs{)} = \bs{(\nabla} TTF\bs{)} = F$ (too good to be true), and $\bs{(\nabla} TFF\bs{)} = \bs{(\nabla} FFF\bs{)} = T$ (we could also call this the ``pessimist function"). So, using the Recursion Theorem, for a truth assignment $v$, $$\ol{v}(\bs{(\nabla\alpha_1\alpha_2\alpha_3)}) = \left\lbrace \begin{array}{ll} F & \text{if } \ol{v}(\alpha_i) = \ol{v}(\alpha_j) = T \text{ where } i\neq j\\
T & \text{if } \ol{v}(\alpha_i) = \ol{v}(\alpha_j) = F \text{ where } i\neq j\\
\end{array}\right.$$
So, having enriched our original sentential language with the ``too good to be true" symbol, can we express more logical structure now in our new language than we could before?
First, we need to make the notion of ``expressing more logical structure" more precise. Recall that two wffs $\bs{\sigma}$ and $\bs{\tau}$ are said to be \textit{tautologically equivalent} if and only if $\bs{\sigma} \tequiv \bs{\tau}$.
We will declare that if any wff in an extended language (extended in the sense just exemplified) is tautologically equivalent (in the extended language) to a wff in the original language, then our extended language can express precisely the same logical structure as can the original language and so we have gained nothing by our extension.
\begin{ex}
$\bs{(\nabla \alpha \beta \gamma)}\tequiv \bs{(\neg(((\alpha \wedge \beta)\vee (\alpha \wedge \gamma)) \vee (\beta \wedge \gamma)))}$.\\ The reader can check this assertion via a truth table.
\end{ex}
The former example indicates that our ``too good to be true" connective does nothing significant to improve the expressibility of our language since there is a tautologically equivalent wff in the original language. However, we would like to see a language (hopefully the sentential language we have developed!) for which \textit{any} extension by \textit{any} connective symbol will result in no improvement of expressibility. The sentential language in fact fits the bill (in fact a much smaller language than the sentential language would suffice), but we need to shift our focus to a new tool to be able to prove this fact.
\begin{df}
A function $B^k:\TF^k \longrightarrow \TF$ with $k \geq 1$ is a \dfem{$\bs{k}$-place Boolean function}. A \dfem{Boolean function} is a $k$-place Boolean function for some $k\geq 1$.
\end{df}
\begin{ex}
The following catalog is a list of Boolean functions.
$$ I_i^k(V_1,V_2,\ldots,V_i,\ldots,V_k) = V_i$$
\begin{center}
\begin{tabular}{cc}
$N(T) = F$&$N(F) = T$\\
$A(T,T) =T$ & $A(V,F) = F$\\
$O(F,F) = F$& $O(V,T) = T$\\
$C(T,F) = F$ & $C(F,V) = C(V,T) = T$\\
$E(V_1, V_2) = T$ & $E(V_1,V_2) = F$ \\
if $V_1 = V_2$ & if $V_1 \neq V_2$
\end{tabular}
\end{center}
\end{ex}
The use of Boolean functions becomes apparent in the following truth table.
\begin{scriptsize}
\begin{tabular}{|c|c|c|c|}
\hline
$\bs{A_1}$ & $\bs{A_2}$ & $\bs{(A_1 \wedge A_2)}$ & $A(v(\bs{A_1}),v(\bs{A_2}))$\\
\hline
$T$ & $T$ & $T$ & $T$\\
\hline
$T$ & $F$ & $F$ & $F$\\
\hline
$F$ & $T$ & $F$ & $F$\\
\hline
$F$ & $F$ & $F$ & $F$ \\
\hline
\end{tabular}\\
\end{scriptsize}
\noindent We see that the 2-place Boolean function $A$ evaluated at the truth values of the sentence symbols involved in the wff $\bs{(A_1 \wedge A_2)}$ gives the same output in every case that $\ol{v}(\bs{(A_1 \wedge A_2)})$ does. The Boolean function $A$ expresses the same intended logical structure as $\bs{\wedge}$ does. It becomes readily apparent that any wff realizes a Boolean function. Given a wff $\bs{\alpha}$, $\bs{\alpha}$ involves a finite number of sentence symbols $\bs{A_1}, \bs{A_2},\ldots, \bs{A_k}$. There will be $2^k$ possible distinct truth assignments, $v$ for these sentence symbols, but we may define $B^k_{\bs{\alpha}} :\TF^k \longrightarrow \TF$ as follows: $B^k_{\bs{\alpha}} (v(\bs{A_1}),v(\bs{A_2}),\ldots,v(\bs{A_k})) = \ol{v}(\bs{\alpha})$ for every truth assignment $v$ (this will exhaust all possible inputs into our defined function since $|\TF^k| = 2^k$). So, given any wff $\bs{\alpha}$ we may define a Boolean function whose output exactly matches that of $\ol{v}$ for every truth assignment $v$. So, the entire structure represented in our formal sentential language can be completely expressed with Boolean functions.
\begin{ex}
We readily see the following:\\
$I_i^k = B^k_{\bs{A_i}}$\\
$N = B^1_{\bs{(\neg A_1)}}$\\
$A = B^2_{\bs{(A_1 \wedge A_2)}}$\\
$O = B^2_{\bs{(A_1 \vee A_2)}}$\\
$C = B^2_{\bs{(A_2 \rightarrow A_2)}}$\\
$E = B^2_{\bs{(A_2 \leftrightarrow A_2)}}$\\
\end{ex}
Even better than saying that each wff $\bs{\alpha}$ realizes a Boolean function $B_{\bs{\alpha}}^k$, we may say that our Boolean function is some composition of the 6 functions above (as long as $\bs{\alpha}$ is in the sentential language developed in Chapter 2). To see this, we recall our development of truth assignments in which we used the Recursion Theorem back in Chapter 2. We used the following functions:$$ \G_\neg(V) =\left\lbrace \begin{array}{cl} T & \hbox{if }V = F\\ F & \hbox{if } V = T\\ \end{array} \right.$$
$$\G_\vee (V_1 , V_2) = \left\lbrace \begin{array}{cl} F & \hbox{if }V_1 = F \hbox{ and } V_2 = F\\ T & \hbox{otherwise}\\ \end{array} \right.$$
$$\G_\wedge (V_1 , V_2) = \left\lbrace \begin{array}{cl} T & \hbox{if }V_1 = T \hbox{ and } V_2 = T\\ F & \hbox{otherwise}\\ \end{array} \right.$$
$$\G_\rightarrow (V_1 , V_2) = \left\lbrace \begin{array}{cl} F & \hbox{if }V_1 = T \hbox{ and } V_2 = F\\ T & \hbox{otherwise}\\ \end{array} \right.$$
$$\G_\leftrightarrow (V_1 , V_2) = \left\lbrace \begin{array}{cl} T & \hbox{if }V_1 = V_2\\ F & \hbox{otherwise}\\ \end{array} \right.$$
These are precisely the Boolean functions $N, \ A, \ O, \ C, \text{ and } E$. The Recursion Theorem told us the following: $$\ol{v}(\bs{\alpha})= \left\lbrace \begin{array}{ll} v(\bs{\alpha}) & \text{if } \bs{\alpha} = \bs{A_i} \text{ for some }i\\
\G_\neg(\ol{v}(\bs{\beta})) & \text{if } \bs{\alpha} = \F_\neg(\bs{\beta})\\
\G_\sharp(\ol{v}(\bs{\beta}),\ol{v}(\bs{\gamma})) & \text{ where } \bs{\alpha} = \F_\sharp(\bs{\beta},\bs{\gamma}) \text{ and } \bs{\sharp} \in \{\bs{\vee}, \bs{\wedge}, \bs{\leftarrow}, \bs{\leftrightarrow}\}\\ \end{array} \right.$$
Since $B_{\bs{\alpha}}^k(I_1^k(\ora{V}),I_2^k(\ora{V}),\ldots,I_k^k(\ora{V})) = \ol{v}(\bs{\alpha})$ where $\ora{V} = (V_1,V_2,\ldots,V_k)$ and where $V_i = v(\bs{A_i})$ for the truth assignment $v$, and since $\G_\sharp = B$ where $B \in \{N,A,O,C,E\}$, we may rewrite the statement given to us by the Recursion Theorem as follows:
$$B_{\bs{\alpha}}^k(I_1^k(\ora{V}),I_2^k(\ora{V}),\ldots,I_k^k(\ora{V}))= \left\lbrace \begin{array}{ll} I_i^k(\ora{V}) & \text{if } \bs{\alpha} = \bs{A_i} \text{ for some }i\\
N(\ol{v}(\bs{\beta})) & \text{if } \bs{\alpha} = \F_\neg(\beta)\\ B(\ol{v}(\bs{\beta}),\ol{v}(\bs{\gamma})) &\text{where } \bs{\alpha} = \F_\sharp(\bs{\beta},\bs{\gamma}) \text{ and } \\ & \bs{\sharp} \in \{\bs{\wedge}, \bs{\vee}, \bs{\leftarrow}, \bs{\leftrightarrow}\}\text{ and}\\& \text{where }B \in \{A,O,C,E\}\\\end{array} \right.$$
The Recursion Theorem applied here tells us how to write each boolean function determined by the wff $\bs{\alpha}$ as a composition of the five boolean functions $N, \ A, \ O, \ C, \ E$.
\begin{ex}
$B_{\bs{((\neg A_1)\leftrightarrow A_2)}}^2(V_1,V_2) = E(N(I_1^2(V_1,V_2)),I_2^2(V_1,V_2))$
\end{ex}
The Boolean functions have changed nothing. They just give a clearer perspective on the essential structure of the intended meaning of the logical connectives used in the sentential language. How do Boolean functions help us answer our primary question? It would make sense that wffs which realize the same Boolean function should be equivalent in every meaningful sense since they are able to express the same logical structure. We could easily create an equivalence relation such that wffs $\bs{\alpha}$ and $\bs{\beta}$ are equivalent if and only if $B^k_{\bs{\alpha}} = B^k_{\bs{\beta}}$. Now, a Boolean function is able to express any logical structure that we might dream up. If we are able to say that given a Boolean function, we can find a wff $\bs{\alpha}$ in some enriched language such that this $\bs{\alpha}$ realizes our Boolean function, and if we are able to say that for any wff $\bs{\beta}$ in any enriched language that there is a wff $\bs{\alpha}$ in our original language such that $\bs{\alpha}$ and $\bs{\beta}$ are equivalent ($B^k_{\bs{\alpha}} = B^k_{\bs{\beta}}$), then we would seem to have achieved our goal. However, we must first ask whether this notion of equivalence coincides with the notion of tautological equivalence, for that is how we originally stated our aim. We now prove that the two notions of equivalence in fact coincide with each other.
We put an ordering on $\TF$ by declaring that $F \aleph_0$, we see that we have more sets of expressions than we have effective procedures that could be used to show that a particular set is decidable. \qed
\end{pf}
Of course, the above results are to familiarize us with effective procedures and their limitations. Our interest is in results that will shed light on our search for mathematical deductions i.e. our search for mathematical knowledge. Our question is, given a set of wffs (premises), $\Sigma$, and another wff (statement), $\bs{\tau}$, can we always demonstrate that $\Sigma \vDash \bs{\tau}$ if this is true or demonstrate that $\Sigma \nvDash \bs{\tau}$ if this is true.
At this point, we again take a moment to think about just exactly what we are doing. Sentential Logic is a mathematical model of humanity's deductive thought processes. Within this model. $\Sigma \vDash \bs{\tau}$ is our model for a deduction or proof. Thus, if we can answer the above question about our model, we can shed some meta-light on our endeavor as mathematicians: Given any set of premises, do we \textit{know} we can always disprove or prove \textit{any other statement} from our given set of premises? We now address this question.
\begin{prop}
Given any finite set $\Sigma \cup \{\bs{\tau}\}$ there is an effective procedure to decide whether or not $\Sigma \vDash \bs{\tau}$.
\end{prop}
\begin{pf}
Step 1. Create a truth table for all the wffs in $\Sigma \cup \{\bs{\tau}\}$. [Since $\Sigma \cup \{\bs{\tau}\}$ is finite, this step is doable in finitely many operations.]
Step 2. Find all rows of the truth table which correspond to truth assignments which satisfy all wffs in the set $\Sigma$. If there are none, return ``$\Sigma \vDash \bs{\tau}$" (this corresponds to our second main case for tautological implications described in Chapter 2). [Since there are finitely many cells in our truth table created in Step 1 this step is doable in finitely many operations.]
Step 3. For each of the rows in Step 2, look at the cell corresponding to $\bs{\tau}$. If for any row, $\bs{\tau}$ has a value of $F$, return $\Sigma \nvDash \bs{\tau}$. Otherwise, if for every row $\bs{\tau}$ has a value of $T$, return $\Sigma \vDash \bs{\tau}$. [This step is doable in finitely many operations.]
There is no guesswork or cleverness in the steps outlined above, and since the instructions are finite and the process produces a ``yes/no" response, the procedure outlined is effective. \qed
\end{pf}
\begin{cor}
For a finite set of wffs $\Sigma$, the set of tautological consequences, $\{\bs{\tau} \in \W|\Sigma \vDash \bs{\tau}\}$, is decidable.
\end{cor}
The above tells us that given finitely many premises, and any other statement, we can definitively prove whether or not that statement is a consequence of the premises. In particular, in axiomatic mathematics, we begin with a set of statements that we assume to be true, and the theory of those axioms (e.g. group theory, field theory, Zermelo-Fraenkel set theory, etc.) is all statements that we can prove assuming the truth of those axioms, including statements that say that certain things \textit{do not follow} from the axioms. If we have finitely many axioms, then our results about the sentential logic model indicate that we can completely decide which statements follow from our axioms and which do not. \textit{There are no undecidable statements in a theory with finitely many axioms.} However, many of our most beloved and familiar axiomatic systems implicitly involve \textit{infinitely many axioms}.
For example, one of the axioms of Peano arithmetic states: ``If $n\in \NN$, then $S(n) \in \NN$" where $S$ is the successor function. As seasoned mathematicians, our concept of this statement is that it asserts one thing, one of the foundational properties that defines the set $\NN$. Now, we could translated this statement into our sentential language as the sentence symbol, say, $\bs{A_1}$. The problem
is that if we wish to express the structure of Peano arithmetic with our sentential language, then such a translation is unhelpful. This unhelpfulness comes from the fact that our sentence symbols are our most basic propositions with no inherent meaning behind the symbol. We never look at the meaning of what the sentence symbol is intended to translate. The power in the above axiom of Peano arithmetic comes in the ``if/then" structure. By translating the whole statement as one sentence symbol, we have lost the deducing power of the axiom.
We can go to the other extreme and intend for $\bs{A_0}$ to translate ``$0 \in \NN$, $\bs{A_1}$ to translate $``1 \in \NN$, etc. So, $\bs{(A_0 \rightarrow A_1)}$ could be used to support the statement ``If $0 \in \NN$, then $S(0) \in \NN$," and similarly for all other natural numbers. Thus, if we wish to support the structure of Peano arithmetic using sentential logic, we could include the infinitely many wffs $\bs{(A_i \rightarrow A_{i+1})}$ to support the statement ``The successor of every natural number is a natural number."
Thus, if we are attempting to represent the proof of a statement that follows from the axioms of Peano arithmetic in the sentential language, we would do so by stating that ``$\Sigma \vDash \bs{\tau}$" where $\Sigma$ is the set of all Peano axioms translated into the sentential language, including the wffs $\bs{(A_{i} \rightarrow A_{i +1})}$ for each $i \in \NN$, and where $\bs{\tau}$ is the statement we are proving, i.e, a statement of the theory of Peano arithmetic. This goes to show that as far as Sentential Logic is concerned we may wish to include the possibility of infinitely many axioms for the theory under consideration. Thus, if our desire is, given the axioms which determine a theory, to be able to decide exactly which statements follow from those axioms and which do not, it is insufficient to say that $\{ \bs{\tau} \in \W| \Sigma \vDash \bs{\tau} \}$ is decidable for $\Sigma$ finite. We should also consider cases where $\Sigma$ is infinite as with the axioms of Peano arithmetic.
We already know from the discussion above that some infinite sets \textit{must} be undecidable. In fact, G\"odel's Incompleteness Theorem will show us that, in general, the set of tautological consequences of an infinite set $\Sigma$ (for example the axioms of Peano arithmetic) will be undecidable. So, our goal of decidability for every particular theory in mathematics is unattainable. However, ``half" of decidability is attainable in the following sense.
\begin{pr}
We will say that a set of expressions $\Sigma$ within the sentential language is \textit{effectively enumerable} if and only if there is an effective procedure that will list in order the elements of $\Sigma$.
\end{pr}
If $\Sigma$ is infinite, then the process which lists the elements of $\Sigma$ will never finish, but for any element in $\Sigma$, the process must eventually (given a sufficient finite amount of time) output the element as an element from $\Sigma$.
We present the next proposition in order to discuss the difference between effective enumerability and decidability.
\begin{prop}\label{effEnumYes}
A set $\Sigma$ of expressions is effectively enumerable if and only if there is an effective procedure which, given any expression $\bs{\varepsilon}$ produces the answer ``Yes" if and only if $\bs{\varepsilon} \in \Sigma$.
\end{prop}
The last piece of our proposition bears some remark before proceeding to the proof. Saying, ``Yes" if and only if $\bs{\varepsilon} \in \Sigma$ \textit{does not mean} that the procedure will answer ``No" if $\bs{\varepsilon} \notin \Sigma$. It \textit{may}, or the process may give no answer but enter an infinite loop instead. The only stipulation is that the procedure cannot answer ``Yes" if $\bs{\varepsilon} \notin \Sigma$.
\begin{pf}
If we are given the expression $\bs{\varepsilon}$, we will use our given effective procedure for listing the elements of $\Sigma$. Our procedure will give a return of ``Yes" if $\bs{\varepsilon}$ is encountered. If $\bs{\varepsilon}$ is not in $\Sigma$, our procedure will continue to list elements of $\Sigma$ forever (we are of course assuming that $\Sigma$ is an infinite set) never answering ``Yes."
If now we are given the effective procedure that will answer ``Yes" if and only if expression $\bs{\varepsilon} \in \Sigma$, we design the following procedure to list the elements of $\Sigma$. Note that our effective procedure must give an answer of ``Yes" when fed $\bs{\varepsilon}$, but may take a time of $k$ minutes or less to report this answer. So, in the following procedure we re-test expressions for greater and greater amounts of time to ensure that they end up in our listing.
Step 1. Examine all 1-tuples which use symbols from the following subset of the Sentential alphabet: $\{\bs{(},\bs{)},\bs{\neg},\bs{\vee},\bs{\wedge},\bs{\rightarrow},\bs{\leftrightarrow},\bs{A_1}\}$. Test each 1-tuple expression under the effective procedure for 1 minute. If the procedure yields an answer of ``Yes", add that expression to the list of $\Sigma$.[Since there are only finitely many 1-tuples using these symbols, this will take a finite amount of time.]
Step 2. Examine all 1-tuples and 2-tuples which use symbols from the following subset of the Sentential alphabet: $\{\bs{(},\bs{)},\bs{\neg},\bs{\vee},\bs{\wedge},\bs{\rightarrow},\bs{\leftrightarrow},\bs{A_1},\bs{A_2}\}$. Test each 1-tuple expression and 2 tuple expression under the effective procedure for 2 minutes. If the procedure yields an answer of ``Yes", add that expression to the list of $\Sigma$.[Since there are only finitely many 1-tuples and 2-tuples using these symbols, this will take a finite amount of time.]\\
\begin{Huge}\vdots \end{Huge}
Step i. Examine all 1-tuples, 2-tuples,\ldots, and $i$-tuples which use symbols from the following subset of the Sentential alphabet: $$\{\bs{(},\bs{)},\bs{\neg},\bs{\vee},\bs{\wedge},\bs{\rightarrow},\bs{\leftrightarrow},\bs{A_1},\bs{A_2},\ldots,\bs{A_i}\}.$$ Test each 1-tuple expression, 2-tuple expression,\ldots, and $i$-tuple expression under the effective procedure for $i$-minutes. If the procedure yields an answer of ``Yes", add that expression to the list of $\Sigma$.[Since there are only finitely many 1-tuples, 2-tuples,\ldots, and $i$-tuples using these symbols, this will take a finite amount of time.]
This procedure consists of finite instructions which could easily be carried out by a computer program, and is thus effective. Given any expression $\bs{\varepsilon}$ in $\Sigma$, this expression is some $n$-tuple and thus involves only finitely many symbols from our sentential alphabet. It will come under examination at all steps subsequent to and including Step $n$. Our effective procedure must give an answer of ``Yes" when fed $\bs{\varepsilon}$, but may take a time of $k$ minutes or less to report this answer. So, this expression will be added to the list of elements of $\Sigma$ for some (and possibly all) steps from Step $n$ to Step $k$ (if $k\geq n$). Also, each step will terminate in finite time since we only have the procedure checking each expression finitely long (although that time for each expression increases as the step number increases). Thus, we avoid an infinite loop if the effective procedure given to us enters an infinite loop when $\bs{\varepsilon} \notin \Sigma$. Thus, the effective procedure given above will list each element of $\Sigma$ (in fact each element of $\Sigma$ will be listed infinitely many times, but the algorithm could be adjusted to fix this fact if it is deemed to be undesirable), and therefore, $\Sigma$ is effectively enumerable. The proposition holds.\qed
\end{pf}
This proposition highlights the difference between decidability and effective enumerability. With decidability, our effective procedure reports ``Yes" when the expression $\bs{\varepsilon} \in \Sigma$ and also ``No" when $\bs{\varepsilon} \notin \Sigma$. We are able to decide exactly what is and what is not in $\Sigma$. But with effective enumerability, our procedure only definitely reports ``Yes" if $\bs{\varepsilon} \in \Sigma$, but not necessarily ``No" if $\bs{\varepsilon} \notin \Sigma$. With an effectively enumerable set, and a particular $\bs{\varepsilon}$ under consideration, if our effective procedure has taken 1,000,000 years and has not given us an answer of ``Yes", we still cannot say that $\bs{\varepsilon}$ is not in our set, for perhaps in the next iteration the procedure will answer ``Yes." So, in this sense effective enumerability is half of decidability. It is in this sense that our goal is ``half" attainable. We use our result to address our question of provability within the sentential model.
\begin{pr}
If $\Sigma$ is a decidable set of wffs, the set of tautological consequences of $\Sigma$ is effectively enumerable.
\end{pr}
\begin{pf}
We have an effective procedure to list all of the elements of $\Sigma$ as $\bs{\sigma_1}, \bs{\sigma_2},\bs{\sigma_3},\ldots$ Let $\bs{\tau}$ be an arbitrarily given wff.
Step 1. Confirm or deny $\emptyset \vDash \bs{\tau}$ using an appropriate truth table. [This is an effective procedure since $\emptyset$ is a finite set.] If the statement is true report ``Yes."
Step 2. Confirm or deny $\bs{\sigma_1} \vDash \bs{\tau}$ using an appropriate truth table. If the statement is true, report ``Yes."\\
\begin{Huge}\vdots \end{Huge}
Step $i$. Confirm or deny $\{\bs{\sigma_1},\bs{\sigma_2},\dots, \bs{\sigma_i}\}\vDash \bs{\tau}$ using an appropriate truth table. If the statement is true, report ``Yes."[This is an effective procedure since $\{\bs{\sigma_1},\bs{\sigma_2},\dots, \bs{\sigma_i}\}$ is a finite set.]
Eventually this procedure, which is effective, containing finite instructions and involving no guesswork, must report ``Yes" if and only if $\bs{\tau}$ is a tautological consequence of $\Sigma$ by the corollary to the Compactness Theorem. For if $\Sigma \vDash \bs{\tau}$, then there exists finite $\Sigma_f \subseteq \Sigma$ such that $\Sigma_f \vDash \bs{\tau}$, and all members of $\Sigma_f$ must eventually be represented in one of the steps above. By Proposition $\ref{effEnumYes}$, the set of tautological consequences of $\Sigma$ must be effectively enumerable. \qed
\end{pf}
Such a result encourages our endeavor in mathematics to find new results for the above proposition indicates that all true facts following from a set of premises must be effectively enumerable. So, what this result indicates is that if a proof is to be found from a set of assumptions, it can be found. If a statement does not follow from our premises or axioms, then we may be able to show that it does not follow or we may not.
For instance, Goldbach's Conjecture in number theory states that every even integer greater than 2 is the sum of two primes. This conjecture, although it has great concrete number evidence to support it, remains unproven. Suppose $\Sigma$ is the set of all statements true in number theory. Now, if Goldbach's Conjecture is a true statement of number theory, then our results above indicate that there must be a deduction which shows it to be true i.e. we can say that $\Sigma_f \vDash \bs{\tau}$ where $\Sigma_f$ is a finite subset of $\Sigma$ and $\bs{\tau}$ is Goldbach's Conjecture. We can think of $\Sigma_f$ as a set of axioms we might be assuming. As long as we are assuming the right axioms $\Sigma_f$, then we ought to be answer ``yes" to Goldbach's Conjecture being a consequence of $\Sigma_f$ if Goldbach's Conjecture is true of number theory. However, if Goldbach's Conjecture is not provable from a given $\Sigma_f$, we may not be able to say so i.e. we may not be able to answer ``No" to its being a consequence of our current set of axioms that we are operating under. We have no idea of whether we should stop searching for a proof for Goldbach's Conjecture given our current set of axioms. It could be (as with another famous number theoretic result that was unproven for hundreds of years, Fermat's Last Theorem) that a couple more years of research will yield exactly the sort of proof that we seek. So, we may soldier on with the mathematical project encouraged to think that we can prove all true mathematical results that are true given our current set of axioms. We just may be unable to know if some statement is not a consequence of our current set of axioms.
\section{Shortcomings of Sentential Logic}
\hspace{0.5in} Having examined some of the nice results and properties that the sentential model of logic has and that we would like to see for a model of humanity's deductive thought processes, we now consider where our model falls short.
A severe limitation of our model was hinted at above when we discussed one of the axioms of Peano arithmetic: ``If $n \in \NN$, then $S(n) \in \NN$." We saw that we could translate this axiom into infinitely many statements in the sentential language. Such a translation is awkward to work with however. On the other hand, we saw that if we attempt to translate the statement as a single sentence symbol, we lose the deductive power that the axiom is intended to express. Of course, we could rephrase the axiom as, ``For all $n \in \NN$, $S(n) \in \NN$". The idea of the axiom is that if we \textit{range over the set} that is the natural numbers, the successor of any one number will also be a natural number. It is the inability to express this idea of ranging over a set that leads us to our dilemma in expressing the Peano axiom in the sentential language and is a significant shortfall in our language. We do not have sufficient structure in our language to compactly describe what we feel to be an intuitive notion. The sentence symbols used as our ``core" or ``atomic" symbols of expressing statements are clunky when we attempt to express connections between them when those connections consist of properties of sets. Our sentential model has a significant shortcoming. However, Sentential Logic is just that: a mathematical model for humanity's deductive thought processes. With it we have proved some interesting and useful results that indicate limits to our deductive endeavors. It has served as an excellent foundation and prototype for our next and more refined model, First-Order Logic.
%Another example illustrates this limitation of our sentential language. ``For a non-empty set, if every element in the set has property $P$, then there is an element in the set that has property $P$." This statement accords readily with our logical intuitions (or in more common terms, ``no duh").
%If I consider the set of prime natural numbers that are greater than 2, we know that this set is non-empty since it contains the element 3. Every element in this set also has the property that it is odd. So, there must be one prime that is odd. In fact, 3 demonstrates this fact since it is in this set and must thus have the property of being odd.
%The set's being non-empty means that there is an element in it, and since every element must have property $P$, the element that shows us that our set is non-empty must have property $P$. This element thus shows us that there is an element in the set with property $P$.
%This deduction is trivial, but let us attempt to express it in the language of sentential logic. We will try to translate each of the smallest statements as sentence symbols. One statement involved is ``The set is non-empty." We will translate this statement as $\bs{A_1}$ Another is ``Every element in the set has property $P$." Note that with this statement, we cannot necessarily break it down into infinitely many statements each of which we could then translate as an individual sentence symbol like we did with the Peano axiom.
%Suppose our set has a cardinality that is greater than $\aleph_0$ and our property was the property of being in the set. If our set is non-empty, then of course every element in the set has the property of being in the set. Since the set is non-empty there is at least one element that has the property of being in the set. So our statement could hold true for sets with uncountable cardinalities. But of course, we cannot translate for every element in our uncountable set the statement that that element is in that set, for we only have countably many sentence symbols to work with. We could extend our alphabet to be uncountable, and then many of the same results we have developed for Sentential Logic would still hold, but our language would become hopelessly unwieldy in expressing our deduction under consideration. And this deduction is so simple!
%So, let us translate ``Every element in the set has property $P$" as the single sentence symbol $\bs{A_2}$. The third statement is ``There is an element of the set that has property $P$." Let us translate this statement as sentence symbol $\bs{A_3}$. This statement is distinct in what it asserts from either of the first two statements, and so we must translate it as a distinct sentence symbol. We could thus attempt to represent our deduction in Sentential Logic as $\{\bs{A_1},\bs{A_2}\}\vDash \bs{A_3}$, but since the sentence symbols our distinct, this will be a false assertion. We could represent our deduction totally in the sentential language as the wff $\bs{((A_1 \wedge A_2)\rightarrow A_3)}$, but this will not be a tautology of its own right as we think it ought to be. The best we could do is think of it as an axiom in whatever system we end up considering. So, even with this very simple deduction, we are sorely disappointed in our sentential model.
\newpage
\chapter{First-Order Languages and Structures}
\hspace{0.5in} In the last two chapters, we developed the structure of sentential logic and examined some of its nice properties as a model for human deduction. We also saw its limitations when we attempted to describe properties of sets. In this chapter, we begin the development of a new and richer model of logic for which sentential logic will serve as the prototype--first-order logic.
Since we are attempting to present a mathematical model of deduction, we will develop first-order logic in a rigorously mathematical fashion. However, many of the results and processes developed in sentential logic carry over to the development of first-order logic, so some discussion of similar results will be suppressed in the first-order setting.
Since G\"odel's Incompleteness Theorem is stated in terms of first-order logical statements, we are moving one step closer to the main result of this thesis. In this chapter, we first develop first-order languages and then discuss what truth and falsity mean within our new system.
\section{First-Order Languages}
\hspace{0.5in} For a first-order language, we assume that we have an infinite, but countable, alphabet in which we have two types of symbols: logical symbols and parameters. We catagorize these in the chart below.
\begin{figure}[!h]
\begin{tabular}{|l|l|}
\hline
\textbf{Symbol} & \textbf{Type}\\
\hline
$\bs{(}$ & Logical Grouping\\
\hline
$\bs{)}$ & Logical Grouping\\
\hline
$\bs{\neg}$ & Logical Connective\\
\hline
$\bs{\rightarrow}$ & Logical Connective\\
\hline
$\bs{v_n}$ for every $n \in \NN$ & Logical Variable Symbols\\
\hline
$\bs{\approx}$ & Logical Equality (optional)\\
\hline
$\bs{\fa}$ & Parameter; Quantifier\\
\hline
$\bs{P^n_i}$ for at least one $n$ and one $i$ in $\ZZ^+$ & $n$-place Predicate Parameter(s)\\
\hline
$\bs{a_n}$ for $n \in \ZZ^+$ & Constant Parameter(s) (optional)\\
\hline
$\bs{f^n_i}$ for $n,i \in \ZZ^+$ & $n$-place Function Parameter(s)\\
& (optional)\\
\hline
\end{tabular}
\end{figure}
Note: even though we have termed the equality symbol as a logical symbol, we will also think of it as a 2-place predicate symbol.
To specify a particular language, we say whether we have equality and what parameters are present. Our language will have an intended interpretation, but our language by itself is just a formal collection of symbols without any inherent meaning. The idea behind a first-order language is that it can \textit{support} a particular mathematical structure.
Why we are including and catagorizing the specific symbols that we have in the table bears some comment. The parentheses, ``$\bs{\neg}$," and ``$\rightarrow$" symbols are familiar from sentential logic. We do not include any other logical connectives because the set $\{\bs{\neg},\bs{\rightarrow}\}$ is a complete set as mentioned in the last chapter.
We saw that the major downfall of sentential logic was its inability to express properties which range across whole sets. This inability came from the clunkiness of the sentence symbols. To remedy this in first-order logic we essentially decompose the sentence symbols to be able to express a richer structure. To this end we introduce a quantifier, variables, constants, predicate symbols and function symbols.
Variable symbols will be stand-ins for the elements in the set that our particular language fundamentally deals with. Constants will also come from this set, but including function symbols allows us to minimize how many constants we use in our language.
For instance, if we are working with the language for number theory, we will specify the constant $\bs{0}$ as being in our language. Of course, the intended translation of $\bs{0}$ is 0. To avoid further constant symbols, we will use the 1-place function symbol $\bs{S}$ (where the intended translation is the successor function), and write $\bs{S(0)}$ to translate for 1.
The quantifier $\bs{\fa}$ is intended to translate ``for every member" in the set that our language fundamentally deals with. This symbol will essentially encode the idea of ranging over a whole set. We will also want to talk about the existence of certain elements in a set. For instance, we might want to say, ``There is a least natural number." We can actually encode this idea using $\bs{\neg\fa\neg}$. ``There is a least natural number" is equivalent to ``It is not the case that for every natural number, the natural number is greater than some other natural number." In some of our discussion and examples, we replace the $\bs{\neg\fa \neg}$ pattern with $\bs{\es}$ as an abbreviation for ``there is a member."
The $n$-place predicate symbols together with the variables in our language essentially take the place of our sentence symbols in sentential logic. The intended translation of each predicate symbol is some property that elements of the foundational set may or may not have. For instance in the language of number theory the 2-place predicate symbol $\bs{<}$ is intended to translate the less than property. Thus, $\bs{S(0) < S(S(0))}$ will translate the proposition ``One is less than two." For a unary predicate symbol $\bs{P}$, $\bs{\es x Px}$ could be used to support the meaning that there is a member of a set that has property $P$ (or equivalently, we could write $\bs{(\neg \fa x (\neg Px))}$).
Since predicate symbols give the translation of properties, the requirement that each particular language should have at least one predicate symbol makes sense. Without a predicate symbol we cannot translate any properties and hence no propositions can be translated since each proposition will include one or more properties that either are or are not fulfilled, determining the truth value of the proposition.
All of the features of our expanded first-order system interplay to give us a wider range of expressiveness.
Since we have mentioned the Peano Axioms several times now and will use them in a few more examples, we list them for the reader's reference (this list is adapted from page 1 of \cite{Ross}).
\noindent\textbf{\underline{Peano Axioms of Arithmetic:}}\\
N1 \quad $0 \in \NN$.\\
N2 \quad If $n \in \NN$, then its successor is in $\NN$.\\
N3 \quad $0$ is not the successor of any element of $\NN$.\\
N4 \quad If $n$ and $m$ in $\NN$ have the same successor, then $n = m$.\\
N5 \quad A subset of $\NN$ which contains $0$, and which contains $n+1$ whenever contains $n$, must equal $\NN$.
\begin{ex}
\textbf{Language of Number Theory}:\\
Equality: Yes\\
Predicate Symbols: One, 2-place predicate symbol $\bs{<}$\\
Constant Symbols: $\bs{0}$\\
1-place Function Symbols: $\bs{S}$ (intended to translate the successor function\\
2-place Function Symbols: $\bs{+}$ (for addition), $\bs{\cdot}$ (for multiplication), and $\bs{E}$ (for exponentiation).\\
Note in the above list that all of these parameters are just symbols. There is no inherent meaning behind them, but we can think of them as being sufficient to support a particular meaning. We will make this idea more rigorous in the discussion to come.
We can use the formal expression
$$\bs{ \fa v_1(\neg Sv_1 \approx 0)}$$ to support the logical structure of the Peano Axiom, ``0 is not the successor of any number."
\end{ex}
\begin{ex}\label{exSucNatrl}
Using the same language for number theory, we can translate the Peano Axiom ``The successor of each natural number is itself a natural number," with ease into the first-order language for number theory $$ \bs{\fa v_1 (\exists v_2 (S(v_1) = v_2))}.$$ In English, ``For each natural number, there is another natural number equal to the successor of the first natural number." In sentential logic, to translate this same axiom, we declared that $\bs{A_{i}}$ was intended to translate ``$i \in \NN$," so that $\bs{A_0} \sim `` 0 \in \NN$", $\bs{A_1} \sim ``1 \in \NN$", etc. Similarly, we declared that $\bs{A_{i + 1}}$ was intended to translate $S(i) \in \NN$. So, $\bs{A_1} \sim ``S(0) \in \NN$", $\bs{A_2} \sim ``S(1) \in \NN$", etc. Thus, we expressed our axiom of Peano arithmetic as the wffs $\bs{(A_{i} \rightarrow A_{i+1})}$ for each $i \in \NN$. So, $\bs{(A_0 \rightarrow A_1)} \sim ``0 \in \NN \text{ implies } S(0) \in \NN$".
\end{ex}
Example $\ref{exSucNatrl}$ demonstrates the strength of first-order logic in expressing properties that hold for entire sets. Despite the enhanced power of expressiveness in our first-order languages, we will not, in general, be able to express every proposition about a particular theory in the first-order language for that theory.
\begin{ex}
Using the language of number theory, we cannot express the proposition, ``Every non-empty set of natural numbers has a least element." The reason for this is that this statement describes a property which ranges over sets. In our language for number theory, our quantifier $\bs{\fa}$ ranges over the set of natural numbers, not the power set of the natural numbers. When we have the ability to range over members of a set and also over members of the power set of that set, we are working with a different mathematical model of logic called ``second-order logic."
Another example of a second-order logical statement is the Completeness Axiom of the real numbers: ``Every bounded above set has a least upper bound." Notice that we are ranging over sets, not elements of sets.
\end{ex}
We could create a language for which our fundamental \textit{class} is all sets (the ``set" of all sets is too large to be a set and hence we have to think of this object as a class, but we may think of our quantifier $\bs{\fa}$ as ranging over a class instead of a set) as follows.
\begin{ex}\label{langSetThy}
\textbf{Language of Set Theory}\\
Equality: Yes\\
Predicate Parameters: One 2-place predicate symbol $\bs{\in}$ (intended translation: ``is a member of")\\
Constant Symbol: $\bs{\emptyset}$ (intended translation: the set that contains no elements)\\
Function Symbols: None\\
With this language, we can write such statements of set theory as $$\bs{(\neg \es v_1 \fa v_2 v_2 \in v_1)}$$
In English, this says that there is no set of which every set is a member.
\end{ex}
In this language for set theory (we may need to add some more predicate symbols) we could express our proposition that every set of natural numbers has a least element, but we cannot express this statement \textit{about} number theory in the first-order language of number theory.
We give another example of a first-order language for a familiar mathematical structure to give the reader a little more intuitive feel for first-order languages before defining them rigorously.
\begin{ex}\label{langGrp}
\textbf{First-Order Language for an Arbitrary Group (Language for Group Theory)}\\
Equality: Yes\\
Predicate Parameters: One 1-place predicate symbol $\bs{\in}$ (intended translation: ``is a member of the group")\\
Constant Symbols: $\bs{e}$ (intended translation: the identity element of the group)\\
Function Symbols: One 2-place function symbole $\bs{\ast}$ (intended translation: the binary group operation)\\
We can translate the group axioms into our language (we assume that our group is non-empty). $$\bs{\fa v_1 \fa v_2 ((\in v_1 \wedge \in v_2) \rightarrow \in v_1 \ast v_2)}$$ $$\bs{\fa v_1 \fa v_2 \fa v_3 (v_1 \ast (v_2 \ast v_3) \approx (v_1 \ast v_2) \ast v_3)}$$ $$\bs{\fa v_1 (v_1 \ast e \approx v_1 \wedge e \ast v_1 \approx v_1)}$$ $$\bs{\fa v_1 \es v_2 (v_1 \ast v_2 \approx e \wedge v_2 \ast v_1 \ast e)}$$
These statements' English equivalents are as follows:\\
``If $v_1$ and $v_2$ are members of the group, then $v_1 \ast v_2$ is a member of the group" (the group is closed under the binary operation).\\
``For all elements $v_1$, $v_2$, and $v_3$ in the group, $v_1 \ast (v_2 \ast v_3) = (v_1 \ast v_2)\ast v_3$" (the binary operation is associative).\\
``For every element $v_1$ in the group, $v_1 \ast e = v_1 = e \ast v_2$" (the group has an identity element with respect to the group operation).\\
``For every element in the group $v_1$, there is an element $v_2$ such that\\ $v_1 \ast v_2 = e = v_2 \ast v_1$" (every element in the group has an inverse).\\
\end{ex}
\section{Rigorous Development of First-Order Languages}
\hspace{0.5in} In our discussion of first order languages above, we were playing fast and loose with the symbols at our disposal to give the reader some initial feel for the differences between first-order languages and the language for sentential logic. We now develop things more rigorously.
First, an expression in a first-order language will be a finite sequence of symbols from the first-order language alphabet. For each first order language and for each $n$-place function symbol $\bs{f}$, we will define a formula-building operation $F_f$ whose domain is the set of all variables and constant symbols in the language, and where $\F_f(\bs{\varepsilon_1},\bs{\varepsilon_2},\ldots,\bs{\varepsilon_n}) = \bs{f\varepsilon_1\varepsilon_2\cdots \varepsilon_n}$.
\begin{df}
The set of \dfem{terms} in a first-order language is the set generated (in the sense of generation discussed in Chapter 2) by the class of formula building operations $\Ff = \{\F_f: \bs{f} \text{ is a } n- \text{place function symbol in the language}\}$ applied to the variables and constant symbols of the language.
\end{df}
\begin{ex}
In the language of number-theory discussed above, $\bs{0}$, $\bs{S0}$, and $\bs{+v_2 S0}$ are terms in the language.
\end{ex}
Note that the intended meaning of $\bs{S0}$ is precisely the same as that for $\bs{S(0)}$, and similarly for $\bs{+v_2S0}$ and $\bs{v_2 + S(0)}$. For the purposes of establishing rigorous results for first-order languages, we have defined terms without parentheses in a non-intuitive way (so that $\bs{+v_2S0}$ means the same thing as $\bs{v_2 + S(0)}$). This way of representing mathematical expressions is actually used in practice as an alternative mode of entry into calculators. It is often referred to as ``Polish notation."
\begin{ex}
In the language of set theory discussed above, only the variables and the constant symbol $\bs{\emptyset}$ are terms since there are no $n$-place function symbols.
In the language for an arbitrary group, $\bs{\ast v_1 v_2}$ and $\bs{\ast e \ast v_1 v_2}$ are terms.
\end{ex}
Notice that terms assert nothing whatsoever but are merely the objects about which assertions can be made. In this sense, the terms are the nouns and pronouns for our particular first-order language.
\begin{df}
An \dfem{atomic formula} is an expression of the form $\bs{Pt_1t_2\cdots t_n}$ where $\bs{P}$ is an $n$-place predicate symbol and where $\bs{t_i}$ for $1\leq i \leq n$ is a term.
\end{df}
Note that terms are not atomic formulas, but atomic formulas are built from a finite sequence of terms and a predicate symbol. The name ``atomic formulas" is suggestive of their function. Just as the sentence symbols were the core wffs in the sentential language, the atomic formulas are the core wffs in each sentential language. Each $n$-place predicate symbol is intended to translate a property that the $n$ terms have or do not have. Thus, $\bs{Pt_1t_2\cdots t_n}$ asserts that the $n$ terms have property $\bs{P}$.
\begin{ex}
$\bs{<0 S0}$ translates the assertion that 0 is less than 1 in the language for number theory.
$\bs{\approx v_1 v_2}$ translates the assertion that one variable is equal to another in any first-order language under consideration. This expression is an atomic formula since we consider $\bs{\approx}$ to be a 2-place predicate symbol as well as a logical symbol.
In the language for an arbitrary group, $\bs{\in \ast v_1 v_2}$ is an atomic formula. It asserts that the group operation between $v_1$ and $v_2$ is a member of the group.
\end{ex}
Having defined the atomic formulas and made the correlation between these expressions and the sentence symbols in sentential logic, we are now in a position to define the wffs for any particular first-order language.
First we define the formula-building operations on the set of expressions for a first order language as follows: $$\F_\neg (\bs{\alpha}) = \bs{(\neg \alpha)}$$ $$\F_\rightarrow (\bs{\alpha},\bs{\beta}) = \bs{(\alpha \rightarrow \beta)}$$
$$\F_{\fa,i}(\bs{\alpha}) = \bs{\fa v_i \alpha} \text{ for } i = 1,2,\ldots$$
The first two formula building operations are familiar from sentential logic. The third is new with the introduction of a quantifier symbol into first-order languages.
\begin{df}
The set of \dfem{wffs} for a first-order language is the set generated from the set of atomic formulas by formula-building operations $\F_\neg, \ \F_\rightarrow,$ and $\F_{\fa,i}$ for each $i=1,2,\ldots$.
\end{df}
\begin{ex}
In the language for number theory, $\bs{<0v_1}$ and $\bs{\approx 0v_1}$ are atomic formulas and hence wffs in that language. Hence $$\F_\neg(\bs{<0v_1}) = \bs{(\neg <0v_1)},$$ $$\F_\rightarrow(\bs{(\neg <0v_1)},\bs{\approx 0v_1}) = \bs{(\bs{(\neg <0v_1)\rightarrow \bs{\approx 0v_1})}},$$ and $$\F_{\fa,1}(\bs{(\bs{(\neg <0v_1)\rightarrow \bs{\approx 0v_1})}}) = \bs{\fa v_1 \bs{(\bs{(\neg <0v_1)\rightarrow \bs{\approx 0v_1})}}}$$ are each wffs in that language as well. Note the different use of equality above. Remember that $\bs{\approx}$ is a formal symbol in the language whereas we use ``=" above to say what the output from a formula building operation is. The last wff is the translation of the Peano axiom ``Zero is not the successor of any natural number." We translated this axiom earlier in our intuitive initial discussion, but this is the form in the strict use of our formal language.
\end{ex}
\begin{ex}
In the language of set theory, the wff $$\bs{\fa v_1 (\neg \fa v_2 \in v_2 v_1)}$$ is the wff that translates the axiom that there is no set which contains every set. Compare this with the more informal Example $\ref{langSetThy}$. Essentially we have replaced $\bs{es}$ with $\bs{\neg \fa \neg}$ and simplified double negations.
In the language of an arbitrary group (Group Theory), the wff $$\bs{ \fa v_1 ( \approx \ast v_1 e v_1 \wedge \approx \ast e v_1 v_1)}$$ This wff translates the group axiom that asserts the existence of inverses.
\end{ex}
Like with sentential logic, there is a Unique Readability Theorem for the wffs in any first-order language. Although the methods are slightly different for the proof for first-order languages, we skip the development trusting that the reader will readily accept the fact of unique readability given the rigorous development for the sentential language.
\subsection{Free Variables}
\hspace{0.5in} Unlike sentential logic, not every wff will be able to translate an English (or other natural language) sentence. For instance, in the language of number theory, $\bs{< v_2 v_1}$ is an atomic formula, hence a wff. However, since $\bs{v_1}$ and $\bs{v_2}$ are each intended to be translated as simple place holders for any natural numbers, it cannot be said that there is an English \textit{statement} that can be translated into this wff. It asserts nothing, but merely provides the structure necessary to say that one natural number is less than another. Unless specific natural numbers are specified or the natural numbers which might fill the place holders are delimited , we have essentially ``\underline{\hspace{0.25in}}$ <$ \underline{\hspace{0.25in}}".
On the other hand the wff $\bs{\fa v_1 \fa v_2 < v_2 v_1}$ has an English equivalent that is a proposition: ``Every natural number is less than every other natural number." Now, this proposition is false, but that is beside the point. The point is that we have delimited both of the variables $\bs{v_1}$ and $\bs{v_2}$ so that we are actually making a claim. Of course such wffs are the most interesting to us, and so we define these notions more rigorously. We first want to design a recursively defined function that will mark by the number 1 the occurrence of a non-delimited (free) variable.
Let $\CA$ denote the set of all atomic formulas, we define for any first-order language $h_v: \CA \longrightarrow \{0,1\}$ by $$h(\bs{\alpha}) = \left\lbrace \begin{array}{ll} 1 & \text{if } \bs{v} \text{ occurs in } \bs{\alpha}\\ 0 & \text{otherwise}\\ \end{array} \right.$$ The Unique Readability Theorem (which we assume holds for all first-order languages) and the Recursion Theorem will guarantee the existence of a unique extension $\ol{h_v}$ of $h_v$ where $$\ol{h_v}(\bs{\alpha}) = h_v(\bs{\alpha}) \text{ for atomic formula } \bs{\alpha},$$ $$\ol{h_v}(\bs{(\neg \alpha)}) = \ol{h_v}(\bs{\alpha}),$$ $$\ol{h_v}(\bs{(\alpha \rightarrow \beta)}) = \max\{\ol{h_v}(\bs{\alpha}), \ol{h_v}(\bs{\beta})\}, \text{ and}$$ $$\ol{h_v}(\bs{\fa v_i \alpha}) = \left\lbrace \begin{array}{ll} \ol{h_v}(\bs{\alpha}) & \text{if } \bs{v} \neq \bs{v_i}\\ 0 & \text{if } \bs{v} = \bs{v_i}\\ \end{array} \right..$$
\begin{df}
In a first-order language a variable $\bs{v}$ \dfem{occurs free} in a wff $\bs{\alpha}$ if $\ol{h_v}(\bs{\alpha}) = 1$.
\end{df}
\begin{ex}
In the language for number theory, for the wff $\bs{0 \text{ and }$$ $$\lfloor a_0,\ldots, a_m\rfloor = a_0 \text{ if } m =0.$$ Note that $p_0 = 2$, $p_1 = 3$, etc. Now take an expression from the first-order language $\bs{\varepsilon} = \bs{s_0s_2\cdots s_m}$ where the $\bs{s_i}$'s are among the indecomposable symbols coming from the alphabet of our language to which we have already assigned natural numbers. We will define the G\"odel number for the expression $\bs{\varepsilon}$ as follows: $$\# \bs{\varepsilon} = \lfloor \# \bs{s_0}, \# \bs{s_1},\ldots, \# \bs{s_m} \rfloor.$$ Notice that if $\bs{\varepsilon} = \bs{s}$ where $\bs{s}$ is an indecomposable symbol in the alphabet of the language, then $\# \bs{\varepsilon} = \lfloor \# \bs{s} \rfloor = \# \bs{s}$ by how we defined the $\lfloor\ldots\rfloor$ operation. Thus, this numbering for all of the expressions in the language is well defined. If $\Psi$ is a set of expressions, then we designate the set of all the G\"odel numbers of all the expressions in $\Psi$ as $$\# \Psi = \{\#\bs{\varepsilon}: \bs{\varepsilon} \in \Psi\}.$$
Notice that our G\"odel numbering of all expressions automatically gives us numbers associated with sequences of expressions (a formal deduction is such a sequence, and we wish to encode deductions as natural numbers). The reason for this is that a sequence of expressions will ultimately be an expression itself.
Now we verify that our numbering is one-to-one. Note that as long as our expression is made up of more than one indecomposable symbol, the G\"odel number for that expression will be a positive even number since it will have at least one power of 2 involved (since $2^{\#\bs{s_0} + 2}$ is a factor of the product). Hence, we will not assign any expression to an odd number (to which we have assigned all of the variables and a few other indecomposable symbols) if it made up of two or more indecomposable symbols. Note also that if we have an expression built up of more than one indecomposable symbol, the smallest its G\"odel number could be would be
$$\# \bs{((} = \lfloor \#\bs{(}, \#\bs{(}\rfloor = \lfloor 0,0\rfloor = 2^{0+2}3^{0+2} = 36.$$ Thus, we are assured that the G\"odel number of any expression built up of more than one indecomposable symbol will be an even number bigger than or equal to 36. We are thus assured that there will be no overlap with the assignments we have already made for the alphabet. The rest of the argument that the assignment of expressions to natural numbers is one-to-one follows immediately from the Fundamental Theorem of Arithmetic which guarantees a unique prime factorization for every natural number and the fact that a G\"odel number of an expression must be a product of consecutive primes, all of which must have a power of at least 2. So, we will have a distinct natural number assigned to every distinct expression/sequence of expressions.
\begin{ex}
Consider the G\"odel number for axiom S1 of the theory $\Cn{A}$.
$$\begin{array}{ll}\#( \bs{\fa v_1 \ Sv_1 \napprox 0} ) &= \#(\bs{\fa v_1 (\neg Sv_1 \approx 0)})\\ & = \lfloor \#(\bs{\fa}),\#(\bs{v_1}), \#(\bs{(}), \#(\bs{\neg}), \#(\bs{S}), \#(\bs{v_1}), \#(\bs{\approx}), \#(\bs{0})\rfloor\\ &= \lfloor 5,11,0,2,7,11,4,6\rfloor\\& = 2^{5+2}3^{11+2}5^{0+2}7^{7+2}11^{11+2}13^{4+2}17^{6+2}\\ & = 2^73^{13}5^27^911^{13}13^617^8\\ &= 239312311565234769445552086952420825357412092800\\\end{array}. $$ Designate this number by $N_1$.
Consider the G\"odel number for the deduction $$\langle \bs{\fa v_1 Sv_1 \napprox 0}, \bs{(\fa v_1 Sv_1 \napprox 0 \rightarrow S0\napprox 0)}, \bs{S0\napprox 0} \rangle$$ (this deduction demonstrates that $\bs{\fa v_1 Sv_1 \napprox 0} \vdash \bs{S0\napprox 0}$ since\\ $\bs{(\fa v_1 Sv_1 \napprox 0 \rightarrow S0\napprox 0)}$ is from logical axiom group 2). Note that following a similar process as above we have $$\begin{array}{ll}\#(\bs{(\fa v_1 Sv_1 \napprox 0 \rightarrow S0\napprox 0)}) = &\\ 2^23^75^{13}7^211^413^917^{13}19^623^829^331^537^241^443^947^853^659^861^367^3&\\ \end{array}.$$ Denote this number by $N_2$. Also, $$\#(\bs{S0\napprox 0}) = 2^23^45^97^811^613^817^3.$$ Denote this number by $N_3$. $$\begin{array}{ll} \#(\langle \bs{\fa v_1 Sv_1 \napprox 0}, \bs{(\fa v_1 Sv_1 \napprox 0 \rightarrow S0\napprox 0)}, \bs{S0\napprox 0} \rangle)&\\ = \lfloor \#(\bs{\fa v_1 Sv_1 \napprox 0}), \#(\bs{(\fa v_1 Sv_1 \napprox 0 \rightarrow S0\napprox 0)}), \#(\bs{S0\napprox 0})\rfloor &\\ = \lfloor N_1, N_2,N_3\rfloor&\\ = 2^{N_1 +2}3^{N_2 +2}5^{N_3 +2}\\ = 2^{2^73^{13}5^27^911^{13}13^617^8 +2}3^{2^23^75^{13}7^211^413^917^{13}19^623^829^331^537^241^443^947^853^659^861^367^3 +2}&\\ \cdot 5^{2^23^45^97^811^613^817^3 +2}&\\ \end{array}$$
\end{ex}
Obviously, the numbers involved in G\"odel numbering are large even for small expressions, but G\"odel numbering allows us to encode all expressions of our first-order language into the universe for the structure $\Nn$. By one-to-oneness, we can also uniquely decode the images of the expressions and sequences of expressions back into the original expressions and sequences of expressions. This will be key to the proof of G\"odel's Theorem, and we give a brief example of the decoding process.
\begin{ex}
Take the natural number $16,669,800$. The prime factorization of this number is $$2^33^55^27^3 = 2^{1+2}3^{3+2}5^{0+2}7^{1+2} = \lfloor 1, 3,0,1\rfloor.$$ Looking at the table for the assignments for the alphabet, we have the expression $\bs{)\rightarrow()}$.
Note that in general, not every natural number has an expression associated with it. For instance, the number $36,432$ factors as $2^43^2\cdot 11\cdot 23$. Since we do not have a product of consecutive primes, we know that this is not the G\"odel number of an expression in the language.
\end{ex}
\section{Representability in $\Cn{A}$}
\hspace{0.5in}In this section we discuss how we can translate numerical relations in $\Nn$ back into the formal relations. In other words, we discuss how certain relations are able to be represented in the formal language. This will be the other piece that we need to formally prove G\"odel's Theorem.
First, we develop some new notation. For the first-order formula $\bs{\varphi}$, let $\bs{\varphi}(\bs{t}) = \bs{\varphi_{v_1|t}}$, $\bs{\varphi}(\bs{t_1},\bs{t_2}) = (\bs{\varphi_{v_1|t_1}})_{\bs{v_2|t_2}}$, etc. Now, recall the definition of a definable relation.
\begin{df}
Given the structure $\Ss$ and the wff $\bs{\varphi}$, whose free variables are among $\bs{v_1}$, $\bs{v_2}$,\ldots, $\bs{v_k}$, $$\{(u_1,u_2,\ldots,u_k):\ \models_\Ss \bs{\varphi}[[u_1,u_2,\ldots, u_k]]\}$$ is the \dfem{relation that} $\bs{\varphi}$ \dfem{defines} in $\Ss$. Given a $k$-ary relation $R$ in the universe $\UU$ determined by $\Ss$, if there is a $\bs{\varphi}$ such that $$R =\{(u_1,u_2,\ldots,u_k):\ \models_\Ss \bs{\varphi}[[u_1,u_2,\ldots, u_k]]\},$$ then $R$ is said to be \dfem{definable} in $\Ss$.
\end{df}
Take as our structure $\Nn$ whose universe is $\NN$. Then for a $k$-ary relation $R$ in the universe $\NN$, this relation is definable in $\Nn$, if and only if there exists a formula $\bs{\varphi}$ such that for all $(n_1,n_2,\ldots, n_k) \in \NN^k$, $$(n_1,n_2,\ldots n_k) \in R \text{ iff } \models_\Nn \bs{\varphi}[[n_1,n_2,\ldots, n_k]].$$ Recall that this last statement will be so if and only if there is a function $s:\V\longrightarrow \NN$ such that $s(\bs{v_i}) = n_i$ and $\models_\Nn \bs{\varphi}[s]$, and by Theorem $\ref{equivFV}$, $\models_\Nn \bs{\varphi}[s]$ for every function such that $s(\bs{v_i}) = n_i$. Note also that $s(\bs{v_i}) = n_i = \ol{s}(\suc{n_i})$ for any function $s:\V \longrightarrow \NN$. Let $$s_{\bs{v_i}|n_i}^{1\leq i \leq k} \equiv (\cdots((s_{\bs{v_1}|n_1})_{\bs{v_2}|n_2})\cdots )_{\bs{v_k}|n_k}.$$ Then, $$s_{\bs{v_i}|n_i}^{1\leq i \leq k}(\bs{x}) = \left\lbrace \begin{array}{ll}
n_i & \text{if } \bs{x} = \bs{v_i} \text{ for some } 1\leq i \leq k\\
s(y) & \text{otherwise}
\end{array}\right.$$ Of course, since $n_i = \ol{s}(\suc{n_i})$, the function above is the same as the following function:
$$s_{\bs{v_i}|\ol{s}(\suc{n_i})}^{1\leq i \leq k}(\bs{x}) = \left\lbrace \begin{array}{ll}
\ol{s}(\suc{n_i}) & \text{if } \bs{x} = \bs{v_i} \text{ for some } 1\leq i \leq k\\
s(y) & \text{otherwise}
\end{array}\right.$$ Hence, $$\models_\Nn \bs{\varphi}[[n_1,n_2,\ldots,n_k]] \text{ iff there is a function } s \text{ as described above such that }$$ $$ \models_\Nn \bs{\varphi}[s] \text{ iff}$$ $$\models_\Nn \bs{\varphi}\left[s_{\bs{v_i}|\ol{s}(\suc{n_i})}^{1\leq i \leq k}\right].$$ Now, since $\suc{n_i}$ involves no variables, it will always be substitutable for any variable symbol $\bs{x}$. Thus, by repeated application of the Substitution Lemma (Lemma $\ref{subLemma}$) and by applying the new notation developed above, $$\models_\Nn \bs{\varphi}\left[s_{\bs{v_i}|\ol{s}(\suc{n_i})}^{1\leq i \leq k}\right] \text{ iff } \models_\Nn \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})[s].$$ Since $\bs{\varphi}$'s free variables were assumed to be among $\bs{v_1}$, $\bs{v_2}$,\ldots,$\bs{v_k}$,\\ $\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})$ is in fact a sentence, since it has no free variables, whence $$\models_\Nn \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})[s] \text{ iff } \models_\Nn \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k}).$$
So, a $k$-ary relation $R$ on $\NN$ will be definable if and only if for every $(n_1,n_2,\ldots,n_k) \in \NN^k$, $$(n_1,n_2,\ldots,n_k) \in R \text{ iff } \models_\Nn \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k}).$$ If we split this last statement into two implications we have that $$(n_1,n_2,\ldots,n_k) \in R \text{ implies } \models_\Nn \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k}) \text{ and}$$ $$(n_1,n_2,\ldots,n_k) \notin R \text{ implies } \models_\Nn \bs{(\neg}\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})\bs{)}$$ if and only if $R$ is definable in $\Nn$.
Now let $T$ be a theory in a language with the symbols $\bs{0}$ and $\bs{S}$. We define the following:
\begin{df}
The formula $\bs{\varphi}$ \dfem{represents} the $k$-ary relation $R$ of the universe of a model for $T$ if $$(n_1,n_2,\ldots,n_k) \in R \text{ implies } \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k}) \in T \text{ and}$$ $$(n_1,n_2,\ldots,n_k) \notin R \text{ implies } \bs{(\neg}\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})\bs{)} \in T.$$ A relation $R$ is said to be \dfem{representable in theory $\bs{T}$} if there is a formula $\bs{\varphi}$ that represents $R$ in that theory.
\end{df}
Representability is a stronger notion than definability. Suppose $\Ss$ is a model for the sentences in $T$ (with universe $\NN$) and suppose that $\bs{\varphi}$ represents the relation $R$ in the theory $T$. Then, if $(n_1,n_2,\ldots,n_k) \in R$, then $\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k}) \in T$, and of course $\models_\Ss \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})$, which, by the previous discussion is so if and only if $\models_\Ss \bs{\varphi}[[n_1,n_2,\ldots,n_k]]$ for any function $s:\V \longrightarrow \NN$ such that $s(\bs{v_i}) = n_i$. If on the other hand, $(n_1,n_2,\ldots n_k) \notin R$, then $\bs{(\neg}\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})\bs{)} \in T$, and\\ $\nmodels_\Ss \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})$. Again, by our previous discussion, this means that $\nmodels_\Ss \bs{\varphi}[[n_1,n_2,\ldots,n_k]]$. Thus, we have that $\bs{\varphi}$ defines $R$ in $\Ss$, a model for $T$, if $\bs{\varphi}$ represents $R$ in $T$. However, if $\bs{\varphi}$ defines a relation $R$ in a structure $\Ss$ for the language, $\bs{\varphi}$ will only be guaranteed to be representable in the theory $\Th{\Ss}$.
What we will be most concerned about is representability of a relation of natural numbers in the theory $\Cn{A}$. Following the definitions of representability for the theory $\Cn{A}$, a relation $R$ will be representable in $\Cn{A}$ if and only if $$(n_1,n_2,\ldots,n_k) \in R \text{ implies } A \vdash \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k}) \text{ and}$$ $$(n_1,n_2,\ldots,n_k) \notin R \text{ implies } A \vdash \bs{(\neg}\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})\bs{)}.$$
\begin{ex}
As a simple example, the equality relation is representable in $\Cn{A}$. If $m = n$, then clearly $\suc{m} = \suc{n}$. Clearly then, by one of the equality logical axioms, $\vdash \suc{m} \bs{\approx} \suc{n}$, and $A \vdash \suc{m} \bs{\approx} \suc{n}$. If $m \neq n$, then without loss of generality $m >n$, and there is $k>0$ such that $m = n+k$. Now, by logical axioms and axiom S1, $S1 \vdash \suc{k} \bs{\napprox 0}$. By $n$ applications of axiom S2, and formal contraposition, we can obtain that $\{\text{S1},\text{S2}\}\vdash \bs{(\neg \suc{m} \approx \suc{n})}$. Hence, equality may be represented in $\Cn{A}$.
\end{ex}
We need to demonstrate/claim that several relations are representable in $\Cn{A}$ leading up to showing that G\"odel numbering is representable in $\Cn{A}$. The following definition and theorem is helpful in establishing results of representability.
\begin{df}
Let $\bs{\varphi}$ be a formula in which only the variables $\bs{v_1},\bs{v_2},\ldots,\bs{v_k}$ occur free. Then $\bs{\varphi}$ is \dfem{numeralwise determined} by $A$ if for any $k$-tuple $(n_1,n_2,\ldots, n_k)$ either $$A \vdash \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k}) \text{ or}$$ $$A \vdash \bs{(\neg}\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})\bs{)}.$$
\end{df}
\newpage
\begin{thm}
A formula $\bs{\varphi}$ represents a relation $R$ in $\Cn{A}$ if and only if
\begin{itemize}
\item[(i)] $\bs{\varphi}$ is numeralwise determined by $A$, and
\item[(ii)] $\bs{\varphi}$ defines $R$ in $\Nn$.
\end{itemize}
\end{thm}
\begin{pf}
If $\bs{\varphi}$ represents a relation $R$ in $\Cn{A}$, then it is clear by the definition of representable relation applied to $\Cn{A}$, that the two items hold since $\Nn$ is a model of $A$, and hence all of $\Cn{A}$ (recall the discussion above about how representability is stronger than definability).
Suppose now that the two items hold for the relation $R$. If\\ $(n_1,n_2,\ldots,n_k) \in R$, then since $\bs{\varphi}$ defines $R$ in $\Nn$, then \\$\models_\Nn \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})$. Since $\Nn$ is a model of $A$, then we must $A\nvdash \bs{(\neg}\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})\bs{)}$, otherwise we have a contradiction. By item (i) and the definition of ``numeralwise determined," $A \vdash \bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})$. The argument if $(n_1,n_2,\ldots,n_k) \notin R$ is completely analogous. We just need the observation that $$\bs{(\neg(\neg}\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})\bs{))}$$ is tautologically equivalent to $\bs{\varphi}(\suc{n_1},\suc{n_2},\ldots, \suc{n_k})$ and Theorem $\ref{dedEquivTaut}$. \qed
\end{pf}
Numeralwise determination has the following closure properties under the formula building operations indicated in the following theorem (stated without proof).
\begin{thm}
\begin{enumerate}
\item[(i)] Any atomic formula is numeralwise determined by $A$.
\item[(ii)] If $\bs{\varphi}$ and $\bs{\psi}$ are numeralwise determined by $A$, then so are $\bs{(\neg \varphi)}$ and $\bs{(\varphi \rightarrow \psi)}$.
\item[(iii)] If $\bs{\varphi}$ is numeralwise determined by $A$, then so are the following formulas: $$\bs{\fa x (x < y \rightarrow \varphi)}$$ $$\bs{\es x (x < y \wedge \varphi)}.$$
\end{enumerate}
\end{thm}
In what follows, we will also need the following notion.
\begin{df}
A relation $R$ on the natural numbers is \dfem{recursive} if and only if it is representable in some consistent finitely axiomatizable theory (in a language with $\bs{0}$ and $\bs{S}$).
\end{df}
Hence, if we can show that a relation is representable in $\Cn{A}$ it is recursive by definition. This notion of recursive relation is the precise notion of a decidable set (relation) discussed in Section 3.3 by what is known as Church's Thesis.\\
\noindent{\textbf{Church's Thesis}} A relation is decidable if and only if it is recursive.\\
The idea is that the effective procedure that we use is encoded in the formal language and vice versa. Intuitively, the ``guts" behind a computer program are arithmetical operations with 1's and 0's, or 0's and the successor function applied to 0 a finite number of times. Thus, recursiveness is the formal counterpart to decidability.
We have a definition for what it means to represent a relation in a theory. From this point forward when we say that a relation $R$ is representable, we will mean that it is representable in the theory $\Cn{A}$. We extend the notion of representability to functions (a specific type of relation).
\begin{df}
Let $f:\NN^k \longrightarrow \NN$. A formula $\bs{\varphi}$ in which only $\bs{v_1},\ldots,\bs{v_{k+1}}$ occur free will be said to \dfem{functionally represent $\bs{f}$} (in the theory $\Cn{A}$) if for any $n_1,\ldots,n_k \in \NN$, $$A \vdash \bs{\fa v_{k+1}[\varphi}(\suc{n_1},\ldots,\suc{n_k})\bs{\leftrightarrow v_{k+1} \approx \suc{f(n_1,\ldots,n_k)}]}$$
\end{df}
The following theorems are intuitively plausible, and so we omit their proof.
\begin{thm}
If $\bs{\varphi}$ functionally represents $f$ in $\Cn{A}$, then it also represents $f$ (as a relation) in $\Cn{A}$.
\end{thm}
\begin{thm}
Let $f$ be a function on $\NN$ which is (as a relation) representable in $\Cn{A}$. Then we can find a formula $\bs{\varphi}$ which functionally represents $f$ in $\Cn{A}$.
\end{thm}
Now we move into discussing the representability of functions and relations. Ultimately, this discussion will lead up to representability dealing with G\"odel numbering. This representability with G\"odel numbers will be the final piece required to prove the Incompleteness Theorem. We will state most of the following theorems without proof. Proofs and further development may be found in \textit{A Mathematical Introduction to Logic} by Herbert Enderton on pages 202-227.
\begin{thm}
The following functions are representable:
\begin{enumerate}
\item[(i)] The successor function by the formula $\bs{v_2 \approx Sv_1}$.
\item[(ii)] Any $m$-place constant function whose output is some $b$ is represented by the formula $\bs{v_{m+1} \approx}\suc{b}$.
\item[(iii)] The projection function $I_i^m(a_1,a_2,\ldots,a_i,\ldots, a_m) = a_i$ for any $m \in \ZZ^+$ and $1\leq i \leq m$ is represented by $\bs{v_{m+1} \approx v_i}$.
\item[(iv)] Addition, multiplication, and exponentiation are represented by the equations $$\begin{array}{ll} \bs{v_3 \approx v_1 + v_2} &\\ \bs{v_3 \approx v_1 \cdot v_2} &\\ \bs{v_3 \approx v_1 E v_2}&\\
\end{array}$$ respectively.
\end{enumerate}
\end{thm}
\begin{thm} The class of representable functions is closed under composition.
\end{thm}
In what follows, it will be convenient to denote $\ora{a} = (a_1,a_2,\ldots,a_m)$ for any given $m \in \ZZ^+$.
\begin{thm}\label{repRel}
\begin{enumerate}
\item[(i)] Any relation which has in $\Nn$ a quantifier-free definition is representable.
\item[(ii)] The class of representable relations is closed under unions, intersections, and complements.
\item[(iii)] If $R$ is representable, then so are $$\{(\ora{a},b): \text{ for all } c***0 \text{ and }$$ $$\lfloor a_0,\ldots, a_m\rfloor = a_0 \text{ if } m =0.$$ We may extend this operation even further and say that for $m = -1$, we define the operation as $\lfloor \rfloor = 1$.
\begin{thm}
For each $m \in \NN$, the mapping $$(a_0,a_1,\ldots,a_m) \longmapsto \lfloor a_0,a_1,\ldots,a_m\rfloor$$ is representable.
\end{thm}
\begin{thm}
There is a representable function such that $(a,b) \longmapsto (a)_b$ where for $b\leq m$, $$(\lfloor a_0,\ldots,a_m\rfloor)_b = a_b$$
\end{thm}
The last function is a decoding function for G\"odel numbering so that if we had the G\"odel number of an expression in the formal language, we can decode its G\"odel number into the numbers that we assigned to the alphabet of the formal language and subsequently retrieve the original formal expression. Their representability essentially allows us to refer to G\"odel numbering in the formal language itself. Thus, we have the potential to have formulas in the language that refer to their own G\"odel number. This self-reference will be key to proving G\"odel's Theorem.
\begin{thm}
Assume that $R$ is a representable relation such that for every $\ora{a}$ there is some $n$ such that $(\ora{a},n) \in R$. Then the function defined by $f(\ora{a}) = \min\{n: (\ora{a},n) \in R\}$ is representable.
\end{thm}
\begin{df}
Say that $b$ is a \dfem{sequence number} if for some $m \geq -1$ and some $a_0,\ldots,a_m$, $b = \lfloor a_0,\ldots, a_m\rfloor$.
\end{df}
This definition allows us to distinguish between which natural numbers are the images of a formal expression under G\"odel numbering and which are not.
\begin{thm}
The set of sequence numbers is representable.
\end{thm}
\begin{thm}
There is a representable function $lh: \NN \longrightarrow \NN$ such that $lh(\lfloor a_0,\ldots, a_m \rfloor) = m+1$ (``$lh$" is intended to stand for ``length").
\end{thm}
\begin{df}
Define a mapping from $\NN \times \NN$ into $\NN$, called the \dfem{restriction}, where $(a,b)\longmapsto a \upharpoonright b$, and $$ a\upharpoonright b = \left\lbrace\begin{array}{ll}
\lfloor a_0,\ldots,a_{b-1}\rfloor & \text{if } a \text{ is a sequence number such that } a = \lfloor a_0,\ldots,a_m\rfloor\\
& \text{and } b\leq m+1\\
0 & \text{otherwise}\\
\end{array}\right.$$
\end{df}
\begin{thm}
The restriction function is representable.
\end{thm}
Given a $(k+1)$-place function $f$, we design a new function $\wh{f}$ where $$\wh{f}(a,b_1,\ldots, b_k) = \lfloor f(0,\ora{b}),\ldots,f(a-1,\ora{b})\rfloor$$. This function $\wh{f}$ will encode the first $a$ values of $f(x,\ora{b})$. Suppose now that we have a $(k+2)$-place function $g$. Applying the Recursion Theorem, we may say that there is a unique $(k+1)$ function $f$ such that $$f(a, \ora{b}) = g(\wh{f}(a,\ora{b}),a,\ora{b}).$$ These preliminary results are necessary to state the following theorem.
\begin{thm}\label{repRecursion}
Let $g$ be a $(k+2)$-place function and let $f$ be the unique $(k+1)$-place function such that for all $a$ and ($k$-tuples) $\ora{b}$, $$f(a,\ora{b}) = g(\wh{f}(a,\ora{b}),a, \ora{b}).$$ If $g$ is representable, then so is $f$.
\end{thm}
\begin{thm}
For a representable function $F$, the mapping defined by $$(a,\ora{b}) \longmapsto \prod_{i**