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

Theorem fpwwe 9903
Description: Given any function 𝐹 from the powerset of 𝐴 to 𝐴, canth2 8507 gives that the function is not injective, but we can say rather more than that. There is a unique well-ordered subset 𝑋, (𝑊𝑋)⟩ which "agrees" with 𝐹 in the sense that each initial segment maps to its upper bound, and such that the entire set maps to an element of the set (so that it cannot be extended without losing the well-ordering). This theorem can be used to prove dfac8a 9291. Theorem 1.1 of [KanamoriPincus] p. 415. (Contributed by Mario Carneiro, 18-May-2015.)
Hypotheses
Ref Expression
fpwwe.1 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 (𝐹‘(𝑟 “ {𝑦})) = 𝑦))}
fpwwe.2 (𝜑𝐴 ∈ V)
fpwwe.3 ((𝜑𝑥 ∈ (𝒫 𝐴 ∩ dom card)) → (𝐹𝑥) ∈ 𝐴)
fpwwe.4 𝑋 = dom 𝑊
Assertion
Ref Expression
fpwwe (𝜑 → ((𝑌𝑊𝑅 ∧ (𝐹𝑌) ∈ 𝑌) ↔ (𝑌 = 𝑋𝑅 = (𝑊𝑋))))
Distinct variable groups:   𝑥,𝑟,𝐴   𝑦,𝑟,𝐹,𝑥   𝜑,𝑟,𝑥,𝑦   𝑅,𝑟,𝑥,𝑦   𝑋,𝑟,𝑥,𝑦   𝑌,𝑟,𝑥,𝑦   𝑊,𝑟,𝑥,𝑦
Allowed substitution hint:   𝐴(𝑦)

