Structure (logique mathématique)

Enlogique mathématique,plus précisément enthéorie des modèles,unestructureest unensemblemuni defonctionset derelationsdéfinies sur cet ensemble. Les structures usuelles de l'algèbresont des structures en ce sens. On utilise également le motmodèlecomme synonyme de structure (voirNote sur l'utilisation du mot modèle).

La sémantique de lalogique du premier ordrese définit dans une structure.

Définition

Formellement, unestructurepeut être définie comme un triplet${\mathcal {A}}=(A,\sigma,I)$représentant respectivement un ensemble non videAappelédomaine,unesignatureσ, et uneinterprétationIqui indique comment la signature doit être interprétée sur le domaine. On nomme σ-structure une structure de signature σ.

Domaine

L'ensembleAest ledomaineouensemble de basede la structure${\mathcal {A}}$.

Enthéorie des modèles,l'ensemble de base d'une structure est toujours non vide (sinon, certaines lois de la logique du premier ordre ne seraient pas préservées).

L'ensemble de base d'une structure${\mathcal {A}}$est souvent noté$|{\mathcal {A}}|$(ou dans la suite$\operatorname {dom} ({\mathcal {A}})$); il peut arriver qu'une structure et son ensemble de base soient notés de la même façon.

La signature

La signature d'une structure comporte un ensemble desymboles de fonctionset desymboles de relationsavec une fonction qui associe à chaque symbolesunentier naturel$n=\operatorname {ar} (s)$qui est appelé l'aritédes,puisqu'il est l'aritéde l'interprétation des(voir ci-dessous:L'interprétation).

La plupart du temps, l'égalité fait partie du langage par défaut, et n'apparaît pas dans la signature. L'interprétation de l'égalité est toujoursl'identité,quelle que soit la structure.

Les signatures enalgèbrene contiennent souvent que des symboles de fonctions. Enalgèbre universelleune signature ne contenant pas de symboles de relation est appelé une signature algébrique, et une structure ayant une telle signature est appelée algèbre.

L'interprétation

L'interprétationIde${\mathcal {A}}$associe une ou des fonctions et relations aux symboles de la signature. À chaque symbole de fonctionfd'ariténest associé une fonction$f^{\mathcal {A}}=I(f)$d'arité n dont l'ensemble de départ est$\operatorname {dom} ({\mathcal {A}})^{n}$et l'ensemble d'arrivée est$\operatorname {dom} ({\mathcal {A}})$.

À chaque symbole de relationRd'ariténest associée une relation d'arité n sur l'ensemble de base, soit$R^{\mathcal {A}}\subseteq A^{n}$.

Un symbole de fonctioncd'arité 0 est appelésymbole de constante,son interprétation$c^{\mathcal {A}}$peut être identifiée à un élément de l'ensemble de base.

S'il n'y a pas d'ambiguïté, on note parfois de la même façon un symbole et son interprétation; par exemple sifest un symbole de fonction d'arité 2 sur${\mathcal {A}}$,il arrive d'écrire$f:{\mathcal {A}}^{2}\rightarrow {\mathcal {A}}$plutôt que$f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\rightarrow |{\mathcal {A}}|$.

Exemples

Une signature usuelle σ_fpour uncorps commutatifcomporte deux symboles de fonctions d'arité 2, + et ×, un symbole de fonction d'arité 1 pour l'opposé,−,et deux symboles de constantes 0 et 1. Il est possible d'énoncer les axiomes de corps dans un langage du premier ordre sur cette signature.

Une structure pour cette signature comporte un ensemble d'élémentsAavec deux fonctions d'arité 2, une fonction d'arité 1, et deux éléments distinctifs; mais il n'y a pas de nécessité à ce qu'il satisfasse n'importe lequel des axiomes descorps commutatifs.Lesnombres rationnelsQ,lesnombres réelsRet lesnombres complexesC,comme n'importe quels autrescorps commutatifs,peuvent être vus comme une σ-structures de manière évidente:

${\mathcal {Q}}=(Q,\sigma _{f},I_{\mathcal {Q}})$

${\mathcal {R}}=(R,\sigma _{f},I_{\mathcal {R}})$

${\mathcal {C}}=(C,\sigma _{f},I_{\mathcal {C}})$

où

$I_{\mathcal {Q}}(+)\colon Q\times Q\to Q$est l'addition des nombres rationnels,

$I_{\mathcal {Q}}(\times )\colon Q\times Q\to Q$est la multiplication des nombres rationnels,

$I_{\mathcal {Q}}(-)\colon Q\to Q$est la fonction qui prend chaque nombre rationnelxet l'envoie sur -x,

$I_{\mathcal {Q}}(0)\in Q$est le nombre rationnel 0,

$I_{\mathcal {Q}}(1)\in Q$est le nombre rationnel 1;

et$I_{\mathcal {R}}$et$I_{\mathcal {C}}$sont définis de manière similaire.

Mais l'anneauZdesentiers relatifs,qui n'est pas uncorps commutatif,est aussi une σ_f-structure de la même manière. La définition de σ_f-structure ne nécessite pas que n'importe quel axiome descorps commutatifssoit valide dans une σ_f-structure.

Une signature pour lescorps ordonnésutilise un symbole de relation d'arité 2 tel que < ou ≤ (des structures ayant de telles signatures ne sont pas des algèbres au sens de l'algèbre universelle^{[réf.souhaitée]}).

Le langage de lathéorie des ensemblescomporte, en plus de l'égalité, un seul symbole, qui est un symbole de relation d'arité 2 noté ∈, pour l'appartenance. Une structure pour cette signature est donc un ensemble (les éléments) muni d'une relation d'arité 2 sur ces éléments, qui est l'interprétation du symbole ∈.

Note sur l'utilisation du mot modèle

Le termemodèle,enthéorie des modèles,est synonyme de « structure », mais tend à être utilisé dans différents contextes. Typiquement, on utilise le terme « modèle » quand on a une théorie à l'esprit, et que l'on considère seulement, parmi les${\mathcal {L}}$-structures, celles qui sont des modèles de cette théorie, c'est-à-dire qui satisfont toutes lesformuleset lesaxiomesde lathéorie.

On tend par contre à utiliser le mot « structure » quand ses propriétés sont moins connues ou moins spécifiées.

Notes et références

(en)Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé«Structure (mathematical logic)»(voir la liste des auteurs).