Un principe semi-constructif qui affirme que pour un prédicat décidables P sur les entiers naturels, si il est impossible qu’aucun n ne vérifie P (¬¬∃n P(n)), alors il existe un n tel que P(n) ; en pratique, la double négation d’une existence se réduit à une existence quand P est décidale sur les naturels.

Principe

Élimination de la double négation restreinte aux existences arithmétiques décidables : lorsque chaque instance P(n) est décidable, la non-impossibilité de l’existence engendre un témoin effectif par un argument de recherche ou de réfutation finie de l’échec universel.

Démonstration

Pour un prédicat décidable P(n) et la vérité méta ¬¬∃n P(n), le principe de Markov permet d’affirmer ∃n P(n) ; du point de vue computationnel cela correspond à une recherche effective qui s’arrête dès qu’un n satisfaisant P est trouvé parce que pour chaque n on peut décider P(n).

Mauvaise application

Appliquer le principe de Markov à des prédicats non décidables, ou le considérer comme déductible dans tous les systèmes constructifs (il est indépendant de l’arithmétique intuitionniste) ; ou le confondre avec le tiers exclu ou l’élimination générale de la double négation.

Conséquence

Accepter le principe de Markov permet d’extraire des témoins à partir d’existences doublement niées quand les prédicats sont décidables, autorisant certaines procédures de recherche constructives et renforçant des interprétations calculables sans adopter la logique classique entière.

Inversion

Rejeter le principe de Markov préserve un comportement strictement constructif : ¬¬∃n P(n) n’implique pas nécessairement ∃n P(n) même si chaque P(n) est décidable, marquant la distinction entre savoir que l’échec universel est impossible et produire un témoin.

Limite

S’applique spécifiquement aux prédicats sur les naturels dont chaque instance est décidable ; il ne s’agit pas d’une élimination générale de la double négation et il ne vaut pas pour des formules arbitraires ni dans toute théorie constructive sans l’avoir été posée comme principe.

Tension sémantique

Tension avec le principe du tiers exclu et le raisonnement classique : le principe de Markov est plus faible que la logique classique entière mais plus fort que l’intuitionnisme pur quant à la conversion de la non-impossibilité méta en existence pour des prédicats décidables.

Synthèse

Le principe de Markov est un renforcement constructif ciblé : lorsque l’appartenance à une propriété est décidable pour chaque entier naturel, l’impossibilité d’un échec universel suffit à garantir l’existence d’un témoin, justifiant une recherche finie sans souscrire à des principes classiques non restreints.