Structure (logique mathématique)

L'ensemble A est le domaine ou ensemble de base de la structure ${\displaystyle {\mathcal {A}}}$.

En thé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)[1].

L'ensemble de base d'une structure ${\displaystyle {\mathcal {A}}}$ est souvent noté ${\displaystyle |{\mathcal {A}}|}$ (ou dans la suite ${\displaystyle \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 d'une structure comporte un ensemble de symboles de fonctions et de symboles de relations avec une fonction qui associe à chaque symbole s un entier naturel ${\displaystyle n=\operatorname {ar} (s)}$ qui est appelé l'arité de s, puisqu'il est l'arité de l'interprétation de s (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 toujours l'identité, quelle que soit la structure.

Les signatures en algèbre ne contiennent souvent que des symboles de fonctions. En algèbre universelle une 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 I de ${\displaystyle {\mathcal {A}}}$ associe une ou des fonctions et relations aux symboles de la signature. À chaque symbole de fonction f d'arité n est associé une fonction ${\displaystyle f^{\mathcal {A}}=I(f)}$ d'arité n dont l'ensemble de départ est ${\displaystyle \operatorname {dom} ({\mathcal {A}})^{n}}$ et l'ensemble d'arrivée est ${\displaystyle \operatorname {dom} ({\mathcal {A}})}$.

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

Un symbole de fonction c d'arité 0 est appelé symbole de constante, son interprétation ${\displaystyle 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 si f est un symbole de fonction d'arité 2 sur ${\displaystyle {\mathcal {A}}}$, il arrive d'écrire ${\displaystyle f:{\mathcal {A}}^{2}\rightarrow {\mathcal {A}}}$ plutôt que ${\displaystyle f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\rightarrow |{\mathcal {A}}|}$.

Une signature usuelle σ_f pour un corps commutatif comporte 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éments A avec 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 des corps commutatifs. Les nombres rationnels Q, les nombres réels R et les nombres complexes C, comme n'importe quels autres corps commutatifs, peuvent être vus comme une σ-structures de manière évidente:

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

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

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

où

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

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

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

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

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

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

Mais l'anneau Z des entiers relatifs, qui n'est pas un corps 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 des corps commutatifs soit valide dans une σ_f-structure.

Une signature pour les corps ordonnés utilise 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).

Le langage de la théorie des ensembles comporte, 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 ∈.