Theorem fpwwe 10569

Description: Given any function 𝐹 from the powerset of 𝐴 to 𝐴, canth2 9070 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 9952. Theorem 1.1 of [KanamoriPincus] p. 415. (Contributed by Mario Carneiro, 18-May-2015.) (Revised by AV, 20-Jul-2024.)

Hypotheses

Ref	Expression
fpwwe.1	⊢ 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))}
fpwwe.2	⊢ (𝜑 → 𝐴 ∈ 𝑉)
fpwwe.3	⊢ ((𝜑 ∧ 𝑥 ∈ (𝒫 𝐴 ∩ dom card)) → (𝐹‘𝑥) ∈ 𝐴)
fpwwe.4	⊢ 𝑋 = ∪ dom 𝑊

Assertion

Ref	Expression
fpwwe	⊢ (𝜑 → ((𝑌𝑊𝑅 ∧ (𝐹‘𝑌) ∈ 𝑌) ↔ (𝑌 = 𝑋 ∧ 𝑅 = (𝑊‘𝑋))))

Distinct variable groups:   𝑥,𝑟,𝐴   𝑦,𝑟,𝐹,𝑥   𝜑,𝑟,𝑥,𝑦   𝑅,𝑟,𝑥,𝑦   𝑋,𝑟,𝑥,𝑦   𝑌,𝑟,𝑥,𝑦   𝑊,𝑟,𝑥,𝑦

Allowed substitution hints:   𝐴(𝑦)   𝑉(𝑥,𝑦,𝑟)

Proof of Theorem fpwwe

