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 32434
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 5250 . . . . . . 7 𝑠(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2 ofpreima.1 . . . . . . 7 (𝜑𝐹:𝐴𝐵)
3 ofpreima.2 . . . . . . 7 (𝜑𝐺:𝐴𝐶)
4 ofpreima.3 . . . . . . 7 (𝜑𝐴𝑉)
5 eqidd 2728 . . . . . . 7 (𝜑 → (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩))
6 ofpreima.4 . . . . . . . 8 (𝜑𝑅 Fn (𝐵 × 𝐶))
7 fnov 7546 . . . . . . . 8 (𝑅 Fn (𝐵 × 𝐶) ↔ 𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
86, 7sylib 217 . . . . . . 7 (𝜑𝑅 = (𝑥𝐵, 𝑦𝐶 ↦ (𝑥𝑅𝑦)))
91, 2, 3, 4, 5, 8ofoprabco 32433 . . . . . 6 (𝜑 → (𝐹f 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
109cnveqd 5872 . . . . 5 (𝜑(𝐹f 𝑅𝐺) = (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)))
11 cnvco 5882 . . . . 5 (𝑅 ∘ (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅)
1210, 11eqtrdi 2783 . . . 4 (𝜑(𝐹f 𝑅𝐺) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅))
1312imaeq1d 6056 . . 3 (𝜑 → ((𝐹f 𝑅𝐺) “ 𝐷) = (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷))
14 imaco 6249 . . 3 (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∘ 𝑅) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷))
1513, 14eqtrdi 2783 . 2 (𝜑 → ((𝐹f 𝑅𝐺) “ 𝐷) = ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)))
16 dfima2 6059 . . 3 ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞}
17 vex 3473 . . . . . . . 8 𝑝 ∈ V
18 vex 3473 . . . . . . . 8 𝑞 ∈ V
1917, 18brcnv 5879 . . . . . . 7 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝)
20 funmpt 6585 . . . . . . . . 9 Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
21 funbrfv2b 6950 . . . . . . . . 9 (Fun (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) → (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝)))
2220, 21ax-mp 5 . . . . . . . 8 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
23 opex 5460 . . . . . . . . . . 11 ⟨(𝐹𝑠), (𝐺𝑠)⟩ ∈ V
24 eqid 2727 . . . . . . . . . . 11 (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)
2523, 24dmmpti 6693 . . . . . . . . . 10 dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) = 𝐴
2625eleq2i 2820 . . . . . . . . 9 (𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ↔ 𝑞𝐴)
2726anbi1i 623 . . . . . . . 8 ((𝑞 ∈ dom (𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
2822, 27bitri 275 . . . . . . 7 (𝑞(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑝 ↔ (𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝))
29 fveq2 6891 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐹𝑠) = (𝐹𝑞))
30 fveq2 6891 . . . . . . . . . . 11 (𝑠 = 𝑞 → (𝐺𝑠) = (𝐺𝑞))
3129, 30opeq12d 4877 . . . . . . . . . 10 (𝑠 = 𝑞 → ⟨(𝐹𝑠), (𝐺𝑠)⟩ = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
32 opex 5460 . . . . . . . . . 10 ⟨(𝐹𝑞), (𝐺𝑞)⟩ ∈ V
3331, 24, 32fvmpt 6999 . . . . . . . . 9 (𝑞𝐴 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = ⟨(𝐹𝑞), (𝐺𝑞)⟩)
3433eqeq1d 2729 . . . . . . . 8 (𝑞𝐴 → (((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3534pm5.32i 574 . . . . . . 7 ((𝑞𝐴 ∧ ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)‘𝑞) = 𝑝) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3619, 28, 353bitri 297 . . . . . 6 (𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3736rexbii 3089 . . . . 5 (∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞 ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
3837abbii 2797 . . . 4 {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
39 nfv 1910 . . . . 5 𝑞𝜑
40 nfab1 2900 . . . . 5 𝑞{𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}
41 nfcv 2898 . . . . 5 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))
42 eliun 4995 . . . . . 6 (𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
43 ffn 6716 . . . . . . . . . . . . 13 (𝐹:𝐴𝐵𝐹 Fn 𝐴)
44 fniniseg 7063 . . . . . . . . . . . . 13 (𝐹 Fn 𝐴 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
452, 43, 443syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ↔ (𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝))))
46 ffn 6716 . . . . . . . . . . . . 13 (𝐺:𝐴𝐶𝐺 Fn 𝐴)
47 fniniseg 7063 . . . . . . . . . . . . 13 (𝐺 Fn 𝐴 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
483, 46, 473syl 18 . . . . . . . . . . . 12 (𝜑 → (𝑞 ∈ (𝐺 “ {(2nd𝑝)}) ↔ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
4945, 48anbi12d 630 . . . . . . . . . . 11 (𝜑 → ((𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝)))))
50 elin 3960 . . . . . . . . . . 11 (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞 ∈ (𝐹 “ {(1st𝑝)}) ∧ 𝑞 ∈ (𝐺 “ {(2nd𝑝)})))
51 anandi 675 . . . . . . . . . . 11 ((𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))) ↔ ((𝑞𝐴 ∧ (𝐹𝑞) = (1st𝑝)) ∧ (𝑞𝐴 ∧ (𝐺𝑞) = (2nd𝑝))))
5249, 50, 513bitr4g 314 . . . . . . . . . 10 (𝜑 → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
5352adantr 480 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
54 cnvimass 6079 . . . . . . . . . . . . . 14 (𝑅𝐷) ⊆ dom 𝑅
556fndmd 6653 . . . . . . . . . . . . . 14 (𝜑 → dom 𝑅 = (𝐵 × 𝐶))
5654, 55sseqtrid 4030 . . . . . . . . . . . . 13 (𝜑 → (𝑅𝐷) ⊆ (𝐵 × 𝐶))
5756sselda 3978 . . . . . . . . . . . 12 ((𝜑𝑝 ∈ (𝑅𝐷)) → 𝑝 ∈ (𝐵 × 𝐶))
58 1st2nd2 8026 . . . . . . . . . . . 12 (𝑝 ∈ (𝐵 × 𝐶) → 𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩)
59 eqeq2 2739 . . . . . . . . . . . 12 (𝑝 = ⟨(1st𝑝), (2nd𝑝)⟩ → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
6057, 58, 593syl 18 . . . . . . . . . . 11 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩))
61 fvex 6904 . . . . . . . . . . . 12 (𝐹𝑞) ∈ V
62 fvex 6904 . . . . . . . . . . . 12 (𝐺𝑞) ∈ V
6361, 62opth 5472 . . . . . . . . . . 11 (⟨(𝐹𝑞), (𝐺𝑞)⟩ = ⟨(1st𝑝), (2nd𝑝)⟩ ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))
6460, 63bitrdi 287 . . . . . . . . . 10 ((𝜑𝑝 ∈ (𝑅𝐷)) → (⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝 ↔ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝))))
6564anbi2d 628 . . . . . . . . 9 ((𝜑𝑝 ∈ (𝑅𝐷)) → ((𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝) ↔ (𝑞𝐴 ∧ ((𝐹𝑞) = (1st𝑝) ∧ (𝐺𝑞) = (2nd𝑝)))))
6653, 65bitr4d 282 . . . . . . . 8 ((𝜑𝑝 ∈ (𝑅𝐷)) → (𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ (𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
6766rexbidva 3171 . . . . . . 7 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)))
68 abid 2708 . . . . . . 7 (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝))
6967, 68bitr4di 289 . . . . . 6 (𝜑 → (∃𝑝 ∈ (𝑅𝐷)𝑞 ∈ ((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})) ↔ 𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)}))
7042, 69bitr2id 284 . . . . 5 (𝜑 → (𝑞 ∈ {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} ↔ 𝑞 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)}))))
7139, 40, 41, 70eqrd 3997 . . . 4 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)(𝑞𝐴 ∧ ⟨(𝐹𝑞), (𝐺𝑞)⟩ = 𝑝)} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7238, 71eqtrid 2779 . . 3 (𝜑 → {𝑞 ∣ ∃𝑝 ∈ (𝑅𝐷)𝑝(𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩)𝑞} = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7316, 72eqtrid 2779 . 2 (𝜑 → ((𝑠𝐴 ↦ ⟨(𝐹𝑠), (𝐺𝑠)⟩) “ (𝑅𝐷)) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
7415, 73eqtrd 2767 1 (𝜑 → ((𝐹f 𝑅𝐺) “ 𝐷) = 𝑝 ∈ (𝑅𝐷)((𝐹 “ {(1st𝑝)}) ∩ (𝐺 “ {(2nd𝑝)})))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 395   = wceq 1534  wcel 2099  {cab 2704  wrex 3065  cin 3943  {csn 4624  cop 4630   ciun 4991   class class class wbr 5142  cmpt 5225   × cxp 5670  ccnv 5671  dom cdm 5672  cima 5675  ccom 5676  Fun wfun 6536   Fn wfn 6537  wf 6538  cfv 6542  (class class class)co 7414  cmpo 7416  f cof 7677  1st c1st 7985  2nd c2nd 7986
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1790  ax-4 1804  ax-5 1906  ax-6 1964  ax-7 2004  ax-8 2101  ax-9 2109  ax-10 2130  ax-11 2147  ax-12 2164  ax-ext 2698  ax-rep 5279  ax-sep 5293  ax-nul 5300  ax-pr 5423  ax-un 7734
This theorem depends on definitions:  df-bi 206  df-an 396  df-or 847  df-3an 1087  df-tru 1537  df-fal 1547  df-ex 1775  df-nf 1779  df-sb 2061  df-mo 2529  df-eu 2558  df-clab 2705  df-cleq 2719  df-clel 2805  df-nfc 2880  df-ne 2936  df-ral 3057  df-rex 3066  df-reu 3372  df-rab 3428  df-v 3471  df-sbc 3775  df-csb 3890  df-dif 3947  df-un 3949  df-in 3951  df-ss 3961  df-nul 4319  df-if 4525  df-sn 4625  df-pr 4627  df-op 4631  df-uni 4904  df-iun 4993  df-br 5143  df-opab 5205  df-mpt 5226  df-id 5570  df-xp 5678  df-rel 5679  df-cnv 5680  df-co 5681  df-dm 5682  df-rn 5683  df-res 5684  df-ima 5685  df-iota 6494  df-fun 6544  df-fn 6545  df-f 6546  df-f1 6547  df-fo 6548  df-f1o 6549  df-fv 6550  df-ov 7417  df-oprab 7418  df-mpo 7419  df-of 7679  df-1st 7987  df-2nd 7988
This theorem is referenced by:  ofpreima2  32435
  Copyright terms: Public domain W3C validator