Le paradoxe du menteur est dérivé du paradoxe du Crétois (ou paradoxe d'Épiménide). Sous sa forme la plus concise, il s'énonce :
On peut y voir deux interprétations :
La plus ancienne trace de ce paradoxe est relatée dans la Bible :
« Quelqu'un d'entre eux, leur propre prophète, a dit : Les Crétois sont toujours menteurs, de méchantes bêtes, des ventres paresseux. »
l'épître à Tite, Paul de Tarse.
Ce prophète, qui vécut au VII siècle av. J.-C., serait Épiménide le Crétois. Toutefois, cette première formulation du paradoxe du menteur n'est apparue paradoxale que bien plus tard ; lorsqu'au IV siècle av. J.-C., Eubulide de Milet énonça
« Un homme disait qu'il était en train de mentir. Ce que l'homme disait est-il vrai ou faux ? »
De nombreuses formulations virent le jour, par la suite. Parmi les plus récentes
« Épiménide, penseur crétois, émit une affirmation immortelle : Tous les Crétois sont des menteurs. »
Gödel, Escher, Bach, Douglas Hofstadter, page 19.
Attribuons à Épiménide le Crétois le propos « Tous les Crétois sont des menteurs.» Épinémide étant Crétois lui-même, si cette affirmation est vraie, alors Épiménide est un menteur, donc son affirmation est fausse : contradiction ! En fait, il n'y a pas vraiment de paradoxe : tout ce qu'on peut déduire de la citation d'Épiménide, c'est qu'elle est fausse ; en particulier tous les Crétois ne sont pas des menteurs, mais Épiménide, lui, en est un. On résout ainsi le paradoxe en l'étalant dans l'espace.
En fait, la négation de « Tous les Crétois sont des menteurs. » n’est pas : « Tous les Crétois disent la vérité », mais : « Il existe au moins un Crétois qui dit la vérité » (et il faudrait même dire, dans le sens où menteur est utilisé jusqu'ici, « Il existe au moins un Crétois qui dit parfois la vérité »). Donc, il peut exister un ou plusieurs menteurs Crétois.
De manière analogue, la phrase paradoxale : « Je mens toujours » cesse de l'être lorsqu'on l'étale dans le temps : au moment où je dis « Je mens toujours », je mens nécessairement (sinon, on a le même problème qu'avec Épiménide), ce qui implique que je ne mens pas toujours. Il n'y a pas de contradiction : il m'arrive de mentir, mais pas toujours !
Le paradoxe du menteur devient plus intéressant lorsqu'on en considère la version suivante : « Je mens en ce moment même ». Si la phrase est vraie, alors c'est qu'elle est fausse. Mais si elle est fausse, alors elle devient vraie !
Cela indique que quand une phrase peut se prendre elle-même pour énoncé, cela peut conduire à une situation instable (voir pangramme autodescriptif).
Que l'on considère que la phrase « Cette phrase est fausse » n'est ni vraie, ni fausse ou encore qu'il s'agit d'un non-sens, elle réfute dans tous les cas le principe du tiers exclu. Les mathématiques classiques, qui se basent sur le tiers exclu, ne peuvent donc permettre de construire formellement un tel énoncé. Cependant, même avec la restriction du tiers exclu, les énoncés paradoxaux peuvent réapparaître via un codage de la logique formelle dans une théorie suffisamment riche pour cela, comme l'arithmétique ou la plupart des théories destinées à fonder les mathématiques.
Ainsi Kurt Gödel fait référence explicitement au paradoxe du menteur dans l'article de 1931 sur ses deux célèbres théorèmes d'incomplétude : pour établir la preuve du premier théorème d'incomplétude, il parvient à coder une certaine forme de ce paradoxe du menteur (où cependant la démontrabilité remplace la vérité). Il n'y a plus paradoxe, mais on montre que l'énoncé ainsi construit n'est pas prouvable (et pour d'autres raisons, sa négation ne l'est pas non plus). Le théorème de Tarski illustre encore plus clairement cette démarche : cette fois il s'agit de montrer que l'on ne peut pas exprimer la vérité dans l'arithmétique, car sinon le paradoxe pourrait s'exprimer et fournirait une contradiction.
On peut tenter d'éclaircir le lien entre le paradoxe du menteur et l'incomplétude de certaines théories mathématiques. Quelqu’un dit « je mens », est-ce qu’il ment ? S’il ment c’est qu’il ne ment pas. S’il ne ment pas c’est qu’il ment. Ce qu’il dit affirme sa propre fausseté. On a vu que ce paradoxe peut être présenté sous une autre forme : la présente phrase qui commence par « la présente phrase » et finit par « est fausse » est fausse, ou plus simplement, cette phrase est fausse.
Une théorie est un ensemble de phrases. On peut la considérer comme une sorte de diseur de vérités. La théorie dit que toutes ses phrases sont vraies. Le paradoxe du menteur prouve qu’il y a des restrictions sur les capacités des diseurs de vérité quand ceux-ci sont capables de formuler des énoncés à propos de ce qu’ils disent. Supposons qu’un diseur de vérité soit capable de répondre par avance à toutes les questions sur ce qu’il va répondre. Posons-lui alors la question « à cette question vas-tu répondre non ? ». Qu’il réponde oui ou non, dans les deux cas il dit faux. Il ne peut donc pas répondre sans se tromper.
Il s’agit d’une incomplétude essentielle pour les théories et les diseurs de vérité. Ils ne peuvent pas dire toute la vérité sur tout ce qu’ils disent à partir du moment où leurs moyens d’expression sont suffisamment riches pour permettre de poser des questions telles que celle qui vient d’être citée. En résumé, dès qu’on peut poser à un diseur de vérité des questions telles que « à cette question vas-tu répondre non ? » il ne peut pas à la fois toujours répondre et toujours dire la vérité.