Theorem coeq0

Description: A composition of two relations is empty iff there is no overlap between the range of the second and the domain of the first. Useful in combination with coundi and coundir to prune meaningless terms in the result. (Contributed by Stefan O'Rear, 8-Oct-2014)

	Ref	Expression
Assertion	coeq0	$$⊢A\circ B=\varnothing \leftrightarrow \mathrm{dom}A\cap \mathrm{ran}B=\varnothing$$

Proof

Step	Hyp	Ref	Expression
1		relco	$$⊢\mathrm{Rel}\left(A\circ B\right)$$
2		relrn0	$$⊢\mathrm{Rel}\left(A\circ B\right)\to \left(A\circ B=\varnothing \leftrightarrow \mathrm{ran}\left(A\circ B\right)=\varnothing \right)$$
3	1 2	ax-mp	$$⊢A\circ B=\varnothing \leftrightarrow \mathrm{ran}\left(A\circ B\right)=\varnothing$$
4		rnco	$$⊢\mathrm{ran}\left(A\circ B\right)=\mathrm{ran}\left({A\upharpoonright }_{\mathrm{ran}B}\right)$$
5	4	eqeq1i	$$⊢\mathrm{ran}\left(A\circ B\right)=\varnothing \leftrightarrow \mathrm{ran}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\varnothing$$
6		relres	$$⊢\mathrm{Rel}\left({A\upharpoonright }_{\mathrm{ran}B}\right)$$
7		reldm0	$$⊢\mathrm{Rel}\left({A\upharpoonright }_{\mathrm{ran}B}\right)\to \left({A\upharpoonright }_{\mathrm{ran}B}=\varnothing \leftrightarrow \mathrm{dom}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\varnothing \right)$$
8	6 7	ax-mp	$$⊢{A\upharpoonright }_{\mathrm{ran}B}=\varnothing \leftrightarrow \mathrm{dom}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\varnothing$$
9		relrn0	$$⊢\mathrm{Rel}\left({A\upharpoonright }_{\mathrm{ran}B}\right)\to \left({A\upharpoonright }_{\mathrm{ran}B}=\varnothing \leftrightarrow \mathrm{ran}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\varnothing \right)$$
10	6 9	ax-mp	$$⊢{A\upharpoonright }_{\mathrm{ran}B}=\varnothing \leftrightarrow \mathrm{ran}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\varnothing$$
11		dmres	$$⊢\mathrm{dom}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\mathrm{ran}B\cap \mathrm{dom}A$$
12		incom	$$⊢\mathrm{ran}B\cap \mathrm{dom}A=\mathrm{dom}A\cap \mathrm{ran}B$$
13	11 12	eqtri	$$⊢\mathrm{dom}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\mathrm{dom}A\cap \mathrm{ran}B$$
14	13	eqeq1i	$$⊢\mathrm{dom}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\varnothing \leftrightarrow \mathrm{dom}A\cap \mathrm{ran}B=\varnothing$$
15	8 10 14	3bitr3i	$$⊢\mathrm{ran}\left({A\upharpoonright }_{\mathrm{ran}B}\right)=\varnothing \leftrightarrow \mathrm{dom}A\cap \mathrm{ran}B=\varnothing$$
16	3 5 15	3bitri	$$⊢A\circ B=\varnothing \leftrightarrow \mathrm{dom}A\cap \mathrm{ran}B=\varnothing$$