Intuitionistic Logic Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  ILE Home  >  Th. List  >  th3qlem2 GIF version

Theorem th3qlem2 6209
 Description: Lemma for Exercise 44 version of Theorem 3Q of [Enderton] p. 60, extended to operations on ordered pairs. The fourth hypothesis is the compatibility assumption. (Contributed by NM, 4-Aug-1995.) (Revised by Mario Carneiro, 12-Aug-2015.)
Hypotheses
Ref Expression
th3q.1 ∈ V
th3q.2 Er (𝑆 × 𝑆)
th3q.4 ((((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) ∧ ((𝑠𝑆𝑓𝑆) ∧ (𝑔𝑆𝑆))) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩)))
Assertion
Ref Expression
th3qlem2 ((𝐴 ∈ ((𝑆 × 𝑆) / ) ∧ 𝐵 ∈ ((𝑆 × 𝑆) / )) → ∃*𝑧𝑤𝑣𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ))
Distinct variable groups:   𝑧,𝑤,𝑣,𝑢,𝑡,𝑠,𝑓,𝑔,,   𝑧,𝑆,𝑤,𝑣,𝑢,𝑡,𝑠,𝑓,𝑔,   𝑧,𝐴,𝑤,𝑣,𝑢,𝑡,𝑠,𝑓   𝑧,𝐵,𝑤,𝑣,𝑢,𝑡,𝑠,𝑓   𝑧, + ,𝑤,𝑣,𝑢,𝑡,𝑠,𝑓,𝑔,
Allowed substitution hints:   𝐴(𝑔,)   𝐵(𝑔,)

