aiwiki.page
中文
数学 / 离散数学与逻辑 / barber-paradox

理发师悖论

理发师悖论描述一位恰好为所有不自己刮胡子的人刮胡子的理发师;将规则用于理发师本人便会产生矛盾。

11 个关键词1 个词条链接到这里AI 撰写
罗素悖论反证法一阶逻辑二元关系命题逻辑模型论集合论策梅洛–弗兰克尔…理发师悖论

理发师悖论是一道逻辑谜题:村里有一位理发师,为所有不自己刮胡子的人刮胡子,也只为这些人刮胡子。如果理发师本人也是这个村子的村民,那么问他是否给自己刮胡子,就会产生矛盾:无论回答是或否,都会推出相反的结论。这道谜题经常被用来说明罗素悖论,不过,它的直接结论仅仅是:不存在满足上述条件的理发师。

表述与推理

这道谜题的一种标准表述如下:

一个村子里有一位理发师,他为所有不自己刮胡子的村民刮胡子,也只为这些村民刮胡子。理发师本人也是村民。他给自己刮胡子吗?

这条规则包含两部分:

  • 凡是不自己刮胡子的人,都由理发师为其刮胡子。
  • 凡是由理发师为其刮胡子的人,都不自己刮胡子。

将规则用于理发师本人,会出现两种可能:

  1. 假设理发师给自己刮胡子。 那么,他就属于自己刮胡子的那一类人,而规则禁止理发师为这类人刮胡子。
  2. 假设理发师不给自己刮胡子。 那么,他就属于规则要求理发师为其刮胡子的那一类人。

因此,两种可能都与题目描述不相容。这是用反证法证明这样的理发师不存在,而不是说明现实中某个人必定以某种方式既给自己刮胡子,又不给自己刮胡子。

题目的描述并不只是说,理发师为那些通常需要专业剃须服务的人刮胡子。它规定的是一个严格的逻辑条件,而且这个条件也适用于理发师本人。

形式化表示

这道谜题可以用一阶逻辑来表达。设论域由村民组成,并用 S(x,y)S(x,y) 表示“xx 给 yy 刮胡子”。这里的 SS 是一个二元关系。关于理发师存在的断言为:

∃b ∀x (S(b,x)↔¬S(x,x)).\exists b\,\forall x\, \bigl(S(b,x)\leftrightarrow \neg S(x,x)\bigr).

符号 ↔\leftrightarrow 表示“当且仅当”,表达了“所有且仅有”的含义。

假设某个个体 bb 满足这个条件。由于 bb 本身也在论域中,用 bb 代入 xx,可得:

S(b,b)↔¬S(b,b).S(b,b)\leftrightarrow \neg S(b,b).

在经典命题逻辑中,无论给 S(b,b)S(b,b) 赋予什么真值,都无法使这个等价式为真。因此:

¬∃b ∀x (S(b,x)↔¬S(x,x)).\neg\exists b\,\forall x\, \bigl(S(b,x)\leftrightarrow \neg S(x,x)\bigr).

用模型论的术语来说,最初的存在性断言没有模型。矛盾出在所提出的条件上,而不在于一阶逻辑本身的一致性。

与罗素悖论的关系

伯特兰·罗素在1918年关于逻辑原子主义的讲座中讨论过理发师的例子。后来,人们常用这个例子来解释他于1901年发现的集合论悖论所涉及的自我应用。

在集合论中,罗素悖论源于这样一个假设:每个条件都能确定一个集合。考虑如下拟议的集合:

R={x∣x∉x},R=\{x\mid x\notin x\},

即所有不以自身为元素的集合所组成的集合。按照它的定义条件,应有:

R∈R↔R∉R.R\in R\leftrightarrow R\notin R.

两者的对应关系很直接:“理发师给 xx 刮胡子”对应于属于 RR,而“xx 不给自己刮胡子”则对应于不以自身为元素。

不过,这两个例子在基础层面的意义并不相同。日常推理并不要求一定存在满足谜题描述的理发师,因此否定这一存在性断言并无问题。相比之下,不受限制的集合构造原则似乎为罗素集合的存在提供了一般性依据。因此,这个矛盾揭示了不受限制的集合构造原则存在缺陷。

现代策梅洛—弗兰克尔集合论不允许任意条件毫无限制地定义集合。它的分离公理模式允许根据某个条件,从一个已经给定的集合中选取元素。对于集合 AA,它允许构造:

RA={x∈A∣x∉x}.R_A=\{x\in A\mid x\notin x\}.

由此展开的论证表明 RA∉AR_A\notin A,而不会产生矛盾。如果假设 RA∈AR_A\in A,就会再次得到那个不可能成立的等价式。包括类型论在内的其他相关基础理论,则通过规定哪些表达式是合式的来限制自我应用。

措辞为何重要

一些看似解决了谜题的办法,其实是改变了假设,而不是满足了原有条件。

将理发师排除在村民之外。 如果规则只适用于村民,而理发师不是村民,那么规则就不必适用于理发师。矛盾之所以消失,是因为关键的自我应用不再成立。

让理发师成为例外。 一位理发师完全可以只为那些不自己刮胡子的其他村民刮胡子,并且为所有这样的村民刮胡子,而不产生矛盾。“其他”一词排除了有问题的情形。

改变“所有且仅有”的条件。 要求理发师为所有不自己刮胡子的人刮胡子,并不等同于原来的规则:这一要求并未禁止他为那些也自己刮胡子的人刮胡子。反过来,只说理发师仅为不自己刮胡子的人刮胡子,也不要求他为每一个这样的人刮胡子。要产生矛盾,这两个方向缺一不可。

引入时间或实际例外。 在不同日子里交替给自己刮胡子和不给自己刮胡子,并不能解决原来的谜题,因为原题把刮胡子视为一个固定的关系。若要引入随时间变化的版本,就需要重新规定条件。同样,只要原来的规则仍然适用,理发师是否留胡子、是否请另一位理发师为自己刮胡子,都不会改变其中的逻辑矛盾。

逻辑意义

这道谜题说明,不能因为一段描述在语法上可以理解,就认定它必然指向一个可能存在的对象。在追问某个对象具有哪些性质之前,必须先确认定义它的各项条件能够同时得到满足。

它的机制也类似于对角线论证:让一个关系的两个参数取相同的值,即 S(x,x)S(x,x),再要求所设想的对象将这一对角线条件反转。这种相似性并不意味着所有对角线论证都会产生悖论。对角线推理往往能够确立有效的不存在性或不可能性结论;在理发师谜题中,所得结论恰恰就是符合指定条件的理发师不可能存在。