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

Theorem ofpreima 30186
 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 5021 . . . . . . 7 𝑠(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2 ofpreima.1 . . . . . . 7 (𝜑𝐹:𝐴𝐵)
3 ofpreima.2 . . . . . . 7 (𝜑𝐺:𝐴𝐶)
4 ofpreima.3 . . . . . . 7 (𝜑𝐴𝑉)
5 eqidd 2773 . . . . . . 7 (𝜑 → (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩))
6 ofpreima.4 . . . . . . . 8 (𝜑𝑅 Fn (𝐵 × 𝐶))
7 fnov 7096 . . . . . . . 8 (𝑅 Fn (𝐵 × 𝐶) ↔ 𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
86, 7sylib 210 . . . . . . 7 (𝜑𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
91, 2, 3, 4, 5, 8ofoprabco 30185 . . . . . 6 (𝜑 → (𝐹𝑓 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
109cnveqd 5592 . . . . 5 (𝜑(𝐹𝑓 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
11 cnvco 5602 . . . . 5 (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅)
1210, 11syl6eq 2824 . . . 4 (𝜑(𝐹𝑓 𝑅𝐺) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅))
1312imaeq1d 5766 . . 3 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷))
14 imaco 5940 . . 3 (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷))
1513, 14syl6eq 2824 . 2 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)))
16 dfima2 5769 . . 3 ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞}
17 vex 3412 . . . . . . . 8 𝑝 ∈ V
18 vex 3412 . . . . . . . 8 𝑞 ∈ V
1917, 18brcnv 5599 . . . . . . 7 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝)
20 funmpt 6223 . . . . . . . . 9 Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
21 funbrfv2b 6550 . . . . . . . . 9 (Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) → (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝)))
2220, 21ax-mp 5 . . . . . . . 8 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
23 opex 5209 . . . . . . . . . . 11 ⟨(𝐹𝑠), (𝐺𝑠)⟩ ∈ V
24 eqid 2772 . . . . . . . . . . 11 (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2523, 24dmmpti 6319 . . . . . . . . . 10 dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = 𝐴
2625eleq2i 2851 . . . . . . . . 9 (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ↔ 𝑞𝐴)
2726anbi1i 614 . . . . . . . 8 ((𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
2822, 27bitri 267 . . . . . . 7 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
29 fveq2 6496 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐹𝑠) = (𝐹𝑞))
30 fveq2 6496 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐺𝑠) = (𝐺𝑞))
3129, 30opeq12d 4681 . . . . . . . . . 10 (𝑠 = 𝑞 → ⟨(𝐹𝑠), (𝐺𝑠)⟩ = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
32 opex 5209 . . . . . . . . . 10 ⟨(𝐹𝑞), (𝐺𝑞)⟩ ∈ V
3331, 24, 32fvmpt 6593 . . . . . . . . 9 (𝑞𝐴 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
3433eqeq1d 2774 . . . . . . . 8 (𝑞𝐴 → (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3534pm5.32i 567 . . . . . . 7 ((𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3619, 28, 353bitri 289 . . . . . 6 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3736rexbii 3188 . . . . 5 (∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3837abbii 2838 . . . 4 {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
39 nfv 1873 . . . . 5 𝑞𝜑
40 nfab1 2928 . . . . 5 𝑞{𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
41 nfcv 2926 . . . . 5 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))
42 eliun 4792 . . . . . 6 (𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
43 ffn 6341 . . . . . . . . . . . . 13 (𝐹:𝐴𝐵𝐹 Fn 𝐴)
44 fniniseg 6653 . . . . . . . . . . . . 13 (𝐹 Fn 𝐴 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
452, 43, 443syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
46 ffn 6341 . . . . . . . . . . . . 13 (𝐺:𝐴𝐶𝐺 Fn 𝐴)
47 fniniseg 6653 . . . . . . . . . . . . 13 (𝐺 Fn 𝐴 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
483, 46, 473syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
4945, 48anbi12d 621 . . . . . . . . . . 11 (𝜑 → ((𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝)))))
50 elin 4051 . . . . . . . . . . 11 (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})))
51 anandi 663 . . . . . . . . . . 11 ((𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
5249, 50, 513bitr4g 306 . . . . . . . . . 10 (𝜑 → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
5352adantr 473 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
54 cnvimass 5786 . . . . . . . . . . . . . 14 (𝑅𝐷) ⊆ dom 𝑅
55 fndm 6285 . . . . . . . . . . . . . . 15 (𝑅 Fn (𝐵 × 𝐶) → dom 𝑅 = (𝐵 × 𝐶))
566, 55syl 17 . . . . . . . . . . . . . 14 (𝜑 → dom 𝑅 = (𝐵 × 𝐶))
5754, 56syl5sseq 3903 . . . . . . . . . . . . 13 (𝜑 → (𝑅𝐷) ⊆ (𝐵 × 𝐶))
5857sselda 3852 . . . . . . . . . . . 12 ((𝜑𝑝 ∈ (𝑅𝐷)) → 𝑝 ∈ (𝐵 × 𝐶))
59 1st2nd2 7538 . . . . . . . . . . . 12 (𝑝 ∈ (𝐵 × 𝐶) → 𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩)
60 eqeq2 2783 . . . . . . . . . . . 12 (𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩ → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
6158, 59, 603syl 18 . . . . . . . . . . 11 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
62 fvex 6509 . . . . . . . . . . . 12 (𝐹𝑞) ∈ V
63 fvex 6509 . . . . . . . . . . . 12 (𝐺𝑞) ∈ V
6462, 63opth 5221 . . . . . . . . . . 11 (⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩ ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))
6561, 64syl6bb 279 . . . . . . . . . 10 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))))
6665anbi2d 619 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → ((𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
6753, 66bitr4d 274 . . . . . . . 8 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
6867rexbidva 3235 . . . . . . 7 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
69 abid 2756 . . . . . . 7 (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
7068, 69syl6bbr 281 . . . . . 6 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ 𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}))
7142, 70syl5rbb 276 . . . . 5 (𝜑 → (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))))
7239, 40, 41, 71eqrd 3871 . . . 4 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7338, 72syl5eq 2820 . . 3 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7416, 73syl5eq 2820 . 2 (𝜑 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7515, 74eqtrd 2808 1 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 198   ∧ wa 387   = wceq 1507   ∈ wcel 2050  {cab 2752  ∃wrex 3083   ∩ cin 3822  {csn 4435  ⟨cop 4441  ∪ ciun 4788   class class class wbr 4925   ↦ cmpt 5004   × cxp 5401  ◡ccnv 5402  dom cdm 5403   “ cima 5406   ∘ ccom 5407  Fun wfun 6179   Fn wfn 6180  ⟶wf 6181  ‘cfv 6185  (class class class)co 6974   ∈ cmpo 6976   ∘𝑓 cof 7223  1st c1st 7497  2nd c2nd 7498 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1758  ax-4 1772  ax-5 1869  ax-6 1928  ax-7 1965  ax-8 2052  ax-9 2059  ax-10 2079  ax-11 2093  ax-12 2106  ax-13 2301  ax-ext 2744  ax-rep 5045  ax-sep 5056  ax-nul 5063  ax-pow 5115  ax-pr 5182  ax-un 7277 This theorem depends on definitions:  df-bi 199  df-an 388  df-or 834  df-3an 1070  df-tru 1510  df-ex 1743  df-nf 1747  df-sb 2016  df-mo 2547  df-eu 2584  df-clab 2753  df-cleq 2765  df-clel 2840  df-nfc 2912  df-ne 2962  df-ral 3087  df-rex 3088  df-reu 3089  df-rab 3091  df-v 3411  df-sbc 3676  df-csb 3781  df-dif 3826  df-un 3828  df-in 3830  df-ss 3837  df-nul 4173  df-if 4345  df-sn 4436  df-pr 4438  df-op 4442  df-uni 4709  df-iun 4790  df-br 4926  df-opab 4988  df-mpt 5005  df-id 5308  df-xp 5409  df-rel 5410  df-cnv 5411  df-co 5412  df-dm 5413  df-rn 5414  df-res 5415  df-ima 5416  df-iota 6149  df-fun 6187  df-fn 6188  df-f 6189  df-f1 6190  df-fo 6191  df-f1o 6192  df-fv 6193  df-ov 6977  df-oprab 6978  df-mpo 6979  df-of 7225  df-1st 7499  df-2nd 7500 This theorem is referenced by:  ofpreima2  30187
 Copyright terms: Public domain W3C validator