Mathématique 22 UCL

Un forum de mathématiciens
 
AccueilAccueil  PortailPortail  CalendrierCalendrier  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  GroupesGroupes  Connexion  

Partagez | 
 

 Logique

Aller en bas 
AuteurMessage
damien
Pirate d'Euler
avatar

Nombre de messages : 100
Age : 33
Localisation : NAMUR
Date d'inscription : 03/10/2006

MessageSujet: Logique   Dim 20 Mai - 3:48

Mich' t'aurais pas envie de mettre ce que t'as déja écris sur le site?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Dim 20 Mai - 15:42

J'en suis à la moitié (j'y ai pas retravaillé depuis), c'est encore bourré de fautes, mais je vais essayer de faire cela demain
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Ven 25 Mai - 4:51

ah ben non, finalement je fait mon rapport de séminaire...


... Si vous avez besoin du bookin de Hodges, c'est pas de chance, je l'ai encore réservé pour trois semaines...

...ou alors appelez moi



[Edit Damien : Ptit salopiaud]
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Laetitia
Magma


Nombre de messages : 15
Age : 33
Date d'inscription : 04/10/2006

MessageSujet: Re: Logique   Sam 2 Juin - 14:00

J'ai trouvé sur internet un cours de théorie des modèles qui a l'air pas mal,
pour ceux que ça interesse voici l'adresse:
http://www.math.uiuc.edu/~henson/Math571/Spring2006/classnotes571.pdf
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
damien
Pirate d'Euler
avatar

Nombre de messages : 100
Age : 33
Localisation : NAMUR
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 4:30

et qué? ca viens ce truc?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 8:30

[T'es malade Mich'!!!]

Voilà tjrs le début :

\documentclass[a4paper,french,12pt]{book}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{babel}
\usepackage{amssymb,amsmath}

\usepackage{amsthm}

%%\newtheorem{thrm}{Théorème}[subsection]


\newtheorem{de}{Définition}[chapter]
\newtheorem{thrm}[de]{Théorème}
\newtheorem{prop}[de]{Proposition}
\newtheorem{lem}[de]{Lemme}
\newtheorem{cor}[de]{Corollaire}

\title {Résumé de logique}
\author{M Thayse}
\date{15 mars 2007}


\begin{document}
\chapter{Dualité de Stone - Dérivation de Cantor}
\section{Treillis distributif et algèbre de Boole}
\subsection{Première définition de treillis}
Une relation d'\emph{ordre} est une relation réflexive, antisymétrique et transitive. Un ordre sur un ensemble est total si toute paire d'éléments est en relation. Un \emph{suprémum} d'une partie d'un ensemble ordonné est un majorant minorant tous les majorants. Lorsqu'il existe, il est unique. L'\emph{infimum} est la notion duale de suprémum.

Un \emph{$\wedge$-demi-treillis} est un ensemble ordonné tel que toute famille finie y admet un suprémum, un \emph{$\vee$-demi-treillis} est un ensmeble ordonné tel que toute famille finie y admet un infimum. Lorsqu'il existe, on note souvent \emph{0} le suprémum du vide et \emph{1} l'infimum du vide. Un ensemble ordonné admettant ces deux propriété est appelé \emph{treillis}. Un treillis est dit \emph{complet} si pour toute famille infinie le suprémum existe. Dans un treillis complet, l'infimum existe aussi pour toute famille infinie. Comme exemples de treillis complets, nous avons l'ensemble des parties d'un ensemble ordonné par inclusion, ou encore l'ensemble des ouverts d'un espace topologique ordonnée par inclusion. %% L'ensemble des parties finies de $X \cup \left\{ X \right\}$ est un treillis incomplet.

\subsection{Deuxième définition de treillis}

Soit un ensemble $A$ muni de deux opérations binaires associatives, commutatives, indempotentes et munies d'un neutre : $\vee$ de neutre $0$ et $\wedge$ de neutre $1$. On pose les relations d'ordre suivante :
\begin{eqnarray*}
a \leq_{\vee} b &\Longleftrightarrow& a \vee b = b\\
a \leq_{\wedge} b &\Longleftrightarrow& a \wedge b = a
\end{eqnarray*}

Pour que ces relations d'ordre soient équivalentes, il suffit d'imposer les relations suivantes, appelées \emph{lois d'absorbtion} :

\begin{eqnarray*}
a \wedge \left(a \vee b \right) &=& a \\ b \vee \left(a \wedge b \right) &=& b
\end{eqnarray*}

Un treillis est dit \emph{distributif} si on a l'une des deux lois de distributions suivantes : (qui sont équivalentes dans le cadre d'un treillis)

\begin{eqnarray*}
a \wedge \left(b \vee c \right) &=& \left(a \wedge b \right) \vee \left(a \wedge c \right)
\\ a \vee \left(b \wedge c \right) &=& \left(a \vee b \right) \wedge \left(a \vee c \right)
\end{eqnarray*}

Une \emph{algèbre de Boole} est un treillis distributif dont les lois de composition sont bornées ($1 \vee a = 1$, $0 \wedge a = 0$) et complémentées (pour tout $a$ il existe un élément (unique ?) $\neg a$ tel que $a \wedge \neg a = 0$ et $a \vee \neg a = 1$). L'ensemble des parties d'un ensemble muni des opération d'union et d'intersection est un treillis distributif.

Etant donné deux éléments a et b d'un treillis, on apelle \emph{pseudo-complément} de a par rapport à b un élément que l'on note $\left(a \rightarrow b \right)$ tel que pour tout c on aie $c \leq \left(a \rightarrow b \right) \Leftrightarrow a \wedge c \leq b$.

Une \emph{algèbre de Heyting} est un treillis admettant pour toute paire d'élement un pseudo-complément. Une algèbre de Heyting est automatiquement un treillis distributif. Une algèbre de Boole est aussi une algèbre de Heyting, le pseudo complément de $a$ par rapport à $b$ étant alors $\left(\neg a \vee b\right)$.

Dans une algèbre de Boole $B$, on peut définir une nouvelle opération $\left(a \Delta b \right) = \left( \neg a \wedge b \right) \vee \left( a \wedge \neg b \right)$. $\left(B,\Delta,\wedge \right)$ forme alors un anneau commutatif avec multiplication idempotente. Pour rappel, un \emph{groupe} est une ensemble munit d'une loi associative, d'un neutre et d'un inverse pour chaque élément, et un \emph{anneau} est un ensemble munit de deux lois de compositions formant un groupe commutatif pour la première et telle que la deuxième est associative et distribue la première. On appelle anneau booléen un anneau $\left(B,\Delta,\wedge \right)$ dont la multiplication est idempotente. Un anneau booléen définit une algèbre de boole en posant $a \vee b = a \Delta b \Delta \left(a \vee b \right)$.

\section{Espaces de filtres premier}

Une partie $I$ d'un $\vee$-demi-treillis est un \emph{idéal} si $I$ est $\wedge$-stable et que si un élément appartient à $I$, alors tout élément inférieur lui appartient aussi. L'ensemble des éléments inférieurs à un élément $a$ donné forme un idéal appelé \emph{idéal principal} engendré par $a$. Un idéal \emph{propre} est un idéal différent du treillis complet.

Une partie $F$ d'un $\wedge$-demi-treillis est un \emph{filtre} si $F$ est $\vee$-stable et que si un élément appartient à $F$, alors tout élément supérieur lui appartient aussi. L'ensemble des éléments supérieurs à un élément $a$ donné forme un filtre appelé \emph{filtre principal} engendré par $a$. Un filtre \emph{propre} est un filtre différent du treillis complet.

Dans un treillis, un idéal propre $I$ est premier si $\left(a \wedge b \right) \in I$ implique que $a \in I$ ou $b \in I$. Un filtre propre $F$ est premier si $\left(a \vee b \right) \in F$ implique que $a \in F$ ou $b \in F$.

Un homomorphisme de treillis sur $\left\{0,1\right\}$ définit un idéal et un filtre premiers en prenant les images invers de $0$ et de $1$.

Un ensemble ordonné est \emph{inductif} si toute partie totalement ordonnée admet un majorant.

\begin{thrm}
Etant donné un treillis $D$, un idéal $I$ et un filtre $F$, $I$ et $F$ étant disjoints, la collection des idéaux contenant $I$ et disjoints de $F$ admet des éléments maximaux pour l'inclusion, ces éléments maximaux étant des idéaux premiers.
\end{thrm}

En particulier; Pour $I = \{0\}$ et $F = \{1\}$ donnés, on voit qu'il existe des idéaux propres premiers (contenant $I$) et des filtres propres premier (contenant $F$).


\begin{cor}
Si dans un treillis distributif $D$ donné on a $a,b$ tels que $b\nleq a$, alors il existe un homomorphisme $h : D \mapsto \{0,1\}$ tel que $h(a) = 0$ et $h(b) = 1$
\end{cor}

De plus, dans une algèbre de Boole, tout filtre premier est un filtre maximal propre.

Etant donné un treillis distributif $D$ donné, on note $S_D$ l'ensemble des filtres premiers sur $D$. A chaque élément $a$ de $D$ attribue un élément $a^*$ de $\mathcal{P}\left(S_D\right)$ composé de tout les filtres contenant $a$. On obtient un homomorphisme injectif de treillis.

On définit une topologie sur $S_D$ en prenant comme base d'ouverts l'ensemble des $a^*$ tels que $a \in D$. C'est un espace \emph{sobre}, c'est à dire que toute partie fermée irréductible (non union de deux fermé) est un point (tout espace séparé est sobre). C'est en plus un espace \emph{cohérent}, c'est à dire sobre et quasi-compact (de tout recouvrement ouvert on peut extraire un sous-recouvrement fini).

Sur un espace sobre, on peut définir un ordre \emph{de spécialisation} : $F_1 \leq F_2 \Leftrightarrow \bar{F}_1 \in \bar{F}_2$.

A chaque treillis distributif $D$ , on associe un espace cohérent $S_D$, de même à chaque homomorphisme de treillis distributifs $h : D_1 \mapsto D_2$ on associe un homomorphisme d'espaces cohérents $S_h : S_{D_1} \mapsto S_{D_2}$. $S_h$ est une fonction continue telle que l'image réciproque d'un ouvert de base (quasi-compact) est un ouvert de base (quasi-compact).

