Theorem acexmid 6022

Description: The axiom of choice implies excluded middle. Theorem 1.3 in [Bauer] p. 483.

The statement of the axiom of choice given here is ac2 in the Metamath Proof Explorer (version of 3-Aug-2019). In particular, note that the choice function 𝑦 provides a value when 𝑧 is inhabited (as opposed to nonempty as in some statements of the axiom of choice).

Essentially the same proof can also be found at "The axiom of choice implies instances of EM", [Crosilla], p. "Set-theoretic principles incompatible with intuitionistic logic".

Often referred to as Diaconescu's theorem, or Diaconescu-Goodman-Myhill theorem, after Radu Diaconescu who discovered it in 1975 in the framework of topos theory and N. D. Goodman and John Myhill in 1978 in the framework of set theory (although it already appeared as an exercise in Errett Bishop's book Foundations of Constructive Analysis from 1967).

For this theorem stated using the df-ac 7426 and df-exmid 4287 syntaxes, see exmidac 7429. (Contributed by Jim Kingdon, 4-Aug-2019.)

Hypothesis

Ref	Expression
acexmid.choice	⊢ ∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)

Assertion

Ref	Expression
acexmid	⊢ (𝜑 ∨ ¬ 𝜑)

Distinct variable group:   𝑥,𝑦,𝑧,𝑤,𝑣,𝑢

Allowed substitution hints:   𝜑(𝑥,𝑦,𝑧,𝑤,𝑣,𝑢)

Proof of Theorem acexmid

