\documentclass[a4paper]{book} \usepackage{amsmath, amsfonts,times,amsthm} \theoremstyle{plain} \newtheorem{proposition}{Proposition}[chapter] \newtheorem{theorem}[proposition]{Theorem} \newtheorem{corollary}[proposition]{Corollary} \newtheorem{observation}[proposition]{Observation} \newtheorem{definition}[proposition]{Definition} \newtheorem{example}[proposition]{Example} \newtheorem{lemma}[proposition]{Lemma} \renewcommand{\implies}{\Rightarrow} \newcommand{\proves}{\vdash} \newcommand{\entails}{\models} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\false}{\bot} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\powerset}{\mathbb{P}} \newcommand{\join}{\wedge} \newcommand{\logicaland}{\wedge} \newcommand{\logicalor}{\vee} % \newcommand{\times}{\cdot} \begin{document} \frontmatter \title{Logic} \date{Mich{\ae}lmas 2003} \maketitle \tableofcontents \mainmatter \chapter{Introduction} The notes were typed up by me, John Fremlin \texttt{john@fremlin.de}. These notes are based on the first three chapters of the part II mathematics course ``Logic, Computation and Set Theory'' given by Dr Leader in Cambridge in Mich{\ae}lmas 2003. These notes are not connected to Dr Leader in any way. If there are any mistakes in them, it is more than very likely that they are my fault, not Dr Leader's. Furthermore these notes are very definitely no substitute for actually going to Dr Leader's lectures (which are very good), because they do not include all of the material and especially examples covered, or any of the asides. Additionally, the material on computation and set theory is not included in these notes. Finally, I would like to thank Dr Leader for taking such care to polish his crystal-clear lectures, and for being a very patient supervisor. \chapter{Propositional logic} % 20031009 (1) \begin{definition}[Primitive propositions] $P = \{ p_1, p_2, p_3, \cdots \}$ is the set of primitive propositions. \end{definition} \begin{definition}[Proposition] A proposition is a subset of strings of symbols from the alphabet $(,),\implies,\false,p_1,p_2,\cdots$. \end{definition} \begin{definition}[Language] The language $L$ (or $L(P)$) is the set of propositions \begin{enumerate} \item $P \subset L$ \item $\false \in L$ \item if $p,q \in L$, $(p \implies q) \in L$ \end{enumerate} $L_n$ is the set of propositions of length $\le n$. \end{definition} \begin{definition}[Shorthands] \begin{tabular}{rll} $ \neg p $ & $(p \implies \false)$ & ``not $p$'' \\ $p \logicalor q$ & $((\neg p) \implies q)$ & ``p or q'' \\ $p \logicaland q$ & $\neg (p \implies (\neg q))$ & ``p and q'' \end{tabular} \end{definition} % 20031010 (1) \begin{definition}[Valuation] A valuation is a function. $v: L \mapsto \{ 0, 1 \}$. \begin{enumerate} \item $v(\false)=0$ \item $v(p \implies q) = \begin{cases}0&\text{if $v(p)=1,v(q)=0$}\\ 1&\text{otherwise} \end{cases}$ \end{enumerate} \end{definition} \begin{theorem}[Valuations agreeing on the basic propositions are the same] If valuations $v,v'$ have $v(p) = v'(p)$ for all $p \in P$ then $v \cong v'$. \end{theorem} \begin{proof} $v = v'$ on $L_1$. If $v(p) = v'(p)$ and $v(q) = v'(q)$ then $v(p \implies q) = v'(p \implies q)$ so by induction $\forall L_n$. \end{proof} \begin{theorem}[A function defined on the primitive propositions can be extended to a valuation] Given $w: P \mapsto \{0,1\}$ there exists a valuation $v$ such that $v(p) = w(p)$ for all $p \in P$. \end{theorem} \begin{proof} Let $v(p) = w(p)$ for all $p \in P$ and let $v(\false)=0$. Extend. \end{proof} \begin{definition}[Model] If $v(p)=1$, $p$ is true in $v$. $v$ is a model of $p$. \end{definition} \begin{definition}[Tautology] If $v(p)=1$ for all valuations $v$ then $p$ is a tautology. $\entails p$. \end{definition} \begin{observation}[Techniques for proving something is a tautology] Draw a truth table, also note that if $v(p \implies q) = 0$ then $p = 1$ and $q = 0$. \end{observation} \begin{definition}[Semantic implication, entails] If $S \subseteq L$, $t \in L$ and $v(s)=1$ for all $s \in S$ means $v(t) = 1$ then $S$ entails or semantically implies $t$ ($S \entails t$). That is, every model of $S$ is a model of $t$. \end{definition} \chapter{Syntactic implication} \begin{definition}[Axioms] \begin{enumerate} \item $p \implies (q \implies p)$ is true $\forall p,q \in L$ \item $(p \implies (q \implies r)) \implies ((p \implies q) \implies (p \implies r))$ $\forall p,q,r \in L$ \item $(\neg \neg p) \implies p$ $\forall p \in L$ \end{enumerate} \end{definition} \begin{observation}[Consistent with semantic implication] All the axioms are tautologies. \end{observation} \begin{definition}[Modus ponens] From $p$ and $p \implies q$ can deduce $q$. \end{definition} % 20031010 (3) \begin{definition}[Proof] Let $S \subseteq L$ be called the set of hypotheses or premises. A proof of a conclusion $t \in L$ from $S$ is a finite set $t_1,\cdots,t_n$ with $t_n = t$ and each $t_i$ is either \begin{enumerate} \item an axiom \item a member of $S$ \item such that there exist $j,k < m: t_k = (t_j \implies t_m)$ \end{enumerate} Then $S \proves t$ ($S$ proves or syntactically implies $t$). If $\emptyset \proves t$ then $t$ is a theorem (written $\proves t$). \end{definition} % 20031014 (1) \begin{theorem} $ ( p \implies q, q \implies r ) \proves ( p \implies r ) $ \end{theorem} \begin{proof}[Proof] \begin{tabular}{rll} 1 & $ ( p \implies ( q \implies r ) ) \implies ( ( p \implies q ) \implies ( p \implies r ) ) $ & Axiom 2 \\ 2 & $ q \implies r $ & Hypothesis \\ 3 & $ ( q \implies r ) \implies ( p \implies ( q \implies r ) ) $ & Axiom 1 \\ 4 & $ p \implies ( q \implies r ) $ & Modus ponens on 2, 3 \\ 5 & $ ( p \implies q ) \implies ( p \implies r ) $ & Modus ponens on 4,1 \\ 6 & $p \implies q$ & Hypothesis \\ 7 & $p \implies r$ & Modus ponens on 6,5 \end{tabular} \end{proof} \begin{theorem} \[ \proves ( p \implies p ) \] \end{theorem} \begin{proof}[Proof] \begin{tabular}{rll} 1 & $p \implies ( ( p \implies p ) \implies p ) \implies ( ( p \implies ( p \implies p ) ) \implies ( p \implies p ) )$ & Axiom 2 \\ 2 & $p \implies ( ( p \implies p ) \implies p )$ & Axoim 1 \\ 3 & $ ( p \implies ( p \implies p ) ) \implies ( p \implies p ) $ & Modus ponens on 2,1 \\ 4 & $ p \implies ( p \implies p )$ & Axiom 1 \\ 5& $ p \implies p $ & Modus ponens on 4,3 \end{tabular} \end{proof} % 20031014 (2) \begin{theorem}[Deduction theorem] Let $S \subseteq L$, $p,q \in L$. Then $S \proves ( p \implies q )$ iff $S \union [p] \proves q$. \end{theorem} \begin{proof} % XXX case $S \proves ( p \implies q )$. Given a proof of $p \implies q$ from S add lines \begin{tabular}{rl} $p$ & Hypothesis \\ $q$ & Modus ponens \end{tabular} Thus proving $q$ from $S \union [p]$. % XXX case $S \union [p] \proves q$ Let $t_1,t_2,...,t_n$ be a proof of $q$ from $S \union [p]$. Show that $S \proves ( p \implies t_i )$ for every $i$. If $t_i = p$ certainly $S \proves ( p \implies p )$ as $\proves ( p \implies p )$. Otherwise if $t_i$ is an axiom or $t_i \in S$, write \begin{tabular}{rl} $t_i$ & Axiom or Hypothesis \\ $t_i \implies ( p \implies t_i )$ & Axiom 1 \\ $p \implies t_i$ & Modus ponens \end{tabular} So $S \proves ( p \implies t_i )$. Otherwise $t_i$ was got from Modus Ponens, i.e. there exist $j$ such that $t_j \implies t_i$. By induction on $i$ assume $S \proves ( p \implies t_j )$ and $S \proves ( p \implies ( t_j \implies t_i ) )$ so write \begin{tabular}{rl} $( p \implies ( t_j \implies t_i ) ) \implies ( ( p \implies t_j ) \implies ( p \implies t_i ) )$ & Axiom 2 \\ $( p \implies t_j ) \implies ( p \implies t_i )$ & Modus ponens \\ $p \implies t_i$ & Modus ponens \end{tabular} \end{proof} % 20031014 (3) \begin{example} To show $\{ p \implies q, q \implies r \} \proves ( p \implies q )$ show $\{ p \implies q, q \implies r, p \} \proves r$ using modus ponens twice. \end{example} \begin{theorem}[Soundness theorem] Let $S \subseteq L$, $t \in L$ then $S \proves t$ implies $S \entails t$. \end{theorem} \begin{proof} Given a valuation $v$ that is a model for $S$, i.e. $v(s) = 1 \forall s \in S$ we want $v(t) = 1$. Certainly axioms (are tautologies) and elements of $S$ are true. Also modus ponens: if $v(p) = 1$ and $v(p \implies q)=1$ then $v(q)=1$. So $v(p) =1$ for all $p$ in a proof of $t$ from $S$. \end{proof} \begin{definition} $S \subseteq L$ is inconsistent if $S \proves \false$. Otherwise it is consistent. \end{definition} % 20031014 (4) \begin{definition}[Deductively closed] A set $S \subseteq L$ is deductively closed if it contains all its consequences. If $S \proves p$ then $p \in S$. \end{definition} \begin{theorem}[$S$ consistent implies it has a model] Let $S \subseteq L$ be consistent. Then $S$ has a model. \end{theorem} \begin{proof} Key idea: the theorem fails if both $p$ and $\neg p$ are in $S$. So try to extend $S$ keeping it consistent to swallow up one of $p$ or $\neg p$ for each $p \in L$. Claim. For any consistent $S \subseteq L$ and any $p \in L$ at least one of $S \union \{ p \}$ and $S \union \{ \neg p \}$ is consistent. Proof of claim. Suppose $S \union \{ p \}$ is inconsistent. Then $p \proves \false$. So $S \proves (p \implies \false)$ so $S$ and $S \union \{ \neg p \}$ prove the same things so $S \union \{ \neg p \}$ is consistent. $L$ is countable. Let $t_1,t_2,t_3,\cdots$ be an ordering of $L$. Let $S_0 = S$. Let $S_{n+1}$ be $S_n \union \{t_n\}$ or $S_n \union \{ \neg t_n\}$ choosing one which is consistent. Let $\bar{S} = \union_{n \ge 1} S_n$. Then for each $p \in L$ at least one of $p \in \bar{S}$ or $\neg p \in \bar{S}$. $\bar{S}$ is consistent because proofs are finite. Also $\bar{S}$ deductively closed. If $p \notin S$ then $S$ does not prove $p$ (as $\neg p \in S$). Define $v \colon L \mapsto \{ 0,1 \}: v(p) = \begin{cases}1&\text{if $p \in S$}\\ 0&\text{otherwise}\end{cases}$. $v$ is a valuation. Proof. $v(\false)=0$. If $v(p)=1,v(q)=0$ then $p \in \bar{S}$, $q \notin \bar{S}$. So $(p \implies q) \notin \bar{S}$ so $v(p \implies q)=0$. If $v(q)=1$ then $q \proves (p \implies q)$ so $(p \implies q) \in \bar{S}$ so $v(p \implies q)=1$. If $v(p)=0$ then $p \notin \bar{S}$ so $\neg p \in \bar{S}$. Enough to show $\neg p \implies (p \implies q)$. That is, $(p,\neg p) \proves q$. \begin{tabular}{rl} $p \implies \false$ & Hypothesis \\ $\false \implies \neg \neg q$ & Axiom 1 \\ $(\neg \neg q) \implies q$ & Axiom 3 \end{tabular} So $v(p \implies q)=1$. So $v$ is a valuation. So there is a model for $S$. \end{proof} \begin{observation} Previous theorem used fact that $P$ is countable (so that $L$ is countable) but this is not necessary by Zorn's lemma (next chapter). \end{observation} \begin{corollary}[Adequacy theorem] Let $S \subseteq L$, $t \in L$. Then $S \entails t$ implies $S \proves t$. \end{corollary} \begin{proof} If $S \entails t$ then $S \union (\neg t) \entails \false$ (has no model) so $S \union (\neg t) \proves \false$ (is inconsistent). $S \proves ((\neg t) \implies \false)$ by deduction theorem. $S \proves (\neg \neg t)$. So $S \proves t$ by axiom. \end{proof} \begin{theorem}[Completeness theorem for propositional logic] Let $S \subseteq L$, $t \in L$. Then $S \entails t$ iff $S \proves t$. \end{theorem} \begin{proof} Adequacy and soundness theorems. \end{proof} \subsection{Two consequences of completeness} \begin{theorem}[Compactness theorem] Let $S \subseteq L$, $t \in L: S \entails t$. Then some finite $S' \subseteq S$ has $S' \entails t$. \end{theorem} \begin{proof} If $S \entails t$ then $S \proves t$. But proofs are finite so some finite $S' \subseteq S$ has $S' \proves t$. Then $S' \entails t$. \end{proof} \begin{corollary}[Equivalent formulation of compactness] If every finite subset of $S$ has a model, then $S$ is consistent. \end{corollary} \begin{proof} There is no finite subset of $S$, such that $S \proves \false$. So $S \not \proves \false$. \end{proof} \begin{theorem}[Decidability theorem] There is an algorithm to determine, for any $S \subseteq L$ and $t \in L$ whether or not $S \proves t$. Note that this is not obvious at all. \end{theorem} \begin{proof} Trivial by replacing $\proves$ with $\entails$. To decide if $S \entails t$ just write down a truth table. \end{proof} % 20031017 (1 tk281) \chapter{Posets and Zorn's lemma} \begin{definition}[Poset] A partially ordered set or poset is a pair $(X, \le)$ where $X$ is a set and $\le$ is a relation on $X$ satisfying: \begin{enumerate} \item Reflexivity: $x \le x$, $\forall x \in X$. \item Antisymmetry: if $x \le y$ and $y \le x$ then $x = y$, $\forall x,y \in X$. \item Transitivity: if $x \le y$ and $y \le z$ then $x \le z$, $\forall x,y,z \in X$. \end{enumerate} Write $x < y$ for $x \le y$ and $x \ne y$. Alternatively in terms of $<$, $\not \exists x: x < x$, $x < y$ and $y < z$ implies $x < z$. \end{definition} \begin{example} $(\N, \le)$, $(\Q, \le)$ and $(\R, \le)$ are posets (in fact total orders). \end{example} \begin{example} $(\N^+, |)$ where ($x | y$ means $x$ divides $y$) is not a poset. \end{example} \begin{example} $S$ a set. $X \subseteq \powerset(S)$ with $A \le B$ if $A \subseteq B$. \end{example} \begin{definition}[Hasse diagram] A Hasse diagram for a poset is a drawing of the points in the poset with an upwards line from $x$ to $y$ if $y$ covers $x$ (meaning $x < y$ and $\not \exists z: x < z < y$). Sometimes a Hasse diagram can be drawn for an infinite poset. For example $(\N, \le)$ but $(\Q, \le)$ has an empty Hasse diagram. \end{definition} \begin{definition}[Chain] A chain in a poset $X$ is a set $A \subseteq X$ that is totally ordered ($\forall x,y \in A: $ have $x \le y$ or $y \le x$). For example in $(\R, \le)$ any subset, like $(\Q,\le)$ is a chain. Note that a chain need not be countable. \end{definition} % 20031017 (3 tk281) \begin{definition}[Antichain] An antichain is a subset $A \subseteq X$ in which no two distinct elements are comparable. $\forall x,y: x \ne y$, neither $x \le y$ nor $y \le x$. \end{definition} \begin{definition}[Upper bound] For $S \subseteq X$ and $x \in X$, say $x$ is an upper bound for $S$ if $y \le x$ $\forall y \in S$. \end{definition} \begin{definition}[Least upper bound, supremum, $\join S$] $x$ is a least upper bound for $S \subseteq X$ if $x$ is an upper bound for $S$ and every upper bound $y$ for $S$ satisfies $x \le y$. Clearly unique if it exists. Write $x = \join S = \sup S$ the supremum or join of $S$. \end{definition} \begin{definition}[Complete] A poset is complete if every set has a supremum. \end{definition} \begin{observation} Every complete poset $X$ has a greatest element, $\join X$ and a least element $\join \emptyset$. \end{observation} \begin{definition}[Monotone, order preserving] A function $f: X \mapsto X$, $X$ a poset, is monotone or order preserving if $x \le y$ implies $f(x) \le f(y)$. \end{definition} % 20031021 (1 tk281) \begin{theorem}[Knaster-Tarski fixed point theorem] $X$ a complete poset, $f: X \mapsto X$ order preserving. Then $f$ has a fixed point. \end{theorem} \begin{proof} Let $E = \{ x \in X : x \le f(x) \}$. Possibly $E = \emptyset$. Claim. If $x \in E$ then $f(x) \in E$. Proof. $x \le f(x)$ so $f(x) \le f(f(x))$ as $f$ order preserving. So $f(x) \in E$. Let $s = \join E$. Claim. $s \in E$. True if $f(s)$ an upper bound for $E$ (so $s \le f(s)$). If $x \in E$, $x \le s$ so $f(x) \le f(s)$. But $x \in E$ so $x \le f(x) \le f(s)$. So $f(s)$ is an upper bound for $E$. So $f(s)$ in $E$ by first claim. So $f(s) \le s$ but second claim showed $s \le f(s)$ so $f(s) = s$. \end{proof} \begin{corollary}[Schr{\"o}der-Bernstein theorem] $A,B$ have injections $f: A \mapsto B$ and $g: B \mapsto A$ then $A,B$ biject. \end{corollary} \begin{proof} Want partitions $A = P \union Q$ and $B = R \union S$ such that $f_p$ bijects $P$ with $R$ and $g_s$ bijects $S$ with $Q$. Then define obvious bijection $h: A \mapsto B$ by taking $h = f$ on $P$ and $h = g^{-1}$ on $Q$. % 20031021 (3 tk281) Set $P \subseteq A: A \setminus g(B \setminus f(P)) = P$, $R = f(P)$, $S = B \setminus R$, $Q = g(S)$. Consider $(X=\powerset(A),\subseteq)$. $X$ complete. Define $\theta: X \mapsto X$. $\theta(P) = A \setminus g(B \setminus f(P))$. Then $\theta$ is order preserving so it has a fixed point by Knaster-Tarski. \end{proof} \begin{definition}[Chain-complete] A (non-empty) poset $X$ is chain-complete if every non-empty chain has a supremum. \end{definition} \begin{observation} Not all functions on chain-complete posets have fixed points. Any function on an anti-chain is order preserving. \end{observation} \begin{observation} The non-empty condition is a little pedantic but necessary. \end{observation} \begin{definition}[Inflationary] $f: X \mapsto X$ is inflationary if $x \le f(x)$ $\forall x \in X$. Not necessarily related to order preserving. \end{definition} % 20031021 (4 tk281) \begin{theorem}[Bourbaki-Witt theorem] $X$ is a chain-complete poset, $f: X \mapsto X$ inflationary. Then $f$ has a fixed point. \end{theorem} \begin{proof} This proof is like battling Godzilla on a tightrope, it has to be carefully choreographed. Although the theorem seems fairly plausible, it has many big consequences. Fix $x_0 \in X$. Say $A \subseteq X$ closed if \begin{enumerate} \item $x_0 \in A$ \item $x \in A$ implies $f(x) \in A$ \item $C$ a non-empty chain in $A$ implies $\join C \in A$. \end{enumerate} Note that any intersection of closed sets is closed. Let $E = \intersect_{A \mbox{closed}} A$ is closed. Therefore if $A \subseteq E$ then $A = E$. Assume $E$ is a chain. Let $s = \join E$. Then $s \in E$ as $E$ is closed. Therefore $f(s) \in E$. So $f(s) \le s$. So $f(s) = s$ as $f$ inflationary. So done. Claim. $E$ is a chain. % 20031023 (1 tk281) Say $x \in E$ is normal if $\forall y \in E: y < x$ then $f(y) \le x$. There are two properties of normality we want prove. All $x \in E$ are normal. Secondly, it should satisfy the condition we might naturally describe as ``normal'': if $x$ normal then $\forall y \in E$ either $y \le x$ or $y \ge f(x)$. Once we have done this, we are finished. $\forall x,y \in E$, $y \le x$ or $y \ge f(x) \ge x$. So $E$ is a chain. Claim. If $x$ normal then $\forall y \in E$ either $y \le x$ or $y \ge f(x)$. Proof of claim. Let $A = \{ y \in E: y \le x $ or $ y \ge f(x) \}$. Will show $A$ is closed. Any closed subset of $E$ is $E$ so $A$ closed implies $A = E$. \begin{enumerate} \item $x_0 \in A$. $x_0 \le x$ ($\forall x \in E$). \item Given $y \in A$ we need $f(y) \in A$. So have $y \le x$ or $y \ge f(x)$ and want $f(y) \le x$ or $f(y) \ge f(x)$. If $y < x$ then $f(y) \le x$ as $x$ is normal.\\ If $y = x$ then $f(y) \ge f(x)$.\\ If $y \ge f(x)$ then $f(y) \ge y \ge f(x).$\\ So $f(y) \in A$. \item Given a (non-empty) chain $C \subseteq A$, want $s = \join A \in A$. If all $y \in C$ have $y \le x$ then certainly $s \le x$ because $s$ a supremum. Otherwise some $y \in C$ has $y \ge x$ and not $y \le x$ so $y \ge f(x)$ as $y \in A$. So $s \ge y \ge f(x)$. So $s \in A$. \end{enumerate} % 20031023 (2 tk281) So $A$ closed, so $A$ closed subset of smallest possible closed set $E$ so $A = E$. Claim. Every $x \in E$ is normal. Proof of claim. Let $N = \{ x \in E: x $ is normal $\}$. We will show that $N$ is closed so $N = E$. $N$ is closed: \begin{enumerate} \item No $y \in E$ has $y < x_0$. So $x_0$ is normal, $x_0 \in N$. \item Given $x$ normal want $f(x)$ normal. So must show $y < f(x)$ implies $f(y) \le f(x)$. By first claim $y < f(x)$ implies $y \le x$. So $y = x$ or $y < x$. So $f(y) = f(x)$ or $f(y) \le x \le f(x)$ (because $x$ is normal). \item Given a (non-empty) chain $C \subseteq N$ need $s = \join C \in N$. That is, we need that if $y < s$ then $f(y) \le s$ $\forall y \in E$. For $y < s$ cannot have $y \ge x$ $\forall x \in C$ (definition of supremum). So some $x \in C$ has not $y \ge x$, so $y < x$ by the first claim. So $f(y) \le x$ ($x$ normal) so certainly $f(y) \le s$. \end{enumerate} So $N$ closed so $N = E$. So $E$ is a chain. \end{proof} \begin{observation} ``Now forget the proof'' - Dr Leader \end{observation} \begin{definition}[Maximal element of a poset] Given a poset $X$ an element $x$ is maximal if no $y \in X$ has $y > x$. \end{definition} \begin{corollary}[Every chain-complete poset has a maximal element] Every chain-complete poset has a maximal element. \end{corollary} \begin{observation} Very non-obvious theorem which trivially implies Bourbaki-Witt ($x$ maximal implies $f(x) = x$). \end{observation} \begin{proof} By contradiction. For each $x \in X$ have $\bar{x} \in X$ with $\bar{x} > x$. Then the function $x \mapsto \bar{x}$ is inflationary. So it has a fixed point. Contradiction. \end{proof} \begin{lemma}[One important chain-complete poset] Let $X$ be any poset and let $P$ be the collection of all chains of $X$ ordered by inclusion. Then $P$ is chain complete. \end{lemma} \begin{proof} Let $\{ C_i: i \in I \}$ be a chain in $P$. $C_i$ is a chain in $X$ for all $i \in I$. Note that $I$ need not be countable. Further $\forall i,j \in I$ $C_i \subseteq C_j$ or $C_j \subseteq C_i$. Now let $C = \union_{i \in I} C_i$. $C$ is clearly a least upper bound for $\{ C_i \}$. We need to show that it is a chain. % 20031023 (4 tk281) Let $x,y \in C$. So $\exists i,j: x \in C_i$ and $y \in C_j$. So $C_i \subseteq C_j$ or $C_j \subseteq C_i$. So $x,y$ related. So $C$ a chain. \end{proof} \begin{corollary}[Kuratowski's lemma] Every poset $X$ has a maximal chain. \end{corollary} \begin{proof} The set of chains of $X$ is a chain-complete poset. \end{proof} \begin{corollary}[Zorn's lemma] Let $X$ be a (non-empty) poset in which every chain has an upper bound. Then $X$ has a maximal element. \end{corollary} \begin{proof} Let $C$ be a maximal chain in $X$. Let $x$ be an upper bound for $C$. Then $x$ is maximal. If $y > x$ then $C \union \{ y \}$ is a chain properly containing $C$. Contradiction. \end{proof} \begin{observation} Non-emptiness actually not needed as it follows from the condition that every chain has an upper bound. \end{observation} % 20031024 (1 tk281) \begin{corollary}[Every vector space $V$ has a basis] Every vector space $V$ has a basis. \end{corollary} \begin{proof} Let $X = \{ A \subseteq V: A $ is linearly independent $\}$ ordered by inclusion. We seek the existence of maximal element $A \in X$ using Zorn's lemma. Then we are done because if $A$ does not span $V$ it is not maximal. % 20031024 (2 tk281) \begin{enumerate} \item $\emptyset$ is linearly independent. So $\emptyset \in X$. So $X \ne \emptyset$. \item Given a chain $\{ A_i: i \in I \}$ in $X$ we seek an upper bound $S$. Let $S = \union_{i \in I} A_i$. Then $S \supseteq A_i$ $\forall i$ so we just need $S \in X$ (that is, $S$ linearly independent). Suppose $\lambda_1 x_1 + \lambda_2 x_2 + \cdots + \lambda_n x_n = 0$ for some $x_1, \cdots, x_n \in A$ and $\lambda_1, \cdots, \lambda_n$ not all zero. Have $A_m \in X$ such that $A_m$ contains all the $x_i$ because $X$ is a chain. But this contradicts $A_m$ being linearly independent. So $S \in X$. So every chain has an upper bound. \end{enumerate} \end{proof} \begin{corollary}[Completeness theorem for L(P) when the set P of primitive propositions may be uncountable] Let $S \subseteq L(P)$ for any $P$. Then $S$ consistent implies $S$ has a model. \end{corollary} \begin{proof} Want $\bar{S} \supset S$, that is consistent, with $t \in \bar{S}$ or $\not t \in \bar{S}$ for all $t \in L$. Then done by setting $v(t) = \chi_{\bar{S}}(t)$. Try to get a maximal consistent $\bar{S} \supset S$. Then for any $t \in L$ have $\bar{S} \union \{ t \}$ or $\bar{S} \union \{ \not t \}$ consistent. So $\bar{S}$ satisfies $t \in \bar{S}$ or $\not t \in \bar{S}$ for all $t \in L$. % 20031024 (3 tk281) Thus let $X = \{ T \subseteq L: T \supseteq S, T $ consistent $\}$. We want to use Zorn's lemma to show that $T$ has a maximal element. \begin{enumerate} \item $X \ne \emptyset$ since $S \in X$. \item Given a non-empty chain $\{ T_i : i \in I \}$ in $X$. Seek an upper bound $T$. Let $T = \union_{i \in I} T_i$. Then $T \supset T_i$ $\forall i$. Just need $T \in X$. $S \subseteq T$ as $S \subseteq T_i$ $\forall i$ (and $I \ne \emptyset$). Claim. $T$ consistent. Proof of claim. Suppose $T \proves \false$. Then have $t_1,\cdots,t_n \in T$ with $\{ t_1,\cdots,t_n \}$ inconsistent. Have $t_j \in T_{i_j}$ for some $i_j \in I$. But one of the $T_{i_j}$ contains the others because they are in the same chain, call this one $T_k$. Then $T_k$ is inconsistent which is a contradiction. \end{enumerate} So we can apply Zorn's lemma. \end{proof} \begin{observation}[Zorn's lemma and the axiom of choice] In the proof of Zorn's lemma (i.e. more precisely the proof that chain-complete posets have maximal elements) we made an infinite number of arbitrary choices: for each $x \in X$ we picked $\bar{x} > x$''. Note that in the IA Numbers and Sets course the axiom of choice was used to simultaneously pick orderings for a countable number of sets. The axiom of choice says: Given a set $I$ and a family $\{ A_i: i \in I \}$ of non-empty sets, there is a function $f: I \mapsto \union_{i \in I} A_i$ such that $f(i) \in A_i$ $\forall i$. This is different from the other rules that are used to build sets because it claims the existence of an object which is not necessarily specified uniquely. Therefore it is sometimes interesting to see if a proof depends on the axiom of choice. % 20031023 (1 tk281) ? Note that the axiom of choice follows from the other axioms for finite sets but not for infinite ones. Furthermore it is not possible to deduce Axiom of Choice for infinite sets from the other axioms(?). From Zorn's lemma we can deduce the axiom of choice. Given a family $\{ A_i \}_{i \in I}$, define a partial choice function (PCF) $f: J \mapsto \union_{i \in I} A_i$ with $f(i) \in A_i$ $\forall i \in J$ for some $J \subseteq I$. Order partial choice functions with $f \le g$ iff $J_f \subseteq J_g$ and $f = g$ on $J_f$. Then the set of all PCFs is a poset on which we can apply Zorn's lemma to find a maximal PCF. % 20031023 (2 tk281) ? Zorn's lemma was hard to prove because Bourbaki-Witt was hard, not because the Axiom of Choice was used. Furthermore Zorn's lemma is easy to prove from the Axiom of Choice using well-ordering and ordinals (chapter 6). \end{observation} \chapter{Predicate logic} \begin{observation} ``The completeness theorem is an absolute highlight of all of mathematics. It's brilliant'' - Dr Leader \end{observation} \begin{definition}[Arity] The number of arguments to a function is its arity. \end{definition} \begin{definition}[Group] A group is a set $A$ with functions $m: A^2 \mapsto A, i: A \mapsto A, e: A^0 \mapsto A$. \begin{equation}[Associativity] (\forall x,y,z)(m(x,m(y,z)) = m(m(x,y),z) \end{equation} \begin{equation}[Identity] (\forall x)(m(x,e) = x \logicaland m(e,x) = x) \end{equation} \begin{equation}[Inverse] (\forall x)(m(x,i(x)) = e \logicaland e = m(i(x),x)) \end{equation} \end{definition} \begin{definition}[Poset] A poset is a set A with a relation $\le \subseteq A^2$. Conveniently $\le (x,y)$ is written $x \le y$. \begin{equation}[Reflexivity] (\forall x)(x \le x) \end{equation} \begin{equation}[Anti-symmetry] (\forall x,y)((x \le y \logicaland y \le x) \implies (x = y)) \end{equation} \begin{equation}[Transitivity] (\forall x,y,z)((x \le y \logicaland y \le z) \implies (x \le z)) \end{equation} \end{definition} % 20031023 (3 tk281) ? \begin{definition}[Language $L$, functions $\Omega$, predicate $\Pi$, arity function $\alpha$] Let the set of functions $\Omega$ and predicates $\Pi$ be distinct sets, and let the arity function be $\alpha: \Omega \union \Pi \mapsto \N$. Then the language $L = L(\Omega,\Pi,\alpha)$ is the set of all formulae. \end{definition} \begin{example} For groups, $\Omega = \{ m, i, e \}, \Pi = \emptyset$. For posets, $\Omega = \emptyset, \Pi = \{ \le \}$. \end{example} \begin{definition}[Term] A term is a subset of strings of symbols from the alphabet $\Omega \union \Pi$. \begin{enumerate} \item Every variable is a term $(x_0,x_1,\cdots)$. \item If $f \in \Omega$, $\alpha(f) = n$ and $t_1,\cdots,t_n$ are terms then $f(t_1,\cdots,t_n)$ is a term. \end{enumerate} \end{definition} \begin{observation} Note that the term $f(t_1,\cdots,t_n)$ is not the value of the function $f$ with these arguments. It is just a string. To emphasize this you can write it $f t_1,\cdots,t_n$. \end{observation} \begin{definition}[Atomic formula] An atomic formula is one of \begin{enumerate} \item $\false$. \item $(s = t)$ if $s,t$ are terms. \item $\phi(t_1,\cdots,t_n)$ if $\phi \in \Pi$ and $\alpha(\phi) = n$ and $t_1,\cdots,t_n$ are terms. \end{enumerate} \end{definition} \begin{definition}[Formula] \begin{enumerate} \item Atomic formulae are formulae. \item If $p$ and $q$ are formulae then so is $(p \implies q)$. \item If $p$ a formula and $x$ a variable then $(\forall x) p$ is a formula. \end{enumerate} \end{definition} \begin{definition}[Shorthands] \begin{tabular}{rll} $ \neg p $ & $(p \implies \false)$ & ``not $p$'' \\ $p \logicalor q$ & $((\neg p) \implies q)$ & ``p or q'' \\ $p \logicaland q$ & $\neg (p \implies (\neg q))$ & ``p and q'' \\ $(\exists x) p$ & $\neg (\forall x) (\neg p)$ & ``exists x such that p'' \\ \end{tabular} \end{definition} \begin{definition}[Free and bound variables] An occurrence of a variable $x$ in a formula is free if it is not within the brackets of a ``$\forall x$''. Otherwise it is bound. \end{definition} \begin{definition}[Sentence] A sentence is a formula with no free variable (for example the axioms for groups and posets). \end{definition} % 20031030 (1 tk281) \begin{definition}[$L$-structure] Let $L = L(\Omega,\Pi,\alpha)$ be a language. An $L$-structure is a non-empty set $A$, for each $f \in \Omega$ a function $f_A: A^{\alpha(f)} \mapsto A$ and for each $\phi \in \Pi$ a subset $\phi_A \subseteq A^{\alpha(\phi)} $. \end{definition} \begin{example} $L$ the language of groups: an $L$-structure is a set $A$ with functions $m_A: A^2 \mapsto A, i_A: A \mapsto A, e_A \in A$. $L$ the language of posets: an $L$-structure is a non-empty set with a relation $\le_A \subseteq A^2$. \end{example} \begin{definition}[Closed term] A closed term is a term with no variables. For example $m(e,i(e))$, \emph{not} $m(x,i(x))$. \end{definition} \begin{definition}[Interpretation of a closed term] The interpretation of a closed term in an $L$-structure $A$ written $t_A \in A$ is defined inductively. If $f \in \Omega$, $\alpha(f) = n$ and $t_1,\cdots,t_n$ closed terms then $f(t_1,\cdots,t_n)_A = f_A(t_{1_A},\cdots,t_{n_A})$. Note that if $c$ is constant symbol then $c_A$ is already defined. \end{definition} % 20031030 (2 tk281) \begin{definition}[Interpretation of a sentence] For a sentence $p \in L$ and an $L$-structure $A$ the interpretation of $p$ in $A$ is a $p_A \in \{ 0,1 \}$ defined inductively \begin{enumerate} \item $\false_A = 0$ \item For closed terms $s,t$ $(s=t)_A = \begin{cases}1&\mbox{ if }s_A = t_A\\ 0&\mbox{otherwise}\end{cases}$. \item For $\phi \in \Pi$, $\alpha(\phi) = n$ and closed terms $t_1,\cdots,t_n$ set \[ \phi(t_1,\cdots,t_n) = \begin{cases}1&\mbox{if} (t_{1_A},\cdots,t_{n_A}) \in \phi_A\\0&\mbox{otherwise}\end{cases} \] \item For sentences $p,q$ set $(p \implies q)_A = \begin{cases}0&\mbox{if } p_A = 1, q_A = 0\\ 1&\mbox{otherwise}\end{cases}$. \item $((\forall x)p)_A = \begin{cases}1&\mbox{if for all } a \in A \mbox{ have } p[\bar{a} / x]_A = 1\\ 0&\mbox{otherwise}\end{cases}$ where we extend $L$ to $L'$ by adding a new constant symbol $\bar{a}$ and make $A$ an $L'$-structure by setting $\bar{a}_A = a$ and for any term $t$, $p[t/x]$ is the formula obtained by replacing each free occurrence of $x$ with $t$. \end{enumerate} \end{definition} \begin{observation} ``Now forget all this nonsense and think of it only as in the original idea.'' - Dr Leader. \end{observation} \begin{definition}[Truth, models, holds] If $p_A = 1$ we say $p$ holds in $A$ or $p$ is true in $A$ or $A$ is a model of $p$ written $A \entails p$. \end{definition} \begin{definition}[Theory, tautology] For a set $T$ of sentences (a theory) say $A$ is a model of $T$ written $A \entails T$ if $A \entails p$ $\forall p \in T$. % 20031030 (3 tk281) For $T$ a theory, $p$ a sentence, say $T$ entails $p$ written $T \entails p$ if every model of $T$ is a model of $p$. If $\emptyset \entails p$ we say $p$ is a tautology. \end{definition} \begin{observation} What is called in propositional logic a valuation is like in predicate logic an interpretation. \end{observation} \begin{definition}[Axiomatize, axioms] Say that the members of a theory $T$ are axioms, and that the theory axiomatizes the things which are models of it. \end{definition} \begin{example}[Theory of groups] Let $L$ be the language of groups and let $T = \{ (\forall x,y,z)(m(x,m(y,z)) = m(m(x,y),z), \\ (\forall x)(m(x,e) = x \logicaland m(e,x) = x), \\ (\forall x)(m(x,i(x)) = e \logicaland e = m(i(x),x)) \}$ Then an $L$-structure $A$ is a model of $T$ iff $A$ is a group. $T$ axiomatizes the class of groups. Suppose we change the third axiom to be just $(\forall x)(m(x,i(x)) = e)$ to produce $T'$. Does $T'$ axiomatize the class of groups? (Think about it but the answer is yes). \end{example} \begin{example}[Theory of posets] Let $L = $ language of posets and let $T = \{ (\forall x,y)((x \le y \logicaland y \le x) \implies (x = y)), (\forall x)(x \le x), (\forall x,y,z)(((x \le y) \logicaland (y \le z)) \implies (x \le x)) \}$. Then a model for $T$ is precisely a poset. \end{example} % 20031030 (4 tk281) \begin{example}[Theory of fields] Let $\Omega = \{ +, \times, -, 0, 1 \}$. $\Pi = \emptyset$. For $T$ take \begin{enumerate} \item Abelian group under $+,-,0$ \item Associative \item Commutative \item Distributive over $+$ \item $\neg (0 = 1)$ \item $(\forall x)((\neg (x = 0)) \implies ((\exists y)(x \times y = y \times x = 1))$ \end{enumerate} Then $T$ axiomatizes the class of fields. \end{example} \begin{example}[Theory of graphs] Language of $\Omega = \emptyset$ and $\Pi = \{ \sim \}$. $T = \{ (\forall x) (\neg (x \sim x)), (\forall x,y)((x \sim y)\implies (y \sim x)) \}$. Then an $L$-structure on $G$ is a $T$-model iff $G$ is a graph. \end{example} \begin{observation} This is called first-order logic. We can qualify over elements but not over subsets. For example we cannot say ``for all subgroups of $A$''. \end{observation} % 20031031 (1 tk281) \begin{observation} Could have an alternative language for groups with $\Omega= \{m,e \}$ and third element of the theory being $(\forall x)(\exists y)(m(x,y) = e \logicaland m(y,x) = e)$. \end{observation} \begin{observation} Many natural theories have $T$ infinite. For example, we have fields of characteristic zero. $L$ language of fields. $T =$ axioms of a field, with $\neg (1 + 1 = 0)$,$\neg (1 + 1 + 1 = 0)$ etc. \end{observation} \begin{observation} Fields of non-zero characteristic. $L$ language of fields, $T$ axioms for a field. Can we axiomatize fields of charactistic $\ne 0$? (Exercise.) \end{observation} % 20031031 (2 tk281) \section{Proofs} \begin{definition}[Logical axioms] Three old ones, two for $=$ and two for $\forall$. \begin{enumerate} \item $p \implies (q \implies p)$ for any formulae $p,q$. \item $(p \implies (q \implies r)) \implies ((p \implies q) \implies (p \implies q))$ for any formulae $p,q,r$. \item $(\neg \neg p) \implies p$ for any formula $p$. \item $(\forall x)(x = x)$ for any variable $x$. \item $(\forall x,y)((x=y) \implies (p \implies p[y/x]))$ where $x,y$ variables, $p$ a formula in which $y$ does not occur bound. \item $((\forall x)p) \implies p[t/x]$ where $x$ is a variable, $p$ a formula, $t$ a term with no free variable occurring that is bound in $p$. \item $((\forall x)(p \implies q)) \implies (p \implies (\forall x)q)$ where $x$ is a variable, $p,q$ formulae with $x$ not occurring free in $p$. \end{enumerate} \end{definition} \begin{definition}[Rules of deduction, modus ponens and generalization] Modus ponens. From $p$, $p \implies q$ deduce $q$. Generalization. From $p$ deduce $(\forall x)p$ as long as $x$ does not occur in any of the premises used to prove $p$. \end{definition} % 20031031 (3 tk281) \begin{definition}[Proof] For $S \subseteq L$ and $p \in L$ a proof of $p$ from $S$ consists of a finite sequence of lines each of which is a logical axiom or a member of $S$ or is obtained from earlier lines by a deduction rule. Write $S \proves p$ if there is a proof of $p$ from $S$. \end{definition} \begin{observation} If we allowed $\emptyset$ to be an $L$-structure we would have a contradiction. % XXX finish this \end{observation} % 20031031 (4 tk281) \begin{theorem}[Deduction theorem] Let $S \subseteq L$ and $p,q \in L$. Then $S \proves (p \implies q)$ iff $S \union \{ p \} \proves q$. \end{theorem} \begin{proof} If $S \proves (p \implies q)$ then have by modus ponens $S \union \{ p \} \proves q$. If $S \union \{ p \} \proves q$ then as in the first chapter we show that for each line in $r$ in a proof of $q$ from $S \union \{ p \}$ in fact $S \proves (p \implies r)$. We do this inductively. The only new case is if we have used generalization. So in proof of $q$ from $S \union \{ p \}$ we have \[ r \] \[ (\forall x)r \] and we know that $S \proves (p \implies r)$. Note that the proof of $r$ from $S \union \{ p \}$ did not use a free $x$ in any hypothesis, so also our proof of $p \implies r$ from $S$ did not use one. Therefore we can deduce $S \proves ((\forall x)(p \implies r))$ by generalization. If $x$ is not free in $p$: deduce $S \proves (p \implies ((\forall x)r))$ by the seventh axiom. Otherwise $x$ is free in $p$. So in our proof of $(\forall x)r$ from $S \union \{ p \}$ cannot have used $p$ (as generalization was used). So $S \proves ((\forall x)r)$ so $S \proves (p \implies ((\forall x)r))$ by the first axiom and modus ponens. \end{proof} % 20031104 (1 tk281) \begin{theorem}[Soundness theorem] $S$ is a set of sentences, and $p$ a sentence. Then $S \proves p$ implies $S \entails p$. \end{theorem} \begin{proof} Given a model of $S$, $p$ holds in this model by induction on the lines in the proof. \end{proof} \begin{theorem}[Model Existence Lemma or Completeness Theorem] Let $S$ be a consistent set of sentences. Then $S$ has a model. \end{theorem} \begin{definition}[Witness] A witness for $(\exists x) p$ is $p[t/x]$ for a closed term $t$. \end{definition} \begin{proof} Have $S$ in language $L = L(\Omega, \Pi)$. Extend $S$ to maximal consistent $S_1 \subseteq L$ by Zorn's lemma. Then $S_1$ is complete (that is for any $p \in L$ either $S_1 \union \{ p \}$ is consistent or $S_1 \union \{ \neg p \}$ consistent. For each $((\exists x)p) \in S$ add a new constant $c$ to the language to form $L_1 = L(\Omega \union C_1, \Pi)$ and add the sentence $p[c/x]$ to $S_1$ to form $T_1$. Then $T_1$ is consistent. $T_1$ has witnesses for $S_1$. Now extend $T_n$ to a complete $S_{n+1}$ and continue inductively. Let $\bar{S} = \union_{n=1}^\infty S_n$ in language $\bar{L} = L(\Omega \union C_1 \union C_2 \union \cdots, \Pi)$. Claim. $\bar{S}$ consistent. Proof of claim. Suppose $\bar{S} \proves \false$. Then some finite $S' \subseteq \bar{S}$ has $S' \proves \false$ whence some $S_n \proves \false$. Contradiction. Claim. $\bar{S}$ complete. Proof of claim. For any sentence $p \in \bar{L}$ have $p \in L_n$ for some $n$ as $p$ mentions only finitely many symbols. But $S_{n+1}$ complete in language $L_n$ so $S_{n+1} \proves p$ or $S_{n+1} \proves (\neg p)$. But $\bar{S} \supseteq S$. Done. Claim. $\bar{S}$ has witnesses. Proof of claim. Basically the same as for consistency. For closed terms $s,t \in \bar{L}$ say $s \sim t$ if $\bar{S} \proves (s = t)$, clearly an equivalence relation. Write $[t]$ for equivalence class of $t$. Let $A = \{ [t]: t \mbox{ a closed term of } \bar{L} \}$. For each $f \in \Omega(\bar{L})$ with arity $n$ and $t_1,\cdots,t_n$ closed terms, set $f_A([t_1],\cdots,[t_n])=[f(t_1,\cdots,t_n)]$. (Clearly well defined.) For each $\phi \in \Pi(\bar{L})$ with arity $n$ and $t_1,\cdots,t_n$ closed terms, set $\phi_A([t_1],\cdots,[t_n])=\{ ([t_1],\cdots,[t_n]) \in A^n: \bar{S} \proves \phi(t_1,\cdots,t_n) \}$. (Clearly well defined.) To show that $A$ is a model for $S$ we will show that for any sentence $p \in I$ we have $p_A = 1$ iff $\bar{S} \proves p$. This is an easy induction. \begin{enumerate} \item $s = t$. $\bar{S} \proves (s = t)$ iff $s \sim t$ iff $s_A = t_A$ iff $[s] = [t]$ iff $(s = t)_A = 1$. % 20031104 (5 tk281) \item $\phi(t_1,\cdots,t_n)$ similarly. \item $\false$. $\bar{S} \not \proves \false$ and $\false_A = 0$. \item $(p \implies q)$. $\bar{S} \proves (p \implies q)$ iff $\bar{S} \proves p$ and $\bar{S} \not \proves q$ (as $\bar{S}$ is complete). By induction hypothesis $p_A = 0$ or $q_A = 1$ iff $(p \implies q)_A = 1$. \item $(\exists x) p$. $\bar{S} \proves (\exists x)p$ iff $\bar{S} \proves p[t/x]$ or some closed term $t$, so $p[t/x]_A = 1$ by induction hypothesis, equivalently $(\exists x)p$ holds in $A$ (since $A$ is the set of all closed terms quotiented). \end{enumerate} \end{proof} % 20031106 (1 tk281) \begin{corollary}[Adequacy theorem] Let $S$ be a theory and $p$ a sentence. Then $S \entails p$ implies $S \proves p$. \end{corollary} \begin{proof} If $S \entails p$ then $S \union \{\neg p\} \entails \false$ implies $S \union \{ \neg p\} \proves \false$. So by the deduction theorem $S \proves (\neg \neg p)$ so $S \proves p$. \end{proof} \begin{theorem}[G{\"o}del's Completeness Theorem, the completeness theorem of first order logic] $S$ a theory, $p$ a sentence. Then $S \proves p$ iff $S \entails p$. \end{theorem} \begin{proof} By adequacy and soundness. \end{proof} \begin{corollary}[Compactness theorem] $S$ a theory. If every finite subset of $S$ has a model then so does $S$. \end{corollary} \begin{proof} Trivial if we replace ``has a model'' with ``is consistent''. \end{proof} \begin{corollary}[Upward L{\"o}wenheim-Skolem theorem] Let $S$ be a theory with an infinite model. Then $S$ has an uncountable model. \end{corollary} \begin{proof} Add to the language uncountably many new constants, say $\{c_i\}_{i \in I}$. Let $S' = S \union \{ \neg (c_i = c_j): i, j \in I, i \ne j \}$. We want a model for $S'$. But every finite $F \subset S'$ certainly has a model since $F$ only mentions finitely many of the $c_i$. So by compactness the infinite model for $S'$ exists, and it is also a model for $S$. \end{proof} \begin{observation} The same trick of adding constants $c_1,\cdots$ shows that no set of sentences (in the language of groups, for example) can axiomatize (i.e. have as a model) the class of finite groups. In other words, ``finiteness is not a first order property''. Equivalently any theory that has arbitrarily large finite models must have an infinite model (called ``overspill''). \end{observation} % 20031106 (2 tk281) \begin{corollary}[Downward L{\"o}wenheim-Skolem theorem] Let $S$ be a consistent theory in a countable language (that is $\Omega, \Pi$ countable). Then $S$ has a countable model. \end{corollary} \begin{proof} The model constructed in the proof of the model existence lemma was maximal and countable. \end{proof} \section{Peano Arithmetic} \begin{definition}[Language of Peano arithmetic] $\Omega = \{ 0, s, +, \times \}$ where $s$ is the successor function. \end{definition} \begin{definition}[Axioms of Peano Arithmetic] \begin{enumerate} \item $(\forall x)(\neg(s(x) = 0))$ \item $(\forall x,y)((s(x) = s(y)) \implies (x=y))$ \item $(\forall y_1)\cdots(\forall y_n)((p[0/x] \logicaland (\forall x)(p \implies p[s(x)/x])) \implies (\forall x)p)$, that is, induction with parameters $(\forall y_1)\cdots(\forall y_n)$ for free variables in $p$. \item $(\forall x)(x + 0 = x)$ \item $(\forall x,y)(x + s(y) = s(x + y))$ \item $(\forall x)(x \times 0 = 0)$ \item $(\forall x,y)(x \times s(y) = (x \times y) + x)$ \end{enumerate} The first three axioms are sometimes called weak Peano Arithmetic. \end{definition} \begin{observation} We might have first guessed that the induction axiom should have been $(p[0/x] \logicaland (\forall x)(p \implies p[s(x)/x]))\implies (\forall x)p$. But this is not how we do induction in real life. \end{observation} \begin{definition}[Axiom scheme] The induction axiom is in fact a different axiom for each $p$. An axiom like this specifying an infinite set of axioms is sometimes called an axiom scheme. \end{definition} \begin{observation} PA has an infinite model ($\N$) so by the Upward-L{\"o}wenheim-Skolem theorem PA has an uncountable model which is therefore not $\N$. But we would like $\N$ to be characterized uniquely by these axioms. The problem is that the induction axiom is not powerful enough - it only refers to countably many subsets of $\N$ (those defined by a $p$) whereas normal induction refers to all subsets. Therefore induction is not a first order property. \end{observation} \end{document}