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。