HOLE Home Higher-Order Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  HOLE Home  >  Th. List  >  exmid Unicode 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 |- T. |= [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 |- T.:*
1211, 4orc 165 . . . . 5 |- T. |= [T. \/ A]
133, 11weqi 76 . . . . . . . 8 |- [x:* = T.]:*
1413id 25 . . . . . . 7 |- [x:* = T.] |= [x:* = T.]
152, 3, 4, 14oveq1 99 . . . . . 6 |- [x:* = T.] |= [[x:* \/ A] = [T. \/ A]]
165, 11, 15cl 116 . . . . 5 |- T. |= [(\x:* [x:* \/ A]T.) = [T. \/ A]]
1712, 16mpbir 87 . . . 4 |- T. |= (\x:* [x:* \/ A]T.)
186, 11ac 197 . . . 4 |- (\x:* [x:* \/ A]T.) |= (\x:* [x:* \/ A](@\x:* [x:* \/ A]))
1917, 18syl 16 . . 3 |- T. |= (\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 |- T. |= [(\x:* \/ y:*) = \/ ]
251, 23ax-17 105 . . . . . 6 |- T. |= [(\x:* @y:*) = @]
265, 23ax-hbl1 103 . . . . . 6 |- T. |= [(\x:* \x:* [x:* \/ A]y:*) = \x:* [x:* \/ A]]
271, 6, 23, 25, 26hbc 110 . . . . 5 |- T. |= [(\x:* (@\x:* [x:* \/ A])y:*) = (@\x:* [x:* \/ A])]
284, 23ax-17 105 . . . . 5 |- T. |= [(\x:* Ay:*) = A]
292, 7, 23, 4, 24, 27, 28hbov 111 . . . 4 |- T. |= [(\x:* [(@\x:* [x:* \/ A]) \/ A]y:*) = [(@\x:* [x:* \/ A]) \/ A]]
305, 7, 22, 29, 27clf 115 . . 3 |- T. |= [(\x:* [x:* \/ A](@\x:* [x:* \/ A])) = [(@\x:* [x:* \/ A]) \/ A]]
3119, 30mpbi 82 . 2 |- T. |= [(@\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 |- F.:*
383, 37weqi 76 . . . . . . . . . . . . 13 |- [x:* = F.]:*
3938id 25 . . . . . . . . . . . 12 |- [x:* = F.] |= [x:* = F.]
408, 3, 39ceq2 90 . . . . . . . . . . 11 |- [x:* = F.] |= [(~ x:*) = (~ F.)]
4111, 37simpr 23 . . . . . . . . . . . . . . . 16 |- (T., F.) |= F.
4241ex 158 . . . . . . . . . . . . . . 15 |- T. |= [F. ==> F.]
4337notval 145 . . . . . . . . . . . . . . 15 |- T. |= [(~ F.) = [F. ==> F.]]
4442, 43mpbir 87 . . . . . . . . . . . . . 14 |- T. |= (~ F.)
4544eqtru 86 . . . . . . . . . . . . 13 |- T. |= [T. = (~ F.)]
4611, 45eqcomi 79 . . . . . . . . . . . 12 |- T. |= [(~ F.) = T.]
4738, 46a1i 28 . . . . . . . . . . 11 |- [x:* = F.] |= [(~ F.) = T.]
4832, 40, 47eqtri 95 . . . . . . . . . 10 |- [x:* = F.] |= [(~ x:*) = T.]
492, 32, 4, 48oveq1 99 . . . . . . . . 9 |- [x:* = F.] |= [[(~ x:*) \/ A] = [T. \/ A]]
5033, 37, 49cl 116 . . . . . . . 8 |- T. |= [(\x:* [(~ x:*) \/ A]F.) = [T. \/ A]]
5112, 50mpbir 87 . . . . . . 7 |- T. |= (\x:* [(~ x:*) \/ A]F.)
5234, 37ac 197 . . . . . . 7 |- (\x:* [(~ x:*) \/ A]F.) |= (\x:* [(~ x:*) \/ A](@\x:* [(~ x:*) \/ A]))
5351, 52syl 16 . . . . . 6 |- T. |= (\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 |- T. |= [(\x:* ~ y:*) = ~ ]
5933, 23ax-hbl1 103 . . . . . . . . . 10 |- T. |= [(\x:* \x:* [(~ x:*) \/ A]y:*) = \x:* [(~ x:*) \/ A]]
601, 34, 23, 25, 59hbc 110 . . . . . . . . 9 |- T. |= [(\x:* (@\x:* [(~ x:*) \/ A])y:*) = (@\x:* [(~ x:*) \/ A])]
618, 35, 23, 58, 60hbc 110 . . . . . . . 8 |- T. |= [(\x:* (~ (@\x:* [(~ x:*) \/ A]))y:*) = (~ (@\x:* [(~ x:*) \/ A]))]
622, 36, 23, 4, 24, 61, 28hbov 111 . . . . . . 7 |- T. |= [(\x:* [(~ (@\x:* [(~ x:*) \/ A])) \/ A]y:*) = [(~ (@\x:* [(~ x:*) \/ A])) \/ A]]
6333, 35, 57, 62, 60clf 115 . . . . . 6 |- T. |= [(\x:* [(~ x:*) \/ A](@\x:* [(~ x:*) \/ A])) = [(~ (@\x:* [(~ x:*) \/ A])) \/ A]]
6453, 63mpbi 82 . . . . 5 |- T. |= [(~ (@\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 |= [T. = [x:* \/ A]]
7111, 70eqcomi 79 . . . . . . . . . . . . 13 |- A |= [[x:* \/ A] = T.]
7232, 4olc 164 . . . . . . . . . . . . . 14 |- A |= [(~ x:*) \/ A]
7372eqtru 86 . . . . . . . . . . . . 13 |- A |= [T. = [(~ 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 |- T. |= [(~ (@\x:* [(~ x:*) \/ A])) = [(@\x:* [(~ x:*) \/ A]) ==> F.]]
8280, 81a1i 28 . . . . . . . . 9 |- (((@\x:* [x:* \/ A]), (~ (@\x:* [(~ x:*) \/ A]))), A) |= [(~ (@\x:* [(~ x:*) \/ A])) = [(@\x:* [(~ x:*) \/ A]) ==> F.]]
8379, 82mpbi 82 . . . . . . . 8 |- (((@\x:* [x:* \/ A]), (~ (@\x:* [(~ x:*) \/ A]))), A) |= [(@\x:* [(~ x:*) \/ A]) ==> F.]
8437, 78, 83mpd 156 . . . . . . 7 |- (((@\x:* [x:* \/ A]), (~ (@\x:* [(~ x:*) \/ A]))), A) |= F.
8584ex 158 . . . . . 6 |- ((@\x:* [x:* \/ A]), (~ (@\x:* [(~ x:*) \/ A]))) |= [A ==> F.]
864notval 145 . . . . . . 7 |- T. |= [(~ A) = [A ==> F.]]
8766, 86a1i 28 . . . . . 6 |- ((@\x:* [x:* \/ A]), (~ (@\x:* [(~ x:*) \/ A]))) |= [(~ A) = [A ==> F.]]
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 |- (T., (@\x:* [x:* \/ A])) |= [A \/ (~ A)]
9591, 11adantl 56 . 2 |- (T., A) |= [A \/ (~ A)]
967, 4, 10, 31, 94, 95ecase 163 1 |- T. |= [A \/ (~ A)]
Colors of variables: type var term
Syntax hints:  tv 1   -> ht 2  *hb 3  kc 5  \kl 6   = ke 7  T.kt 8  [kbr 9  kct 10   |= wffMMJ2 11  wffMMJ2t 12  F.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