Dummy variable 𝑢 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		df-ov 7371	. . . . . 6 ⊢ (𝑌(𝐹 ∘ 1st )𝑅) = ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩)
2		fo1st 7963	. . . . . . . 8 ⊢ 1st :V–onto→V
3		fofn 6756	. . . . . . . 8 ⊢ (1st :V–onto→V → 1st Fn V)
4	2, 3	ax-mp 5	. . . . . . 7 ⊢ 1st Fn V
5		opex 5419	. . . . . . 7 ⊢ ⟨𝑌, 𝑅⟩ ∈ V
6		fvco2 6939	. . . . . . 7 ⊢ ((1st Fn V ∧ ⟨𝑌, 𝑅⟩ ∈ V) → ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩)))
7	4, 5, 6	mp2an 693	. . . . . 6 ⊢ ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩))
8	1, 7	eqtri 2760	. . . . 5 ⊢ (𝑌(𝐹 ∘ 1st )𝑅) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩))
9		fpwwe.1	. . . . . . . 8 ⊢ 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))}
10	9	bropaex12 5723	. . . . . . 7 ⊢ (𝑌𝑊𝑅 → (𝑌 ∈ V ∧ 𝑅 ∈ V))
11		op1stg 7955	. . . . . . 7 ⊢ ((𝑌 ∈ V ∧ 𝑅 ∈ V) → (1st ‘⟨𝑌, 𝑅⟩) = 𝑌)
12	10, 11	syl 17	. . . . . 6 ⊢ (𝑌𝑊𝑅 → (1st ‘⟨𝑌, 𝑅⟩) = 𝑌)
13	12	fveq2d 6846	. . . . 5 ⊢ (𝑌𝑊𝑅 → (𝐹‘(1st ‘⟨𝑌, 𝑅⟩)) = (𝐹‘𝑌))
14	8, 13	eqtrid 2784	. . . 4 ⊢ (𝑌𝑊𝑅 → (𝑌(𝐹 ∘ 1st )𝑅) = (𝐹‘𝑌))
15	14	eleq1d 2822	. . 3 ⊢ (𝑌𝑊𝑅 → ((𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌 ↔ (𝐹‘𝑌) ∈ 𝑌))
16	15	pm5.32i 574	. 2 ⊢ ((𝑌𝑊𝑅 ∧ (𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌) ↔ (𝑌𝑊𝑅 ∧ (𝐹‘𝑌) ∈ 𝑌))
17		vex 3446	. . . . . . . . . . 11 ⊢ 𝑟 ∈ V
18	17	cnvex 7877	. . . . . . . . . 10 ⊢ ◡𝑟 ∈ V
19	18	imaex 7866	. . . . . . . . 9 ⊢ (◡𝑟 “ {𝑦}) ∈ V
20		vex 3446	. . . . . . . . . . . 12 ⊢ 𝑢 ∈ V
21	17	inex1 5264	. . . . . . . . . . . 12 ⊢ (𝑟 ∩ (𝑢 × 𝑢)) ∈ V
22	20, 21	opco1i 8077	. . . . . . . . . . 11 ⊢ (𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = (𝐹‘𝑢)
23		fveq2 6842	. . . . . . . . . . 11 ⊢ (𝑢 = (◡𝑟 “ {𝑦}) → (𝐹‘𝑢) = (𝐹‘(◡𝑟 “ {𝑦})))
24	22, 23	eqtrid 2784	. . . . . . . . . 10 ⊢ (𝑢 = (◡𝑟 “ {𝑦}) → (𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = (𝐹‘(◡𝑟 “ {𝑦})))
25	24	eqeq1d 2739	. . . . . . . . 9 ⊢ (𝑢 = (◡𝑟 “ {𝑦}) → ((𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))
26	19, 25	sbcie 3784	. . . . . . . 8 ⊢ ([(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦)
27	26	ralbii 3084	. . . . . . 7 ⊢ (∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦)
28	27	anbi2i 624	. . . . . 6 ⊢ ((𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦) ↔ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))
29	28	anbi2i 624	. . . . 5 ⊢ (((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦)) ↔ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦)))
30	29	opabbii 5167	. . . 4 ⊢ {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦))} = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))}
31	9, 30	eqtr4i 2763	. . 3 ⊢ 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦))}
32		fpwwe.2	. . 3 ⊢ (𝜑 → 𝐴 ∈ 𝑉)
33		vex 3446	. . . . 5 ⊢ 𝑥 ∈ V
34	33, 17	opco1i 8077	. . . 4 ⊢ (𝑥(𝐹 ∘ 1st )𝑟) = (𝐹‘𝑥)
35		simp1 1137	. . . . . . 7 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ⊆ 𝐴)
36		velpw 4561	. . . . . . 7 ⊢ (𝑥 ∈ 𝒫 𝐴 ↔ 𝑥 ⊆ 𝐴)
37	35, 36	sylibr 234	. . . . . 6 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ 𝒫 𝐴)
38		19.8a 2189	. . . . . . . 8 ⊢ (𝑟 We 𝑥 → ∃𝑟 𝑟 We 𝑥)
39	38	3ad2ant3 1136	. . . . . . 7 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → ∃𝑟 𝑟 We 𝑥)
40		ween 9957	. . . . . . 7 ⊢ (𝑥 ∈ dom card ↔ ∃𝑟 𝑟 We 𝑥)
41	39, 40	sylibr 234	. . . . . 6 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ dom card)
42	37, 41	elind 4154	. . . . 5 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ (𝒫 𝐴 ∩ dom card))
43		fpwwe.3	. . . . 5 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝒫 𝐴 ∩ dom card)) → (𝐹‘𝑥) ∈ 𝐴)
44	42, 43	sylan2 594	. . . 4 ⊢ ((𝜑 ∧ (𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥)) → (𝐹‘𝑥) ∈ 𝐴)
45	34, 44	eqeltrid 2841	. . 3 ⊢ ((𝜑 ∧ (𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥)) → (𝑥(𝐹 ∘ 1st )𝑟) ∈ 𝐴)
46		fpwwe.4	. . 3 ⊢ 𝑋 = ∪ dom 𝑊
47	31, 32, 45, 46	fpwwe2 10566	. 2 ⊢ (𝜑 → ((𝑌𝑊𝑅 ∧ (𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌) ↔ (𝑌 = 𝑋 ∧ 𝑅 = (𝑊‘𝑋))))
48	16, 47	bitr3id 285	1 ⊢ (𝜑 → ((𝑌𝑊𝑅 ∧ (𝐹‘𝑌) ∈ 𝑌) ↔ (𝑌 = 𝑋 ∧ 𝑅 = (𝑊‘𝑋))))

Syntax hints:   → wi 4   ↔ wb 206   ∧ wa 395   ∧ w3a 1087   = wceq 1542  ∃wex 1781   ∈ wcel 2114  ∀wral 3052  Vcvv 3442  [wsbc 3742   ∩ cin 3902   ⊆ wss 3903  𝒫 cpw 4556  {csn 4582  ⟨cop 4588  ∪ cuni 4865   class class class wbr 5100  {copab 5162   We wwe 5584   × cxp 5630  ^◡ccnv 5631  dom cdm 5632   “ cima 5635   ∘ ccom 5636   Fn wfn 6495  –onto→wfo 6498  ‘cfv 6500  (class class class)co 7368  1^st c1st 7941  cardccrd 9859

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 1912  ax-6 1969  ax-7 2010  ax-8 2116  ax-9 2124  ax-10 2147  ax-11 2163  ax-12 2185  ax-ext 2709  ax-rep 5226  ax-sep 5243  ax-nul 5253  ax-pow 5312  ax-pr 5379  ax-un 7690

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3or 1088  df-3an 1089  df-tru 1545  df-fal 1555  df-ex 1782  df-nf 1786  df-sb 2069  df-mo 2540  df-eu 2570  df-clab 2716  df-cleq 2729  df-clel 2812  df-nfc 2886  df-ne 2934  df-ral 3053  df-rex 3063  df-rmo 3352  df-reu 3353  df-rab 3402  df-v 3444  df-sbc 3743  df-csb 3852  df-dif 3906  df-un 3908  df-in 3910  df-ss 3920  df-pss 3923  df-nul 4288  df-if 4482  df-pw 4558  df-sn 4583  df-pr 4585  df-tp 4587  df-op 4589  df-uni 4866  df-int 4905  df-iun 4950  df-br 5101  df-opab 5163  df-mpt 5182  df-tr 5208  df-id 5527  df-eprel 5532  df-po 5540  df-so 5541  df-fr 5585  df-se 5586  df-we 5587  df-xp 5638  df-rel 5639  df-cnv 5640  df-co 5641  df-dm 5642  df-rn 5643  df-res 5644  df-ima 5645  df-pred 6267  df-ord 6328  df-on 6329  df-lim 6330  df-suc 6331  df-iota 6456  df-fun 6502  df-fn 6503  df-f 6504  df-f1 6505  df-fo 6506  df-f1o 6507  df-fv 6508  df-isom 6509  df-riota 7325  df-ov 7371  df-1st 7943  df-2nd 7944  df-frecs 8233  df-wrecs 8264  df-recs 8313  df-en 8896  df-oi 9427  df-card 9863

This theorem is referenced by:  canth4  10570  canthnumlem  10571  canthp1lem2  10576