MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  ac10ct Structured version   Visualization version   GIF version

Theorem ac10ct 10011
Description: A proof of the well-ordering theorem weth 10472, an Axiom of Choice equivalent, restricted to sets dominated by some ordinal (in particular finite sets and countable sets), proven in ZF without AC. (Contributed by Mario Carneiro, 5-Jan-2013.)
Assertion
Ref Expression
ac10ct (∃𝑦 ∈ On 𝐴𝑦 → ∃𝑥 𝑥 We 𝐴)
Distinct variable group:   𝑥,𝐴,𝑦

Proof of Theorem ac10ct
Dummy variables 𝑓 𝑤 𝑧 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 vex 3477 . . . . . 6 𝑦 ∈ V
21brdom 8939 . . . . 5 (𝐴𝑦 ↔ ∃𝑓 𝑓:𝐴1-1𝑦)
3 f1f 6774 . . . . . . . . . . . 12 (𝑓:𝐴1-1𝑦𝑓:𝐴𝑦)
43frnd 6712 . . . . . . . . . . 11 (𝑓:𝐴1-1𝑦 → ran 𝑓𝑦)
5 onss 7755 . . . . . . . . . . 11 (𝑦 ∈ On → 𝑦 ⊆ On)
6 sstr2 3985 . . . . . . . . . . 11 (ran 𝑓𝑦 → (𝑦 ⊆ On → ran 𝑓 ⊆ On))
74, 5, 6syl2im 40 . . . . . . . . . 10 (𝑓:𝐴1-1𝑦 → (𝑦 ∈ On → ran 𝑓 ⊆ On))
8 epweon 7745 . . . . . . . . . 10 E We On
9 wess 5656 . . . . . . . . . 10 (ran 𝑓 ⊆ On → ( E We On → E We ran 𝑓))
107, 8, 9syl6mpi 67 . . . . . . . . 9 (𝑓:𝐴1-1𝑦 → (𝑦 ∈ On → E We ran 𝑓))
1110adantl 482 . . . . . . . 8 ((𝐴𝑦𝑓:𝐴1-1𝑦) → (𝑦 ∈ On → E We ran 𝑓))
12 f1f1orn 6831 . . . . . . . . . 10 (𝑓:𝐴1-1𝑦𝑓:𝐴1-1-onto→ran 𝑓)
13 eqid 2731 . . . . . . . . . . 11 {⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} = {⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)}
1413f1owe 7334 . . . . . . . . . 10 (𝑓:𝐴1-1-onto→ran 𝑓 → ( E We ran 𝑓 → {⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} We 𝐴))
1512, 14syl 17 . . . . . . . . 9 (𝑓:𝐴1-1𝑦 → ( E We ran 𝑓 → {⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} We 𝐴))
16 weinxp 5752 . . . . . . . . . 10 ({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} We 𝐴 ↔ ({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴)) We 𝐴)
17 reldom 8928 . . . . . . . . . . . 12 Rel ≼
1817brrelex1i 5724 . . . . . . . . . . 11 (𝐴𝑦𝐴 ∈ V)
19 sqxpexg 7725 . . . . . . . . . . 11 (𝐴 ∈ V → (𝐴 × 𝐴) ∈ V)
20 incom 4197 . . . . . . . . . . . 12 ((𝐴 × 𝐴) ∩ {⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)}) = ({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴))
21 inex1g 5312 . . . . . . . . . . . 12 ((𝐴 × 𝐴) ∈ V → ((𝐴 × 𝐴) ∩ {⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)}) ∈ V)
2220, 21eqeltrrid 2837 . . . . . . . . . . 11 ((𝐴 × 𝐴) ∈ V → ({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴)) ∈ V)
23 weeq1 5657 . . . . . . . . . . . 12 (𝑥 = ({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴)) → (𝑥 We 𝐴 ↔ ({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴)) We 𝐴))
2423spcegv 3584 . . . . . . . . . . 11 (({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴)) ∈ V → (({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴)) We 𝐴 → ∃𝑥 𝑥 We 𝐴))
2518, 19, 22, 244syl 19 . . . . . . . . . 10 (𝐴𝑦 → (({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} ∩ (𝐴 × 𝐴)) We 𝐴 → ∃𝑥 𝑥 We 𝐴))
2616, 25biimtrid 241 . . . . . . . . 9 (𝐴𝑦 → ({⟨𝑤, 𝑧⟩ ∣ (𝑓𝑤) E (𝑓𝑧)} We 𝐴 → ∃𝑥 𝑥 We 𝐴))
2715, 26sylan9r 509 . . . . . . . 8 ((𝐴𝑦𝑓:𝐴1-1𝑦) → ( E We ran 𝑓 → ∃𝑥 𝑥 We 𝐴))
2811, 27syld 47 . . . . . . 7 ((𝐴𝑦𝑓:𝐴1-1𝑦) → (𝑦 ∈ On → ∃𝑥 𝑥 We 𝐴))
2928impancom 452 . . . . . 6 ((𝐴𝑦𝑦 ∈ On) → (𝑓:𝐴1-1𝑦 → ∃𝑥 𝑥 We 𝐴))
3029exlimdv 1936 . . . . 5 ((𝐴𝑦𝑦 ∈ On) → (∃𝑓 𝑓:𝐴1-1𝑦 → ∃𝑥 𝑥 We 𝐴))
312, 30biimtrid 241 . . . 4 ((𝐴𝑦𝑦 ∈ On) → (𝐴𝑦 → ∃𝑥 𝑥 We 𝐴))
3231ex 413 . . 3 (𝐴𝑦 → (𝑦 ∈ On → (𝐴𝑦 → ∃𝑥 𝑥 We 𝐴)))
3332pm2.43b 55 . 2 (𝑦 ∈ On → (𝐴𝑦 → ∃𝑥 𝑥 We 𝐴))
3433rexlimiv 3147 1 (∃𝑦 ∈ On 𝐴𝑦 → ∃𝑥 𝑥 We 𝐴)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 396  wex 1781  wcel 2106  wrex 3069  Vcvv 3473  cin 3943  wss 3944   class class class wbr 5141  {copab 5203   E cep 5572   We wwe 5623   × cxp 5667  ran crn 5670  Oncon0 6353  1-1wf1 6529  1-1-ontowf1o 6531  cfv 6532  cdom 8920
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2702  ax-rep 5278  ax-sep 5292  ax-nul 5299  ax-pow 5356  ax-pr 5420  ax-un 7708
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3or 1088  df-3an 1089  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2533  df-eu 2562  df-clab 2709  df-cleq 2723  df-clel 2809  df-ne 2940  df-ral 3061  df-rex 3070  df-rab 3432  df-v 3475  df-dif 3947  df-un 3949  df-in 3951  df-ss 3961  df-pss 3963  df-nul 4319  df-if 4523  df-pw 4598  df-sn 4623  df-pr 4625  df-op 4629  df-uni 4902  df-br 5142  df-opab 5204  df-tr 5259  df-id 5567  df-eprel 5573  df-po 5581  df-so 5582  df-fr 5624  df-we 5626  df-xp 5675  df-rel 5676  df-cnv 5677  df-co 5678  df-dm 5679  df-rn 5680  df-res 5681  df-ima 5682  df-ord 6356  df-on 6357  df-iota 6484  df-fun 6534  df-fn 6535  df-f 6536  df-f1 6537  df-fo 6538  df-f1o 6539  df-fv 6540  df-isom 6541  df-dom 8924
This theorem is referenced by:  ondomen  10014
  Copyright terms: Public domain W3C validator