Proof of Theorem th3qlem2
Dummy variables 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 th3q.2 . . 3 Er (𝑆 × 𝑆)
2 eqid 2040 . . . . 5 (𝑆 × 𝑆) = (𝑆 × 𝑆)
3 breq1 3767 . . . . . . . 8 (⟨𝑤, 𝑣⟩ = 𝑠 → (⟨𝑤, 𝑣𝑢, 𝑡⟩ ↔ 𝑠 𝑢, 𝑡⟩))
43anbi1d 438 . . . . . . 7 (⟨𝑤, 𝑣⟩ = 𝑠 → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) ↔ (𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦)))
5 oveq1 5519 . . . . . . . 8 (⟨𝑤, 𝑣⟩ = 𝑠 → (⟨𝑤, 𝑣+ 𝑥) = (𝑠 + 𝑥))
65breq1d 3774 . . . . . . 7 (⟨𝑤, 𝑣⟩ = 𝑠 → ((⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦) ↔ (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦)))
74, 6imbi12d 223 . . . . . 6 (⟨𝑤, 𝑣⟩ = 𝑠 → (((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦)) ↔ ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
87imbi2d 219 . . . . 5 (⟨𝑤, 𝑣⟩ = 𝑠 → (((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))) ↔ ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦)))))
9 breq2 3768 . . . . . . . 8 (⟨𝑢, 𝑡⟩ = 𝑓 → (𝑠 𝑢, 𝑡⟩ ↔ 𝑠 𝑓))
109anbi1d 438 . . . . . . 7 (⟨𝑢, 𝑡⟩ = 𝑓 → ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) ↔ (𝑠 𝑓𝑥 𝑦)))
11 oveq1 5519 . . . . . . . 8 (⟨𝑢, 𝑡⟩ = 𝑓 → (⟨𝑢, 𝑡+ 𝑦) = (𝑓 + 𝑦))
1211breq2d 3776 . . . . . . 7 (⟨𝑢, 𝑡⟩ = 𝑓 → ((𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦) ↔ (𝑠 + 𝑥) (𝑓 + 𝑦)))
1310, 12imbi12d 223 . . . . . 6 (⟨𝑢, 𝑡⟩ = 𝑓 → (((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦)) ↔ ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦))))
1413imbi2d 219 . . . . 5 (⟨𝑢, 𝑡⟩ = 𝑓 → (((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦))) ↔ ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦)))))
15 breq1 3767 . . . . . . . . . 10 (⟨𝑠, 𝑓⟩ = 𝑥 → (⟨𝑠, 𝑓𝑔, ⟩ ↔ 𝑥 𝑔, ⟩))
1615anbi2d 437 . . . . . . . . 9 (⟨𝑠, 𝑓⟩ = 𝑥 → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) ↔ (⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩)))
17 oveq2 5520 . . . . . . . . . 10 (⟨𝑠, 𝑓⟩ = 𝑥 → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) = (⟨𝑤, 𝑣+ 𝑥))
1817breq1d 3774 . . . . . . . . 9 (⟨𝑠, 𝑓⟩ = 𝑥 → ((⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩) ↔ (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩)))
1916, 18imbi12d 223 . . . . . . . 8 (⟨𝑠, 𝑓⟩ = 𝑥 → (((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩)) ↔ ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩))))
2019imbi2d 219 . . . . . . 7 (⟨𝑠, 𝑓⟩ = 𝑥 → ((((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩))) ↔ (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩)))))
21 breq2 3768 . . . . . . . . . 10 (⟨𝑔, ⟩ = 𝑦 → (𝑥 𝑔, ⟩ ↔ 𝑥 𝑦))
2221anbi2d 437 . . . . . . . . 9 (⟨𝑔, ⟩ = 𝑦 → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) ↔ (⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦)))
23 oveq2 5520 . . . . . . . . . 10 (⟨𝑔, ⟩ = 𝑦 → (⟨𝑢, 𝑡+𝑔, ⟩) = (⟨𝑢, 𝑡+ 𝑦))
2423breq2d 3776 . . . . . . . . 9 (⟨𝑔, ⟩ = 𝑦 → ((⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩) ↔ (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦)))
2522, 24imbi12d 223 . . . . . . . 8 (⟨𝑔, ⟩ = 𝑦 → (((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩)) ↔ ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
2625imbi2d 219 . . . . . . 7 (⟨𝑔, ⟩ = 𝑦 → ((((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩))) ↔ (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦)))))
27 th3q.4 . . . . . . . 8 ((((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) ∧ ((𝑠𝑆𝑓𝑆) ∧ (𝑔𝑆𝑆))) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩)))
2827expcom 109 . . . . . . 7 (((𝑠𝑆𝑓𝑆) ∧ (𝑔𝑆𝑆)) → (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩))))
292, 20, 26, 282optocl 4417 . . . . . 6 ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
3029com12 27 . . . . 5 (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
312, 8, 14, 302optocl 4417 . . . 4 ((𝑠 ∈ (𝑆 × 𝑆) ∧ 𝑓 ∈ (𝑆 × 𝑆)) → ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦))))
3231imp 115 . . 3 (((𝑠 ∈ (𝑆 × 𝑆) ∧ 𝑓 ∈ (𝑆 × 𝑆)) ∧ (𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆))) → ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦)))
331, 32th3qlem1 6208 . 2 ((𝐴 ∈ ((𝑆 × 𝑆) / ) ∧ 𝐵 ∈ ((𝑆 × 𝑆) / )) → ∃*𝑧𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
34 vex 2560 . . . . . . 7 𝑤 ∈ V
35 vex 2560 . . . . . . 7 𝑣 ∈ V
3634, 35opex 3966 . . . . . 6 𝑤, 𝑣⟩ ∈ V
37 vex 2560 . . . . . . 7 𝑢 ∈ V
38 vex 2560 . . . . . . 7 𝑡 ∈ V
3937, 38opex 3966 . . . . . 6 𝑢, 𝑡⟩ ∈ V
40 eceq1 6141 . . . . . . . . 9 (𝑠 = ⟨𝑤, 𝑣⟩ → [𝑠] = [⟨𝑤, 𝑣⟩] )
4140eqeq2d 2051 . . . . . . . 8 (𝑠 = ⟨𝑤, 𝑣⟩ → (𝐴 = [𝑠] 𝐴 = [⟨𝑤, 𝑣⟩] ))
42 eceq1 6141 . . . . . . . . 9 (𝑥 = ⟨𝑢, 𝑡⟩ → [𝑥] = [⟨𝑢, 𝑡⟩] )
4342eqeq2d 2051 . . . . . . . 8 (𝑥 = ⟨𝑢, 𝑡⟩ → (𝐵 = [𝑥] 𝐵 = [⟨𝑢, 𝑡⟩] ))
4441, 43bi2anan9 538 . . . . . . 7 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → ((𝐴 = [𝑠] 𝐵 = [𝑥] ) ↔ (𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] )))
45 oveq12 5521 . . . . . . . . 9 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → (𝑠 + 𝑥) = (⟨𝑤, 𝑣+𝑢, 𝑡⟩))
4645eceq1d 6142 . . . . . . . 8 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → [(𝑠 + 𝑥)] = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] )
4746eqeq2d 2051 . . . . . . 7 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → (𝑧 = [(𝑠 + 𝑥)] 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ))
4844, 47anbi12d 442 . . . . . 6 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → (((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ) ↔ ((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] )))
4936, 39, 48spc2ev 2648 . . . . 5 (((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ) → ∃𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
5049exlimivv 1776 . . . 4 (∃𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ) → ∃𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
5150exlimivv 1776 . . 3 (∃𝑤𝑣𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ) → ∃𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
5251moimi 1965 . 2 (∃*𝑧𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ) → ∃*𝑧𝑤𝑣𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ))
5333, 52syl 14 1 ((𝐴 ∈ ((𝑆 × 𝑆) / ) ∧ 𝐵 ∈ ((𝑆 × 𝑆) / )) → ∃*𝑧𝑤𝑣𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ))
 Colors of variables: wff set class Syntax hints:   → wi 4   ∧ wa 97   = wceq 1243  ∃wex 1381   ∈ wcel 1393  ∃*wmo 1901  Vcvv 2557  ⟨cop 3378   class class class wbr 3764   × cxp 4343  (class class class)co 5512   Er wer 6103  [cec 6104   / cqs 6105 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 99  ax-ia2 100  ax-ia3 101  ax-io 630  ax-5 1336  ax-7 1337  ax-gen 1338  ax-ie1 1382  ax-ie2 1383  ax-8 1395  ax-10 1396  ax-11 1397  ax-i12 1398  ax-bndl 1399  ax-4 1400  ax-14 1405  ax-17 1419  ax-i9 1423  ax-ial 1427  ax-i5r 1428  ax-ext 2022  ax-sep 3875  ax-pow 3927  ax-pr 3944 This theorem depends on definitions:  df-bi 110  df-3an 887  df-tru 1246  df-nf 1350  df-sb 1646  df-eu 1903  df-mo 1904  df-clab 2027  df-cleq 2033  df-clel 2036  df-nfc 2167  df-ral 2311  df-rex 2312  df-v 2559  df-sbc 2765  df-un 2922  df-in 2924  df-ss 2931  df-pw 3361  df-sn 3381  df-pr 3382  df-op 3384  df-uni 3581  df-br 3765  df-opab 3819  df-xp 4351  df-rel 4352  df-cnv 4353  df-co 4354  df-dm 4355  df-rn 4356  df-res 4357  df-ima 4358  df-iota 4867  df-fv 4910  df-ov 5515  df-er 6106  df-ec 6108  df-qs 6112 This theorem is referenced by:  th3qcor  6210  th3q  6211
 Copyright terms: Public domain W3C validator