Si, en plus d'être un treillis distributif, $D$ est une algèbre de Boole, alors $S_D$ devient un espace \emph{booléen}, c'est-à-dire un espace séparé, quasi-compact, avec une base d'ouverts fermés (les $a^*$).

Dans un espace booléen, l'ordre de spécialisation revient à l'inclusion. %Pourquoi ?

A tout morphisme de treillis $h : D_1 \mapsto D_2$ on associe une application continue $S_h : S_{D_2} \mapsto S_{D_1}$ telle que $S_h^{-1} \left(a_1^*\right) = \left(h\left(a_1\right)\right)^*$

Pour chaque homomorphisme $h : D_1 \mapsto D_2$ de structure algébrique, on a une factorisation naturelle à travers l'image, en passant par la relation d'équivalence définie par l'égalité de l'image. Cette équivalence est une emph{congruence}, c'est-à-dire une équivalence compatible avec les opérations, de sorte que le quotient garde à son tour la structure algébrique (ici, le treillis distributif) : $h = i \circ s : D_1 \stackrel{s}{\rightarrow} \frac{D_1}{\sim} \stackrel{i}{\rightarrow} D_2$

A cette factorisation correspond une factorisation sur l'espace cohérent : $S_h = S_i \circ S_s : S_{D_2} \stackrel{S_s}{\rightarrow} \frac{S_{D_1}}{\sim} \stackrel{S_i}{\rightarrow} S_{D_2}$

Etant donné un filtre $F$ sur une algèbre de Boole $B$, on peut définir une congruence en posant $(a \sim b)\Leftrightarrow (a \leftrightarrow b ) \subset F$. Le quotient obtenu p ar cette congruence est noté $B_F$. On obtient une surjection $s : B \mapsto B_F$ ry unr injection $i : S_{B_F} \mapsto S_B$, $S_{B_F}$ étant l'ensemble des filtres maximaux sur $B$ qui contiennent $F$, c'est-à-dire l'intersection de tous les $b^*$ tels que $b \in F$.

\section{Points isolés et dérivation de Cantor}

Nous avons vu que le treillis distributif est un notion moins forte que celle d'algèbre de Boole. Toutefois nous allons montrer qu'un treillis distributif peut toujours être plongé dans yne algèbre de Boole.


On dit qu'un point $x$ est \emph{isolé} dans une partie $A$ d'un espace topologique $X$ si il existe un ouvert $O$ tel que $O \cap A = \left\{x\right\}$

\begin{thrm}
Un point $F$ d'un espace $S_D$ est isolé si et seulement si $F = \left[ a, \rightarrow \right[$ pour $a$ atomique
\end{thrm}

En fait, les points isolés sont exactement les filtres principaux engendrés par les éléments atomiques.

\begin{thrm}
Soit $X$ un espace booléen. Un fermé non vide sans point isolé a nécessairement au moins $2^{\aleph_0}$ points.
\end{thrm}

Un ensemble est dit \emph{rare} dans un espace topologique si son intérieur est vide.

\begin{thrm}
Le complémentaire d'une union dénombrable de fermés rares dans un espace booléen est partout dense.
\end{thrm}

Soit $X$ un espace topologique. on note $dX$ comme l'ensemble des points non isolés dans $X$. Si $x$ appartient à la n-ième dérivation de Cantor sans appartenir à la n+1-ième, on dit que $x$ est de \emph{rang $\alpha$ de Cantor}. Le \emph{noyau parfait} de $X$ est l'ensemble des points appartenant à toutes les dérivations de Cantor de $X$.

\begin{thrm}
Si $X$ admet une base d'ouverts fermés dénombrables, le processus s'arrête après un nombre au plus dénombrable d'étapes. Si $X$ est lui-même dénombrable, alors le noyau parfait est vide et les points isolés constituent une partie partout dense.
\end{thrm}

\begin{thrm}
Soit $f : X \mapsto Y$ une surjection continue entre espaces compacts. Alors $dY \subseteq f_* \left(dx\right)$.
\end{thrm}
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 8:34

\chapter{Notions fondamentales}
\section{ Langages et structures du premier ordre}

Un \emph{langage du premier ordre} $\mathcal{L}$ est composé d'un ensemble infini dénombrable de variables $V\left(\mathcal{L}\right)$, d'une famille dénombrable d'ensembles $\left(\mathcal{O}_{\mathcal{L},n}\right)_{n \in \mathbb{N}}$ dont les éléments sont les \emph{symboles d'opération n-aire}, comprenant le plus souvent les projections $p_{i}^n$ sur la i-ème coordonnées, d'une famille dénombrable d'ensembles $\left(\mathcal{O}_{\mathcal{R},n}\right)_{n \in \mathbb{N}}$ dont les éléments sont les \emph{symboles de relation n-aire}, comprenant le plus souvent les symboles de relation 0-aire $\bot$ et $\top$, et enfin les symboles logiques de connection ($\neg$, $\wedge$, $\cup$, $\rightarrow$) et de quantification ($\forall x$ et $\exists x$, un exemplaire pour chaque variable du langage).

Avec ces ingrédients, on construit successivement :
\begin{itemize}
\item L'ensemble des \emph{termes} $T\left(\mathcal{L}\right)$, composé des variable, des symboles d'opérations $0$-aires et des symboles d'opération $n$-aires suivis de $n$ termes.
\item L'ensemble des formules atomiques $At\left(\mathcal{L}\right)$ composé des symboles de relations $n$-aires suivis de $n$ termes.
\item L'ensemble des formules $Form\left(\mathcal{L}\right)$ composé des formules atomiques, des négations ($\neg$) ou quantification appliquées aux formules, des connections binaires appliquées à des paires de formules.
\end{itemize}

