\documentclass[12pt]{article}
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry} 
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}

\usepackage{psfrag}
\usepackage{tabularx}

\newenvironment{mylist}[1]%
  {\begin{list}{}{\settowidth{\labelwidth}{\textbf{#1}}
   \setlength{\leftmargin}{\labelwidth}
   \addtolength{\leftmargin}{\labelsep}
   \renewcommand{\makelabel}[1]{\textbf{\hfill##1}}}}%
  {\end{list}}

\def\phi{\varphi}

\usepackage{proof}
\usepackage{lgarron}
\usepackage{color}
\newcommand{\hly}[1]{\colorbox{yellow}{#1}}
\usepackage{ wasysym }

\def\A{\mathfrak{A}}
\def\B{\mathfrak{B}}

\begin{document} 

\title{Philosophy 151: Definitions from \emph{van Dalen}}
\author{Lucas Garron}
\maketitle

Trying to make sense of a ``slightly'' inconsistent book about logic.

\def\n{\newline}
\def\e{\\[3mm]\hline\\[3mm]}

\begin{mylist}{new Document}

\subsection*{Chapter 1. Propositional Logic}

\item[$PROP$ (7)]
smallest set $X$ with:
(i) $p_i \in X$\n
-- $\bot \in X$\n
(ii) $(\phi \square \psi) \in X$ $\{\wedge, \vee, \rightarrow, \leftrightarrow \}$\n
(iii) $(\neg \phi)$\n\n
Typical element name: $p$

\item[rank (12)]
Recursively defined ``depth'' of a proposition.

\item[valuation (18)]
A mapping $v: PROP \-> \{0, 1\}$, defined recursively on $PROP$. $[|\phi \wedge \psi|] = v(\phi \wedge \psi) = min(v(\phi), v(\psi))$, etc.

\item[ $\vDash \phi$ (19, propositional) ]
$\phi$ is a tautology (true for all valuations)

\item[ $\Gamma \vDash \phi$ ]
$[|\psi|]_v = 1$ or all $\phi \in \Gamma$ $\iff$ $[|\phi|]_v = 1$

\item[ $\Gamma \vdash \phi$ (36) ]
There is a derivation with conclusion $\phi$ and all hypotheses in $\Gamma$

\item[ $\vdash \phi$ (36) ]
$\Gamma = \0$. $\phi$ is a theorem.

\item[ Consistency ]
$\Gamma$ (set of propositions) is consistent if $\Gamma \not \vdash \bot$.

\item[ Maximal Consistency ]
$\Gamma$ consistent such that $\Gamma \subseteq \Gamma'$ and $\Gamma'$ consistent $\imp$ $\Gamma = \Gamma'$.

\subsection*{Chapter 2. Predicate Logic}

\item[Structure (58)]
An ordered sequence $\langle A, R_1, ..., R_n, F_1, ..., F_m, \{c_i | i \in I\} \rangle$, where the relations and functions are on $A$, and the constants are elements of $A$.\n\n
Typical element name: $\A$

\item[Similarity Type (of a Structure) (59)]
A sequence $\langle r_1, ..., r_n; a_1, ..., a_n; \kappa \rangle$ where $r_i$ an $a_i$ are arities (number of arguments / number of arguments without output value) of $R_i$ and $F_i$, and $\kappa$ is the number of constants.\n\n
Typical name: none.

\item[Language]
A set of expressions(?) (sentences?) built up of a set of symbols with amounts corresponding to a similarity type.\n
(n.b.  $\doteq$ is always a relation: identity/equality.)\n\n
Typical name: $L$

\item[Universe of a Structure]
$|\A| = A$ as in the definition.

\item[$TERM$ (61)]
smallest set $X$ such that:\n
(i) constants ${\overline c_i}, i \in I$, variables $x_i, i \in \N$\n
(ii) $t_{1}, ..., t_{a_i} \in X \imp f_i(t_1, p..., t_{a_i}) \in X$\n\n
Typical element name: $t$.

\item[$FORM$ (61)]
smallest set $X$ with:\n
(i) $\bot$\n
- - $P_i(...)$ (... each in X)\n
- - $t_1 = t_2 \in X$\n
(ii) $(\phi \square \psi) \in X$ $\{\wedge, \vee, \rightarrow, \leftrightarrow \}$\n
(iii) $(\neg \phi)$\n
(iii) $((\forall x_i) \phi)$,  $((\E x_i) \phi)$\n\n
Typical element name: $\phi$

\item[Free variables (63-64)]
The set $FV(t)$ and $FV(\phi)$ is defined recursively.

\item[Closed / Open / Sentence (64)]
$t$ (or $\phi$) is closed if $FV(t) = \0$.\n
A closed formula is a sentence.\n
A formula without quantifiers is open.\\

\item[$TERM_c$ (64)]
Set of closed terms (in a language?).

\item[$SENT$ (64)]
Set of sentences (in a language?).

\item[Free variable (66)]
$\phi$ free for $\$$ in $\phi$, defined recursively using $FV$.

\item[Extended language (67)]
$L(\A)$: add constant symbols for all elements of $\mathfrak{\A}$ to $L$. $\overline a$ from $a \in |\A|$

\item[Interpretation/valuation of sentences in $L(\A)$ (69-70)]
Recursively defined valuation over $FORM$(?).\n
$[|\phi|]_\A$ or $v_\A(\phi)$ is a mapping $[|.|]_\A: SENT\->\{0, 1\}$, recursively defined.\\
(Valuation of a term: $(.)^\A: TERM_c \-> |\A|$)

\item[$\A \vDash \phi$ (70)]
Defined as $[|\phi|]_\A = 1$ ($\vDash$ is the ``satisfaction relation'').

\item[(Universal) closure]
If $FV(\phi) = {z_1, ..., z_k}$, then $Cl(\phi) := \forall z_1 ... z_k \phi$.

\item[Some Semantics (71)]
(i) $\A \vDash \phi \iff \A \vDash Cl(\phi)$\n
(ii) $\vDash \phi \iff \A \vDash \phi\ \forall \A$ (of the appropriate type)\n
(iii) $\A \vDash \Gamma \iff \A \vDash \psi\ \forall \psi \in \Gamma$.\n
(iv) $\Gamma \vDash \phi \iff (\A \vDash \Gamma \imp \A \vDash \phi)$, where $a \in \Gamma$ and $\phi$ are sentences.

\item[Model (71)]
If $\A \vDash \sigma$, then $\A$ is a model of $\sigma$.

\item[Semantic consequence (71)]
$\phi$ is a semantic consequence of $\Gamma$ if $\Gamma \vDash \phi$ ($\phi$ holds in each model of $\Gamma$.)\n
($\vDash \phi$ means $\phi$ is \emph{true}.)

\item[Satisfiability]
A formula with free variables $z_i$ is satisfiable if there is a set of elements $a_i \in |\A|$ such that $\A \vDash \phi[{\overline a}_1, ..., {\overline a}_k, / {\overline z}_1, ..., {\overline z}_k]$ (substitution).

\item[Prenex (normal) form (78)]
$\phi$ with quantifiers followed by an open formula.\n
(Theorem:  For each $\phi$, $\E$ a prenex formula $\psi \st \vDash \phi \leftrightarrow \psi$)

\item[Identity Axioms]
$I_1$: $\forall x\ (x=x)$ (reflexive)\n
$I_2$: $\forall xy\ (x=y \-> y=x)$ (symmetric)\n
$I_3$: $\forall xyz\ (x=y \wedge y=z \-> x=z)$ (transitive)\n
$I_4$: If the arguments are equal, $t(x_1, ..., x_n) = t(y_1, ..., y_n)$ and $\phi(x_1, ..., x_n) \-> \phi(y_1, ..., y_n)$

\subsection*{Chapter 3. Completeness}

\item[Theory (104)]
A theory $T$ is a collection of sentences such that $T \vdash \phi \imp \phi \in T$ (closed under derivability).\\
Typical name: $T$.

\item[Axiom Set (104)]
A set $\Gamma$ such that $T = \{\phi | \Gamma \vdash \phi\}$.

\item[Henkin Theory (104)]
$T$ is a Henkin theory if for each sentence $\E x\ \phi(x)$ there exists a constant $c$ such that $((\E x\ \phi(x)) \-> \phi(c)) \in T$. ($c$ is a \emph{witness} for $\E x\ \phi(x)$.)

\item[Extension (of a theory) (104)]
Theories $T$ and $T'$ with respective languages $L, L'$:\n
(i) $T$ is an extension of $T'$ if $T \subseteq T'$\n
(ii) $T'$ is a \emph{conservative extension} of $T$ if $T' \cup L = T$\n\n
$L*$: Add $c_\phi$ for each $\phi$ of the form $\E x\ \phi(x)$\n
$T*$: $T \cup \{ \E x\ \phi(x) | \E x\ \phi(x)$ closed, with witness $c_\phi\}$ (theorem: conservative over $T$)

\item[Model Existence Lemma (103, 109)]
A theorem. If $L$ has cardinality $\kappa$ and $\Gamma$ is a set of consistent sentences, then $\Gamma$ has a model of cardinality $\leq \kappa$.

\item[Compactness Theorem (111)]
$\Gamma$ has a model $\iff$ each finite $\delta \subset \Gamma$ has a model.

\item[$Mod(\Gamma)$]
$Mod(\Gamma) = \{\A | \A \vDash \sigma$ for all $\sigma \in \Gamma\}$.

\item[Theory of $(\mathcal{K})$]
If $\mathcal{K}$ is a class of structures with the same similarity type,\n
$Th(\mathcal{K}) = \{\sigma | \A \vDash \sigma$ for all $\A \in \mathcal{K}\}$

\item[Reduct / Expansion]
$\A$ is a reduct of $\B$ if $|\A| = |\B|$ and $R_i, F_j, c_k$ from $\A$ are also in $\B$. $\B$ is an expansion of $\A$.

\item[Axiomatizability]
A class $\mathcal{K}$ of structures is (finitely) axiomatizable of there is a (finite) set $\Gamma$ such that $\mathcal{K} = Mod(\Gamma)$.

\item[Structure Universe Homomorphism (119)]
(i) $f: |\A| \-> |\B|$ is a homomorphism if each $P_i, F_j, c_k$ maps from $\A$ to $\B$ if $f$ is mapped over its arguments.\n
(ii) $f$ is an isomorphism if it's also bijective and predicates can map back.

\item[Isomorphic Structures (119)]
$\A \cong \B$ if there is an isomorphism $f: \A \-> \B$.

\item[Elementary Equivalence (NOT SYMMETRIC) ($\A \equiv \B$) (119)]
$\A$ is elementarily equivalent to $\B$ if for all sentences $\sigma \in L$ (language of $\A$), $\A \vDash \sigma \iff \B \vDash \sigma$. (Note: $\A \equiv \B \iff Th(\A) = Th(\B)$)\n

\item[Substructure / Submodel ($\A \subseteq \B$) (119)]
$\A$ is a substructure/submodel of $\B$ (same type) if all elements of $\B$, ``restricted to the universe of $\A$,'' are in $\A$.

\item[Elementary Substructure ($\A \prec \B$) (119)]
$\A$ is an elementary substructure of $\B$ ($\B$ is an elementary extension of $\A$) if $\A \subseteq \B$ and for all $\phi(...) \in L$, $a_i \in |\A|$, $\A \vDash \phi({\overline a}_1, ..., {\overline a}_n) \iff \B \vDash \phi({\overline a}_1, ..., {\overline a}_n)$. ($\A$ and $\B$ have the same true sentences \emph{with parameters in $\A$}.) Note that $\A \prec \B \imp \A \equiv \B$.

\item[Complete theory (124)]
$T$ with axioms $\Gamma \subset L$ is called complete if for each sentence $\sigma \in L$, either $\Gamma \vdash \sigma$ or $\Gamma \vdash \neg \sigma$.

\item[$\kappa$-categorical (125)]
Let $\kappa$ be a cardinal. $T$ is $\kappa$-categorical if it has exactly one model of cardinality $\kappa$  up to isomorphism.

\item[Model complete (131)]
$T$ is model complete if $\A, \B \in Mod(T)$, $\A \subseteq \B \imp \A \prec \B$.

\item[Prime model]
$T$ has a a prime model if that model is contained in every model of $T$ up to isomorphism.

\subsection*{Chapter 4. Second Order Logic}

\item[Second-order alphabet]
(i) individual variables $x_0, ...$\n
(ii) individual constants $c_0, ...$\n
for each $n \geq 0$: \n
(iii) $n$-ary set (predicate) variables $X_0^n, X_1^n, ...$\n
also for each $n \geq 0$: \n
(iv) $n$-ary set (predicate) constants $\bot, P_0^n, P_1^n, ...$\n
(v) connectives: $\wedge', \->, \vee, \neg, \leftrightarrow, \E, \forall$.\n
(and auxiliary symbols: $(),$)\n
Countable variables of each kind, any number of constants.

\item[Second-order formulas]
$FORM$ is inductively defined, again:\n
(i) $X_i^0, P_i^0, \bot \in FORM$\n
(ii) for $n>0$, $X^n(t_1, ..., t_n) \in FORM$, $P^n(t_1, ..., t_n) \in FORM$\n
(iii) $FORM$ is closed under the propositional connectives\n
(iv) $FORM$ is closed under first- and second-order quantification.

\item[Second-order structure (144)]
$\A = \langle A, A*, c*, R* \rangle$, where:\n
$A* = \langle A_n | n \in \N \rangle$\n
$c* = \{ c_i | i \in \N \} \subset A$\n
$A = \langle R_i^n | i, n \in \N \rangle$, and $A_i \subseteq \mathcal{P}(A^n), R_i^n \in A_n$.

\item[Full structure (144)]
$A_n = \mathcal{P}(A^n)$; each $A_n$ contains all $n$-ary relations.

\item[Validity (144)]
$\A \vDash \phi$ similar to first-order logic.

\item[Comprehension Schema (145)]
$\E X^n \forall x_1...x_n[\phi(x_1, ..., x_n) \leftrightarrow X^n(x_1, ..., x_n)]$.

\item[Model of second-order logic (147)]
A second-order structure $\A$ is a model of second-order logic if the comprehension schema is valid in $\A$.

\subsection*{Intuitionistic Logic}

\item[G\"{o}del Translation]
The mapping $^\circ: FORM\->FORM$:\n
(i) $\bot^\circ := \bot$, $\phi^\circ := \neg\neg ^ \phi$.\n
(ii) $(\phi \wedge \psi)^\circ := \phi^\circ \wedge \psi^\circ$\n
(iii) $(\phi \vee \psi)^\circ = \neg(\neg\phi^\circ \wedge \neg \psi^\circ)$\n
(iv) $(\phi \-> \psi)^\circ := \phi^\circ \-> \psi^\circ$\n
(v) $(\forall x\ \phi(x))^\circ := \forall x\ \phi^\circ(x)$\n
(vi) $(\E x\ \phi(x))^\circ := \neg \forall x\ \neg\phi^\circ(x)$\n\n
(Theorem: $\Gamma \vdash_c \phi \iff \Gamma \vdash_i \phi^\circ$)

\item[Kripke Model]
$\mathcal{K} = \langle K, \Sigma, C, D\rangle$. $K$ is a (non-empty) poset, $C$ a function on the constants of $L$, $D$ a set-valued function on $K$, $\Sigma$ a function on $K$ with certain constraints. ($D$ and $\Sigma$ also satisfy constraints.)

\end{mylist}


\subsection*{Comments}
Not included:
\li
\item Some alphabets
\item Various definitions of substitution.
\item $Diag(\A)$, isomorpically embedded (120).
\item decidable ($\Gamma$), decidable ($T$), effectively enumerable ($\Gamma$), effectively axiomatizable ($T$)
\item Skolem functions, axioms, extensions, expansions (136), hulls (141)
\lid



\end{document}