Russell's paradox

Dijkstra 在〈For brevity's sake〉(EWD1070) 用簡潔符號重述 Russell's paradox: 若集合 $R \defeq \{\, x \mid x \notin x \,\}$ 存在，則
$$x \in R ~\Leftrightarrow~ x \notin x \qquad \text{for all } x$$ 將上式之 $x$ 代以 $R$ 即得
$$R \in R ~\Leftrightarrow~ R \notin R$$ 若接納排中律（從而 $R \in R ~\vee~ R \notin R$）則上式矛盾。我想到金次的一題練習：試證明集合 $S$ 和 $\mathcal P\,S$ 間不存在對射。這個證明應該也能三言兩語說完：假設 $f : S \to \mathcal P\,S$ 為對射。定義 $A \defeq \{\, x \in S \mid x \notin f\,x \,\}$, 則
$$x \in A ~\Leftrightarrow~ x \notin f\,x \qquad\text{for all } x \in S$$ 將上式之 $x$ 代以 $f^{-1}\,A$ 即得矛盾
$$f^{-1}\,A \in A ~\Leftrightarrow~ f^{-1}\,A \notin A$$ （我們只用到 $f \circ f^{-1} = \mathit{id}$, 所以「$S$ 和 $\mathcal P\,S$ 間不存在對射」其實是因為「不存在 $S$ 到 $\mathcal P\,S$ 的蓋射」。）

練習：將停機問題不可判定之證明以上述型式重寫。

--
其實這篇的主要目的是測試 MathJax XD。