# Theory OrdQuant

Up to index of Isabelle/ZF

theory OrdQuant
imports Ordinal
begin

    (*  Title:      ZF/AC/OrdQuant.thy
        ID:         $Id: OrdQuant.thy,v 1.33 2005/08/02 17:47:12 wenzelm Exp $
        Authors:    Krzysztof Grabczewski and L C Paulson
    *)

    header {*Special quantifiers*}

    theory OrdQuant imports Ordinal begin

    subsection {*Quantifiers and union operator for ordinals*}

    constdefs

      (* Ordinal Quantifiers *)
      oall :: "[i, i => o] => o"
        "oall(A, P) == ALL x. x<A --> P(x)"

      oex :: "[i, i => o] => o"
        "oex(A, P)  == EX x. x<A & P(x)"

      (* Ordinal Union *)
      OUnion :: "[i, i => i] => i"
        "OUnion(i,B) == {z: \<Union>x∈i. B(x). Ord(i)}"

    syntax
      "@oall"     :: "[idt, i, o] => o"        ("(3ALL _<_./ _)" 10)
      "@oex"      :: "[idt, i, o] => o"        ("(3EX _<_./ _)" 10)
      "@OUNION"   :: "[idt, i, i] => i"        ("(3UN _<_./ _)" 10)

    translations
      "ALL x<a. P"  == "oall(a, %x. P)"
      "EX x<a. P"   == "oex(a, %x. P)"
      "UN x<a. B"   == "OUnion(a, %x. B)"

    syntax (xsymbols)
      "@oall"     :: "[idt, i, o] => o"        ("(3∀_<_./ _)" 10)
      "@oex"      :: "[idt, i, o] => o"        ("(3∃_<_./ _)" 10)
      "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
    syntax (HTML output)
      "@oall"     :: "[idt, i, o] => o"        ("(3∀_<_./ _)" 10)
      "@oex"      :: "[idt, i, o] => o"        ("(3∃_<_./ _)" 10)
      "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)

    subsubsection {*simplification of the new quantifiers*}

    (*MOST IMPORTANT that this is added to the simpset BEFORE Ord_atomize
      is proved.  Ord_atomize would convert this rule to
        x < 0 ==> P(x) == True, which causes dire effects!*)
    lemma [simp]: "(ALL x<0. P(x))"
    by (simp add: oall_def)

    lemma [simp]: "~(EX x<0. P(x))"
    by (simp add: oex_def)

    lemma [simp]: "(ALL x<succ(i). P(x)) <-> (Ord(i) --> P(i) & (ALL x<i. P(x)))"
    apply (simp add: oall_def le_iff)
    apply (blast intro: lt_Ord2)
    done

    lemma [simp]: "(EX x<succ(i). P(x)) <-> (Ord(i) & (P(i) | (EX x<i. P(x))))"
    apply (simp add: oex_def le_iff)
    apply (blast intro: lt_Ord2)
    done

    subsubsection {*Union over ordinals*}

    lemma Ord_OUN [intro,simp]:
         "[| !!x. x<A ==> Ord(B(x)) |] ==> Ord(\<Union>x<A. B(x))"
    by (simp add: OUnion_def ltI Ord_UN)

    lemma OUN_upper_lt:
         "[| a<A;  i < b(a);  Ord(\<Union>x<A. b(x)) |] ==> i < (\<Union>x<A. b(x))"
    by (unfold OUnion_def lt_def, blast )

    lemma OUN_upper_le:
         "[| a<A;  i≤b(a);  Ord(\<Union>x<A. b(x)) |] ==> i ≤ (\<Union>x<A. b(x))"
    apply (unfold OUnion_def, auto)
    apply (rule UN_upper_le )
    apply (auto simp add: lt_def)
    done

    lemma Limit_OUN_eq: "Limit(i) ==> (\<Union>x<i. x) = i"
    by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)

    (* No < version; consider (\<Union>i∈nat.i)=nat *)
    lemma OUN_least:
         "(!!x. x<A ==> B(x) ⊆ C) ==> (\<Union>x<A. B(x)) ⊆ C"
    by (simp add: OUnion_def UN_least ltI)

    (* No < version; consider (\<Union>i∈nat.i)=nat *)
    lemma OUN_least_le:
         "[| Ord(i);  !!x. x<A ==> b(x) ≤ i |] ==> (\<Union>x<A. b(x)) ≤ i"
    by (simp add: OUnion_def UN_least_le ltI Ord_0_le)

    lemma le_implies_OUN_le_OUN:
         "[| !!x. x<A ==> c(x) ≤ d(x) |] ==> (\<Union>x<A. c(x)) ≤ (\<Union>x<A. d(x))"
    by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)

    lemma OUN_UN_eq:
         "(!!x. x:A ==> Ord(B(x)))
          ==> (\<Union>z < (\<Union>x∈A. B(x)). C(z)) = (\<Union>x∈A. \<Union>z < B(x). C(z))"
    by (simp add: OUnion_def)

    lemma OUN_Union_eq:
         "(!!x. x:X ==> Ord(x))
          ==> (\<Union>z < Union(X). C(z)) = (\<Union>x∈X. \<Union>z < x. C(z))"
    by (simp add: OUnion_def)

    (*So that rule_format will get rid of ALL x<A...*)
    lemma atomize_oall [symmetric, rulify]:
         "(!!x. x<A ==> P(x)) == Trueprop (ALL x<A. P(x))"
    by (simp add: oall_def atomize_all atomize_imp)

    subsubsection {*universal quantifier for ordinals*}

    lemma oallI [intro!]:
        "[| !!x. x<A ==> P(x) |] ==> ALL x<A. P(x)"
    by (simp add: oall_def)

    lemma ospec: "[| ALL x<A. P(x);  x<A |] ==> P(x)"
    by (simp add: oall_def)

    lemma oallE:
        "[| ALL x<A. P(x);  P(x) ==> Q;  ~x<A ==> Q |] ==> Q"
    by (simp add: oall_def, blast)

    lemma rev_oallE [elim]:
        "[| ALL x<A. P(x);  ~x<A ==> Q;  P(x) ==> Q |] ==> Q"
    by (simp add: oall_def, blast)

    (*Trival rewrite rule;   (ALL x<a.P)<->P holds only if a is not 0!*)
    lemma oall_simp [simp]: "(ALL x<a. True) <-> True"
    by blast

    (*Congruence rule for rewriting*)
    lemma oall_cong [cong]:
        "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
         ==> oall(a, %x. P(x)) <-> oall(a', %x. P'(x))"
    by (simp add: oall_def)

    subsubsection {*existential quantifier for ordinals*}

    lemma oexI [intro]:
        "[| P(x);  x<A |] ==> EX x<A. P(x)"
    apply (simp add: oex_def, blast)
    done

    (*Not of the general form for such rules; ~EX has become ALL~ *)
    lemma oexCI:
       "[| ALL x<A. ~P(x) ==> P(a);  a<A |] ==> EX x<A. P(x)"
    apply (simp add: oex_def, blast)
    done

    lemma oexE [elim!]:
        "[| EX x<A. P(x);  !!x. [| x<A; P(x) |] ==> Q |] ==> Q"
    apply (simp add: oex_def, blast)
    done

    lemma oex_cong [cong]:
        "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
         ==> oex(a, %x. P(x)) <-> oex(a', %x. P'(x))"
    apply (simp add: oex_def cong add: conj_cong)
    done

    subsubsection {*Rules for Ordinal-Indexed Unions*}

    lemma OUN_I [intro]: "[| a<i;  b: B(a) |] ==> b: (\<Union>z<i. B(z))"
    by (unfold OUnion_def lt_def, blast)

    lemma OUN_E [elim!]:
        "[| b : (\<Union>z<i. B(z));  !!a.[| b: B(a);  a<i |] ==> R |] ==> R"
    apply (unfold OUnion_def lt_def, blast)
    done

    lemma OUN_iff: "b : (\<Union>x<i. B(x)) <-> (EX x<i. b : B(x))"
    by (unfold OUnion_def oex_def lt_def, blast)

    lemma OUN_cong [cong]:
        "[| i=j;  !!x. x<j ==> C(x)=D(x) |] ==> (\<Union>x<i. C(x)) = (\<Union>x<j. D(x))"
    by (simp add: OUnion_def lt_def OUN_iff)

    lemma lt_induct:
        "[| i<k;  !!x.[| x<k;  ALL y<x. P(y) |] ==> P(x) |]  ==>  P(i)"
    apply (simp add: lt_def oall_def)
    apply (erule conjE)
    apply (erule Ord_induct, assumption, blast)
    done

    subsection {*Quantification over a class*}

    constdefs
      "rall"     :: "[i=>o, i=>o] => o"
        "rall(M, P) == ALL x. M(x) --> P(x)"

      "rex"      :: "[i=>o, i=>o] => o"
        "rex(M, P) == EX x. M(x) & P(x)"

    syntax
      "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3ALL _[_]./ _)" 10)
      "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3EX _[_]./ _)" 10)

    syntax (xsymbols)
      "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3∀_[_]./ _)" 10)
      "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3∃_[_]./ _)" 10)
    syntax (HTML output)
      "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3∀_[_]./ _)" 10)
      "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3∃_[_]./ _)" 10)

    translations
      "ALL x[M]. P"  == "rall(M, %x. P)"
      "EX x[M]. P"   == "rex(M, %x. P)"

    subsubsection{*Relativized universal quantifier*}

    lemma rallI [intro!]: "[| !!x. M(x) ==> P(x) |] ==> ALL x[M]. P(x)"
    by (simp add: rall_def)

    lemma rspec: "[| ALL x[M]. P(x); M(x) |] ==> P(x)"
    by (simp add: rall_def)

    (*Instantiates x first: better for automatic theorem proving?*)
    lemma rev_rallE [elim]:
        "[| ALL x[M]. P(x);  ~ M(x) ==> Q;  P(x) ==> Q |] ==> Q"
    by (simp add: rall_def, blast)

    lemma rallE: "[| ALL x[M]. P(x);  P(x) ==> Q;  ~ M(x) ==> Q |] ==> Q"
    by blast

    (*Trival rewrite rule;   (ALL x[M].P)<->P holds only if A is nonempty!*)
    lemma rall_triv [simp]: "(ALL x[M]. P) <-> ((EX x. M(x)) --> P)"
    by (simp add: rall_def)

    (*Congruence rule for rewriting*)
    lemma rall_cong [cong]:
        "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (ALL x[M]. P(x)) <-> (ALL x[M]. P'(x))"
    by (simp add: rall_def)

    subsubsection{*Relativized existential quantifier*}

    lemma rexI [intro]: "[| P(x); M(x) |] ==> EX x[M]. P(x)"
    by (simp add: rex_def, blast)

    (*The best argument order when there is only one M(x)*)
    lemma rev_rexI: "[| M(x);  P(x) |] ==> EX x[M]. P(x)"
    by blast

    (*Not of the general form for such rules; ~EX has become ALL~ *)
    lemma rexCI: "[| ALL x[M]. ~P(x) ==> P(a); M(a) |] ==> EX x[M]. P(x)"
    by blast

    lemma rexE [elim!]: "[| EX x[M]. P(x);  !!x. [| M(x); P(x) |] ==> Q |] ==> Q"
    by (simp add: rex_def, blast)

    (*We do not even have (EX x[M]. True) <-> True unless A is nonempty!!*)
    lemma rex_triv [simp]: "(EX x[M]. P) <-> ((EX x. M(x)) & P)"
    by (simp add: rex_def)

    lemma rex_cong [cong]:
        "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (EX x[M]. P(x)) <-> (EX x[M]. P'(x))"
    by (simp add: rex_def cong: conj_cong)

    lemma rall_is_ball [simp]: "(∀x[%z. z∈A]. P(x)) <-> (∀x∈A. P(x))"
    by blast

    lemma rex_is_bex [simp]: "(∃x[%z. z∈A]. P(x)) <-> (∃x∈A. P(x))"
    by blast

    lemma atomize_rall: "(!!x. M(x) ==> P(x)) == Trueprop (ALL x[M]. P(x))";
    by (simp add: rall_def atomize_all atomize_imp)

    declare atomize_rall [symmetric, rulify]

    lemma rall_simps1:
         "(ALL x[M]. P(x) & Q)   <-> (ALL x[M]. P(x)) & ((ALL x[M]. False) | Q)"
         "(ALL x[M]. P(x) | Q)   <-> ((ALL x[M]. P(x)) | Q)"
         "(ALL x[M]. P(x) --> Q) <-> ((EX x[M]. P(x)) --> Q)"
         "(~(ALL x[M]. P(x))) <-> (EX x[M]. ~P(x))"
    by blast+

    lemma rall_simps2:
         "(ALL x[M]. P & Q(x))   <-> ((ALL x[M]. False) | P) & (ALL x[M]. Q(x))"
         "(ALL x[M]. P | Q(x))   <-> (P | (ALL x[M]. Q(x)))"
         "(ALL x[M]. P --> Q(x)) <-> (P --> (ALL x[M]. Q(x)))"
    by blast+

    lemmas rall_simps [simp] = rall_simps1 rall_simps2

    lemma rall_conj_distrib:
        "(ALL x[M]. P(x) & Q(x)) <-> ((ALL x[M]. P(x)) & (ALL x[M]. Q(x)))"
    by blast

    lemma rex_simps1:
         "(EX x[M]. P(x) & Q) <-> ((EX x[M]. P(x)) & Q)"
         "(EX x[M]. P(x) | Q) <-> (EX x[M]. P(x)) | ((EX x[M]. True) & Q)"
         "(EX x[M]. P(x) --> Q) <-> ((ALL x[M]. P(x)) --> ((EX x[M]. True) & Q))"
         "(~(EX x[M]. P(x))) <-> (ALL x[M]. ~P(x))"
    by blast+

    lemma rex_simps2:
         "(EX x[M]. P & Q(x)) <-> (P & (EX x[M]. Q(x)))"
         "(EX x[M]. P | Q(x)) <-> ((EX x[M]. True) & P) | (EX x[M]. Q(x))"
         "(EX x[M]. P --> Q(x)) <-> (((ALL x[M]. False) | P) --> (EX x[M]. Q(x)))"
    by blast+

    lemmas rex_simps [simp] = rex_simps1 rex_simps2

    lemma rex_disj_distrib:
        "(EX x[M]. P(x) | Q(x)) <-> ((EX x[M]. P(x)) | (EX x[M]. Q(x)))"
    by blast

    subsubsection{*One-point rule for bounded quantifiers*}

    lemma rex_triv_one_point1 [simp]: "(EX x[M]. x=a) <-> ( M(a))"
    by blast

    lemma rex_triv_one_point2 [simp]: "(EX x[M]. a=x) <-> ( M(a))"
    by blast

    lemma rex_one_point1 [simp]: "(EX x[M]. x=a & P(x)) <-> ( M(a) & P(a))"
    by blast

    lemma rex_one_point2 [simp]: "(EX x[M]. a=x & P(x)) <-> ( M(a) & P(a))"
    by blast

    lemma rall_one_point1 [simp]: "(ALL x[M]. x=a --> P(x)) <-> ( M(a) --> P(a))"
    by blast

    lemma rall_one_point2 [simp]: "(ALL x[M]. a=x --> P(x)) <-> ( M(a) --> P(a))"
    by blast

    subsubsection{*Sets as Classes*}

    constdefs setclass :: "[i,i] => o"       ("##_" [40] 40)
       "setclass(A) == %x. x : A"

    lemma setclass_iff [simp]: "setclass(A,x) <-> x : A"
    by (simp add: setclass_def)

    lemma rall_setclass_is_ball [simp]: "(∀x[##A]. P(x)) <-> (∀x∈A. P(x))"
    by auto

    lemma rex_setclass_is_bex [simp]: "(∃x[##A]. P(x)) <-> (∃x∈A. P(x))"
    by auto

    ML
    {*
    val oall_def = thm "oall_def"
    val oex_def = thm "oex_def"
    val OUnion_def = thm "OUnion_def"

    val oallI = thm "oallI";
    val ospec = thm "ospec";
    val oallE = thm "oallE";
    val rev_oallE = thm "rev_oallE";
    val oall_simp = thm "oall_simp";
    val oall_cong = thm "oall_cong";
    val oexI = thm "oexI";
    val oexCI = thm "oexCI";
    val oexE = thm "oexE";
    val oex_cong = thm "oex_cong";
    val OUN_I = thm "OUN_I";
    val OUN_E = thm "OUN_E";
    val OUN_iff = thm "OUN_iff";
    val OUN_cong = thm "OUN_cong";
    val lt_induct = thm "lt_induct";

    val rall_def = thm "rall_def"
    val rex_def = thm "rex_def"

    val rallI = thm "rallI";
    val rspec = thm "rspec";
    val rallE = thm "rallE";
    val rev_oallE = thm "rev_oallE";
    val rall_cong = thm "rall_cong";
    val rexI = thm "rexI";
    val rexCI = thm "rexCI";
    val rexE = thm "rexE";
    val rex_cong = thm "rex_cong";

    val Ord_atomize =
        atomize ([("OrdQuant.oall", [ospec]),("OrdQuant.rall", [rspec])]@
                     ZF_conn_pairs,
                 ZF_mem_pairs);
    simpset_ref() := simpset() setmksimps (map mk_eq o Ord_atomize o gen_all);
    *}

    text {* Setting up the one-point-rule simproc *}

    ML_setup {*
    local

    fun prove_rex_tac ss = unfold_tac ss [rex_def] THEN Quantifier1.prove_one_point_ex_tac;
    val rearrange_bex = Quantifier1.rearrange_bex prove_rex_tac;

    fun prove_rall_tac ss = unfold_tac ss [rall_def] THEN Quantifier1.prove_one_point_all_tac;
    val rearrange_ball = Quantifier1.rearrange_ball prove_rall_tac;

    in

    val defREX_regroup = Simplifier.simproc (the_context ())
      "defined REX" ["EX x[M]. P(x) & Q(x)"] rearrange_bex;
    val defRALL_regroup = Simplifier.simproc (the_context ())
      "defined RALL" ["ALL x[M]. P(x) --> Q(x)"] rearrange_ball;

    end;

    Addsimprocs [defRALL_regroup,defREX_regroup];
    *}

    end

### Quantifiers and union operator for ordinals

#### simplification of the new quantifiers

lemma

      ∀x<0. P(x)

lemma

      ¬ (∃x<0. P(x))

lemma

      (∀x<succ(i). P(x)) <-> Ord(i) --> P(i) ∧ (∀x<i. P(x))

lemma

      (∃x<succ(i). P(x)) <-> Ord(i) ∧ (P(i) ∨ (∃x<i. P(x)))

#### Union over ordinals

lemma Ord_OUN:

      (!!x. x < A ==> Ord(B(x))) ==> Ord(\<Union>x<A. B(x))

lemma OUN_upper_lt:

      [| a < A; i < b(a); Ord(\<Union>x<A. b(x)) |] ==> i < (\<Union>x<A. b(x))

lemma OUN_upper_le:

      [| a < A; i ≤ b(a); Ord(\<Union>x<A. b(x)) |] ==> i ≤ (\<Union>x<A. b(x))

lemma Limit_OUN_eq:

      Limit(i) ==> (\<Union>x<i. x) = i

lemma OUN_least:

      (!!x. x < A ==> B(x) ⊆ C) ==> (\<Union>x<A. B(x)) ⊆ C

lemma OUN_least_le:

      [| Ord(i); !!x. x < A ==> b(x) ≤ i |] ==> (\<Union>x<A. b(x)) ≤ i

lemma le_implies_OUN_le_OUN:

      (!!x. x < A ==> c(x) ≤ d(x)) ==> (\<Union>x<A. c(x)) ≤ (\<Union>x<A. d(x))

lemma OUN_UN_eq:

      (!!x. x ∈ A ==> Ord(B(x)))
      ==> (\<Union>z<\<Union>x∈A. B(x). C(z)) = (\<Union>x∈A. \<Union>z<B(x). C(z))

lemma OUN_Union_eq:

      (!!x. x ∈ X ==> Ord(x))
      ==> (\<Union>z<\<Union>X. C(z)) = (\<Union>x∈X. \<Union>z<x. C(z))

lemma atomize_oall:

      ∀x<A1. P1(x) == (!!x. x < A1 ==> P1(x))

#### universal quantifier for ordinals

lemma oallI:

      (!!x. x < A ==> P(x)) ==> ∀x<A. P(x)

lemma ospec:

      [| ∀x<A. P(x); x < A |] ==> P(x)

lemma oallE:

      [| ∀x<A. P(x); P(x) ==> Q; ¬ x < A ==> Q |] ==> Q

lemma rev_oallE:

      [| ∀x<A. P(x); ¬ x < A ==> Q; P(x) ==> Q |] ==> Q

lemma oall_simp:

      (∀x<a. True) <-> True

