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 29305
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 4707 . . . . . . 7 𝑠(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2 ofpreima.1 . . . . . . 7 (𝜑𝐹:𝐴𝐵)
3 ofpreima.2 . . . . . . 7 (𝜑𝐺:𝐴𝐶)
4 ofpreima.3 . . . . . . 7 (𝜑𝐴𝑉)
5 eqidd 2622 . . . . . . 7 (𝜑 → (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩))
6 ofpreima.4 . . . . . . . 8 (𝜑𝑅 Fn (𝐵 × 𝐶))
7 fnov 6721 . . . . . . . 8 (𝑅 Fn (𝐵 × 𝐶) ↔ 𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
86, 7sylib 208 . . . . . . 7 (𝜑𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
91, 2, 3, 4, 5, 8ofoprabco 29304 . . . . . 6 (𝜑 → (𝐹𝑓 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
109cnveqd 5258 . . . . 5 (𝜑(𝐹𝑓 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
11 cnvco 5268 . . . . 5 (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅)
1210, 11syl6eq 2671 . . . 4 (𝜑(𝐹𝑓 𝑅𝐺) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅))
1312imaeq1d 5424 . . 3 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷))
14 imaco 5599 . . 3 (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷))
1513, 14syl6eq 2671 . 2 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)))
16 dfima2 5427 . . 3 ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞}
17 vex 3189 . . . . . . . 8 𝑝 ∈ V
18 vex 3189 . . . . . . . 8 𝑞 ∈ V
1917, 18brcnv 5265 . . . . . . 7 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝)
20 funmpt 5884 . . . . . . . . 9 Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
21 funbrfv2b 6197 . . . . . . . . 9 (Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) → (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝)))
2220, 21ax-mp 5 . . . . . . . 8 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
23 opex 4893 . . . . . . . . . . 11 ⟨(𝐹𝑠), (𝐺𝑠)⟩ ∈ V
24 eqid 2621 . . . . . . . . . . 11 (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2523, 24dmmpti 5980 . . . . . . . . . 10 dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = 𝐴
2625eleq2i 2690 . . . . . . . . 9 (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ↔ 𝑞𝐴)
2726anbi1i 730 . . . . . . . 8 ((𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
2822, 27bitri 264 . . . . . . 7 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
29 fveq2 6148 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐹𝑠) = (𝐹𝑞))
30 fveq2 6148 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐺𝑠) = (𝐺𝑞))
3129, 30opeq12d 4378 . . . . . . . . . 10 (𝑠 = 𝑞 → ⟨(𝐹𝑠), (𝐺𝑠)⟩ = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
32 opex 4893 . . . . . . . . . 10 ⟨(𝐹𝑞), (𝐺𝑞)⟩ ∈ V
3331, 24, 32fvmpt 6239 . . . . . . . . 9 (𝑞𝐴 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
3433eqeq1d 2623 . . . . . . . 8 (𝑞𝐴 → (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3534pm5.32i 668 . . . . . . 7 ((𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3619, 28, 353bitri 286 . . . . . 6 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3736rexbii 3034 . . . . 5 (∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3837abbii 2736 . . . 4 {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
39 nfv 1840 . . . . 5 𝑞𝜑
40 nfab1 2763 . . . . 5 𝑞{𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
41 nfcv 2761 . . . . 5 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))
42 eliun 4490 . . . . . 6 (𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
43 ffn 6002 . . . . . . . . . . . . 13 (𝐹:𝐴𝐵𝐹 Fn 𝐴)
44 fniniseg 6294 . . . . . . . . . . . . 13 (𝐹 Fn 𝐴 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
452, 43, 443syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
46 ffn 6002 . . . . . . . . . . . . 13 (𝐺:𝐴𝐶𝐺 Fn 𝐴)
47 fniniseg 6294 . . . . . . . . . . . . 13 (𝐺 Fn 𝐴 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
483, 46, 473syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
4945, 48anbi12d 746 . . . . . . . . . . 11 (𝜑 → ((𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝)))))
50 elin 3774 . . . . . . . . . . 11 (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})))
51 anandi 870 . . . . . . . . . . 11 ((𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
5249, 50, 513bitr4g 303 . . . . . . . . . 10 (𝜑 → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
5352adantr 481 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
54 cnvimass 5444 . . . . . . . . . . . . . 14 (𝑅𝐷) ⊆ dom 𝑅
55 fndm 5948 . . . . . . . . . . . . . . 15 (𝑅 Fn (𝐵 × 𝐶) → dom 𝑅 = (𝐵 × 𝐶))
566, 55syl 17 . . . . . . . . . . . . . 14 (𝜑 → dom 𝑅 = (𝐵 × 𝐶))
5754, 56syl5sseq 3632 . . . . . . . . . . . . 13 (𝜑 → (𝑅𝐷) ⊆ (𝐵 × 𝐶))
5857sselda 3583 . . . . . . . . . . . 12 ((𝜑𝑝 ∈ (𝑅𝐷)) → 𝑝 ∈ (𝐵 × 𝐶))
59 1st2nd2 7150 . . . . . . . . . . . 12 (𝑝 ∈ (𝐵 × 𝐶) → 𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩)
60 eqeq2 2632 . . . . . . . . . . . 12 (𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩ → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
6158, 59, 603syl 18 . . . . . . . . . . 11 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
62 fvex 6158 . . . . . . . . . . . 12 (𝐹𝑞) ∈ V
63 fvex 6158 . . . . . . . . . . . 12 (𝐺𝑞) ∈ V
6462, 63opth 4905 . . . . . . . . . . 11 (⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩ ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))
6561, 64syl6bb 276 . . . . . . . . . 10 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))))
6665anbi2d 739 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → ((𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
6753, 66bitr4d 271 . . . . . . . 8 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
6867rexbidva 3042 . . . . . . 7 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
69 abid 2609 . . . . . . 7 (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
7068, 69syl6bbr 278 . . . . . 6 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ 𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}))
7142, 70syl5rbb 273 . . . . 5 (𝜑 → (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))))
7239, 40, 41, 71eqrd 3602 . . . 4 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7338, 72syl5eq 2667 . . 3 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7416, 73syl5eq 2667 . 2 (𝜑 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7515, 74eqtrd 2655 1 (𝜑 → ((𝐹𝑓 𝑅𝐺) “ 𝐷) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 196  wa 384   = wceq 1480  wcel 1987  {cab 2607  wrex 2908  cin 3554  {csn 4148  cop 4154   ciun 4485   class class class wbr 4613  cmpt 4673   × cxp 5072  ccnv 5073  dom cdm 5074  cima 5077  ccom 5078  Fun wfun 5841   Fn wfn 5842  wf 5843  cfv 5847  (class class class)co 6604  cmpt2 6606  𝑓 cof 6848  1st c1st 7111  2nd c2nd 7112
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1719  ax-4 1734  ax-5 1836  ax-6 1885  ax-7 1932  ax-8 1989  ax-9 1996  ax-10 2016  ax-11 2031  ax-12 2044  ax-13 2245  ax-ext 2601  ax-rep 4731  ax-sep 4741  ax-nul 4749  ax-pow 4803  ax-pr 4867  ax-un 6902
This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3an 1038  df-tru 1483  df-ex 1702  df-nf 1707  df-sb 1878  df-eu 2473  df-mo 2474  df-clab 2608  df-cleq 2614  df-clel 2617  df-nfc 2750  df-ne 2791  df-ral 2912  df-rex 2913  df-reu 2914  df-rab 2916  df-v 3188  df-sbc 3418  df-csb 3515  df-dif 3558  df-un 3560  df-in 3562  df-ss 3569  df-nul 3892  df-if 4059  df-sn 4149  df-pr 4151  df-op 4155  df-uni 4403  df-iun 4487  df-br 4614  df-opab 4674  df-mpt 4675  df-id 4989  df-xp 5080  df-rel 5081  df-cnv 5082  df-co 5083  df-dm 5084  df-rn 5085  df-res 5086  df-ima 5087  df-iota 5810  df-fun 5849  df-fn 5850  df-f 5851  df-f1 5852  df-fo 5853  df-f1o 5854  df-fv 5855  df-ov 6607  df-oprab 6608  df-mpt2 6609  df-of 6850  df-1st 7113  df-2nd 7114
This theorem is referenced by:  ofpreima2  29306
  Copyright terms: Public domain W3C validator