Metamath Proof Explorer


Theorem cotrg

Description: Two ways of saying that the composition of two relations is included in a third relation. See its special instance cotr for the main application. (Contributed by NM, 27-Dec-1996) (Proof shortened by Andrew Salmon, 27-Aug-2011) Generalized from its special instance cotr . (Revised by Richard Penner, 24-Dec-2019)

Ref Expression
Assertion cotrg ( ( 𝐴𝐵 ) ⊆ 𝐶 ↔ ∀ 𝑥𝑦𝑧 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )

Proof

Step Hyp Ref Expression
1 df-co ( 𝐴𝐵 ) = { ⟨ 𝑥 , 𝑧 ⟩ ∣ ∃ 𝑦 ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) }
2 1 relopabiv Rel ( 𝐴𝐵 )
3 ssrel ( Rel ( 𝐴𝐵 ) → ( ( 𝐴𝐵 ) ⊆ 𝐶 ↔ ∀ 𝑥𝑧 ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) → ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 ) ) )
4 2 3 ax-mp ( ( 𝐴𝐵 ) ⊆ 𝐶 ↔ ∀ 𝑥𝑧 ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) → ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 ) )
5 vex 𝑥 ∈ V
6 vex 𝑧 ∈ V
7 5 6 opelco ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) ↔ ∃ 𝑦 ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) )
8 df-br ( 𝑥 𝐶 𝑧 ↔ ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 )
9 8 bicomi ( ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶𝑥 𝐶 𝑧 )
10 7 9 imbi12i ( ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) → ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 ) ↔ ( ∃ 𝑦 ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )
11 19.23v ( ∀ 𝑦 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) ↔ ( ∃ 𝑦 ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )
12 10 11 bitr4i ( ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) → ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 ) ↔ ∀ 𝑦 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )
13 12 albii ( ∀ 𝑧 ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) → ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 ) ↔ ∀ 𝑧𝑦 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )
14 alcom ( ∀ 𝑧𝑦 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) ↔ ∀ 𝑦𝑧 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )
15 13 14 bitri ( ∀ 𝑧 ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) → ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 ) ↔ ∀ 𝑦𝑧 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )
16 15 albii ( ∀ 𝑥𝑧 ( ⟨ 𝑥 , 𝑧 ⟩ ∈ ( 𝐴𝐵 ) → ⟨ 𝑥 , 𝑧 ⟩ ∈ 𝐶 ) ↔ ∀ 𝑥𝑦𝑧 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )
17 4 16 bitri ( ( 𝐴𝐵 ) ⊆ 𝐶 ↔ ∀ 𝑥𝑦𝑧 ( ( 𝑥 𝐵 𝑦𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )