Theorem fpwwe 10768

Description: Given any function 𝐹 from the powerset of 𝐴 to 𝐴, canth2 9185 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 10146. 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 7452	. . . . . 6 ⊢ (𝑌(𝐹 ∘ 1st )𝑅) = ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩)
2		fo1st 8053	. . . . . . . 8 ⊢ 1st :V⟶ontoV
3		fofn 6826	. . . . . . . 8 ⊢ (1st :V⟶ontoV → 1st Fn V)
4	2, 3	ax-mp 5	. . . . . . 7 ⊢ 1st Fn V
5		opex 5437	. . . . . . 7 ⊢ ⟨𝑌, 𝑅⟩ ∈ V
6		fvco2 7011	. . . . . . 7 ⊢ ((1st Fn V ∧ ⟨𝑌, 𝑅⟩ ∈ V) → ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩)))
7	4, 5, 6	mp2an 705	. . . . . 6 ⊢ ((𝐹 ∘ 1st )‘⟨𝑌, 𝑅⟩) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩))
8	1, 7	eqtri 2786	. . . . 5 ⊢ (𝑌(𝐹 ∘ 1st )𝑅) = (𝐹‘(1st ‘⟨𝑌, 𝑅⟩))
9		fpwwe.1	. . . . . . . 8 ⊢ 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))}
10	9	bropaex12 5748	. . . . . . 7 ⊢ (𝑌𝑊𝑅 → (𝑌 ∈ V ∧ 𝑅 ∈ V))
11		op1stg 8045	. . . . . . 7 ⊢ ((𝑌 ∈ V ∧ 𝑅 ∈ V) → (1st ‘⟨𝑌, 𝑅⟩) = 𝑌)
12	10, 11	syl 18	. . . . . 6 ⊢ (𝑌𝑊𝑅 → (1st ‘⟨𝑌, 𝑅⟩) = 𝑌)
13	12	fveq2d 6918	. . . . 5 ⊢ (𝑌𝑊𝑅 → (𝐹‘(1st ‘⟨𝑌, 𝑅⟩)) = (𝐹‘𝑌))
14	8, 13	eqtrid 2810	. . . 4 ⊢ (𝑌𝑊𝑅 → (𝑌(𝐹 ∘ 1st )𝑅) = (𝐹‘𝑌))
15	14	eleq1d 2849	. . 3 ⊢ (𝑌𝑊𝑅 → ((𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌 ↔ (𝐹‘𝑌) ∈ 𝑌))
16	15	pm5.32i 585	. 2 ⊢ ((𝑌𝑊𝑅 ∧ (𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌) ↔ (𝑌𝑊𝑅 ∧ (𝐹‘𝑌) ∈ 𝑌))
17		vex 3458	. . . . . . . . . . 11 ⊢ 𝑟 ∈ V
18	17	cnvex 7969	. . . . . . . . . 10 ⊢ ◡𝑟 ∈ V
19	18	imaex 7958	. . . . . . . . 9 ⊢ (◡𝑟 “ {𝑦}) ∈ V
20		vex 3458	. . . . . . . . . . . 12 ⊢ 𝑢 ∈ V
21	17	inex1 5282	. . . . . . . . . . . 12 ⊢ (𝑟 ∩ (𝑢 × 𝑢)) ∈ V
22	20, 21	opco1i 8171	. . . . . . . . . . 11 ⊢ (𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = (𝐹‘𝑢)
23		fveq2 6914	. . . . . . . . . . 11 ⊢ (𝑢 = (◡𝑟 “ {𝑦}) → (𝐹‘𝑢) = (𝐹‘(◡𝑟 “ {𝑦})))
24	22, 23	eqtrid 2810	. . . . . . . . . 10 ⊢ (𝑢 = (◡𝑟 “ {𝑦}) → (𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = (𝐹‘(◡𝑟 “ {𝑦})))
25	24	eqeq1d 2765	. . . . . . . . 9 ⊢ (𝑢 = (◡𝑟 “ {𝑦}) → ((𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))
26	19, 25	sbcie 3783	. . . . . . . 8 ⊢ ([(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦)
27	26	ralbii 3112	. . . . . . 7 ⊢ (∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦 ↔ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦)
28	27	anbi2i 635	. . . . . 6 ⊢ ((𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦) ↔ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))
29	28	anbi2i 635	. . . . 5 ⊢ (((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦)) ↔ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦)))
30	29	opabbii 5176	. . . 4 ⊢ {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦))} = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝐹‘(◡𝑟 “ {𝑦})) = 𝑦))}
31	9, 30	eqtr4i 2789	. . 3 ⊢ 𝑊 = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 [(◡𝑟 “ {𝑦}) / 𝑢](𝑢(𝐹 ∘ 1st )(𝑟 ∩ (𝑢 × 𝑢))) = 𝑦))}
32		fpwwe.2	. . 3 ⊢ (𝜑 → 𝐴 ∈ 𝑉)
33		vex 3458	. . . . 5 ⊢ 𝑥 ∈ V
34	33, 17	opco1i 8171	. . . 4 ⊢ (𝑥(𝐹 ∘ 1st )𝑟) = (𝐹‘𝑥)
35		simp1 1154	. . . . . . 7 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ⊆ 𝐴)
36		velpw 4565	. . . . . . 7 ⊢ (𝑥 ∈ 𝒫 𝐴 ↔ 𝑥 ⊆ 𝐴)
37	35, 36	sylibr 237	. . . . . 6 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ 𝒫 𝐴)
38		19.8a 2221	. . . . . . . 8 ⊢ (𝑟 We 𝑥 → ∃𝑟 𝑟 We 𝑥)
39	38	3ad2ant3 1153	. . . . . . 7 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → ∃𝑟 𝑟 We 𝑥)
40		ween 10151	. . . . . . 7 ⊢ (𝑥 ∈ dom card ↔ ∃𝑟 𝑟 We 𝑥)
41	39, 40	sylibr 237	. . . . . 6 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ dom card)
42	37, 41	elind 4100	. . . . 5 ⊢ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥) → 𝑥 ∈ (𝒫 𝐴 ∩ dom card))
43		fpwwe.3	. . . . 5 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝒫 𝐴 ∩ dom card)) → (𝐹‘𝑥) ∈ 𝐴)
44	42, 43	sylan2 605	. . . 4 ⊢ ((𝜑 ∧ (𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥)) → (𝐹‘𝑥) ∈ 𝐴)
45	34, 44	eqeltrid 2868	. . 3 ⊢ ((𝜑 ∧ (𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥) ∧ 𝑟 We 𝑥)) → (𝑥(𝐹 ∘ 1st )𝑟) ∈ 𝐴)
46		fpwwe.4	. . 3 ⊢ 𝑋 = ∪ dom 𝑊
47	31, 32, 45, 46	fpwwe2 10765	. 2 ⊢ (𝜑 → ((𝑌𝑊𝑅 ∧ (𝑌(𝐹 ∘ 1st )𝑅) ∈ 𝑌) ↔ (𝑌 = 𝑋 ∧ 𝑅 = (𝑊‘𝑋))))
48	16, 47	bitr3id 288	1 ⊢ (𝜑 → ((𝑌𝑊𝑅 ∧ (𝐹‘𝑌) ∈ 𝑌) ↔ (𝑌 = 𝑋 ∧ 𝑅 = (𝑊‘𝑋))))

