La propriété d'une classe de structures ou d'une propriété sémantique selon laquelle elle ne peut être captée par aucun ensemble unique d'axiomes effectif (par exemple récursivement énumérable) ou fini dans un langage formel donné ; aucun système axiomatique dans ce langage ne caractérise exactement la classe visée.

Principe

Lorsque la complexité ou l'inadéquation expressive entre la propriété et la logique choisie empêche une axiomatisation récursive ou finie, la classe est non axiomatisable dans cette logique ; changer de logique ou ajouter des ressources d'ordre supérieur peut modifier l'axiomatisabilité.

Démonstration

La classe de tous les graphes finis n'est pas axiomatisable par des phrases du premier ordre car la finitude n'est pas définissable en logique du premier ordre ; de même, l'ensemble des phrases arithmétiques vraies dans le modèle standard de l'arithmétique n'est pas récursivement énumérable, donc il n'est pas efficacement axiomatisable.

Mauvaise application

Confondre non axiomatisabilité et indécidabilité de phrases individuelles ; une théorie peut être non axiomatisable alors que certains problèmes de décision sur ses membres sont décidable, et réciproquement.

Conséquence

La non axiomatisabilité indique une limitation expressive réelle du formalisme choisi et motive soit des langages plus puissants (second ordre, infinitaires), soit des cadres sémantiques alternatifs pour capturer la classe visée.

Inversion

L'axiomatisabilité est l'opposé : il existe un ensemble fini ou effectif d'axiomes dont les modèles sont précisément la classe considérée, permettant à une théorie unique de capturer la propriété.

Limite

La notion dépend de la logique ambiante (premier ordre, second ordre, ordre supérieur), de l'exigence d'effectivité (calculabilité), et de l'acceptation ou non de schémas d'axiomes infinis plutôt que d'ensembles finis.

Tension sémantique

Une tension naît entre le souhait d'une axiomatisation compacte et effective et la nécessité d'une plus grande puissance expressive ; il existe des compromis entre décidabilité, complétude et ressources expressives.

Synthèse

La non axiomatisabilité signale les limites d'un langage logique choisi pour capturer une classe de structures ou une propriété sémantique ; elle révèle soit la complexité inhérente de la classe soit la nécessité d'élargir les ressources logiques.