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	relopabi	⊢ 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	⊢ ( ( 𝐴 ∘ 𝐵 ) ⊆ 𝐶 ↔ ∀ 𝑥 ∀ 𝑦 ∀ 𝑧 ( ( 𝑥 𝐵 𝑦 ∧ 𝑦 𝐴 𝑧 ) → 𝑥 𝐶 𝑧 ) )