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

Theorem th3qlem2 6500
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 2117 . . . . 5 (𝑆 × 𝑆) = (𝑆 × 𝑆)
3 breq1 3902 . . . . . . . 8 (⟨𝑤, 𝑣⟩ = 𝑠 → (⟨𝑤, 𝑣𝑢, 𝑡⟩ ↔ 𝑠 𝑢, 𝑡⟩))
43anbi1d 460 . . . . . . 7 (⟨𝑤, 𝑣⟩ = 𝑠 → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) ↔ (𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦)))
5 oveq1 5749 . . . . . . . 8 (⟨𝑤, 𝑣⟩ = 𝑠 → (⟨𝑤, 𝑣+ 𝑥) = (𝑠 + 𝑥))
65breq1d 3909 . . . . . . 7 (⟨𝑤, 𝑣⟩ = 𝑠 → ((⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦) ↔ (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦)))
74, 6imbi12d 233 . . . . . 6 (⟨𝑤, 𝑣⟩ = 𝑠 → (((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦)) ↔ ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
87imbi2d 229 . . . . 5 (⟨𝑤, 𝑣⟩ = 𝑠 → (((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))) ↔ ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦)))))
9 breq2 3903 . . . . . . . 8 (⟨𝑢, 𝑡⟩ = 𝑓 → (𝑠 𝑢, 𝑡⟩ ↔ 𝑠 𝑓))
109anbi1d 460 . . . . . . 7 (⟨𝑢, 𝑡⟩ = 𝑓 → ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) ↔ (𝑠 𝑓𝑥 𝑦)))
11 oveq1 5749 . . . . . . . 8 (⟨𝑢, 𝑡⟩ = 𝑓 → (⟨𝑢, 𝑡+ 𝑦) = (𝑓 + 𝑦))
1211breq2d 3911 . . . . . . 7 (⟨𝑢, 𝑡⟩ = 𝑓 → ((𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦) ↔ (𝑠 + 𝑥) (𝑓 + 𝑦)))
1310, 12imbi12d 233 . . . . . 6 (⟨𝑢, 𝑡⟩ = 𝑓 → (((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦)) ↔ ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦))))
1413imbi2d 229 . . . . 5 (⟨𝑢, 𝑡⟩ = 𝑓 → (((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (𝑠 + 𝑥) (⟨𝑢, 𝑡+ 𝑦))) ↔ ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦)))))
15 breq1 3902 . . . . . . . . . 10 (⟨𝑠, 𝑓⟩ = 𝑥 → (⟨𝑠, 𝑓𝑔, ⟩ ↔ 𝑥 𝑔, ⟩))
1615anbi2d 459 . . . . . . . . 9 (⟨𝑠, 𝑓⟩ = 𝑥 → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) ↔ (⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩)))
17 oveq2 5750 . . . . . . . . . 10 (⟨𝑠, 𝑓⟩ = 𝑥 → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) = (⟨𝑤, 𝑣+ 𝑥))
1817breq1d 3909 . . . . . . . . 9 (⟨𝑠, 𝑓⟩ = 𝑥 → ((⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩) ↔ (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩)))
1916, 18imbi12d 233 . . . . . . . 8 (⟨𝑠, 𝑓⟩ = 𝑥 → (((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩)) ↔ ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩))))
2019imbi2d 229 . . . . . . 7 (⟨𝑠, 𝑓⟩ = 𝑥 → ((((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩))) ↔ (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩)))))
21 breq2 3903 . . . . . . . . . 10 (⟨𝑔, ⟩ = 𝑦 → (𝑥 𝑔, ⟩ ↔ 𝑥 𝑦))
2221anbi2d 459 . . . . . . . . 9 (⟨𝑔, ⟩ = 𝑦 → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) ↔ (⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦)))
23 oveq2 5750 . . . . . . . . . 10 (⟨𝑔, ⟩ = 𝑦 → (⟨𝑢, 𝑡+𝑔, ⟩) = (⟨𝑢, 𝑡+ 𝑦))
2423breq2d 3911 . . . . . . . . 9 (⟨𝑔, ⟩ = 𝑦 → ((⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩) ↔ (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦)))
2522, 24imbi12d 233 . . . . . . . 8 (⟨𝑔, ⟩ = 𝑦 → (((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩)) ↔ ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
2625imbi2d 229 . . . . . . 7 (⟨𝑔, ⟩ = 𝑦 → ((((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑔, ⟩) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+𝑔, ⟩))) ↔ (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦)))))
27 th3q.4 . . . . . . . 8 ((((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) ∧ ((𝑠𝑆𝑓𝑆) ∧ (𝑔𝑆𝑆))) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩)))
2827expcom 115 . . . . . . 7 (((𝑠𝑆𝑓𝑆) ∧ (𝑔𝑆𝑆)) → (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ ⟨𝑠, 𝑓𝑔, ⟩) → (⟨𝑤, 𝑣+𝑠, 𝑓⟩) (⟨𝑢, 𝑡+𝑔, ⟩))))
292, 20, 26, 282optocl 4586 . . . . . 6 ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
3029com12 30 . . . . 5 (((𝑤𝑆𝑣𝑆) ∧ (𝑢𝑆𝑡𝑆)) → ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((⟨𝑤, 𝑣𝑢, 𝑡⟩ ∧ 𝑥 𝑦) → (⟨𝑤, 𝑣+ 𝑥) (⟨𝑢, 𝑡+ 𝑦))))
312, 8, 14, 302optocl 4586 . . . 4 ((𝑠 ∈ (𝑆 × 𝑆) ∧ 𝑓 ∈ (𝑆 × 𝑆)) → ((𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆)) → ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦))))
3231imp 123 . . 3 (((𝑠 ∈ (𝑆 × 𝑆) ∧ 𝑓 ∈ (𝑆 × 𝑆)) ∧ (𝑥 ∈ (𝑆 × 𝑆) ∧ 𝑦 ∈ (𝑆 × 𝑆))) → ((𝑠 𝑓𝑥 𝑦) → (𝑠 + 𝑥) (𝑓 + 𝑦)))
331, 32th3qlem1 6499 . 2 ((𝐴 ∈ ((𝑆 × 𝑆) / ) ∧ 𝐵 ∈ ((𝑆 × 𝑆) / )) → ∃*𝑧𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
34 vex 2663 . . . . . . 7 𝑤 ∈ V
35 vex 2663 . . . . . . 7 𝑣 ∈ V
3634, 35opex 4121 . . . . . 6 𝑤, 𝑣⟩ ∈ V
37 vex 2663 . . . . . . 7 𝑢 ∈ V
38 vex 2663 . . . . . . 7 𝑡 ∈ V
3937, 38opex 4121 . . . . . 6 𝑢, 𝑡⟩ ∈ V
40 eceq1 6432 . . . . . . . . 9 (𝑠 = ⟨𝑤, 𝑣⟩ → [𝑠] = [⟨𝑤, 𝑣⟩] )
4140eqeq2d 2129 . . . . . . . 8 (𝑠 = ⟨𝑤, 𝑣⟩ → (𝐴 = [𝑠] 𝐴 = [⟨𝑤, 𝑣⟩] ))
42 eceq1 6432 . . . . . . . . 9 (𝑥 = ⟨𝑢, 𝑡⟩ → [𝑥] = [⟨𝑢, 𝑡⟩] )
4342eqeq2d 2129 . . . . . . . 8 (𝑥 = ⟨𝑢, 𝑡⟩ → (𝐵 = [𝑥] 𝐵 = [⟨𝑢, 𝑡⟩] ))
4441, 43bi2anan9 580 . . . . . . 7 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → ((𝐴 = [𝑠] 𝐵 = [𝑥] ) ↔ (𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] )))
45 oveq12 5751 . . . . . . . . 9 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → (𝑠 + 𝑥) = (⟨𝑤, 𝑣+𝑢, 𝑡⟩))
4645eceq1d 6433 . . . . . . . 8 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → [(𝑠 + 𝑥)] = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] )
4746eqeq2d 2129 . . . . . . 7 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → (𝑧 = [(𝑠 + 𝑥)] 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ))
4844, 47anbi12d 464 . . . . . 6 ((𝑠 = ⟨𝑤, 𝑣⟩ ∧ 𝑥 = ⟨𝑢, 𝑡⟩) → (((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ) ↔ ((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] )))
4936, 39, 48spc2ev 2755 . . . . 5 (((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ) → ∃𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
5049exlimivv 1852 . . . 4 (∃𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ) → ∃𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
5150exlimivv 1852 . . 3 (∃𝑤𝑣𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ) → ∃𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ))
5251moimi 2042 . 2 (∃*𝑧𝑠𝑥((𝐴 = [𝑠] 𝐵 = [𝑥] ) ∧ 𝑧 = [(𝑠 + 𝑥)] ) → ∃*𝑧𝑤𝑣𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ))
5333, 52syl 14 1 ((𝐴 ∈ ((𝑆 × 𝑆) / ) ∧ 𝐵 ∈ ((𝑆 × 𝑆) / )) → ∃*𝑧𝑤𝑣𝑢𝑡((𝐴 = [⟨𝑤, 𝑣⟩] 𝐵 = [⟨𝑢, 𝑡⟩] ) ∧ 𝑧 = [(⟨𝑤, 𝑣+𝑢, 𝑡⟩)] ))
Colors of variables: wff set class
Syntax hints:  wi 4  wa 103   = wceq 1316  wex 1453  wcel 1465  ∃*wmo 1978  Vcvv 2660  cop 3500   class class class wbr 3899   × cxp 4507  (class class class)co 5742   Er wer 6394  [cec 6395   / cqs 6396
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-io 683  ax-5 1408  ax-7 1409  ax-gen 1410  ax-ie1 1454  ax-ie2 1455  ax-8 1467  ax-10 1468  ax-11 1469  ax-i12 1470  ax-bndl 1471  ax-4 1472  ax-14 1477  ax-17 1491  ax-i9 1495  ax-ial 1499  ax-i5r 1500  ax-ext 2099  ax-sep 4016  ax-pow 4068  ax-pr 4101
This theorem depends on definitions:  df-bi 116  df-3an 949  df-tru 1319  df-nf 1422  df-sb 1721  df-eu 1980  df-mo 1981  df-clab 2104  df-cleq 2110  df-clel 2113  df-nfc 2247  df-ral 2398  df-rex 2399  df-v 2662  df-sbc 2883  df-un 3045  df-in 3047  df-ss 3054  df-pw 3482  df-sn 3503  df-pr 3504  df-op 3506  df-uni 3707  df-br 3900  df-opab 3960  df-xp 4515  df-rel 4516  df-cnv 4517  df-co 4518  df-dm 4519  df-rn 4520  df-res 4521  df-ima 4522  df-iota 5058  df-fv 5101  df-ov 5745  df-er 6397  df-ec 6399  df-qs 6403
This theorem is referenced by:  th3qcor  6501  th3q  6502
  Copyright terms: Public domain W3C validator