解ける人にしか解けない！ #数理論理学クイズ

実際De Morganの法則, ¬(∀x∈A)φ(x)↔(∃x∈A)¬φ(x), (∀x∈A)¬φ(x)↔¬(∃x∈A)φ(x)が成り立つのは正解の組のみである. 余談だが数学に於ける空虚な真はA=∅の場合である. 実際x∈∅は常に偽であり, よって(∀x)[x∈∅→φ(x)]は常に真である.

ZFCの無矛盾性からZFCのモデルの存在が完全性から従う. またZFCに有限のモデルは存在しないためそれは無限モデルである. よってLöwenheim–Skolemの定理から可算モデルが取れる. これは集合論的には可算性が絶対的ではないことを表している.

PAはΣ_1-完全かつΣ_1-健全であり, 「ℕ⊨φ∨ψ」ならば「ℕ⊨φまたはℕ⊨ψ」が成り立つため良い. 一般の論理式ならPA⊢Con(PA)∨¬Con(PA)であるがCon(PA), ¬Con(PA)はどちらもPAで示せないため成り立たない.

まずLöwenheim–Skolemの定理から可算モデルを取りMostowski崩壊定理によって推移モデルを得ることはできない. Mostowski崩壊定理の前提は∈-整礎であることで, 一般に基礎の公理を満たすことからは示せないからだ. 示せないことの証明は省略する.

人間が行っている証明は証明の長さが有限で抑えられるため証明の長さがある有限の値に抑えられた証明可能性を考えるのが正しい. またこれは計算可能である.

完備性は一階述語論理で記述できないため初等同値性から*ℝで成り立つことを言うことはできない. 実際*ℝは順序完備ではない.

例えばZFCを加えてカット除去が可能だとしたらカット除去を通してZFCからCon(ZFC)が示せて不完全性定理に矛盾してしまう. よって成り立たないが適当な公理と同値である推論規則で下件が空になり得るなら成り立つ場合がある.