Theorem nnregexmid 4617

Description: If inhabited sets of natural numbers always have minimal elements, excluded middle follows. The argument is essentially the same as regexmid 4531 and the larger lesson is that although natural numbers may behave "non-constructively" even in a constructive set theory (for example see nndceq 6494 or nntri3or 6488), sets of natural numbers are a different animal. (Contributed by Jim Kingdon, 6-Sep-2019.)

Hypothesis

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

Assertion

Ref	Expression
nnregexmid	⊢ (𝜑 ∨ ¬ 𝜑)

Distinct variable group:   𝜑,𝑥,𝑦,𝑧

Proof of Theorem nnregexmid

Dummy variable 𝑤 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		ssrab2 3240	. . . 4 ⊢ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ⊆ {∅, {∅}}
2		peano1 4590	. . . . 5 ⊢ ∅ ∈ ω
3		suc0 4408	. . . . . 6 ⊢ suc ∅ = {∅}
4		peano2 4591	. . . . . . 7 ⊢ (∅ ∈ ω → suc ∅ ∈ ω)
5	2, 4	ax-mp 5	. . . . . 6 ⊢ suc ∅ ∈ ω
6	3, 5	eqeltrri 2251	. . . . 5 ⊢ {∅} ∈ ω
7		prssi 3749	. . . . 5 ⊢ ((∅ ∈ ω ∧ {∅} ∈ ω) → {∅, {∅}} ⊆ ω)
8	2, 6, 7	mp2an 426	. . . 4 ⊢ {∅, {∅}} ⊆ ω
9	1, 8	sstri 3164	. . 3 ⊢ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ⊆ ω
10		eqid 2177	. . . 4 ⊢ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}
11	10	regexmidlemm 4528	. . 3 ⊢ ∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}
12		pp0ex 4186	. . . . 5 ⊢ {∅, {∅}} ∈ V
13	12	rabex 4144	. . . 4 ⊢ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∈ V
14		sseq1 3178	. . . . . 6 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (𝑥 ⊆ ω ↔ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ⊆ ω))
15		eleq2 2241	. . . . . . 7 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (𝑦 ∈ 𝑥 ↔ 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
16	15	exbidv 1825	. . . . . 6 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (∃𝑦 𝑦 ∈ 𝑥 ↔ ∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
17	14, 16	anbi12d 473	. . . . 5 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ((𝑥 ⊆ ω ∧ ∃𝑦 𝑦 ∈ 𝑥) ↔ ({𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ⊆ ω ∧ ∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))
18		eleq2 2241	. . . . . . . . . 10 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (𝑧 ∈ 𝑥 ↔ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
19	18	notbid 667	. . . . . . . . 9 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (¬ 𝑧 ∈ 𝑥 ↔ ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
20	19	imbi2d 230	. . . . . . . 8 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ((𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥) ↔ (𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))
21	20	albidv 1824	. . . . . . 7 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥) ↔ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))
22	15, 21	anbi12d 473	. . . . . 6 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → ((𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥)) ↔ (𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))))
23	22	exbidv 1825	. . . . 5 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥)) ↔ ∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))))
24	17, 23	imbi12d 234	. . . 4 ⊢ (𝑥 = {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} → (((𝑥 ⊆ ω ∧ ∃𝑦 𝑦 ∈ 𝑥) → ∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥))) ↔ (({𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ⊆ ω ∧ ∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}) → ∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))))
25		nnregexmid.1	. . . 4 ⊢ ((𝑥 ⊆ ω ∧ ∃𝑦 𝑦 ∈ 𝑥) → ∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ 𝑥)))
26	13, 24, 25	vtocl 2791	. . 3 ⊢ (({𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ⊆ ω ∧ ∃𝑦 𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}) → ∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})))
27	9, 11, 26	mp2an 426	. 2 ⊢ ∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))}))
28	10	regexmidlem1 4529	. 2 ⊢ (∃𝑦(𝑦 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))} ∧ ∀𝑧(𝑧 ∈ 𝑦 → ¬ 𝑧 ∈ {𝑤 ∈ {∅, {∅}} ∣ (𝑤 = {∅} ∨ (𝑤 = ∅ ∧ 𝜑))})) → (𝜑 ∨ ¬ 𝜑))
29	27, 28	ax-mp 5	1 ⊢ (𝜑 ∨ ¬ 𝜑)

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 104   ∨ wo 708  ∀wal 1351   = wceq 1353  ∃wex 1492   ∈ wcel 2148  {crab 2459   ⊆ wss 3129  ∅c0 3422  {csn 3591  {cpr 3592  suc csuc 4362  ωcom 4586

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 614  ax-in2 615  ax-io 709  ax-5 1447  ax-7 1448  ax-gen 1449  ax-ie1 1493  ax-ie2 1494  ax-8 1504  ax-10 1505  ax-11 1506  ax-i12 1507  ax-bndl 1509  ax-4 1510  ax-17 1526  ax-i9 1530  ax-ial 1534  ax-i5r 1535  ax-13 2150  ax-14 2151  ax-ext 2159  ax-sep 4118  ax-nul 4126  ax-pow 4171  ax-pr 4206  ax-un 4430

This theorem depends on definitions:  df-bi 117  df-3an 980  df-tru 1356  df-nf 1461  df-sb 1763  df-clab 2164  df-cleq 2170  df-clel 2173  df-nfc 2308  df-ral 2460  df-rex 2461  df-rab 2464  df-v 2739  df-dif 3131  df-un 3133  df-in 3135  df-ss 3142  df-nul 3423  df-pw 3576  df-sn 3597  df-pr 3598  df-uni 3808  df-int 3843  df-suc 4368  df-iom 4587

This theorem is referenced by: (None)