Proposition 4

Tag 03HL, permanent. Cite it as [Bourbaki, Tag 03HL].

Theory of Sets, chapter II, § 3. Correspondences

Let $G_1$ , $G_2$ , $G_3$ be graphs. Then

(G_3 \circ G_2) \circ G_1 = G_3 \circ (G_2 \circ G_1).

The relation $(x, t) \in (G_3 \circ G_2) \circ G_1$ is equivalent to the relation

(\exists y)((x, y) \in G_1 \text{ and } \exists z((y, z) \in G_2 \text{ and } (z, t) \in G_3))

and therefore (by C33 (Chapter I, § 4, no. 3)) to the relation

(1)

(\exists y)(\exists z)((x, y) \in G_1 \text{ and } (y, z) \in G_2 \text{ and } (z, t) \in G_3).

Similarly, the relation $(x, t) \in G_3 \circ (G_2 \circ G_1)$ is equivalent to

(2)

(\exists z)(\exists y)((x, y) \in G_1 \text{ and } (y, z) \in G_2 \text{ and } (z, t) \in G_3).

But the relations (1) and (2) are equivalent; hence the result.

¶ The graph $G_3 \circ (G_2 \circ G_1)$ is denoted by $G_3 \circ G_2 \circ G_1$ . Similarly, if $G_1$ , $G_2$ , $G_3$ , $G_4$ are graphs, we put

G_4 \circ (G_3 \circ G_2 \circ G_1) = G_4 \circ G_3 \circ G_2 \circ G_1;

and so on.

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.

Cited by

Nothing.

Cites

Chapter I, § 4, no. 3