Let G, G′ be graphs and let A be a set. Then
(G′∘G)⟨A⟩=G′⟨G⟨A⟩⟩.
For by virtue of C33 (Chapter I, § 4, no. 3) the relation z∈(G′∘G)⟨A⟩ is equivalent to
(∃y)((∃x)(x∈A and (x,y)∈G) and (y,z)∈G′)
and is therefore equivalent to (∃y)(y∈G⟨A⟩ and (y,z)∈G′); hence the result.
¶ If G and G′ are two graphs, we have pr1(G′∘G)=G−1⟨pr1G′⟩, and pr2(G′∘G)=G′⟨pr2G⟩. For example, to prove the second of these relations it is enough to note that the relation z∈pr2(G′∘G) is equivalent to (∃x)((x,z)∈G′∘G) and therefore to
(∃y)((∃x)((x,y)∈G)and(y,z)∈G′);
but this is equivalent to z∈G′⟨pr2G⟩.
¶ If G is a graph and X a set such that X⊂pr1G, we have
X⊂G−1⟨G⟨X⟩⟩.
For the relation x∈X implies by hypothesis that (∃y)((x,y)∈G); but (x,y)∈G is equivalent to (y,x)∈G−1, and on the other hand (x,y)∈G implies (∃z)(z∈X and (z,y)∈G); hence x∈X implies
(∃y)((∃z)(z∈Xand(z,y)∈G)and(y,x)∈G−1),
that is to say, x∈G−1⟨G⟨X⟩⟩.
¶ It is clear that if G1, G2, G1′, G2′ are graphs, the relations G1⊂G2 and G1′⊂G2′ imply G1′∘G1⊂G2′∘G2.
¶ Let Γ=(G,A,B) and Γ′=(G′,B,C) be two correspondences such that the target of Γ is the same as the source of Γ′. From the above discussion we have pr1(G′∘G)⊂pr1G⊂A and pr2(G′∘G)⊂pr2G′⊂C; hence we may state the following definition :
Bourbaki sets the proof directly after the statement, and the corpus does not separate them, so what is above is the statement and its proof together.