This proof depends on syntax axioms:   → wi 4   ↔ wb 209   ∧ wa 401   ∧ w3a 1103   = wceq 1570  ∃wex 1812   ∈ wcel 2147  ∀wral 3080  Vcvv 3454  [wsbc 3742   ⊆ wss 3900   ∩ cin 4092  𝒫 cpw 4560  {csn 4588  ⟨cop 4838  ∪ cuni 4870   class class class wbr 5106  {copab 5171   We wwe 5608   × cxp 5654  ^◡ccnv 5655  dom cdm 5656   “ cima 5659   ∘ ccom 5660   Fn wfn 6559  ⟶ontowfo 6562  ‘cfv 6564  (class class class)co 7449  1^st c1st 8031  cardccrd 10051

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-10 2180  ax-11 2197  ax-12 2216  ax-ext 2735  ax-rep 5236  ax-sep 5253  ax-nul 5264  ax-pow 5332  ax-pr 5396  ax-un 7781

This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1104  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2102  df-mo 2567  df-eu 2597  df-clab 2742  df-cleq 2755  df-clel 2839  df-nfc 2913  df-ne 2960  df-ral 3081  df-rex 3091  df-rmo 3369  df-reu 3370  df-rab 3417  df-v 3456  df-sbc 3743  df-csb 3852  df-ss 3901  df-pss 4017  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-pw 4562  df-sn 4589  df-pr 4591  df-tp 4593  df-op 4839  df-uni 4871  df-int 4911  df-iun 4956  df-br 5107  df-opab 5172  df-mpt 5191  df-tr 5217  df-id 5551  df-eprel 5556  df-po 5564  df-so 5565  df-fr 5609  df-se 5610  df-we 5611  df-xp 5662  df-rel 5663  df-cnv 5664  df-co 5665  df-dm 5666  df-rn 5667  df-res 5668  df-ima 5669  df-pred 6328  df-ord 6389  df-on 6390  df-lim 6391  df-suc 6392  df-iota 6518  df-fun 6566  df-fn 6567  df-f 6568  df-f1 6569  df-fo 6570  df-f1o 6571  df-fv 6572  df-isom 6573  df-riota 7406  df-ov 7452  df-1st 8033  df-2nd 8034  df-frecs 8335  df-wrecs 8366  df-recs 8415  df-en 9010  df-oi 9539  df-card 10055

This theorem is used by:  canth4  10769  canthnumlem  10770  canthp1lem2  10775