Pour chaque terme $t$, on note $V\left(t\right)$ l'ensemble de ses variables. Pour chaque formule $\varphi$, on note $V_l \left( \varphi \right)$ l'ensemble de ses variables libres (c'est-à-dire non quantifiée). Si $\varphi$ est une relation entre différents termes, alors l'ensemble de ses variables libres est l'unions des ensembles de variables libres de ses termes. Si $\varphi$ est une négation d'une autre formule, elle a les même variables libres que cette formule. Si c'est une conjonction, disjonction, implication, alors on prend l'union des variables libres. Si c'est une fomule précédée d'un quantificateur, alors on garde l'ensemble des variables libres de la formule auquel on retire la variable quantifiée.

Un langage $\mathcal{L}$ du premier ordre sert à parler de réalisations de $\mathcal{L}$ appelées $\mathcal{L}$-structures.

Une \emph{réalisation} $\mathcal{M}$ de $\mathcal{L}$ est composé de :
\begin{itemize}
\item Un ensemble non vide $M$ appelé $\emph{univers}$ de la réalisation.
\item Une famille d'applications d'interprétations $\sigma_n : \mathcal{O}_{\mathcal{L},n} \mapsto Appl[M^n,M] : f \mapsto f^M$
\item Une famille d'applications d'interprétations $\sigma_o : \mathcal{O}_{\mathcal{L},o} \mapsto Appl[\{*\},M] : c \mapsto c^M$
\item Une famille d'applications d'interprétations $\tau_n : \mathcal{R}_{\mathcal{L},n} \mapsto \mathcal{P}(M^n) : r \mapsto r^M$ avec $\tau_0 (\top) = \{*\}$, $\tau_0(\bot) = \emptyset$
\end{itemize}

On va vers l'interprétation de tous les termes de toutes les formules via l'\emph{assignation} $a : V(\mathcal{L}) \mapsto M : x_i \mapsto a(x_i)$.

On définit pour les termes une l'extension $\bar{a}$ de la manière suivante : $\bar{a} : Term(\mathcal{L}) \mapsto M :$
\begin{itemize}
\item $\bar{a}(x_i) = a(x_i)$
\item $\bar{a}(c) = c^M$
\item $\bar{a}(ft_1...t_n) = f^M(\bar{a}(t_1)...\bar{a}(t_n)$
\end{itemize}

Pour chaque terme $t$ à variables libres $V(t) \subset \{x_1,...,x_n\}$ associer une application $t^M : M^n \mapsto M : (a_1,...a_n) \mapsto \bar{a}(t) = t^M(a_1,...,a_n)$. telle que $a(x_1) = a_1$, ..., $a(x_n)=a_n$.

Pour chaque formule $\varphi$ à variables libres $V_l(varphi) \subset \{x_1,...,x_n\}$ associer une relation n-aire $\varphi^M \subset M^n$ en procédant :
\begin{itemize}
\item De manière traditionnelle via la notion de satisfaction. On dit que la réalisation $\mathcal{M}$ \emph{satisfait} $\varphi$ pour l'assignation a, et l'on note $\mathcal{M} \models_a \varphi$ signifie que :
\begin{enumerate}
\item $\varphi = rx_1...x_n$ : $\mathcal{M} \models_a \varphi$ ssi $(a(x_1)...a(x_n)) \in r^M$
\item $\varphi = st_1...t_m$ : $\mathcal{M} \models_a \varphi$

ssi $(t_1^M(a(x_1),...,a(x_n)),...,t_m^M(a(x_1),...,a(x_n))) \in s^M$
\item $\varphi = \neg \psi$ : $\mathcal{M} \models_a \varphi$ ssi non $\mathcal{M} \models_a \psi$
\item $\varphi = \psi_1 \wedge \psi_2$ : $\mathcal{M} \models_a \varphi$ ssi $\mathcal{M} \models_a \psi_1$ et $\mathcal{M} \models_a \psi_2$
\item $\varphi = \psi_1 \vee \psi_2$ : $\mathcal{M} \models_a \varphi$ ssi $\mathcal{M} \models_a \psi_1$ ou $\mathcal{M} \models_a \psi_2$
\item $\varphi = \psi_1 \rightarrow \psi_2$ : $\mathcal{M} \models_a \varphi$ ssi $\mathcal{M} \models_a \psi_1$ implique $\mathcal{M} \models_a \psi_2$
\item $\varphi = \exists x_{n+1} \psi(x_1...x_{n+1})$ : $\mathcal{M} \models_a \varphi$ ssi il existe une assignation $a^\prime$ telle que $a^\prime |_{\{x_1...x_n\}} = a|_{\{x_1...x_n\}}$ avec $\mathcal{M} \models_{a^\prime} \psi$
\item $\varphi = \forall x_{n+1} \psi(x_1...x_{n+1})$ : $\mathcal{M} \models_a \varphi$ ssi pour toute assignation $a^\prime$ telle que $a^\prime |_{\{x_1...x_n\}} = a|_{\{x_1...x_n\}}$ on aie $\mathcal{M} \models_{a^\prime} \psi$
\end{enumerate}
Pour chaque formule $\varphi$ de variables libres $V_l(\varphi) \subset \{x_1...x_n\}$ on a alors une interprétation $\varphi^M \subset M^n$ donnée par $(a_1...a_n) \in \varphi^M$ si on a $\mathcal{M} \models_a \varphi$ pour toute assignation $a$ telle que $a(x_n) = a_n$.
\item De manière non traditionnelle sans passer par la satisfaction) on peu associer à toute formule $\varphi$ du langage $\mathcal{L}$ à variables libres $V_l(\varphi) \subset \{x_1...x_n\}$ une relation n-aire $\varphi^M \subset M^n$ en procédant de amnière plus directe :
\begin{enumerate}
\item $\varphi = rx_1...x_n$ : $\varphi^M = r^M$
\item $\varphi = st_1...t_m$ : $\varphi^M = (t_1^M,...,t_m^M)^*(s^M)$
\item $\varphi = \neg \psi$ : $\varphi^M =(\psi^M)^C = M^n \backslash \psi^M$
\item $\varphi = \psi_1 \wedge \psi_2$ : $\varphi^M = \psi_1^M \cap \psi_2^M$
\item $\varphi = \psi_1 \vee \psi_2$ : $\varphi^M = \psi_1^M \cup \psi_2^M$
\item $\varphi = \psi_1 \rightarrow \psi_2$ : $\varphi^M = (\psi_1^M)^C \cup \psi_2^M$
\item $\varphi = \exists x_{n+1} \psi(x_1...x_{n+1})$ : $\varphi^M = (p_1^{n+1},...,p_n^{n+1})_*(\psi^M)$
\item $\varphi = \forall x_{n+1} \psi(x_1...x_{n+1})$ : $\varphi^M = (p_1^{n+1},...,p_n^{n+1})_!(\psi^M)$
\end{enumerate}
Rappel : $()_*$ : image directe.
Soit $g:X \mapsto Y$, on définit $g_! : \mathcal{P}(X) \mapsto \mathcal{P}(Y) : g_!(A) = [g_*[(x^\prime)^C]]^C$
\end{itemize}

Soit $\mathcal{L}$ un langage du premier ordre, $\mathcal{M}$ une réalisation de ce langage. On dit que la formule $\varphi$ de variables libre $V_l(\varphi) \subset \{x_1...x_n\}$ est $\emph{vraie}$ dans $\mathcal{M}$ si $\varphi^M = M^n$, c'est à dire si $\mathcal{M} \models_a \varphi$ pour toute assignation $a$.

Pour chaque formule $\varphi$ on note $\hat{\varphi} = \forall x_1 ... \forall x_n \varphi(x_1...x_n)$ la \emph{clôture universelle} de $\varphi$. On voit qu'une formule est vraie dans un réalisation si et seulement si sa clôture universelle est vraie dans cette réalisation.

On appelle \emph{théorie} $T$ dans un langage $\mathcal{L}$ un ensemble de formule de ce langage. Une réalisation est un \emph{modèle} d'une théorie si et seulement si toutes les formules de cette théorie sont vraie dans la réalisation.

On appelle \emph{fermeture universelle} $\hat{T}$ d'une théorie $T$ l'ensemble des fermetures universelle de ses formules. $\mathcal{M}$ est modèle de $T$ ssi $\mathcal{M}$ est modèle de $\hat{T}$.

Une formule $\varphi$ est dite \emph{valide} si elle est vraie dans toute réalisation du langage. On note $\models \varphi$.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 8:36

\section{Adéquation et complétude}

Le calcul des prédicats est un jeu pour obtenir des formules valides dans un langage $\mathcal{L}$ donné... et si possible toutes les formules valides. Ce jeu consiste à écrire des \emph{démonstrations}, c'est-à-dire des suites finies de formules telles que chaque formule de la suite ou bien fait partie d'un stock fixé au départ (les axiomes), ou bien s'obtient à partir d'une ou plusieurs formules par application des règles de déductions admises.

Axiomes :
\begin{itemize}
\item $\varphi \rightarrow (\psi \rightarrow \varphi)$
\item $(\varphi \rightarrow (\psi \rightarrow \theta)) \rightarrow ((\varphi \rightarrow \psi) \rightarrow (\varphi \rightarrow \theta))$
\item $(\neg \varphi \rightarrow \neg \psi) \rightarrow ((\neg \varphi \rightarrow \psi) \rightarrow \varphi)$
\item Si $x$ est non-libre dans $\varphi$ : $\forall x (\varphi \rightarrow \psi) \rightarrow (\varphi \rightarrow \forall x \psi)$
\item Si $t$ est libre pour $x$ dans $\varphi$ (c'est à dire qu'aucune occurence libre de $x$ dans $\varphi$ ne figure dans le champ d'un quantificateur portant sur une variable de $t$) : $\forall x \varphi (x) \rightarrow [t | x] \varphi (x)$
\end{itemize}

Règles de déductions :
\begin{itemize}
\item Le modus ponens : si on a $\varphi$ et $\varphi \rightarrow \psi$ alors on a $\psi$
\item La généralisation : si on a $\varphi$ alors on a $\forall x \varphi$.
\end{itemize}

On montre que ce jeu ne donne toutes les formules valides (théorème de complétude) et que des formules valides (théorème d'adéquation). Les formules obtenues ainsi sont appelées \emph{théorèmes} et on écrit $\vdash \varphi$.

\begin{thrm}[Theorème d'adéquation]
$\vdash \varphi \Rightarrow \models \varphi$
\end{thrm}

\begin{thrm}[Theorème de complétude]
$\models \varphi \Rightarrow \vdash \varphi$
\end{thrm}

\begin{thrm}[Theorème de complétude généralisé]
$T \models \varphi \Rightarrow T \vdash \varphi$
\end{thrm}

\begin{lem}
Si $T$ est consistante alors elle admet un modèle.
\end{lem}

Un théorie $T$ est \emph{riche} si pour toute formule $\varphi(x)$ à variable libre il existe une constante $c_\varphi$ telle que $T \vdash \varphi(c_\varphi) \rightarrow \forall x \varphi(x)$, ou encore que pour toute formule $\theta (x)$ il existe $c_\theta$ telle que $T \vdash \exists x \theta (x) \rightarrow \theta (c_\theta)$.

Une théorie consistante est \emph{maximale} si on ne peut lui rajouter de formule sans perdre sa consistance.

\begin{lem}
Si $T$ est fermée, riche, maximale, consistante alors elle admet un modèle.
\end{lem}

Une collection partiellement ordonnée est \emph{inductive} si toute partie totallement ordonnée admet un majorant.

\begin{lem}[Lemme de Zorn]
Toute collection ordonnée inductive admet au moins un élément maximal.
\end{lem}

Soit $T$ une théorie. La collection des théories fermées consistantes contenant $T$ étant un ordonné inductif, il existe des théories fermées consistantes maximales.

\begin{thrm}[Théorème de compacité]
Une théorie $T$ admet un modèle ssi toute partie finie de $T$ admet un modèle ssi $T$ est consistante.
\end{thrm}

Dans la plus grande majorité des cas, $\mathcal{L}$ comprend une relation binaire d'égalité $= \in \mathcal{R}_{\mathcal{L},2}$, et l'on ne s'intéresse qu'aux \emph{réalisations égalitaires}, c'est-à-dire telles que $[=]^M=D_M$.

Une formule $\varphi$ est \emph{égalitairement valide} si elle est vraie dans toute réalisation égalitaire. On note $\models_{eg} \varphi$.

Exemple de théorie égalitairement valide : la théorie Eg :
\begin{itemize}
\item $x=x$
\item $x=y \wedge y=z \rightarrow x=z$
\item Pour chaque $f \in \mathcal{O}_{\mathcal{L},n}$ : $(\bigwedge_{i=1}^n x_i = x_i^\prime) \rightarrow [fx_1...x_n = fx^\prime_1...x^\prime_n]$
\item Pour chaque $r \in \mathcal{R}_{\mathcal{L},n}$ : $(\bigwedge_{i=1}^n x_i = x_i^\prime) \rightarrow [rx_1...x_n = rx^\prime_1...x^\prime_n]$
\end{itemize}

On peut être un modèle de Eg sans être une réalisation égalitaire. Mais on peut définir une nouvelle réalisation $\tilde{\mathcal{M}}$ qui sera égalitaire. Définition de l'univers :
\begin{itemize}
\item $\tilde{M} = \frac{M}{[=]^M}$
\item $f^{\tilde{M}}(\tilde{a}_1,...,\tilde{a}_m) = \tilde{f}^M(a_1...a_m)$
\item $(\tilde{a}_1,...,\tilde{a}_m) \in r^{\tilde{M}}$ ssi $(a_1,...,a_m) \in r^M$
\end{itemize}

A chaque assignation $a : V(\mathcal{L}) \mapsto M$ on a une assignation $\tilde{a} : V(\mathcal{L}) \mapsto \tilde{M} : x_i \mapsto \tilde{a}(x_i)$.

On montre par induction sur la complexité que $\mathcal{M} \models_a \varphi(x_1...x_n)$ ssi $\tilde{\mathcal{M}} \models_a \varphi(x_1...x_n)$.
Et donc $T \models_{eg} \varphi$ ssi $T \cup Eg \models \varphi$.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 8:36

\section{Algèbre de Lindebaum et espaces de types}

Tout langage $\mathcal{L}$ du premier ordre peut être muni d'une interprétation canonique des symboles d'opération.

On définit sur $Form(\mathcal{L})$ une relation binaire en posant $\varphi \leq \psi$ ssi $\vdash \varphi \rightarrow \psi$. Cette relation est réflexive et transitive (de part le calcul des prédicats). C'est un pré-ordre (pas d'anti-symétrie). Pour obtenir un ordre, il suffit de quotienter par la relation d'équivalence $\sim$ déduite du pré-ordre. On obtient une algèbre de Boole $\frac{Form(\mathcal{L})}{\sim}$ :
\begin{itemize}
\item $[\varphi]\wedge[\psi] = [\varphi \wedge \psi]$
\item $[\varphi]\vee[\psi] = [\varphi \vee \psi]$
\item $1 = [\varphi]$ pour $\phi$ théorème du calcul des prédicats.
\item $0 = [\neg \varphi]$ pour $\phi$ théorème du calcul des prédicats.
\end{itemize}

Cette algèbre de Boole est appelée \emph{algèbre de Lindenbaum} du langage $\mathcal{L}$ et est notée $B_{\mathcal{L}}$. On lui associe l'espace booléen $S_{\mathcal{L}}$ avec des ouverts fermés de base $[\varphi]^* = \{F\}$ avec $F$ filtres maximals sur $B_{\mathcal{L}}$ tels que $[\varphi] \in F$.

Si on donne une théorie $T$, on note $[T] = \{[\varphi]|\varphi \in T\}$. On note $F_T$ l'ensemble des éléments de l'algèbre de Lindenbaum démontrables dans la théorie $T$. C'est un filtre sur $\mathcal{B}_{\mathcal{L}}$. On peut former l'\emph{algèbre de Lindenbaum de la théorie} $T$ $B_T = \frac{\mathcal{B}_{\mathcal{L}}}{F_T}$. A l'algèbre $B_T$ correspond l'espace booléen $S_T$, sous-espace de $S_{\mathcal{L}}$
$$S_T = \bigcap_{T \vdash \psi} [\psi]^*$$

Si $T$ est maximale consistante alors $F_T$ sera maximal.

On défini les sous-algèbre de Boole suivantes :
$$\mathcal{B}_{\mathcal{L}}(n) = \{[\varphi] | V_l(\varphi) \subset \{x_1,...,x_n\}\}$$
On obtient une suite d'injections identitaires $\mathcal{B}_{\mathcal{L}}(n) \leftarrow \mathcal{B}_{\mathcal{L}}(n+1) \leftarrow \mathcal{B}_{\mathcal{L}}$.
Dualement, on a une suite de surjections $S_{\mathcal{L}}(n) \leftarrow S_{\mathcal{L}}(n+1)\leftarrow S_{\mathcal{L}}$.
Ces espaces sont est appelés l'\emph{espace des n-types} du langage $\mathcal{L}$.

Une théorie (fermée) défini un filtre $F_T$ sur $\mathcal{B}_{\mathcal{L}}(0)$, mais aussi un filtre $F_{T,n}$ sur $\mathcal{B}_{\mathcal{L}}(n)$ en posant $F_{T,n} = \{[\psi] | \forall (x_1...x_n) \psi\}$. On peut prendre le quotient $B_T(n) = \frac{\mathcal{B}_{\mathcal{L}}(n)}{F_{T,n}}$. C'est l'\emph{algèbre des relations n-aires} de la théorie $T$.

On a une bijection naturelle ($\bar{c} = c_1...c_n$) :
$$\mathcal{B}_{\mathcal{L} \cup \bar{c}} \leftrightarrow \mathcal{B}_{\mathcal{L}}(n) : \varphi(c_1,...,c_n) \leftrightarrow \varphi(x_1,...,x_n)$$

Un n-type correspond à une théorie maximale consistante dans $\mathcal{L} \cup \bar{c}$.

\begin{thrm}[Théorème de la forme normale prénexe]
Pour toute formule on peut trouver une formule équivalente en forme normale prénexe.
\end{thrm}

Dans $\mathcal{B}_{\mathcal{L}}$, on peut distinguer :
\begin{itemize}
\item La sous-algèbre des classes d'équivalence des formules ouvertes
\item Le sous-treillis distributif des (classes d'équivalence des) formules $\exists_1$ (c'est à dire qui s'écrive sous la forme $\exists x_{n+1}...x_{n+m} \psi(x_1...x_{n+m}$ ou des formules $\forall_1$.
\item Le sous treillis des formules $\exists_2$ (c'est à dire qui s'écrive sous la forme $\exists ... \forall ... \psi$
\item Le sous treillis des formules $\forall_2$
\end{itemize}
Ces trois sous-treillis sont des sous-treillis distributifs, pas des algèbres de Boole.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 8:37

\section{Morphismes et diagrammes}
Soit $\mathcal{L}$ un langage du premier ordre, $\mathcal{M}$ et $\mathcal{N}$ deux réalisations avec $M$ et $N$ leurs univers respectifs. Une application $h : M \mapsto N$ est un \emph{homomorphisme} de $\mathcal{L}$-structures si :
\begin{enumerate}
\item Pour tout symbole fonctionnel $f \in \mathcal{O}_{\mathcal{L},n}$ et tout $\bar{a} \in M^n$ on a $h(f^M_{(\bar{a})})=f^N(h\bar{a})$
\item Pour tout symbole relationnel $r \in \mathcal{R}_{\mathcal{L},n}$ et tout $\bar{b} \in M^n$, si $\bar{b} in r^M$ alors $h\bar{b} \in r^N$.
\end{enumerate}

Une formule est dite \emph{positive} si elle est obtenue uniquement à partir de formules atomiques, de conjonctions, de disjonctions et de quantificateurs existentiels.

\begin{prop}
Si $h : M \mapsto N$ est un homomorphisme de $\mathcal{L}$-structures alors :
\begin{enumerate}
\item Pour tout terme $t \in T(\mathcal{L})$ à variables libres $V(t) \subset \{x_1...x_n\}$ et pour tout $\bar{a} \in M^n$ on a $h(t^M(\bar{a})) = t^N(h\bar{a})$.
\item Pour toute formule positive $\varphi(x_1...x_n)$ et tout $\bar{a} \in M^n$ on a que $\bar{a} \in \varphi^M$ implique que $h\bar{a} \in \varphi^N$
\end{enumerate}
\end{prop}

Un homomorphisme préserve donc l'interprétation de tous les termes et est compatible avec l'interprétation des formules positives.

Une application $h : M \mapsto N$ est un \emph{plongement} si c'est un homomorphisme tel que pour tout symbole relationnel $r \in \mathcal{R}_{\mathcal{L},p}$ et tout $\bar{b} \in M^p$, on aie $\bar{b} \in r^M$ ssi $h\bar{b} \in r^N$. Dans les réalisations égalitaires, c'est forcément une injection.

Une formule est \emph{ouverte} si elle n'a pas de quantificateurs.

\begin{prop}
Si $h : M \mapsto N$ est un plongement alors :
\begin{enumerate}
\item Pour toute formule ouverte (sans quantificateur ???) à variables libres $V(t) \subset \{x_1...x_n\}$ et tout $\bar{a} \in M^n$ on a que $\bar{a} \in \varphi^M$ ssi $h\bar{a} \in \varphi^N$
\item Pour toute formule $\psi(x_1...x_n)$ du type $\exists_1$ et pour tout $\bar{a} \in M^n$ on a que $\bar{a} \in \psi^M$ implique que $h\bar{a} \in \psi^N$
\end{enumerate}
\end{prop}

Un plongement est dit \emph{élémentaire} si pour toute formule $\varphi$ on a $\bar{a} \in \varphi^M$ ssi $h \bar{a} \in \varphi^N$.
Un plongement est un \emph{1-plongement} ou un plongement \emph{1-élémentaire} si pour toute formule $\varphi$ de type $\exists_1$ on a $\bar{a} \in \varphi^M$ ssi $h \bar{a} \in \varphi^N$.
Un plongement est un \emph{2-plongement} ou un plongement \emph{2-élémentaire} si pour toute formule $\varphi$ de type $\exists_2$ on a $\bar{a} \in \varphi^M$ ssi $h \bar{a} \in \varphi^N$.

Pour certaines théories, ces intermédiaires n'existent pas, et même parfois tout plongement est élémentaire.

\begin{thrm}[Critère de Tarski-Vaught]
Soit $h : M \mapsto N$ un plongement. Si pour toute formule $\varphi=\exists x_{n+1} \psi(x_1...x_{n+1})$ et tout $\bar{a} \in M^n$ tel que $h \bar{a} \in \varphi^N$ il existe $b \in M$ tel que $(h(\bar{a}),h(b)) \in \psi^N$ alors $h$ est élémentaire.
\end{thrm}

\begin{cor}
Soit $g : M \mapsto M$ un plongement surjectif. Alors g est un plongement élémentaire.
\end{cor}

Soit $M$ un univers d'une $\mathcal{L}$-structure $\mathcal{M}$. Soit $A$ une partie de $M$. On ajoute à $\mathcal{L}$ une constante nouvelle par élément de $A$, et on obtient $\mathcal{L}_A$. $\mathcal{M}$ est trivialement une $\mathcal{L}_A$-structure avec une interprétation canonique.

On a $\mathcal{B}_\mathcal{L} \subset \mathcal{B}_{\mathcal{L}_A}$ et en particulier $\mathcal{B}_\mathcal{L}(n) \subset \mathcal{B}_{\mathcal{L}_A(n)}$

Dualement, on a $S_\mathcal{L} \leftarrow S_{\mathcal{L}_A}$ et $S_\mathcal{L}(n) \leftarrow S_{\mathcal{L}_A}(n)$

On note $Th_{\mathcal{L}_A}(\mathcal{M})$ (ou plus simplement $Th_{A}(\mathcal{M})$) les énoncés de $\mathcal{L}_A$ vrais dans $\mathcal{M}$. C'est une théorie maximale consistance dans $\mathcal{L}_A$. Elle définit un filtre maximal sur $\mathcal{B}_{\mathcal{L}_A}(0)$ et un point de l'espace dual $S_{\mathcal{L}_A}(0)$.

$Th_M(\mathcal{M})$ est appelé \emph{diagramme élémentaire} de $\mathcal{M}$.

Si on ne retient que les formules ouvertes, on obtient le \emph{diagramme} de $\mathcal{M}$.

Se donner une $\mathcal{L}_M$-structure $\mathcal{N})$ qui est un modèle de $Diag(\mathcal{M})$ revient à se donner un plongement de $\mathcal{M}$ dans $\mathcal{N}$.
Se donner une $\mathcal{L}_M$-structure $\mathcal{N})$ qui est un modèle de $Th_M(\mathcal{M})$ revient à se donner un plongement élémentaire de $\mathcal{M}$ dans $\mathcal{N}$.

Deux $\mathcal{L}$-structures $\mathcal{M}_1$ et $\mathcal{M}_2$ sont \emph{équivalentes} si elles satisfont aux mêmes énoncés de $\mathcal{L}$, c'est-à-dire si $Th_\mathcal{L}(\mathcal{M}_1)=Th_\mathcal{L}(\mathcal{M}_2)$ (ceci n'implique donc pas nécessairement l'existence d'un morphisme)

\begin{prop}
Si deux $\mathcal{L}$-structures sont élémentairement équivalentees (on note $\mathcal{M}_1 \equiv_\mathcal{L} (\mathcal{M}_2)$) alors elles se plongent élémentairement dans une troisième $\mathcal{L}$-structure.
\end{prop}

Un $n$-type $p$ est \emph{isolé} dans $\mathcal{M}$ si il existe $\varphi$ tel que pour tout $\psi \in p$ on aie $Th_M {\mathcal{M}} \vdash \varphi \rightarrow \psi$
Les $n$-types satisfaits dans $Th_M {\mathcal{M}}$ sont exactement les $n$-types isolés dans $\mathcal{M}$ (ce n'est plus vrai dans $\mathcal{L}_A$).

\section{Automorphismes, poids, types et éléments}

On appelle \emph{automorphisme} un plongement surjectif d'un ensemble dans lui-même. Un automorphisme de $\mathcal{L}$-structure est toujours élémentaire. Les automorphismes d'un ensemble dans lui-même forment un sous-groupe du groupe $Sym M$ des fonctions de cet ensemble dans lui-même qui opère sur $M^n$

On définit le \emph{stabilisateur} de $A \subset X$ d'un sous-groupe opérant sur $X$ comme étant l'ensemble des éléments du sous-groupe tel que leur restriction à $A$ forme un automorphisme.On le note $G_{\{A\}}$.

On définit le \emph{fixateur} de $A \subset X$ d'un sous-groupe opérant sur $X$ comme étant l'ensemble des éléments du sous-groupe tel que leur restriction à $A$ est l'identité. On le note $G_{(A)}$.

Si $A = \{a\}$ alors $ G_{\{A\}} = G_{(A)} = G_a$.

On peut définir une topologie sur $Sym M$. Pour un groupe topologique, la topologie est totalement déterminée par les voisinages ouverts du neutre. Les voisinages ouverts de $Id_M$ sont les $G_{\bar{a}}$ pour $\bar{a} \in M^n$. Pour $g \in G$ quelconques, ses voisinages ouverts seront les classes latérales $g G_{\bar{a}}$. Notons que $h \in gG_{\bar{a}} \Leftrightarrow h(\bar{a}) = g(\bar{a})$.

On observe que $Aut(M)$ est un sous-groupe fermé de $Sym(M)$.

Un élément $b \in M$ est dit \emph{$Aut_{A}(\mathcal{M})$-algébrique} si son orbite est finie pour le stabilisateur $Aut_{A}(\mathcal{M})$.
Un élément $b \in M$ est dit \emph{$Aut_{A}(\mathcal{M})$-définissable} si son orbite est un singleton pour le stabilisateur $Aut_{A}(\mathcal{M})$.

On dit que $b \in M$ est \emph{$\mathcal{L}_A$-algébrique} si il existe une formule $\varphi(x,\bar{a}) \in \mathcal{L}_A$ telle que $\mathcal{M} \models \varphi(b,\bar{a})$ et $[\varphi(x,\bar{a})]^M$ est fini.

Si $b$ est $\mathcal{L}_A$-algébrique alors b est $\mathcal{M})$-algébrique.

On appelle \emph{clôture algébrique de $A$} l'ensemble des $b \in M$ tel que b est $\mathcal{L}_A$-algébrique. On le note $aclA$. Ses propriétés sont les suivantes :
\begin{enumerate}
\item $A \subset aclA$
\item $A \subset B \Rightarrow aclA \subset aclB$
\item $acl(aclA)=aclA$
\item $b \in aclA$ ssi il existe $A_0$ finie, $A_0 \subset A$ et $b \in aclA_0$.
\end{enumerate}

Un type complet $p \in S_{Th_A(\mathcal{M})}$ est dit \emph{algébrique} si dans tout modèle de $Th_A(\mathcal{M})$ le type n'admet qu'un nombre fini de réalisations.

Si $b \in M$ est $\mathcal{L}_A$-algébrique alors $tp(b|A)$ est algébrique.

\begin{prop}
Un type algébrique de $Th_A(\mathcal{M})$ est toujours un type isolé dans $S_{Th_A(\mathcal{M})}$.
\end{prop}


\chapter{Elimination des quantificateurs}
\section{Point de vue syntaxique}
On dit qu'une théorie $T$ dans un langage $\mathcal{L}$ admet l'\emph{élimination des quantificateurs} (EQ) si pour toute formule $\phi(x_1...x_n)$ on peut trouver une formule ouverte $\psi(x_1...x_n)$ telle que $T \vdash (\forall x_1...x_n)(\phi(x_1...x_n) \leftrightarrow \psi(x_1...x_n))$.

\begin{lem}
Pour que $T$ admette EQ il suffit de trouver une formule équivalente modulo $T$ à chaque formule \emph{primitive}, c'est-à-dire à chaque formule de type $\exists y (\bigwedge_{i \in I} a(y,\bar{x}))$ avec a atomique ou négation d'atomique.
\end{lem}

\begin{lem}
Toute formule ouverte est équivalente à une formule $\bigvee_{i \in I}(\bigwedge_{j \in J_I} \theta_{ij})$ où $\theta_{ij}$ sont atomiques ou négations d'atomiques.
\end{lem}

Exemple : Théorie de l'ordre total sans premier ni dernier élément :
\begin{itemize}
\item Langage : 2 symboles de relation binaires : $=$ et $<$, 2 symboles de relation 0-aire : $\bot$ et $\top$.
\item Axiomes du CP et Eg
\item $(\forall x) \neg (x < x)$
\item $(\forall x y z) (x < y \wedge y < z \rightarrow x < z)$
\item $(\forall xy) (x<y \vee x=y \vee y<x)$
\item $(\forall xy) (x<y \rightarrow (\exists z)(x<z \wedge z<y))$
\item $(\forall x) (\exists y) (y<x)$
\item $(\forall x) (\exists y) (x<y)$
\end{itemize}



\section{Point de vue sémantique}
Si $h : \mathcal{M} \mapsto \mathcal{N}$ est l'inclusion d'une sous-structure et est 1-élémentaire, on dira que $\mathcal{M}$ est une 1-sous-structure de $\mathcal{N}$, ou que $\mathcal{M}$ est existentiellement close dans $\mathcal{N}$. On écrit $\mathcal{M}\prec_1 \mathcal{N}$. On note qu'alors ces deux modèles satisfont les même énoncés existentiels de $\mathcal{L}_M$.

Lorsque tous les énoncés de type $\exists_1$ de $\mathcal{L}$ vrais dans $\mathcal{N}$ sont vrais dans $\mathcal{M}$, on note $\mathcal{N} \Rrightarrow_1 \mathcal{M}$.

\begin{prop}
Si $\mathcal{N} \Rrightarrow_1 \mathcal{M}$ alors il existe un plongement élémentaire $g : \mathcal{M} \rightarrow \mathcal{M}^\prime$ et un plongement simple $h : \mathcal{N} \mapsto \mathcal{M}^\prime$.
\end{prop}

\begin{cor}
Si on a un plongement 1-élémentaire $g_1 :\mathcal{M} \mapsto \mathcal{N}$, il existe un plongement élémentaire $g : \mathcal{M} \rightarrow \mathcal{M}^\prime$ et un plongement $h : \mathcal{N} \mapsto \mathcal{M}^\prime$ tel que $h \circ g_1 = g$
\end{cor}

%\begin{cor}
%Si on a $\mathcal{M}$ avec $\bar{a} \subset \mathcal{O}_{\mathcal{L},0}$, $\mathcal{N}$ avec $\bar{b} \subset \mathcal{O}_{\mathcal{L},0}$ alors il %existe $\mathcal{M}^\prime$ avec $\bar{d} \subset \mathcal{O}_{\mathcal{L},0}$ tel que $(\mathcal{M},\bar{a})$

Pour une théorie $T$ donnée, nous noterons $T_\forall$ l'ensemble des énoncés $\forall_1$ de $\mathcal{L}$ démontrables dans la théorie $T$. Nous noterons $T_{\forall_2}$ l'ensemble des énoncés $\forall_2$ de $\mathcal{L}$ démontrables dans la théorie $T$.


\begin{prop}
Pour une $\mathcal{L}$-structure $\mathcal{M}$ donnée, $\mathcal{M} \models T_\forall$ ssi $\mathcal{M}$ peut se plonger dans un modèle de $T$.
\end{prop}

Deux théories $T_1$ et $T_2$ sont appelée \emph{modèles-compagnes} si $T_{\forall_1} =T_{\forall_2}$. Tout modèle de l'une peut alors se plonger dans un modèle de l'autre.

\begin{prop}
Pour une théorie $T$ les conditions suivantes sont équivalentes :
\begin{itemize}
\item Tout plongement entre modèles de $T$ est 1-élémentaire.
\item Toute formule $\exists_1$ est équivalente modulo $T$ à une formule $\forall_1$.
\end{itemize}
\end{prop}

\begin{cor}[Caractérisation des théories modèles-complètes]
Pour une théorie $T$ les conditions suivantes sont équivalentes :
\begin{enumerate}
\item Pour tout modèle $\mathcal{M}$ de $T$, $T \cup Diag(\mathcal{M}) \vdash Th_{\mathcal{L}_M} (\mathcal{M})$ (c'est-à-dire que $T$ est une théorie complète de $\mathcal{M}$).
\item Tout plongement entre modèles de $T$ est élémentaire.
\item Tout plongement entre modèles de $T$ est 1-élémentaire.
\item Toute formule $\exists_1$ est équivalente modulo $T$ à une formule $\forall_1$.
\item Toute formule est équivalente modulo $T$ à une formule $\forall_1$.
\end{enumerate}
\end{cor}

Nous dirons que $T_{\forall}$ \emph{admet l'amalagamation faible} si lorsqu'un modèle $\mathcal{A}$ de $T_{\forall}$ se plonge (s'injecte ???) dans deux autres modèles $\mathcal{A}_1$ et $\mathcal{A}_2$ de $T_{\forall}$ alors il existe un quatrième modèle de $T_{\forall}$ dans lequel se plonge les trois autres de telle manière que tous les diagrammes commutent.

\begin{thrm}
Pour une théorie $T$, les conditions suivantes sont équivalentes :
\begin{enumerate}
\item $T$ admet EQ
\item Si une structure $\mathcal{A}$ d'univers $A$, sous-structure de $\mathcal{M}$ modèle de $T$, se plonge dans une structure $\mathcal{N}$ modèle de $T$, on a $\mathcal{N} \Rrightarrow_1 \mathcal{M}$ dans $\mathcal{L}_A$.
\item Si une structure $\mathcal{A}$ d'univers $A$, sous-structure de $\mathcal{M}$ modèle de $T$, se plonge dans une structure $\mathcal{N}$ modèle de $T$, il existe $\mathcal{M}_1$ tel que $\mathcal{M}$ se plonge élémentairement dans $\mathcal{M}_1$, $\mathcal{N}$ se plonge dans $\mathcal{M}_1$ et ces quatres plongements commutent.
\item $T$ est modèle-complet et $T_{\forall}$ admet l'amalgamation faible
\item Pour tout modèle $\mathcal{M}$ de $T$ et toute sous-structure $\mathcal{A}$ de $\mathcal{M}$ on a que $T \cup Diag(\mathcal{A}) \vdash Th_{\mathcal{L}_A} (\mathcal{M})$, c'est à dire que $T$ est une sous-structure complète.
\end{enumerate}
\end{thrm}
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 8:37

\chapter{Constructions importantes}
\section{Limites inductives filtrantes}
On appelle \emph{ensemble ordonné filtrant} un ensemble ordonné non vide tel que toute famille finie a un majorant commun.

Soit $\mathcal{L}$ un langage du 1er ordre fixé. Soit $I$ un ensemble ordonné filtrant. Soit $(\mathcal{A}_i)_{i \in I}$ une famille de $\mathcal{L}$-structures avec pour chaque couple $i \leq i^\prime$ un homéomorphisme $h_{ii^\prime} : A_i \mapsto A_{i^\prime}$ tel que :
\begin{itemize}
\item $h_{ii} = id_{A_i}(\mathcal{L}_i)$
\item $i \leq i^\prime \leq i^{\prime \prime} \Rightarrow h_{ii^{\prime\prime}} = h_{i^\prime i^{\prime\prime}} \circ h_{i i^\prime}$
\end{itemize}

On a ainsi définit un système inductif filtrant de $\mathcal{L}$-structures.

On peut maintenant définir une nouvelle $\mathcal{L}$-structure $\mathcal{A}$ :

\begin{itemize}
\item D'univers $A = \frac{\coprod_{i \in I}}{\sim}$, avec $a \in A_i$ équivalent à $b \in A_j$ si il existe $k$ majorant $i$ et $j$ tel que $h_{ik}(a) = h_{jk}(b)$. On notera $h_i : A_i \mapsto A : a \mapsto [a]$ l'application canonique.
\item Soient $a_1 \in A_{i_1}$, ..., $a_n \in A_{i_n}$. On doit définir $f^A([a_1],...,[a_n])$. On prend $i$ majorant commun de tous les $i_1...i_n$ et on pose $f^A([a_1],...,[a_n]) = f^{A_i}(h_{i_1i}(a_1),...,h_{i_ni}(a_n))$. On peut montrer que cette valeur est indépendante du choix de $i$.
\item $([a_1],...,[a_n]) \in r^A$ si il existe $i$ majorant commun tel que $(h_{i_1i}(a_1),...,h_{i_ni}(a_n)) \in r^{A_i}$.
\end{itemize}

\begin{thrm}
Dans un système inductif filtrant de $\mathcal{L}$-structures, si les $h_{ij}$ sont des homéomorphismes/plongements/plongements élémentaires, alors les $h_i$ le sont aussi.
\end{thrm}

Dans un système inductif filtrant de $\mathcal{L}$-structures, si l'ensemble ordonné filtrant est $\mathbb{N}$ et que les $h_{ij}$ sont des plongementsou des plongements élémentaire, on parle alors de \emph{chaîne} ou de \emph{chaîne élémentaire} de $\mathcal{L}$-structures. $\mathcal{A}$ esr alors appelé $union$ de la chaîne.

\begin{thrm}
Tous les maillons d'une chaîne (resp. élémentaire) se plonge (resp. élémentairement) dans l'union.
\end{thrm}

\begin{prop}
Si $T$ est modèle-complète alors l'union d'une chaîne de modèles de $T$ est modèle de $T$.
\end{prop}

\begin{prop}
Si $T$ est équivalente à $T_{\forall_2}$ (c'est-à-dire que $T$ est axiomatisable par des théorèmes $\forall_2$) alors l'union d'une chaîne de modèles de $T$ est un modèle de $T$.
\end{prop}

\begin{lem}
Si $\mathcal{N} \Rrightarrow_2 \mathcal{M}$ alors il existe un plongement élémentaire $g : \mathcal{M} \mapsto \mathcal{M}_1$ et un 1-plongement $\mathcal{N} \mapsto \mathcal{M}_1$.
\end{lem}

\begin{cor}
Si on a un 2-plongement élémentaire $h_2 : \mathcal{M} \mapsto \mathcal{N}$ alors il existe un plongement élémentaire $\mathcal{M} \mapsto \mathcal{M}_1$ et un 1-plongement $h_1 : \mathcal{N} \mapsto \mathcal{M}_1$ tel que $g = h_1 \circ h_2$.
\end{cor}

\begin{prop}
Une $\mathcal{L}$-structure $\mathcal{A}$ admet un 1-plongement dans un modèle de $T$ ssi $\mathcal{A} \models T_{\forall_2}$.
\end{prop}

\begin{thrm}
Si toute union d'une chaîne de modèles de $T$ est modèle de $T$ alors T est équivalente à $T_{\forall_2}$.
\end{thrm}

\section{Ultraproduits}

On appelle \emph{ultrafiltre} un filtre maximal. Soit $I$ un ensemble quelconque non vide. Soit $(\mathcal{A}_i)_{i \in I}$ une famille de $\mathcal{L}$-structures. Soit U un ultrafiltre sur $\mathcal{P}(I)$. On définit une nouvelle $\mathcal{L}$-structure que nous notons $\frac{\prod{A_i}}{\mathcal{U}}$ :
\begin{itemize}
\item Univers : $\frac{\prod{A_i}}{\sim}$. Deux éléments $(a_i)_{i \in I}$ et $(b_i)_{i \in I}$ seront équivalent si l'ensemble des $i$ pour lesquels $a_i = b_i$ appartient à l'ultrafiltre.
\item $f^{\mathcal{U}}=f^{\frac{\prod{A_i}}{\mathcal{U}}}((a_i)^1_{i \in I},...,(a_i)^n_{i \in I}) = (f^{\mathcal{A}_i}(a_i^1,...,a_i^n))_{i \in I}$
\item $((a_i)^1_{i \in I},...,(a_i)^n_{i \in I}) \in r^\mathcal{U}$ si l'ensemble des $i$ où cette relation est satisfaite appartient à l'ultrafiltre.
\end{itemize}

\begin{thrm}[Los, 1955]
Pour toute formule $\varphi(x_1...x_n)$, $\frac{\prod{A_i}}{\mathcal{U}} \models \varphi(x_1...x_n)$ ssi l'ensemble des $i$ pour lesquels $\mathcal{A}_i$ est un modèle de $ \varphi(x_1...x_n)$ appartient à l'ultrafiltre.
\end{thrm}

\begin{thrm}[Théorème de compacité sémantique]
Une théorie $T$ admet un modèle ssi toute partie finie de $T$ admet un modèle.
\end{thrm}

Une classe de $\mathcal{L}$-structures est dite \emph{axiomatisable} ssi il existe une théorie $T$ telle que une $\mathcal{L}$ structure appartient à la classe si et seulement si elle modélise $T$.

\begin{prop}[Critère d'axiomatisabilité]
Une classe est axiomatisable si et seulement si elle est fermée par équivalence élémentaire et par ultra-produits.
\end{prop}

\begin{prop}
Une classe est finiment axiomatisable si et seulement si elle et sa classe complémentaire sont fermées par équivalence élémentaire et par ultra-produits.
\end{prop}

\begin{prop}
Si une théorie admet des modèles finis arbitrairement grands, elle doit admettre un modèle infini.
\end{prop}

\begin{cor}
La classe des ensembles finis n'est pas axiomatisable. Par contre on peut aximoatiser la classe des ensembles infinis.
\end{cor}


\section{Modèles d'Ethaemfeults-Mostowski}
\begin{thrm}[Théorème de Ramsey]
Soit $I$ un ensemble infini et $n \geq 2$. Si l'ensemble des parties de $I$ à $n$ éléments est découpé en deux morceaux disjoints, alors il existe une partie infinie $J \subset I$ telle que l'ensemble des parties à $n$ éléments de $J$ est entièrement comprise dans un des deux morceaux.
\end{thrm}

\begin{cor}
Soit $I$ un ensemble infini et $n \geq 2$. Si l'esnemble des parties de $I$ à $n$ éléments est découpé en un nombre fini de morceaux disjoints, alors il existe une partie infinie $J \subset I$ telle que l'ensemble des parties à $n$ éléments de $J$ est entièrement comprise dans un des morceaux.
\end{cor}

Soit $\mathcal{A}$ $\mathcal{L}$-structure, soit $X$ une partie de l'univers $A$ munie d'un ordre total. On dit que $X$ est \emph{indiscernable dans l'ordre} si pour tout $n$ et toutes suites croissantes $a_1<...<a_n$ et $b_1<...<b_n$, pour tout $\varphi(x_1,...,x_n)$ dans $\mathcal{L}$ on a $\mathcal{A} \models \varphi(a_1...a_n)$ ssi $\mathcal{A} \models \varphi(b_1...b_n)$. Autrement dit $tp_{\mathcal{A}}(a_1...a_n) = tp_{\mathcal{A}}(b_1...b_n)$.

\begin{thrm}
Soit $T$ une théorie ayant un modèle infini. Pour toute chaîne $C$ donnée, il existe un modèle de $T$ tel que $C$ soit comprise dans l'univers et soit undiscernable dans l'ordre dans le modèle.
\end{thrm}

$T$ est \emph{(à fonctions) de Skolem} si pour toute formule $\varphi$ à $n+1$ variables libres il existe un symbole fonctionnel n-aire $f_\varphi$ tel que $T \vdash (\forall x_1...x_n)((\exists x_{n+1} \varphi(x_1...x_{n+1}) \rightarrow \varphi(x_1...x_n,f_\varphi(x_1...x_n)))$.

Si une théorie $T$ donnée n'est pas riche, il est possible, en lui ajoutant une suite de constantes et d'axiomes, de définir une théorie riche $T^R$. De même si une théorie n'est pas de Skolem, on peut la transformer en théorie de Skolem $T^{\mathcal{S}}$ en ajoutant une suite de symboles fonctionnels et d'axiomes.


Dans une théorie de Skolem, toute formule est équivalente à une formule ouverte. Une théorie de Skolem admet donc l'élimination des quantificateurs. ??? Elle est sous-structure complète.

A partir d'une théorie $T$, on peut donc construire la \emph{skolemisée} $T^\mathcal{S}$ de $T$. Soit $\mathcal{M}$ un modèle de $T$ (et donc de sa skolemisée) et $X$ une partie de $M$. On appelle \emph{enveloppe de Skolem de $X$} la sous-$\mathcal{L}^\mathcal{S}$-structure de $\mathcal{M}$ engendrée par $X$, et on la note $\xi(X)$. C'est une sous-$\mathcal{L}$-structure élémentaire de $\mathcal{M}$. ???

\begin{thrm}[Löwenheim : Skolem descendant]
Soit $T$ une théorie avec un modèle $\mathcal{M}$ fini. Soit $A \subset M$. Il existe alors $\mathcal{N}$ une sous-structure élémentaire de $\mathcal{M}$ telle que $A \subset N$ et $card(N) \leq card(A) + card(\mathcal{K})$. Il suffit de poser $\mathcal{N} = \xi(A)$.
\end{thrm}

\begin{thrm}[(Morley)]
Soit $T$ théorie complète dans un langage dénombrable admettant des modèles infinis. Pour tout cardinal infini on peut trouver un modèle de $T$ ayant cette cardinalité tel que pour toute partie $A$ de l'univers, le modèle réalise au plus $(card(A) + \aleph_0)$ types de $Th_A(\mathcal{M})$.
\end{thrm}
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
damien
Pirate d'Euler
avatar

Nombre de messages : 100
Age : 33
Localisation : NAMUR
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Sam 16 Juin - 10:39

T'es complètement fous Mich'!!!

C'est bien gentil en tout cas! Ca s'arrete pil la ou j'ai finis de lire...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Lun 18 Juin - 7:51

\chapter{Petits et gros modèles}

Soit $T$ une théorie admettant des modèles infinis dans un langage dénombrable. Pour chaque cardinal infini, $T$ admet modèle ayant cette cardinalité. Dans ce chapitre, on compare des modèles de même cardinal infini et voir qu'ils se différencient d'après le nombre de types réalisés ou omis.

\section{Types réalisés et omis}

\begin{prop}
Soit $T$ une théorie consistante dans un langage dénombrable. Si $p \in S_T(n)$ alors $T$ admet un modèle réalisant le type $p$.
\end{prop}

\begin{prop}
Si $T$ est complète (donc $B_T(0) = \{0,1\}$ et $S_T(0) = \{x\}$) et si $\mathcal{M}$ est un modèle de $T$ alors la collection des $n$-types réalisés dans $\mathcal{M}$ est une partie dense de $S_T(n)$.
\end{prop}

Cette proposition implique que si $p$ est un type isolé de $S_T(n)$ alors il est satisfait dans tout modèle de la théorie $T$ complète.

\begin{thrm}
Soit $T$ une théorie dénombrable complète avec modèles infinis. Si $p \in S_T(1)$ alors il existe un modèle de $T$ où $p$ est omis.
\end{thrm}

En fait on peut pour une théorie $T$ donnée omettre n'importe quel $n$-type non isolé. De plus, si on se donne pour tout $n$ un fermé $F_n$ de $S_T(n)$ à intérieur vide,on peut toujours trouver un modèle de $T$ dans lequel tous les $n$-types d'un $F_n$ sont omis.

\section{Modèles atomiques et premiers}

Un modèle $\mathcal{M}$ d'une théorie complète $T$ dans un langage dénombrable est dit \emph{premier} si il se plonge élémentairement dans tout modèle de $T$. Il est dit \emph{atomique} si il ne réalise que des types isolés.

\begin{thrm}
Pour $T$ théorie dénombrable complète avec modèles infinis, un modèle dénombrable est premier ssi il est atomique.
\end{thrm}

\begin{thrm}
Deux modèles dénombrables premiers sont nécessairement isomorphes.
\end{thrm}

\begin{thrm}
$T$ admet un modèle atomique dénombrable ssi $T$ est atomique (ce qui revient à demander que les types isolés de $S_T(n)$ forment une parite dense pour tout $n$.
\end{thrm}

\section{Modèles universels et saturés}

Un moodèle dénombrable de $T$ est dit \emph{$\omega$-universel} si tout les modèles dénombrables de $T$ se plongent dedant.
Un moodèle dénombrable de $T$ est dit \emph{$\omega$-saturé} si pour toute partie finie $A$ de l'univers, tous les $1$-types de $Th_A(\mathcal{M})$ sont réalisés dans $\mathcal{M}$. Ceci implique que tous les $n$-types de $Th_A(\mathcal{M})$ sont également réalisés.

\begin{prop}
Un modèle dénombrable $\omega$-saturé est un modèle $\omega$-universel.
\end{prop}

\begin{thrm}
Deux modèles dénombrables $\omega$-saturés sont nécessairement isomorphes.
\end{thrm}

Une théorie $T$ est dite \emph{petite} si $S_T(n)$ est dénombrable pour tout $n$.

\begin{thrm}
$T$ admet un modèle dénombrable $\omega$-saturé ssi $T$ est petite.
\end{thrm}

\section{Modèles homogènes}

Soient $A$ une partie de l'univers $M$ et un univers $N$ d'une même $\mathcal{L}$-structure. Une application \emph{partielle élémentaire} $f : A \mapsto N$ est une application telle que si un formule à $n$ variables libres est réalisée dans $\mathcal{M}$ pour un $n$-uple de $A$, alors cette formule sera réalisée dans $\mathcal{N}$ pour l'image de ce $n$-uple. Cela revient à dire que l'application image conserve les $n$-types.

Une application élémentaire partielle sera dite \emph{immédiatement extensible} si pour tout $a^\prime \in (M \backslash A)$ il existe une application élémentaire partielle prolongeant $f$ à $A \cup \{a^\prime\}$.

Un modèle d'univers $M$ sera dit \emph{$\omega$-homogène} si toute application élémentaire partielle d'une partie finie de $M$ vers $M$ est immédiatement extensible. Notons que l'inverse d'une telle application est également une application élémentaire partielle d'une partie finie de $M$ vers $M$. ???? C'est forcément inbversible ????

\begin{prop}
Toute application élémentaire partielle d'une partie finie de $M$ vers $M$ peut se prolonger en un automorphisme de $\mathcal{M}$.
\end{prop}


\begin{prop}
Pour une théorie dénombrable complète avec modèles infinis, un modèle dénombrable qui est soit soit $\omega$-saturé soit atomique est forcément $\omega$-homogène.
\end{prop}

\begin{prop}
Deux modèles dénombrables $\omega$-homogènes réalisant la même collection de types sont isomorphes.
\end{prop}

\begin{prop}
Tout modèle dénombrable d'une théorie dénombrable complète admettant des modèles infinis peut être plongé élémentairement dans un modèle dénombrable $\omega$-homogène.
\end{prop}

\section{Théories $\aleph_0$-catégoriques}

Une théorie est dite \emph{$\aleph_0$-catégorique} si tous ses modèles dénombrables sont isomorphes.

\begin{thrm}[Ryll-Nardjeski]
Pour une théorie $T$ donnée, les caractéristiques suivantes sont équivalentes :
\begin{enumerate}
\item $T$ est $\aleph_0$-catégorique.
\item $T$ a un modèle axiomatique $\omega$-saturé.
\item $T$ n'a que des types isolés.
\item Tous les modèles dénombrables de $T$ sont $\omega$-saturés.
\item Pour tout $n$, $S_T(n)$ est fini.
\item Pour tout $n$, $B_T(n)$ est fini.
\end{enumerate}
\end{thrm}

\begin{prop}[Vaught]
Il n'existe pas de théorie n'ayant que deux modèles dénombrables non isomorphes.
\end{prop}
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Lun 18 Juin - 9:37

\chapter{Théories $\omega$-stables}

Une théorie $T$ dénombrable complète avec modèles infinis est dite \emph{$\omega$-stable} si pour tout partie au plus dénombrable $A$ d'univers de tout modèle $\mathcal{M}$ de $T$, l'espace des $n$-types de $Th_A(\mathcal{M})$ est de cardinal au plus dénombrable pour chaque $n$. On remarque d'une théorie $\omega$-stable est forcément petite.


\section{Formules fortements minimales - Bases, dimensions}
\begin{itemize}
\item Soit $\mathcal{M}$ un modèle de $T$, soit $\phi(x) \in \mathcal{L}_M$. La partie $\phi^M$ est dite \emph{minimale} si elle est au moins dénombrable et que pour toute formule $\psi(x)$, soit $[\phi \wedge \psi]^M$ est fini, soit $[\phi \wedge \neg \psi]^M$ est fini.
\item Une structure est dite \emph{minimale} si son univers est une partie minimale.
\item Une formule est dite \emph{minimale} pour une structure donnée si elle définit une partie minimale de cette structure.
\item Une formule est dite \emph{fortement minimale} pour une structure donnée si elle définit une partie minimale de cette structure et de toute extension élémentaire de cette structure.
\item Une formule est dite \emph{fortement minimale} pour une théorie donnée si elle définit une partie minimale pour tout modèle de cette théorie.
\end{itemize}

\begin{thrm}
Si $T$ est $\omega$-stable, alors tout modèle de $T$ dénombrable et $\omega$-saturé admet une formule fortement minimale.
\end{thrm}

Une formule algébrique est une formule satisfaite par un nombre fini d'éléments. Un élément $a$ d'un univers est algébrique si ... ???

\begin{prop}[Propriété d'échange]
Soit une théorie $\omega$-stable, un modèle de cette théorie et une formule minimale pour ce modèle. Soient $a$ et $b$ deux éléments de la partie minimale définie par $\phi$. Si $a$ appartient à la clôture algébrique de $\{b\}$ et si $a$ n'est pas algébrique alors $b$ appartient à la clôture algébrique de $a$.
\end{prop}

\begin{prop}[Propriété d'échange]
Soit une théorie $\omega$-stable, un modèle de cette théorie et une formule minimale pour ce modèle. Soient $a$ et $b$ deux éléments de la partie minimale définie par $\phi$ et soit $A$ une partie de l'univers. Si $a$ appartient à la clôture algébrique de $A \cup \{b\}$ et si $a$ n'appartient pas à la clôture algébrique de $A$ alors $b$ appartient à la clôture algébrique de $A \cup \{a\}$.
\end{prop}

Une famille $(a_i)_{i \in I}$ dans $D$ est dite \emph{génératrice} si $D$ est la clôture algébrique de l'ensemble des $(a_i)_{i \in I}$. Une famille $(a_i)_{i \in I}$ dans $D$ est dite \emph{libre} si chacun des $a_i$ n'appartient pas à la clôture algébrique des l'ensemble des autres $a_i$. Une \emph{base} est une famille libre et génératrice.

\begin{prop}
Pour un ensemble $D$, si on a une partie libre $L$ et une partie génératrice $G$ alors il existe une base $B$ telle que $L \subset B \subset L \cup G$. De plus, si $G$ est fini, on peut trouver une base de cardinalité au plus égal à celle de $G$. Ceci implique alors que toutes les bases (finies) ont même cardinal.
\end{prop}

\begin{prop}
Une bijection entre deux bases d'une partie minimale est nécessairement partielle élémentaire.
\end{prop}


\begin{prop}
Soient $A$ et $B$ des parties d'univers de deux modèles de $T$. Si l'on a une bijection élémentaire $f : A \mapsto B$, elle peut être prolongée en une bijection élémentaire entre les clôtures algébriques.
\end{prop}


\section{Modèles relativement premiers}
Soit $T$ une théorie dénombrable complète avec modèles infinis. Soit $\mathcal{M}$ un modèle de $T$, soit $A$ une partie de l'univers $M$.

Le modèle est dit \emph{premier sur $A$} si pour tout modèle $\mathcal{N}$ de $T$ comprenant $A$ dans son univers il existe un plongement élémentaire de $M$ dans $N$ telle que sa restriction à $A$ soit l'identité.

Le modèle est dit \emph{atomique sur $A$} si les éléments de $M$ satisfont uniquement des types isolés de $Th_A(\mathcal{M})$

\begin{prop}
Soit $B$ une partie d'univers d'un modèle d'une théorie $\omega$-stable. Les types isolés de $S_B(n)$ forme une partie dense de $B$.
\end{prop}

\begin{thrm}
Pour toute partie $A$ d'univers d'un modèles $\mathcal{M}$ d'une théorie $T$ $\omega$-stable il existe une sous-structure élémentaire $\mathcal{N}$ de $\mathcal{M}$ contenant $A$ dans son univers et telle que $\mathcal{N}$ soit premier et atomique sur $A$.
\end{thrm}
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Lun 18 Juin - 10:38

\chapter{Théories $\aleph_1$-catégoriques}
\section{Paires de Vaught}
Soit $T$ théorie dénombrable complète avec modèles infinis. Une \emph{paire de Vaught} pour $T$ est un triplet constitué de 2 modèles $\mathcal{M}$ et $\mathcal{N}$ de $T$, tels que $\mathcal{N}$ soit une extension élémentaire propre de $\mathcal{M}$, et d'une formule $\theta$ non algébrique tel que $\theta^N = \theta ^M$.

\begin{thrm}
Si une théorie dénombrable complète admet une paire de Vaught, alors elle admet une paire de Vaught dénombrable. Si de plus elle est petite, alors on peut s'arranger pour que cette paire soit isomorphe.
\end{thrm}

\begin{prop}[Etirement d'une paire de Vaught]
Soit $T$ une théorie $\omega$-stable, soit $\mathcal{N} \prec \mathcal{M}$ une paire de Vaught avec $\mathcal{N}$ dénombrable. On peut alors trouver une extension élémentaire propre $\mathcal{M}^\prime$ de $\mathcal{M}$ telle que $\mathcal{N} \prec \mathcal{M}^\prime$ forme toujours une paire de Vaught.
\end{prop}

\section{Théorème de Morley}
\begin{thrm}
Si $T$ est dénombrable, complète et $K$-catégorique pour $K$ non dénombrable, alors $T$ est $\omega$-stable.
\end{thrm}

\begin{thrm}
Si $T$ est dénombrable, complète et $K$-catégorique pour $K$ non dénombrable, alors elle n'admet pas de paire de Vaught.
\end{thrm}

\begin{thrm}
Si $T$ est dénombrable, complète, $\omega$-stable et n'admet pas de paire de Vaught, il existe alors une formule fortement minimale dans le modèle premier.
\end{thrm}

%\begin{lem}
%Soit $T$ sans paire de Vaught. Pour toute formule $\varphi(x, \bar{y})$ il existe un naturel $n_\varphi$ tel que pour tout modèle de $T$ et tout $\bar{a}$ pris dans son univers, soit $card[\varphi(x,\bar{a})]^M \leq n_\varphi$, soit $card[\varphi(x,\bar{a})]^M$ est infini. ????????????
%\end{lem}

\begin{thrm}
Si $T$ est dénombrable, complète, $\omega$-stable et n'admet pas de paire de Vaught, alors si l'on a un modèle $\mathcal{M}$ de $T$ non dénombrable avec une une formule $\phi(x)$ fortement minimale, à paramètres dans une partie finie $A$ de $M$ alors $\mathcal{M}$ est premier et atomique sur $\phi^M \cup A$.
\end{thrm}

\begin{thrm}
Si $T$ est dénombrable, complète, $\omega$-stable et n'admet pas de paire de Vaught, alors si l'on a deux modèles de $T$ $\mathcal{M}_1$ et $\mathcal{M}_2$, non dénombrables et de même cardinal alors ces deux modèles sont nécessairement isomorphes.
\end{thrm}


\begin{thrm}[Morley]
Soit $T$ une théorie dénombrable. Si $T$ est $K$-catégorique pour un certain cardinal $K$ non dénombrable, alors $T$ est $K$-catégorique pour tout cardinal $K$ non dénombrable.
\end{thrm}

\end{document}
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
damien
Pirate d'Euler
avatar

Nombre de messages : 100
Age : 33
Localisation : NAMUR
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Lun 18 Juin - 11:43

Bravo!
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Laetitia
Magma


Nombre de messages : 15
Age : 33
Date d'inscription : 04/10/2006

MessageSujet: Re: Logique   Lun 18 Juin - 12:52

Hé bien merci Mich!
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Laetitia
Magma


Nombre de messages : 15
Age : 33
Date d'inscription : 04/10/2006

MessageSujet: Re: Logique   Mar 19 Juin - 14:06

quelqu' un peut me dire ce qu'est une classe fremée par équivalence et ultra produit? (proposition 4.11 dans le résumé de Mich)?Merci!
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Mietzsche
Anneau
avatar

Nombre de messages : 76
Date d'inscription : 03/10/2006

MessageSujet: Re: Logique   Mer 20 Juin - 2:37

Classe fermée par ultra-produit :

Si on a une famille indexée par I de L-structures appartenant à cette classe, que l'on a un ultra-filtre sur I, alors l'ultra-produit correspondant appartient à cette classe.

Classe fermée équivalence élémentaire :

Si une L-structure de la classe est élémentairement équivalente à une autre L-structure, alors cette dernière appartient aussi à cette classe.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Laetitia
Magma


Nombre de messages : 15
Age : 33
Date d'inscription : 04/10/2006

MessageSujet: Re: Logique   Mer 20 Juin - 10:04

MERCI
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Contenu sponsorisé




MessageSujet: Re: Logique   

Revenir en haut Aller en bas
 
Logique
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Questions de logique
» Bible et logique exégétique
» conne mais logique
» exercice de la logique
» exercice de logique pur

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Mathématique 22 UCL :: Entraide pour les cours :: MATH 2450 : Logique mathématique-
Sauter vers: