HOLE Home Higher-Order Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  HOLE Home  >  Th. List  >  exmid GIF version

Theorem exmid 199
Description: Diaconescu's theorem, which derives the law of the excluded middle from the axiom of choice. (Contributed by Mario Carneiro, 10-Oct-2014.)
Hypothesis
Ref Expression
exmid.1 A:∗
Assertion
Ref Expression
exmid ⊤⊧[A A)]

Proof of Theorem exmid
Dummy variables x y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 wat 193 . . 3 ε:((∗ → ∗) → ∗)
2 wor 140 . . . . 5 :(∗ → (∗ → ∗))
3 wv 64 . . . . 5 x:∗:∗
4 exmid.1 . . . . 5 A:∗
52, 3, 4wov 72 . . . 4 [x:∗ A]:∗
65wl 66 . . 3 λx:∗ [x:∗ A]:(∗ → ∗)
71, 6wc 50 . 2 λx:∗ [x:∗ A]):∗
8 wnot 138 . . . 4 ¬ :(∗ → ∗)
98, 4wc 50 . . 3 A):∗
102, 4, 9wov 72 . 2 [A A)]:∗
11 wtru 43 . . . . . 6 ⊤:∗
1211, 4orc 165 . . . . 5 ⊤⊧[⊤ A]
133, 11weqi 76 . . . . . . . 8 [x:∗ = ⊤]:∗
1413id 25 . . . . . . 7 [x:∗ = ⊤]⊧[x:∗ = ⊤]
152, 3, 4, 14oveq1 99 . . . . . 6 [x:∗ = ⊤]⊧[[x:∗ A] = [⊤ A]]
165, 11, 15cl 116 . . . . 5 ⊤⊧[(λx:∗ [x:∗ A]⊤) = [⊤ A]]
1712, 16mpbir 87 . . . 4 ⊤⊧(λx:∗ [x:∗ A]⊤)
186, 11ac 197 . . . 4 (λx:∗ [x:∗ A]⊤)⊧(λx:∗ [x:∗ A](ελx:∗ [x:∗ A]))
1917, 18syl 16 . . 3 ⊤⊧(λx:∗ [x:∗ A](ελx:∗ [x:∗ A]))
203, 7weqi 76 . . . . . 6 [x:∗ = (ελx:∗ [x:∗ A])]:∗
2120id 25 . . . . 5 [x:∗ = (ελx:∗ [x:∗ A])]⊧[x:∗ = (ελx:∗ [x:∗ A])]
222, 3, 4, 21oveq1 99 . . . 4 [x:∗ = (ελx:∗ [x:∗ A])]⊧[[x:∗ A] = [(ελx:∗ [x:∗ A]) A]]
23 wv 64 . . . . 5 y:∗:∗
242, 23ax-17 105 . . . . 5 ⊤⊧[(λx:∗ y:∗) = ]
251, 23ax-17 105 . . . . . 6 ⊤⊧[(λx:∗ εy:∗) = ε]
265, 23ax-hbl1 103 . . . . . 6 ⊤⊧[(λx:∗ λx:∗ [x:∗ A]y:∗) = λx:∗ [x:∗ A]]
271, 6, 23, 25, 26hbc 110 . . . . 5 ⊤⊧[(λx:∗ (ελx:∗ [x:∗ A])y:∗) = (ελx:∗ [x:∗ A])]
284, 23ax-17 105 . . . . 5 ⊤⊧[(λx:∗ Ay:∗) = A]
292, 7, 23, 4, 24, 27, 28hbov 111 . . . 4 ⊤⊧[(λx:∗ [(ελx:∗ [x:∗ A]) A]y:∗) = [(ελx:∗ [x:∗ A]) A]]
305, 7, 22, 29, 27clf 115 . . 3 ⊤⊧[(λx:∗ [x:∗ A](ελx:∗ [x:∗ A])) = [(ελx:∗ [x:∗ A]) A]]
3119, 30mpbi 82 . 2 ⊤⊧[(ελx:∗ [x:∗ A]) A]
328, 3wc 50 . . . . . . . 8 x:∗):∗
332, 32, 4wov 72 . . . . . . 7 [(¬ x:∗) A]:∗
3433wl 66 . . . . . 6 λx:∗ [(¬ x:∗) A]:(∗ → ∗)
351, 34wc 50 . . . . 5 λx:∗ [(¬ x:∗) A]):∗
368, 35wc 50 . . . 4 (¬ (ελx:∗ [(¬ x:∗) A])):∗
37 wfal 135 . . . . . . . . 9 ⊥:∗
383, 37weqi 76 . . . . . . . . . . . . 13 [x:∗ = ⊥]:∗
3938id 25 . . . . . . . . . . . 12 [x:∗ = ⊥]⊧[x:∗ = ⊥]
408, 3, 39ceq2 90 . . . . . . . . . . 11 [x:∗ = ⊥]⊧[(¬ x:∗) = (¬ ⊥)]
4111, 37simpr 23 . . . . . . . . . . . . . . . 16 (⊤, ⊥)⊧⊥
4241ex 158 . . . . . . . . . . . . . . 15 ⊤⊧[⊥ ⇒ ⊥]
4337notval 145 . . . . . . . . . . . . . . 15 ⊤⊧[(¬ ⊥) = [⊥ ⇒ ⊥]]
4442, 43mpbir 87 . . . . . . . . . . . . . 14 ⊤⊧(¬ ⊥)
4544eqtru 86 . . . . . . . . . . . . 13 ⊤⊧[⊤ = (¬ ⊥)]
4611, 45eqcomi 79 . . . . . . . . . . . 12 ⊤⊧[(¬ ⊥) = ⊤]
4738, 46a1i 28 . . . . . . . . . . 11 [x:∗ = ⊥]⊧[(¬ ⊥) = ⊤]
4832, 40, 47eqtri 95 . . . . . . . . . 10 [x:∗ = ⊥]⊧[(¬ x:∗) = ⊤]
492, 32, 4, 48oveq1 99 . . . . . . . . 9 [x:∗ = ⊥]⊧[[(¬ x:∗) A] = [⊤ A]]
5033, 37, 49cl 116 . . . . . . . 8 ⊤⊧[(λx:∗ [(¬ x:∗) A]⊥) = [⊤ A]]
5112, 50mpbir 87 . . . . . . 7 ⊤⊧(λx:∗ [(¬ x:∗) A]⊥)
5234, 37ac 197 . . . . . . 7 (λx:∗ [(¬ x:∗) A]⊥)⊧(λx:∗ [(¬ x:∗) A](ελx:∗ [(¬ x:∗) A]))
5351, 52syl 16 . . . . . 6 ⊤⊧(λx:∗ [(¬ x:∗) A](ελx:∗ [(¬ x:∗) A]))
543, 35weqi 76 . . . . . . . . . 10 [x:∗ = (ελx:∗ [(¬ x:∗) A])]:∗
5554id 25 . . . . . . . . 9 [x:∗ = (ελx:∗ [(¬ x:∗) A])]⊧[x:∗ = (ελx:∗ [(¬ x:∗) A])]
568, 3, 55ceq2 90 . . . . . . . 8 [x:∗ = (ελx:∗ [(¬ x:∗) A])]⊧[(¬ x:∗) = (¬ (ελx:∗ [(¬ x:∗) A]))]
572, 32, 4, 56oveq1 99 . . . . . . 7 [x:∗ = (ελx:∗ [(¬ x:∗) A])]⊧[[(¬ x:∗) A] = [(¬ (ελx:∗ [(¬ x:∗) A])) A]]
588, 23ax-17 105 . . . . . . . . 9 ⊤⊧[(λx:∗ ¬ y:∗) = ¬ ]
5933, 23ax-hbl1 103 . . . . . . . . . 10 ⊤⊧[(λx:∗ λx:∗ [(¬ x:∗) A]y:∗) = λx:∗ [(¬ x:∗) A]]
601, 34, 23, 25, 59hbc 110 . . . . . . . . 9 ⊤⊧[(λx:∗ (ελx:∗ [(¬ x:∗) A])y:∗) = (ελx:∗ [(¬ x:∗) A])]
618, 35, 23, 58, 60hbc 110 . . . . . . . 8 ⊤⊧[(λx:∗ (¬ (ελx:∗ [(¬ x:∗) A]))y:∗) = (¬ (ελx:∗ [(¬ x:∗) A]))]
622, 36, 23, 4, 24, 61, 28hbov 111 . . . . . . 7 ⊤⊧[(λx:∗ [(¬ (ελx:∗ [(¬ x:∗) A])) A]y:∗) = [(¬ (ελx:∗ [(¬ x:∗) A])) A]]
6333, 35, 57, 62, 60clf 115 . . . . . 6 ⊤⊧[(λx:∗ [(¬ x:∗) A](ελx:∗ [(¬ x:∗) A])) = [(¬ (ελx:∗ [(¬ x:∗) A])) A]]
6453, 63mpbi 82 . . . . 5 ⊤⊧[(¬ (ελx:∗ [(¬ x:∗) A])) A]
657, 64a1i 28 . . . 4 λx:∗ [x:∗ A])⊧[(¬ (ελx:∗ [(¬ x:∗) A])) A]
667, 36wct 48 . . . . . . . . . . 11 ((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))):∗
6766, 4simpl 22 . . . . . . . . . 10 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A])))
6867simpld 37 . . . . . . . . 9 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧(ελx:∗ [x:∗ A])
693, 4olc 164 . . . . . . . . . . . . . . 15 A⊧[x:∗ A]
7069eqtru 86 . . . . . . . . . . . . . 14 A⊧[⊤ = [x:∗ A]]
7111, 70eqcomi 79 . . . . . . . . . . . . 13 A⊧[[x:∗ A] = ⊤]
7232, 4olc 164 . . . . . . . . . . . . . 14 A⊧[(¬ x:∗) A]
7372eqtru 86 . . . . . . . . . . . . 13 A⊧[⊤ = [(¬ x:∗) A]]
745, 71, 73eqtri 95 . . . . . . . . . . . 12 A⊧[[x:∗ A] = [(¬ x:∗) A]]
755, 74leq 91 . . . . . . . . . . 11 A⊧[λx:∗ [x:∗ A] = λx:∗ [(¬ x:∗) A]]
761, 6, 75ceq2 90 . . . . . . . . . 10 A⊧[(ελx:∗ [x:∗ A]) = (ελx:∗ [(¬ x:∗) A])]
7776, 66adantl 56 . . . . . . . . 9 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧[(ελx:∗ [x:∗ A]) = (ελx:∗ [(¬ x:∗) A])]
7868, 77mpbi 82 . . . . . . . 8 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧(ελx:∗ [(¬ x:∗) A])
7967simprd 38 . . . . . . . . 9 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧(¬ (ελx:∗ [(¬ x:∗) A]))
8067ax-cb1 29 . . . . . . . . . 10 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A):∗
8135notval 145 . . . . . . . . . 10 ⊤⊧[(¬ (ελx:∗ [(¬ x:∗) A])) = [(ελx:∗ [(¬ x:∗) A]) ⇒ ⊥]]
8280, 81a1i 28 . . . . . . . . 9 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧[(¬ (ελx:∗ [(¬ x:∗) A])) = [(ελx:∗ [(¬ x:∗) A]) ⇒ ⊥]]
8379, 82mpbi 82 . . . . . . . 8 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧[(ελx:∗ [(¬ x:∗) A]) ⇒ ⊥]
8437, 78, 83mpd 156 . . . . . . 7 (((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A]))), A)⊧⊥
8584ex 158 . . . . . 6 ((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A])))⊧[A ⇒ ⊥]
864notval 145 . . . . . . 7 ⊤⊧[(¬ A) = [A ⇒ ⊥]]
8766, 86a1i 28 . . . . . 6 ((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A])))⊧[(¬ A) = [A ⇒ ⊥]]
8885, 87mpbir 87 . . . . 5 ((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A])))⊧(¬ A)
894, 9olc 164 . . . . 5 A)⊧[A A)]
9088, 89syl 16 . . . 4 ((ελx:∗ [x:∗ A]), (¬ (ελx:∗ [(¬ x:∗) A])))⊧[A A)]
914, 9orc 165 . . . . 5 A⊧[A A)]
9291, 7adantl 56 . . . 4 ((ελx:∗ [x:∗ A]), A)⊧[A A)]
9336, 4, 10, 65, 90, 92ecase 163 . . 3 λx:∗ [x:∗ A])⊧[A A)]
9493, 11adantl 56 . 2 (⊤, (ελx:∗ [x:∗ A]))⊧[A A)]
9591, 11adantl 56 . 2 (⊤, A)⊧[A A)]
967, 4, 10, 31, 94, 95ecase 163 1 ⊤⊧[A A)]
Colors of variables: type var term
Syntax hints:  tv 1  ht 2  hb 3  kc 5  λkl 6   = ke 7  kt 8  [kbr 9  kct 10  wffMMJ2 11  wffMMJ2t 12  tfal 118  ¬ tne 120  tim 121   tor 124  εtat 191
This theorem was proved from axioms:  ax-syl 15  ax-jca 17  ax-simpl 20  ax-simpr 21  ax-id 24  ax-trud 26  ax-cb1 29  ax-cb2 30  ax-wctl 31  ax-wctr 32  ax-weq 40  ax-refl 42  ax-eqmp 45  ax-ded 46  ax-wct 47  ax-wc 49  ax-ceq 51  ax-wv 63  ax-wl 65  ax-beta 67  ax-distrc 68  ax-leq 69  ax-distrl 70  ax-wov 71  ax-eqtypi 77  ax-eqtypri 80  ax-hbl1 103  ax-17 105  ax-inst 113  ax-wat 192  ax-ac 196
This theorem depends on definitions:  df-ov 73  df-al 126  df-fal 127  df-an 128  df-im 129  df-not 130  df-or 132
This theorem is referenced by:  notnot  200  ax3  205
  Copyright terms: Public domain W3C validator