不完全性定理ゼミで出た宿題 [趣味のゲーデル]

昨日リチャード・ザックによる不完全性定理ゼミの第1回目があったのですが、初回にもかかわらず、いきなり宿題が出やがりました。で、宿題は以下のもの。

• \(Y \subseteq \mathbb{N}\) を実効的に決定可能とし、 \(X \subseteq Y\) と \(Y-X\) を実効的に枚挙可能とする。（ \(Y-X\) は \(\{y \in Y | y \not \in X\}\) を表す）このとき、 \(X\) は実効的に決定可能であることを示せ。（できれば、 \(Y\) の特性函数と \(X\) と \(Y-X\) を枚挙する函数を用いた \(X\) の特性函数を使うこと）

• \(L\) を、関係記号 \({\rm R}\) だけを持つ一階言語とする。このとき、 \(\forall x \forall y ({\rm R}xy \rightarrow \exists z ({\rm R}xz {\normalsize \wedge} {\rm R}yz))\) を唯一の公理として持つ理論 \(T\) に、それが健全となるような \(L\) の解釈を与え、その解釈がなぜ理論 \(T\) を健全たらしめるか説明せよ。

まあ、見ての通り、それほどむずかしくない、というか、ごく基本的なことの確認にすぎないのですが、ちゃんと証明しろって言われると、やっぱりちょっとメンドイですよね。

ちなみに、上の問題はレベル的に、哲学科の学部三年生レベルです。