Theorem regexmid 4313

Description: The axiom of foundation implies excluded middle.

By foundation (or regularity), we mean the principle that every inhabited set has an element which is minimal (when arranged by ∈). The statement of foundation here is taken from Metamath Proof Explorer's ax-reg, and is identical (modulo one unnecessary quantifier) to the statement of foundation in Theorem "Foundation implies instances of EM" of [Crosilla], p. "Set-theoretic principles incompatible with intuitionistic logic".

For this reason, IZF does not adopt foundation as an axiom and instead replaces it with ax-setind 4315. (Contributed by Jim Kingdon, 3-Sep-2019.)

Hypothesis

Ref	Expression
regexmid.1	⊢ (∃𝑦 𝑦 ∈ 𝑥 → ∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥)))

Assertion

Ref	Expression
regexmid	⊢ (𝜑 ∨ ¬ 𝜑)

Distinct variable group:   𝜑,𝑥,𝑦,𝑧

Proof of Theorem regexmid

Dummy variable 𝑤 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		eqid 2083	. . 3 ⊢ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}
2	1	regexmidlemm 4310	. 2 ⊢ ∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}
3		pp0ex 3987	. . . 4 ⊢ {∅, {∅}} ∈ V
4	3	rabex 3948	. . 3 ⊢ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∈ V
5		eleq2 2146	. . . . 5 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (𝑦 ∈ 𝑥 ↔ 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
6	5	exbidv 1748	. . . 4 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (∃𝑦 𝑦 ∈ 𝑥 ↔ ∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
7		eleq2 2146	. . . . . . . . 9 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (𝑧 ∈ 𝑥 ↔ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
8	7	notbid 625	. . . . . . . 8 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (¬ 𝑧 ∈ 𝑥 ↔ ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
9	8	imbi2d 228	. . . . . . 7 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ((𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥) ↔ (𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))
10	9	albidv 1747	. . . . . 6 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥) ↔ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))
11	5, 10	anbi12d 457	. . . . 5 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ((𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥)) ↔ (𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))))
12	11	exbidv 1748	. . . 4 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥)) ↔ ∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))))
13	6, 12	imbi12d 232	. . 3 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ((∃𝑦 𝑦 ∈ 𝑥 → ∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥))) ↔ (∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))))
14		regexmid.1	. . 3 ⊢ (∃𝑦 𝑦 ∈ 𝑥 → ∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥)))
15	4, 13, 14	vtocl 2664	. 2 ⊢ (∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))
16	1	regexmidlem1 4311	. 2 ⊢ (∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})) → (𝜑 ∨ ¬ 𝜑))
17	2, 15, 16	mp2b 8	1 ⊢ (𝜑 ∨ ¬ 𝜑)

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 102   ∨ wo 662  ∀wal 1283   = wceq 1285  ∃wex 1422   ∈ wcel 1434  {crab 2357  ∅c0 3269  {csn 3422  {cpr 3423

This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 577  ax-in2 578  ax-io 663  ax-5 1377  ax-7 1378  ax-gen 1379  ax-ie1 1423  ax-ie2 1424  ax-8 1436  ax-10 1437  ax-11 1438  ax-i12 1439  ax-bndl 1440  ax-4 1441  ax-14 1446  ax-17 1460  ax-i9 1464  ax-ial 1468  ax-i5r 1469  ax-ext 2065  ax-sep 3922  ax-nul 3930  ax-pow 3974

This theorem depends on definitions:  df-bi 115  df-tru 1288  df-nf 1391  df-sb 1688  df-clab 2070  df-cleq 2076  df-clel 2079  df-nfc 2212  df-rab 2362  df-v 2614  df-dif 2986  df-un 2988  df-in 2990  df-ss 2997  df-nul 3270  df-pw 3408  df-sn 3428  df-pr 3429

This theorem is referenced by: (None)