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 31581
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 (𝜑 → ((𝐹f 𝑅𝐺) “ 𝐷) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(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 5213 . . . . . . 7 𝑠(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2 ofpreima.1 . . . . . . 7 (𝜑𝐹:𝐴𝐵)
3 ofpreima.2 . . . . . . 7 (𝜑𝐺:𝐴𝐶)
4 ofpreima.3 . . . . . . 7 (𝜑𝐴𝑉)
5 eqidd 2737 . . . . . . 7 (𝜑 → (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩))
6 ofpreima.4 . . . . . . . 8 (𝜑𝑅 Fn (𝐵 × 𝐶))
7 fnov 7487 . . . . . . . 8 (𝑅 Fn (𝐵 × 𝐶) ↔ 𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
86, 7sylib 217 . . . . . . 7 (𝜑𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
91, 2, 3, 4, 5, 8ofoprabco 31580 . . . . . 6 (𝜑 → (𝐹f 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
109cnveqd 5831 . . . . 5 (𝜑(𝐹f 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
11 cnvco 5841 . . . . 5 (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅)
1210, 11eqtrdi 2792 . . . 4 (𝜑(𝐹f 𝑅𝐺) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅))
1312imaeq1d 6012 . . 3 (𝜑 → ((𝐹f 𝑅𝐺) “ 𝐷) = (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷))
14 imaco 6203 . . 3 (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷))
1513, 14eqtrdi 2792 . 2 (𝜑 → ((𝐹f 𝑅𝐺) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)))
16 dfima2 6015 . . 3 ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞}
17 vex 3449 . . . . . . . 8 𝑝 ∈ V
18 vex 3449 . . . . . . . 8 𝑞 ∈ V
1917, 18brcnv 5838 . . . . . . 7 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝)
20 funmpt 6539 . . . . . . . . 9 Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
21 funbrfv2b 6900 . . . . . . . . 9 (Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) → (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝)))
2220, 21ax-mp 5 . . . . . . . 8 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
23 opex 5421 . . . . . . . . . . 11 ⟨(𝐹𝑠), (𝐺𝑠)⟩ ∈ V
24 eqid 2736 . . . . . . . . . . 11 (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2523, 24dmmpti 6645 . . . . . . . . . 10 dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = 𝐴
2625eleq2i 2829 . . . . . . . . 9 (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ↔ 𝑞𝐴)
2726anbi1i 624 . . . . . . . 8 ((𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
2822, 27bitri 274 . . . . . . 7 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
29 fveq2 6842 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐹𝑠) = (𝐹𝑞))
30 fveq2 6842 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐺𝑠) = (𝐺𝑞))
3129, 30opeq12d 4838 . . . . . . . . . 10 (𝑠 = 𝑞 → ⟨(𝐹𝑠), (𝐺𝑠)⟩ = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
32 opex 5421 . . . . . . . . . 10 ⟨(𝐹𝑞), (𝐺𝑞)⟩ ∈ V
3331, 24, 32fvmpt 6948 . . . . . . . . 9 (𝑞𝐴 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
3433eqeq1d 2738 . . . . . . . 8 (𝑞𝐴 → (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3534pm5.32i 575 . . . . . . 7 ((𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3619, 28, 353bitri 296 . . . . . 6 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3736rexbii 3097 . . . . 5 (∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3837abbii 2806 . . . 4 {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
39 nfv 1917 . . . . 5 𝑞𝜑
40 nfab1 2909 . . . . 5 𝑞{𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
41 nfcv 2907 . . . . 5 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))
42 eliun 4958 . . . . . 6 (𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
43 ffn 6668 . . . . . . . . . . . . 13 (𝐹:𝐴𝐵𝐹 Fn 𝐴)
44 fniniseg 7010 . . . . . . . . . . . . 13 (𝐹 Fn 𝐴 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
452, 43, 443syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
46 ffn 6668 . . . . . . . . . . . . 13 (𝐺:𝐴𝐶𝐺 Fn 𝐴)
47 fniniseg 7010 . . . . . . . . . . . . 13 (𝐺 Fn 𝐴 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
483, 46, 473syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
4945, 48anbi12d 631 . . . . . . . . . . 11 (𝜑 → ((𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝)))))
50 elin 3926 . . . . . . . . . . 11 (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})))
51 anandi 674 . . . . . . . . . . 11 ((𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
5249, 50, 513bitr4g 313 . . . . . . . . . 10 (𝜑 → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
5352adantr 481 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
54 cnvimass 6033 . . . . . . . . . . . . . 14 (𝑅𝐷) ⊆ dom 𝑅
556fndmd 6607 . . . . . . . . . . . . . 14 (𝜑 → dom 𝑅 = (𝐵 × 𝐶))
5654, 55sseqtrid 3996 . . . . . . . . . . . . 13 (𝜑 → (𝑅𝐷) ⊆ (𝐵 × 𝐶))
5756sselda 3944 . . . . . . . . . . . 12 ((𝜑𝑝 ∈ (𝑅𝐷)) → 𝑝 ∈ (𝐵 × 𝐶))
58 1st2nd2 7960 . . . . . . . . . . . 12 (𝑝 ∈ (𝐵 × 𝐶) → 𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩)
59 eqeq2 2748 . . . . . . . . . . . 12 (𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩ → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
6057, 58, 593syl 18 . . . . . . . . . . 11 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
61 fvex 6855 . . . . . . . . . . . 12 (𝐹𝑞) ∈ V
62 fvex 6855 . . . . . . . . . . . 12 (𝐺𝑞) ∈ V
6361, 62opth 5433 . . . . . . . . . . 11 (⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩ ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))
6460, 63bitrdi 286 . . . . . . . . . 10 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))))
6564anbi2d 629 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → ((𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
6653, 65bitr4d 281 . . . . . . . 8 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
6766rexbidva 3173 . . . . . . 7 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
68 abid 2717 . . . . . . 7 (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
6967, 68bitr4di 288 . . . . . 6 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ 𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}))
7042, 69bitr2id 283 . . . . 5 (𝜑 → (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))))
7139, 40, 41, 70eqrd 3963 . . . 4 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7238, 71eqtrid 2788 . . 3 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7316, 72eqtrid 2788 . 2 (𝜑 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7415, 73eqtrd 2776 1 (𝜑 → ((𝐹f 𝑅𝐺) “ 𝐷) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 396   = wceq 1541  wcel 2106  {cab 2713  wrex 3073  cin 3909  {csn 4586  cop 4592   ciun 4954   class class class wbr 5105  cmpt 5188   × cxp 5631  ccnv 5632  dom cdm 5633  cima 5636  ccom 5637  Fun wfun 6490   Fn wfn 6491  wf 6492  cfv 6496  (class class class)co 7357  cmpo 7359  f cof 7615  1st c1st 7919  2nd c2nd 7920
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 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2707  ax-rep 5242  ax-sep 5256  ax-nul 5263  ax-pr 5384  ax-un 7672
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3an 1089  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2538  df-eu 2567  df-clab 2714  df-cleq 2728  df-clel 2814  df-nfc 2889  df-ne 2944  df-ral 3065  df-rex 3074  df-reu 3354  df-rab 3408  df-v 3447  df-sbc 3740  df-csb 3856  df-dif 3913  df-un 3915  df-in 3917  df-ss 3927  df-nul 4283  df-if 4487  df-sn 4587  df-pr 4589  df-op 4593  df-uni 4866  df-iun 4956  df-br 5106  df-opab 5168  df-mpt 5189  df-id 5531  df-xp 5639  df-rel 5640  df-cnv 5641  df-co 5642  df-dm 5643  df-rn 5644  df-res 5645  df-ima 5646  df-iota 6448  df-fun 6498  df-fn 6499  df-f 6500  df-f1 6501  df-fo 6502  df-f1o 6503  df-fv 6504  df-ov 7360  df-oprab 7361  df-mpo 7362  df-of 7617  df-1st 7921  df-2nd 7922
This theorem is referenced by:  ofpreima2  31582
  Copyright terms: Public domain W3C validator