Dummy variables 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		nfv 1576	. . . . . . . . . . . . . 14 ⊢ Ⅎ𝑣(𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒))
2	1	sb8eu 2091	. . . . . . . . . . . . 13 ⊢ (∃!𝑓(𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)) ↔ ∃!𝑣[𝑣 / 𝑓](𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)))
3		eleq12 2295	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑓 = 𝑣 ∧ 𝑐 = 𝑧) → (𝑓 ∈ 𝑐 ↔ 𝑣 ∈ 𝑧))
4	3	ancoms 268	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑐 = 𝑧 ∧ 𝑓 = 𝑣) → (𝑓 ∈ 𝑐 ↔ 𝑣 ∈ 𝑧))
5	4	3adant3 1043	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑐 = 𝑧 ∧ 𝑓 = 𝑣 ∧ 𝑏 = 𝑦) → (𝑓 ∈ 𝑐 ↔ 𝑣 ∈ 𝑧))
6		eleq12 2295	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑐 = 𝑧 ∧ 𝑒 = 𝑢) → (𝑐 ∈ 𝑒 ↔ 𝑧 ∈ 𝑢))
7	6	3ad2antl1 1185	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑐 = 𝑧 ∧ 𝑓 = 𝑣 ∧ 𝑏 = 𝑦) ∧ 𝑒 = 𝑢) → (𝑐 ∈ 𝑒 ↔ 𝑧 ∈ 𝑢))
8		eleq12 2295	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑓 = 𝑣 ∧ 𝑒 = 𝑢) → (𝑓 ∈ 𝑒 ↔ 𝑣 ∈ 𝑢))
9	8	3ad2antl2 1186	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑐 = 𝑧 ∧ 𝑓 = 𝑣 ∧ 𝑏 = 𝑦) ∧ 𝑒 = 𝑢) → (𝑓 ∈ 𝑒 ↔ 𝑣 ∈ 𝑢))
10	7, 9	anbi12d 473	. . . . . . . . . . . . . . . . . . 19 ⊢ (((𝑐 = 𝑧 ∧ 𝑓 = 𝑣 ∧ 𝑏 = 𝑦) ∧ 𝑒 = 𝑢) → ((𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
11		simpl3 1028	. . . . . . . . . . . . . . . . . . 19 ⊢ (((𝑐 = 𝑧 ∧ 𝑓 = 𝑣 ∧ 𝑏 = 𝑦) ∧ 𝑒 = 𝑢) → 𝑏 = 𝑦)
12	10, 11	cbvrexdva2 2774	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑐 = 𝑧 ∧ 𝑓 = 𝑣 ∧ 𝑏 = 𝑦) → (∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
13	5, 12	anbi12d 473	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑐 = 𝑧 ∧ 𝑓 = 𝑣 ∧ 𝑏 = 𝑦) → ((𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)) ↔ (𝑣 ∈ 𝑧 ∧ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢))))
14	13	3com23 1235	. . . . . . . . . . . . . . . 16 ⊢ ((𝑐 = 𝑧 ∧ 𝑏 = 𝑦 ∧ 𝑓 = 𝑣) → ((𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)) ↔ (𝑣 ∈ 𝑧 ∧ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢))))
15	14	3expa 1229	. . . . . . . . . . . . . . 15 ⊢ (((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) ∧ 𝑓 = 𝑣) → ((𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)) ↔ (𝑣 ∈ 𝑧 ∧ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢))))
16	15	sbiedv 1836	. . . . . . . . . . . . . 14 ⊢ ((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) → ([𝑣 / 𝑓](𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)) ↔ (𝑣 ∈ 𝑧 ∧ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢))))
17	16	eubidv 2086	. . . . . . . . . . . . 13 ⊢ ((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) → (∃!𝑣[𝑣 / 𝑓](𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)) ↔ ∃!𝑣(𝑣 ∈ 𝑧 ∧ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢))))
18	2, 17	bitrid 192	. . . . . . . . . . . 12 ⊢ ((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) → (∃!𝑓(𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)) ↔ ∃!𝑣(𝑣 ∈ 𝑧 ∧ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢))))
19		df-reu 2516	. . . . . . . . . . . 12 ⊢ (∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∃!𝑓(𝑓 ∈ 𝑐 ∧ ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)))
20		df-reu 2516	. . . . . . . . . . . 12 ⊢ (∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢) ↔ ∃!𝑣(𝑣 ∈ 𝑧 ∧ ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
21	18, 19, 20	3bitr4g 223	. . . . . . . . . . 11 ⊢ ((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) → (∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
22	21	adantr 276	. . . . . . . . . 10 ⊢ (((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) ∧ 𝑑 = 𝑤) → (∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
23		simpll 527	. . . . . . . . . 10 ⊢ (((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) ∧ 𝑑 = 𝑤) → 𝑐 = 𝑧)
24	22, 23	cbvraldva2 2773	. . . . . . . . 9 ⊢ ((𝑐 = 𝑧 ∧ 𝑏 = 𝑦) → (∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
25	24	ancoms 268	. . . . . . . 8 ⊢ ((𝑏 = 𝑦 ∧ 𝑐 = 𝑧) → (∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
26	25	adantll 476	. . . . . . 7 ⊢ (((𝑎 = 𝑥 ∧ 𝑏 = 𝑦) ∧ 𝑐 = 𝑧) → (∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
27		simpll 527	. . . . . . 7 ⊢ (((𝑎 = 𝑥 ∧ 𝑏 = 𝑦) ∧ 𝑐 = 𝑧) → 𝑎 = 𝑥)
28	26, 27	cbvraldva2 2773	. . . . . 6 ⊢ ((𝑎 = 𝑥 ∧ 𝑏 = 𝑦) → (∀𝑐 ∈ 𝑎 ∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
29	28	cbvexdva 1977	. . . . 5 ⊢ (𝑎 = 𝑥 → (∃𝑏∀𝑐 ∈ 𝑎 ∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)))
30	29	cbvalv 1965	. . . 4 ⊢ (∀𝑎∃𝑏∀𝑐 ∈ 𝑎 ∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒) ↔ ∀𝑥∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢))
31		acexmid.choice	. . . 4 ⊢ ∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)
32	30, 31	mpgbir 1501	. . 3 ⊢ ∀𝑎∃𝑏∀𝑐 ∈ 𝑎 ∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)
33	32	spi 1584	. 2 ⊢ ∃𝑏∀𝑐 ∈ 𝑎 ∀𝑑 ∈ 𝑐 ∃!𝑓 ∈ 𝑐 ∃𝑒 ∈ 𝑏 (𝑐 ∈ 𝑒 ∧ 𝑓 ∈ 𝑒)
34	33	acexmidlemv 6021	1 ⊢ (𝜑 ∨ ¬ 𝜑)

Syntax hints:  ¬ wn 3   ∧ wa 104   ↔ wb 105   ∨ wo 715   ∧ w3a 1004  ∀wal 1395  ∃wex 1540  [wsb 1809  ∃!weu 2078  ∀wral 2509  ∃wrex 2510  ∃!wreu 2511

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 619  ax-in2 620  ax-io 716  ax-5 1495  ax-7 1496  ax-gen 1497  ax-ie1 1541  ax-ie2 1542  ax-8 1552  ax-10 1553  ax-11 1554  ax-i12 1555  ax-bndl 1557  ax-4 1558  ax-17 1574  ax-i9 1578  ax-ial 1582  ax-i5r 1583  ax-14 2204  ax-ext 2212  ax-sep 4208  ax-nul 4216  ax-pow 4266  ax-pr 4301

This theorem depends on definitions:  df-bi 117  df-3or 1005  df-3an 1006  df-tru 1400  df-nf 1509  df-sb 1810  df-eu 2081  df-clab 2217  df-cleq 2223  df-clel 2226  df-nfc 2362  df-ral 2514  df-rex 2515  df-reu 2516  df-rab 2518  df-v 2803  df-sbc 3031  df-dif 3201  df-un 3203  df-in 3205  df-ss 3212  df-nul 3494  df-pw 3655  df-sn 3676  df-pr 3677  df-uni 3895  df-tr 4189  df-iord 4465  df-on 4467  df-suc 4470  df-iota 5288  df-riota 5976

This theorem is referenced by: (None)