Stickynotes

とるにたらない数学のメモを書いていくサイトです。自由に見てください。

なおこのサイトを大学のレポートに引用するのはおすすめしません。 自分の頭で考え、自分の言葉で書くことをお勧めします。

文責は全て私にあります。謝辞にある方々への直接の問い合わせはご遠慮ください。


どんな x も含む集合 A は存在するか?

公理的集合論上で分出公理を用いて上記のAが存在しないことを示す。

分出公理: ∀A∃B∀x(x∈B⟺x∈A∧φ(x))

※ φ は x と A を含む論理式である。とくに FOL で考えているため、 これを量化することはしない。

φ ごとに分出公理が成り立つので、以下も成り立つ。

∀A∃B∀x(x∈B⟺x∈A∧x∈x)

Aとして ∀x.x∈A を満すような集合をとってくる。

公理から次のような集合が存在することが導かれる。

B={x∈A∣x∈x}

もし B∈B だったとき、φの定義から B∉B となり矛盾。 もし B∉B だったとき、φの定義から B∈B となり矛盾。

したがって、以上の議論のどこかに矛盾がある。

  • B の作り方は公理の変形なので否定できない。
  • Axiom schema から公理を作ることも否定できない。
  • したがって、A の作り方に問題がある。 そもそも存在しない集合を取ってきている。

以上より、どんな x も含む集合 A は存在しない。■

謝辞

2023年4月に仙台にて学生から質問を受けてこの問題を解きました。 解くにあたって Yudai Suzuki 氏にも助言をもらいました。 お二人ともありがとうございます。


Date: 2023-05-12T00:00:00.000Z

カット除去定理は無矛盾性を導くのに役立つ

適当なシーケント計算の体系 (たとえば G3cp) において、 その体系が無矛盾であることを導くことを考える。

体系が無矛盾であることは ⇒⊥ が導かれないことである。 背理法を用いて、⇒⊥ が導かれると仮定する。

現在の体系でカット除去定理が成り立つならば、 このシーケントもカット以外の推論規則で証明できるはずである。

ところが、このシーケントに至るまでに、 直前に適用されたと考える推論規則はカットのみである(※体系依存)。 なぜなら、⊥ 以外の項がシーケントに含まれていないからである。

したがって、このシーケントがカットを用いずに証明できないことから、 仮定が否定されるため、体系は無矛盾であることが示される。■

謝辞

Leuven に滞在中の 2024 年 8 月 に Marianna Girlando 氏にこの証明のアイデアを教えていただきました。 ありがとうございます。


Date: 2024-08-09T00:00:00.000Z