##  [Principe de Markov](/fr/node/60956) 

 Définition

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

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

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

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

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

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

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 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

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.