Proof of Theorem fpwwe
Dummy variable 𝑢 is distinct from all other variables.
StepHypRef Expression
1 df-ov 7010 . . . . . 6 (𝑌(𝐹 ∘ 1st )𝑅) = ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩)
2 fo1st 7556 . . . . . . . 8 1st :V–onto→V
3 fofn 6452 . . . . . . . 8 (1st :V–onto→V → 1st Fn V)
42, 3ax-mp 5 . . . . . . 7 1st Fn V
5 opex 5241 . . . . . . 7 𝑌, 𝑅⟩ ∈ V
6 fvco2 6617 . . . . . . 7 ((1st Fn V ∧ ⟨𝑌, 𝑅⟩ ∈ V) → ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩)))
74, 5, 6mp2an 688 . . . . . 6 ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩))
81, 7eqtri 2817 . . . . 5 (𝑌(𝐹 ∘ 1st )𝑅) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩))
9 fpwwe.1 . . . . . . . 8 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 (𝐹‘(𝑟 “ {𝑦})) = 𝑦))}
109bropaex12 5520 . . . . . . 7 (𝑌𝑊𝑅 → (𝑌 ∈ V ∧ 𝑅 ∈ V))
11 op1stg 7548 . . . . . . 7 ((𝑌 ∈ V ∧ 𝑅 ∈ V) → (1st ‘⟨𝑌, 𝑅⟩) = 𝑌)
1210, 11syl 17 . . . . . 6 (𝑌𝑊𝑅 → (1st ‘⟨𝑌, 𝑅⟩) = 𝑌)
1312fveq2d 6534 . . . . 5 (𝑌𝑊𝑅 → (𝐹‘(1st ‘⟨𝑌, 𝑅⟩)) = (𝐹𝑌))
148, 13syl5eq 2841 . . . 4 (𝑌𝑊𝑅 → (𝑌(𝐹 ∘ 1st )𝑅) = (𝐹𝑌))
1514eleq1d 2865 . . 3 (𝑌𝑊𝑅 → ((𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌 ↔ (𝐹𝑌) ∈ 𝑌))
1615pm5.32i 575 . 2 ((𝑌𝑊𝑅 ∧ (𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌) ↔ (𝑌𝑊𝑅 ∧ (𝐹𝑌) ∈ 𝑌))
17 vex 3435 . . . . . . . . . . 11 𝑟 ∈ V
1817cnvex 7477 . . . . . . . . . 10 𝑟 ∈ V
1918imaex 7468 . . . . . . . . 9 (𝑟 “ {𝑦}) ∈ V
20 vex 3435 . . . . . . . . . . . 12 𝑢 ∈ V
2117inex1 5106 . . . . . . . . . . . 12 (𝑟 ∩ (𝑢 × 𝑢)) ∈ V
2220, 21algrflem 7663 . . . . . . . . . . 11 (𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = (𝐹𝑢)
23 fveq2 6530 . . . . . . . . . . 11 (𝑢 = (𝑟 “ {𝑦}) → (𝐹𝑢) = (𝐹‘(𝑟 “ {𝑦})))
2422, 23syl5eq 2841 . . . . . . . . . 10 (𝑢 = (𝑟 “ {𝑦}) → (𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = (𝐹‘(𝑟 “ {𝑦})))
2524eqeq1d 2795 . . . . . . . . 9 (𝑢 = (𝑟 “ {𝑦}) → ((𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ (𝐹‘(𝑟 “ {𝑦})) = 𝑦))
2619, 25sbcie 3736 . . . . . . . 8 ([(𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ (𝐹‘(𝑟 “ {𝑦})) = 𝑦)
2726ralbii 3130 . . . . . . 7 (∀𝑦𝑥 [(𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ ∀𝑦𝑥 (𝐹‘(𝑟 “ {𝑦})) = 𝑦)
2827anbi2i 622 . . . . . 6 ((𝑟 We 𝑥 ∧ ∀𝑦𝑥 [(𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦) ↔ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 (𝐹‘(𝑟 “ {𝑦})) = 𝑦))
2928anbi2i 622 . . . . 5 (((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 [(𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦)) ↔ ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 (𝐹‘(𝑟 “ {𝑦})) = 𝑦)))
3029opabbii 5023 . . . 4 {⟨𝑥, 𝑟⟩ ∣ ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 [(𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦))} = {⟨𝑥, 𝑟⟩ ∣ ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 (𝐹‘(𝑟 “ {𝑦})) = 𝑦))}
319, 30eqtr4i 2820 . . 3 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦𝑥 [(𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦))}
32 fpwwe.2 . . 3 (𝜑𝐴 ∈ V)
33 vex 3435 . . . . 5 𝑥 ∈ V
3433, 17algrflem 7663 . . . 4 (𝑥(𝐹 ∘ 1st )𝑟) = (𝐹𝑥)
35 simp1 1127 . . . . . . 7 ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥𝐴)
36 selpw 4454 . . . . . . 7 (𝑥 ∈ 𝒫 𝐴𝑥𝐴)
3735, 36sylibr 235 . . . . . 6 ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ 𝒫 𝐴)
38 19.8a 2142 . . . . . . . 8 (𝑟 We 𝑥 → ∃𝑟 𝑟 We 𝑥)
39383ad2ant3 1126 . . . . . . 7 ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → ∃𝑟 𝑟 We 𝑥)
40 ween 9296 . . . . . . 7 (𝑥 ∈ dom card ↔ ∃𝑟 𝑟 We 𝑥)
4139, 40sylibr 235 . . . . . 6 ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ dom card)
4237, 41elind 4087 . . . . 5 ((𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ (𝒫 𝐴 ∩ dom card))
43 fpwwe.3 . . . . 5 ((𝜑𝑥 ∈ (𝒫 𝐴 ∩ dom card)) → (𝐹𝑥) ∈ 𝐴)
4442, 43sylan2 592 . . . 4 ((𝜑 ∧ (𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥)) → (𝐹𝑥) ∈ 𝐴)
4534, 44syl5eqel 2885 . . 3 ((𝜑 ∧ (𝑥𝐴𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥)) → (𝑥(𝐹 ∘ 1st )𝑟) ∈ 𝐴)
46 fpwwe.4 . . 3 𝑋 = dom 𝑊
4731, 32, 45, 46fpwwe2 9900 . 2 (𝜑 → ((𝑌𝑊𝑅 ∧ (𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌) ↔ (𝑌 = 𝑋𝑅 = (𝑊𝑋))))
4816, 47syl5bbr 286 1 (𝜑 → ((𝑌𝑊𝑅 ∧ (𝐹𝑌) ∈ 𝑌) ↔ (𝑌 = 𝑋𝑅 = (𝑊𝑋))))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 207  wa 396  w3a 1078   = wceq 1520  wex 1759  wcel 2079  wral 3103  Vcvv 3432  [wsbc 3701  cin 3853  wss 3854  𝒫 cpw 4447  {csn 4466  cop 4472   cuni 4739   class class class wbr 4956  {copab 5018   We wwe 5393   × cxp 5433  ccnv 5434  dom cdm 5435  cima 5438  ccom 5439   Fn wfn 6212  ontowfo 6215  cfv 6217  (class class class)co 7007  1st c1st 7534  cardccrd 9199
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1775  ax-4 1789  ax-5 1886  ax-6 1945  ax-7 1990  ax-8 2081  ax-9 2089  ax-10 2110  ax-11 2124  ax-12 2139  ax-13 2342  ax-ext 2767  ax-rep 5075  ax-sep 5088  ax-nul 5095  ax-pow 5150  ax-pr 5214  ax-un 7310
This theorem depends on definitions:  df-bi 208  df-an 397  df-or 843  df-3or 1079  df-3an 1080  df-tru 1523  df-ex 1760  df-nf 1764  df-sb 2041  df-mo 2574  df-eu 2610  df-clab 2774  df-cleq 2786  df-clel 2861  df-nfc 2933  df-ne 2983  df-ral 3108  df-rex 3109  df-reu 3110  df-rmo 3111  df-rab 3112  df-v 3434  df-sbc 3702  df-csb 3807  df-dif 3857  df-un 3859  df-in 3861  df-ss 3869  df-pss 3871  df-nul 4207  df-if 4376  df-pw 4449  df-sn 4467  df-pr 4469  df-tp 4471  df-op 4473  df-uni 4740  df-int 4777  df-iun 4821  df-br 4957  df-opab 5019  df-mpt 5036  df-tr 5058  df-id 5340  df-eprel 5345  df-po 5354  df-so 5355  df-fr 5394  df-se 5395  df-we 5396  df-xp 5441  df-rel 5442  df-cnv 5443  df-co 5444  df-dm 5445  df-rn 5446  df-res 5447  df-ima 5448  df-pred 6015  df-ord 6061  df-on 6062  df-lim 6063  df-suc 6064  df-iota 6181  df-fun 6219  df-fn 6220  df-f 6221  df-f1 6222  df-fo 6223  df-f1o 6224  df-fv 6225  df-isom 6226  df-riota 6968  df-ov 7010  df-1st 7536  df-wrecs 7789  df-recs 7851  df-en 8348  df-oi 8810  df-card 9203
This theorem is referenced by:  canth4  9904  canthnumlem  9905  canthp1lem2  9910
  Copyright terms: Public domain W3C validator