タイプ理論におけるカンターの定理

カンターの定理は、

任意の集合Aについて、Aのすべての部分集合の集合は、A自身よりも厳密に大きな基数を持つ。

ZFCセットを参照せずにタイプ/命題のみを使ってこのようなものをエンコードすることは可能ですか?この命題を依存型言語でコード化するためのコードまたは擬似コードは高く評価されます。

ベストアンサー

短い答え:はい!あなたは証拠を得るために多くの機械を必要としません。

1つの微妙な点:除外された真ん中が使用されているように見えます:セット$ D $と数字$ d $を作成し、D $または$ d
D $で矛盾につながる。しかし、直感主義論理に真のという補助金があります。

$$ mbox {すべての文} P、(P iff neg P) Rightarrow bot $$

これは、通常の証拠と一緒に十分です。一般に、「射撃」は建設的/直観主義的な論理(選択肢なし)に微妙な微妙なニュアンスがあるかもしれないので、代わりに「正しい逆可逆性」で行う必要があることに注意してください。

Coqの何かの理由で私がオンラインで見つけることができなかった非常に標準的な証明は次のようになるかもしれません:

Inductive right_invertible {A B:Type}(f : A->B):Prop :=
| inverse: forall g, (forall b:B, f (g b) = b) -> right_invertible f.


Lemma case_to_false :  forall P : Prop, (P <-> ~P) -> False.
Proof.
  intros P H; apply H.
    - apply <- H.
      intro p.
      apply H; exact p.
    - apply <- H; intro p; apply H; exact p.
Qed.


Theorem cantor :  forall f : nat -> (nat -> Prop), ~right_invertible f.
Proof.
  intros f inv.
  destruct inv.
  pose (diag := fun n => ~ (f n n)).
  apply case_to_false with (diag (g diag)).
  split.
  - intro I; unfold diag in I.
    rewrite H in I. auto.
  - intro nI.
    unfold diag. rewrite H. auto.
Qed.

もちろん、これらの成人について考えなければならない「正しい」枠組みは、この証拠の最小限の要件と見なすことができます。合成計算可能性の固定小数点定理では、この答えに追加する興味深いものがいくつかあると思われます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です