Users' Mathboxes Mathbox for Thierry Arnoux < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  ofpreima Structured version   Visualization version   GIF version

Theorem ofpreima 29805
Description: Express the preimage of a function operation as a union of preimages. (Contributed by Thierry Arnoux, 8-Mar-2018.)
Hypotheses
Ref Expression
ofpreima.1 (𝜑𝐹:𝐴𝐵)
ofpreima.2 (𝜑𝐺:𝐴𝐶)
ofpreima.3 (𝜑𝐴𝑉)
ofpreima.4 (𝜑𝑅 Fn (𝐵 × 𝐶))
Assertion
Ref Expression
ofpreima (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
Distinct variable groups:   𝐴,𝑝   𝐷,𝑝   𝐹,𝑝   𝐺,𝑝   𝑅,𝑝   𝜑,𝑝
Allowed substitution hints:   𝐵(𝑝)   𝐶(𝑝)   𝑉(𝑝)

Proof of Theorem ofpreima
Dummy variables 𝑞 𝑠 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 nfmpt1 4882 . . . . . . 7 𝑠(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2 ofpreima.1 . . . . . . 7 (𝜑𝐹:𝐴𝐵)
3 ofpreima.2 . . . . . . 7 (𝜑𝐺:𝐴𝐶)
4 ofpreima.3 . . . . . . 7 (𝜑𝐴𝑉)
5 eqidd 2772 . . . . . . 7 (𝜑 → (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩))
6 ofpreima.4 . . . . . . . 8 (𝜑𝑅 Fn (𝐵 × 𝐶))
7 fnov 6919 . . . . . . . 8 (𝑅 Fn (𝐵 × 𝐶) ↔ 𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
86, 7sylib 208 . . . . . . 7 (𝜑𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
91, 2, 3, 4, 5, 8ofoprabco 29804 . . . . . 6 (𝜑 → (𝐹𝑓 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
109cnveqd 5435 . . . . 5 (𝜑(𝐹𝑓 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
11 cnvco 5445 . . . . 5 (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅)
1210, 11syl6eq 2821 . . . 4 (𝜑(𝐹𝑓 𝑅𝐺) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅))
1312imaeq1d 5605 . . 3 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷))
14 imaco 5783 . . 3 (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷))
1513, 14syl6eq 2821 . 2 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)))
16 dfima2 5608 . . 3 ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞}
17 vex 3354 . . . . . . . 8 𝑝 ∈ V
18 vex 3354 . . . . . . . 8 𝑞 ∈ V
1917, 18brcnv 5442 . . . . . . 7 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝)
20 funmpt 6068 . . . . . . . . 9 Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
21 funbrfv2b 6384 . . . . . . . . 9 (Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) → (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝)))
2220, 21ax-mp 5 . . . . . . . 8 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
23 opex 5061 . . . . . . . . . . 11 ⟨(𝐹𝑠), (𝐺𝑠)⟩ ∈ V
24 eqid 2771 . . . . . . . . . . 11 (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2523, 24dmmpti 6162 . . . . . . . . . 10 dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = 𝐴
2625eleq2i 2842 . . . . . . . . 9 (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ↔ 𝑞𝐴)
2726anbi1i 610 . . . . . . . 8 ((𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
2822, 27bitri 264 . . . . . . 7 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
29 fveq2 6333 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐹𝑠) = (𝐹𝑞))
30 fveq2 6333 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐺𝑠) = (𝐺𝑞))
3129, 30opeq12d 4548 . . . . . . . . . 10 (𝑠 = 𝑞 → ⟨(𝐹𝑠), (𝐺𝑠)⟩ = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
32 opex 5061 . . . . . . . . . 10 ⟨(𝐹𝑞), (𝐺𝑞)⟩ ∈ V
3331, 24, 32fvmpt 6426 . . . . . . . . 9 (𝑞𝐴 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
3433eqeq1d 2773 . . . . . . . 8 (𝑞𝐴 → (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3534pm5.32i 564 . . . . . . 7 ((𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3619, 28, 353bitri 286 . . . . . 6 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3736rexbii 3189 . . . . 5 (∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3837abbii 2888 . . . 4 {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
39 nfv 1995 . . . . 5 𝑞𝜑
40 nfab1 2915 . . . . 5 𝑞{𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
41 nfcv 2913 . . . . 5 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))
42 eliun 4659 . . . . . 6 (𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
43 ffn 6184 . . . . . . . . . . . . 13 (𝐹:𝐴𝐵𝐹 Fn 𝐴)
44 fniniseg 6483 . . . . . . . . . . . . 13 (𝐹 Fn 𝐴 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
452, 43, 443syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
46 ffn 6184 . . . . . . . . . . . . 13 (𝐺:𝐴𝐶𝐺 Fn 𝐴)
47 fniniseg 6483 . . . . . . . . . . . . 13 (𝐺 Fn 𝐴 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
483, 46, 473syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
4945, 48anbi12d 616 . . . . . . . . . . 11 (𝜑 → ((𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝)))))
50 elin 3947 . . . . . . . . . . 11 (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})))
51 anandi 655 . . . . . . . . . . 11 ((𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
5249, 50, 513bitr4g 303 . . . . . . . . . 10 (𝜑 → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
5352adantr 466 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
54 cnvimass 5625 . . . . . . . . . . . . . 14 (𝑅𝐷) ⊆ dom 𝑅
55 fndm 6129 . . . . . . . . . . . . . . 15 (𝑅 Fn (𝐵 × 𝐶) → dom 𝑅 = (𝐵 × 𝐶))
566, 55syl 17 . . . . . . . . . . . . . 14 (𝜑 → dom 𝑅 = (𝐵 × 𝐶))
5754, 56syl5sseq 3802 . . . . . . . . . . . . 13 (𝜑 → (𝑅𝐷) ⊆ (𝐵 × 𝐶))
5857sselda 3752 . . . . . . . . . . . 12 ((𝜑𝑝 ∈ (𝑅𝐷)) → 𝑝 ∈ (𝐵 × 𝐶))
59 1st2nd2 7358 . . . . . . . . . . . 12 (𝑝 ∈ (𝐵 × 𝐶) → 𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩)
60 eqeq2 2782 . . . . . . . . . . . 12 (𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩ → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
6158, 59, 603syl 18 . . . . . . . . . . 11 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
62 fvex 6344 . . . . . . . . . . . 12 (𝐹𝑞) ∈ V
63 fvex 6344 . . . . . . . . . . . 12 (𝐺𝑞) ∈ V
6462, 63opth 5073 . . . . . . . . . . 11 (⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩ ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))
6561, 64syl6bb 276 . . . . . . . . . 10 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))))
6665anbi2d 614 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → ((𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
6753, 66bitr4d 271 . . . . . . . 8 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
6867rexbidva 3197 . . . . . . 7 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
69 abid 2759 . . . . . . 7 (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
7068, 69syl6bbr 278 . . . . . 6 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ 𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}))
7142, 70syl5rbb 273 . . . . 5 (𝜑 → (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))))
7239, 40, 41, 71eqrd 3771 . . . 4 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7338, 72syl5eq 2817 . . 3 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7416, 73syl5eq 2817 . 2 (𝜑 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7515, 74eqtrd 2805 1 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 196  wa 382   = wceq 1631  wcel 2145  {cab 2757  wrex 3062  cin 3722  {csn 4317  cop 4323   ciun 4655   class class class wbr 4787  cmpt 4864   × cxp 5248  ccnv 5249  dom cdm 5250  cima 5253  ccom 5254  Fun wfun 6024   Fn wfn 6025  wf 6026  cfv 6030  (class class class)co 6796  cmpt2 6798  𝑓 cof 7046  1st c1st 7317  2nd c2nd 7318
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1870  ax-4 1885  ax-5 1991  ax-6 2057  ax-7 2093  ax-8 2147  ax-9 2154  ax-10 2174  ax-11 2190  ax-12 2203  ax-13 2408  ax-ext 2751  ax-rep 4905  ax-sep 4916  ax-nul 4924  ax-pow 4975  ax-pr 5035  ax-un 7100
This theorem depends on definitions:  df-bi 197  df-an 383  df-or 837  df-3an 1073  df-tru 1634  df-ex 1853  df-nf 1858  df-sb 2050  df-eu 2622  df-mo 2623  df-clab 2758  df-cleq 2764  df-clel 2767  df-nfc 2902  df-ne 2944  df-ral 3066  df-rex 3067  df-reu 3068  df-rab 3070  df-v 3353  df-sbc 3588  df-csb 3683  df-dif 3726  df-un 3728  df-in 3730  df-ss 3737  df-nul 4064  df-if 4227  df-sn 4318  df-pr 4320  df-op 4324  df-uni 4576  df-iun 4657  df-br 4788  df-opab 4848  df-mpt 4865  df-id 5158  df-xp 5256  df-rel 5257  df-cnv 5258  df-co 5259  df-dm 5260  df-rn 5261  df-res 5262  df-ima 5263  df-iota 5993  df-fun 6032  df-fn 6033  df-f 6034  df-f1 6035  df-fo 6036  df-f1o 6037  df-fv 6038  df-ov 6799  df-oprab 6800  df-mpt2 6801  df-of 7048  df-1st 7319  df-2nd 7320
This theorem is referenced by:  ofpreima2  29806
  Copyright terms: Public domain W3C validator