lemma oall_cong:

      [| a = a'; !!x. x < a' ==> P(x) <-> P'(x) |] ==> (∀x<a. P(x)) <-> (∀x<a'. P'(x))

#### existential quantifier for ordinals

lemma oexI:

      [| P(x); x < A |] ==> ∃x<A. P(x)

lemma oexCI:

      [| ∀x<A. ¬ P(x) ==> P(a); a < A |] ==> ∃x<A. P(x)

lemma oexE:

      [| ∃x<A. P(x); !!x. [| x < A; P(x) |] ==> Q |] ==> Q

lemma oex_cong:

      [| a = a'; !!x. x < a' ==> P(x) <-> P'(x) |] ==> (∃x<a. P(x)) <-> (∃x<a'. P'(x))

#### Rules for Ordinal-Indexed Unions

lemma OUN_I:

      [| a < i; b ∈ B(a) |] ==> b ∈ (\<Union>z<i. B(z))

lemma OUN_E:

      [| b ∈ (\<Union>z<i. B(z)); !!a. [| b ∈ B(a); a < i |] ==> R |] ==> R

lemma OUN_iff:

      b ∈ (\<Union>x<i. B(x)) <-> (∃x<i. b ∈ B(x))

lemma OUN_cong:

      [| i = j; !!x. x < j ==> C(x) = D(x) |]
      ==> (\<Union>x<i. C(x)) = (\<Union>x<j. D(x))

lemma lt_induct:

      [| i < k; !!x. [| x < k; ∀y<x. P(y) |] ==> P(x) |] ==> P(i)

### Quantification over a class

#### Relativized universal quantifier

lemma rallI:

      (!!x. M(x) ==> P(x)) ==> ∀x[M]. P(x)

lemma rspec:

      [| ∀x[M]. P(x); M(x) |] ==> P(x)

lemma rev_rallE:

      [| ∀x[M]. P(x); ¬ M(x) ==> Q; P(x) ==> Q |] ==> Q

lemma rallE:

      [| ∀x[M]. P(x); P(x) ==> Q; ¬ M(x) ==> Q |] ==> Q

lemma rall_triv:

      (∀x[M]. P) <-> (∃x. M(x)) --> P

lemma rall_cong:

      (!!x. M(x) ==> P(x) <-> P'(x)) ==> (∀x[M]. P(x)) <-> (∀x[M]. P'(x))

#### Relativized existential quantifier

lemma rexI:

      [| P(x); M(x) |] ==> ∃x[M]. P(x)

lemma rev_rexI:

      [| M(x); P(x) |] ==> ∃x[M]. P(x)

lemma rexCI:

      [| ∀x[M]. ¬ P(x) ==> P(a); M(a) |] ==> ∃x[M]. P(x)

lemma rexE:

      [| ∃x[M]. P(x); !!x. [| M(x); P(x) |] ==> Q |] ==> Q

lemma rex_triv:

      (∃x[M]. P) <-> (∃x. M(x)) ∧ P

lemma rex_cong:

      (!!x. M(x) ==> P(x) <-> P'(x)) ==> (∃x[M]. P(x)) <-> (∃x[M]. P'(x))

lemma rall_is_ball:

      (∀x[%z. z ∈ A]. P(x)) <-> (∀x∈A. P(x))

lemma rex_is_bex:

      (∃x[%z. z ∈ A]. P(x)) <-> (∃x∈A. P(x))

lemma atomize_rall:

      (!!x. M(x) ==> P(x)) == ∀x[M]. P(x)

lemma rall_simps1:

      (∀x[M]. P(x) ∧ Q) <-> (∀x[M]. P(x)) ∧ ((∀x[M]. False) ∨ Q)

      (∀x[M]. P(x) ∨ Q) <-> (∀x[M]. P(x)) ∨ Q

      (∀x[M]. P(x) --> Q) <-> (∃x[M]. P(x)) --> Q

      ¬ (∀x[M]. P(x)) <-> (∃x[M]. ¬ P(x))

lemma rall_simps2:

      (∀x[M]. P ∧ Q(x)) <-> ((∀x[M]. False) ∨ P) ∧ (∀x[M]. Q(x))

      (∀x[M]. P ∨ Q(x)) <-> P ∨ (∀x[M]. Q(x))

      (∀x[M]. P --> Q(x)) <-> P --> (∀x[M]. Q(x))

lemmas rall_simps:

      (∀x[M]. P(x) ∧ Q) <-> (∀x[M]. P(x)) ∧ ((∀x[M]. False) ∨ Q)

      (∀x[M]. P(x) ∨ Q) <-> (∀x[M]. P(x)) ∨ Q

      (∀x[M]. P(x) --> Q) <-> (∃x[M]. P(x)) --> Q

      ¬ (∀x[M]. P(x)) <-> (∃x[M]. ¬ P(x))

      (∀x[M]. P ∧ Q(x)) <-> ((∀x[M]. False) ∨ P) ∧ (∀x[M]. Q(x))

      (∀x[M]. P ∨ Q(x)) <-> P ∨ (∀x[M]. Q(x))

      (∀x[M]. P --> Q(x)) <-> P --> (∀x[M]. Q(x))

lemmas rall_simps:

      (∀x[M]. P(x) ∧ Q) <-> (∀x[M]. P(x)) ∧ ((∀x[M]. False) ∨ Q)

      (∀x[M]. P(x) ∨ Q) <-> (∀x[M]. P(x)) ∨ Q

      (∀x[M]. P(x) --> Q) <-> (∃x[M]. P(x)) --> Q

      ¬ (∀x[M]. P(x)) <-> (∃x[M]. ¬ P(x))

      (∀x[M]. P ∧ Q(x)) <-> ((∀x[M]. False) ∨ P) ∧ (∀x[M]. Q(x))

      (∀x[M]. P ∨ Q(x)) <-> P ∨ (∀x[M]. Q(x))

      (∀x[M]. P --> Q(x)) <-> P --> (∀x[M]. Q(x))

lemma rall_conj_distrib:

      (∀x[M]. P(x) ∧ Q(x)) <-> (∀x[M]. P(x)) ∧ (∀x[M]. Q(x))

lemma rex_simps1:

      (∃x[M]. P(x) ∧ Q) <-> (∃x[M]. P(x)) ∧ Q

      (∃x[M]. P(x) ∨ Q) <-> (∃x[M]. P(x)) ∨ (∃x[M]. True) ∧ Q

      (∃x[M]. P(x) --> Q) <-> (∀x[M]. P(x)) --> (∃x[M]. True) ∧ Q

      ¬ (∃x[M]. P(x)) <-> (∀x[M]. ¬ P(x))

lemma rex_simps2:

      (∃x[M]. P ∧ Q(x)) <-> P ∧ (∃x[M]. Q(x))

      (∃x[M]. P ∨ Q(x)) <-> (∃x[M]. True) ∧ P ∨ (∃x[M]. Q(x))

      (∃x[M]. P --> Q(x)) <-> (∀x[M]. False) ∨ P --> (∃x[M]. Q(x))

lemmas rex_simps:

      (∃x[M]. P(x) ∧ Q) <-> (∃x[M]. P(x)) ∧ Q

      (∃x[M]. P(x) ∨ Q) <-> (∃x[M]. P(x)) ∨ (∃x[M]. True) ∧ Q

      (∃x[M]. P(x) --> Q) <-> (∀x[M]. P(x)) --> (∃x[M]. True) ∧ Q

      ¬ (∃x[M]. P(x)) <-> (∀x[M]. ¬ P(x))

      (∃x[M]. P ∧ Q(x)) <-> P ∧ (∃x[M]. Q(x))

      (∃x[M]. P ∨ Q(x)) <-> (∃x[M]. True) ∧ P ∨ (∃x[M]. Q(x))

      (∃x[M]. P --> Q(x)) <-> (∀x[M]. False) ∨ P --> (∃x[M]. Q(x))

lemmas rex_simps:

      (∃x[M]. P(x) ∧ Q) <-> (∃x[M]. P(x)) ∧ Q

      (∃x[M]. P(x) ∨ Q) <-> (∃x[M]. P(x)) ∨ (∃x[M]. True) ∧ Q

      (∃x[M]. P(x) --> Q) <-> (∀x[M]. P(x)) --> (∃x[M]. True) ∧ Q

      ¬ (∃x[M]. P(x)) <-> (∀x[M]. ¬ P(x))

      (∃x[M]. P ∧ Q(x)) <-> P ∧ (∃x[M]. Q(x))

      (∃x[M]. P ∨ Q(x)) <-> (∃x[M]. True) ∧ P ∨ (∃x[M]. Q(x))

      (∃x[M]. P --> Q(x)) <-> (∀x[M]. False) ∨ P --> (∃x[M]. Q(x))

lemma rex_disj_distrib:

      (∃x[M]. P(x) ∨ Q(x)) <-> (∃x[M]. P(x)) ∨ (∃x[M]. Q(x))

#### One-point rule for bounded quantifiers

lemma rex_triv_one_point1:

      (∃x[M]. x = a) <-> M(a)

lemma rex_triv_one_point2:

      (∃x[M]. a = x) <-> M(a)

lemma rex_one_point1:

      (∃x[M]. x = a ∧ P(x)) <-> M(a) ∧ P(a)

lemma rex_one_point2:

      (∃x[M]. a = x ∧ P(x)) <-> M(a) ∧ P(a)

lemma rall_one_point1:

      (∀x[M]. x = a --> P(x)) <-> M(a) --> P(a)

lemma rall_one_point2:

      (∀x[M]. a = x --> P(x)) <-> M(a) --> P(a)

#### Sets as Classes

lemma setclass_iff:

      (##A)(x) <-> x ∈ A

lemma rall_setclass_is_ball:

      (∀x[##A]. P(x)) <-> (∀x∈A. P(x))

lemma rex_setclass_is_bex:

      (∃x[##A]. P(x)) <-> (∃x∈A. P(x))