\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage[french]{babel}


\newcommand{\e}[1]{\mathbb{#1}}
\newcommand{\m}[1]{\mathcal{#1}}
\newcommand{\me}[1]{|\mathcal{#1}|}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\F}{\mathcal{F}}

\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\val}{Val}



\title{Théorème de Lowenheim-Skolem}
\author{Mathias Millet}




\begin{document}

\maketitle
On se place sur un langage $\L$.
\paragraph{Définition} Soit $\m{M}$ un modèle, un sous-modèle $\m{N}$ de $\m{M}$ est un modèle tel que 
\begin{itemize}
\item $\me{N} \subset \me{M}$
\item pour tout symbole de fonction $f$, $f_{\m{N}} = f_{\m{M}}$
\item pour tout symbole de relation $R$, $R_{\m{N}} = R_{\m{M}} \cap \me{N}\times\me{N}$
\end{itemize}

\paragraph{Définition} Soient $\m{M}$ un modèle, $\m{N}$ un sous-modèle. $\m{N}$ est un sous-modèle élémentaire si pour toute formule $F[x_1,...,x_n]$, pour tous $a_1, ..., a_n \in \me{N}$, on a 
\[ \m{M} \models F[a_1, ..., a_n] \text{ ssi } \m{N} \models F[a_1, ..., a_n] \]
%\paragraph{Définition} Soit $F$ une formule à $n$ variables libres. On dira que est F à paramètres dans $A \subset \me{M}$ si l'évaluation de $F$ est restreinte à des environnements où les variables libres de $F$ sont liées à des valeurs dans $A$.

\paragraph{Définition} Pour $A \subset \me{M}$, on note $E(A)$ un plus petit ensemble satisfaisant: pour $F[x]$ une formule à paramètres dans $A$, si $\m{M} \models \exists x F[x]$, alors E(A) contient un élément de $\{y_F , \m{M} \models F[y_F] \}$ (qui est non vide par définition).


\paragraph{Théorème de Lowenheim-Skolem descendant (affaibli)} Soit $\m{M}$ un modèle, si $\L$ est au plus dénombrable, alors $\m{M}$ admet un sous-modèle élémentaire au plus dénombrable.


\subparagraph{Preuve}

\begin{enumerate}

\item On définit la suite $(X_n)_{n \geq 0}$ par $X_0 = \emptyset$, $X_{n+1} = X_n \cup E(X_n)$. Soit alors $\m{N}$ le sous-modèle de $\m{M}$ tel que $\me{N} = \cup_{n \in \N} X_n$. Notons que $\me{N}$ est alors stable par l'opérateur $E$ : $E(\me{N}) = \me{N}$


\begin{enumerate}

\item Montrons tout d'abord que ce nouveau modèle est correctement défini, c'est à dire que pour tout $n\in \N$, pour tous $(a_1, ..., a_n) \in \medskip{N}^n$, $f \in \F_n$, on a bien: $f(a_1, ..., a_n) \in \me{N}$. 

C'est en fait immédiat, puisque, $f$ étant partout définie, on a $\m{M} \models \exists x f(a_1, ..., a_n)~=~x$. La suite $(X_n)_n$ étant croissante, il existe $p$ tel que $a_1, ..., a_n \in X_p$. Par définition de $(X_n)_n$, l'élément $y = f(a_1, ..., a_n) \in \m{M}$ appartient alors à $X_{p+1}$, et donc à~$\me{N}$.

Notons en particulier que les constantes sont dans $X_1$.

\item $\m{N}$ est au plus dénombrable. En effet, $\L$ étant au plus dénombrable, les variables, fonctions et relations sont aussi en quantité au plus dénombrable. L'ensemble des formules étant aussi dénombrable, chaque $X_n$ est au plus dénombrable; leur réunion l'est aussi. 


\end{enumerate}

\item Montrons maintenant que $\m{N}$ est un sous-modèle élémentaire de $\m{M}$, c'est à dire que, pour  $a_1, ... a_n \in \me{N}$ on a bien: pour toute formule $F[x_1,...,x_n]$, 

$\m{M} \models F[a_1, ..., a_n] \text{ ssi } \m{N} \models F[a_1, ..., a_n]$


Tout d'abord, on a : pour tout terme $t[x_1, ..., x_n]$, $\val_{\m{M}}(t[a_1, ..., a_n]) = \val_{\m{N}}(t[a_1, ..., a_n])$ (immédiat par induction sur les termes, $\m{N}$ étant un sous-modèle de $\m{M}$).

Effectuons maintenant une induction sur les formules\footnote{les cas d'induction commencent avec l'hypothèse, que l'on aurait pu préférer cacher sous le tapis : $\forall n, \forall a_1, ..., a_n in \me{N}$}.

Soit $F[x_1, .., x_n]$ une formule.
	\begin{enumerate}
	\item Cas de base : si $F[a_1, ..., a_n] = R(t_1[a_1, ..., a_n], ..., t_s[a_1, ..., a_[n])$ : immédiat, $\m{N}$ étant un sous-modèle de $\m{M}$
	
	\item Cas des connecteurs propositionnels : immédiat par hypothèse d'induction.	
	
	\item Cas où $F[a_1, ..., a_n] = \forall y G[a_1, ..., a_n, y]$ : on se ramène à $F = \neg \exists y \neg G$
	\item Cas où $F[a_1, ..., a_n] = \exists y G[a_1, ..., a_n, y]$ :
		\begin{description}
		\item[$\Rightarrow$] Supposons $\m{M} \models \exists y G[a_1, ..., a_n, y]$, alors, la suite $(X_n)_n)$ étant croissante, il existe $p$ tel que, pour tout $i$, $a_i \in X_p$. Par construction des $(X_n)_n$, il existe donc $a_{n+1} \in X_{p+1} \subset \me{N}$ tel que $\m{M} \models G[a_1, ..., a_n, a_{n+1}]$.  De plus, l'hypothèse d'induction nous donne : $\m{N} \models G[a_1, ..., a_n, a_{n+1}]$. Enfin, par définition de la validité des formules, on obtient : $\m{N}~\models~\exists y G[a_1, ..., a_n, y]$
		\item[$\Leftarrow$] Supposons $\m{N} \models \exists y G[a_1, ..., a_n, y]$, alors il existe $a_{n+1} \in \me{N}$ tel que $\m{N} \models G[a_1, ..., a_n, a_{n+1}]$; par hypothèse d'induction, $\m{M} \models G[a_1, ..., a_n, a_{n+1}]$, et enfin $\m{M} \models \exists y G[a_1, ..., a_n, y]$
		\end{description}
	\end{enumerate}	 
 
	Si l'on voulait faire des preuves correctes, on ajouterait que ceci constitue bien une induction sur l'ensemble des formules. En effet, pour l'ordre sur les formules donné par $\varsigma(F) = $(nombre de $\forall$ dans $F$, nombre de $\exists$ et de connecteurs logiques dans $F$), $\varsigma(F)$ décroit à chaque étape d'induction. 
\end{enumerate}


\paragraph{Corollaire} Soit $T$ une théorie sur un langage $\L$ au plus dénombrable. Si $T$ possède un modèle infini, alors $T$ possède un modèle au plus dénombrable.

\paragraph{Lemme complémentaire} Si $\m{M}$ est infini, le modèle $\m{N}$ ainsi construit est en fait exactement dénombrable. En effet, la propriété \og être un ensemble infini \fg étant axiomatisable, $\m{M}$ a cette propriété si et seulement si $\m{N}$ l'a.


\begin{thebibliography}{15}

   \bibitem{cori lascar}
          Cori, Lascar,
          \textit{Logique mathématique, tome 2}.

	\bibitem{hodges}
		Hodges,
		\textit{Model theory}

\end{thebibliography}
\end{document}