PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

$T \circ (S \circ R) = (T \circ S) \circ R$ , $(S \circ R)^{- 1} = R^{- 1} \circ S^{- 1}$ , $(R^{- 1})^{- 1} = R$ , $dom (R^{- 1}) = ran R$ , and $Δ_{B} \circ R = R = R \circ Δ_{A}$ for a relation $R$ from $A$ to $B$

Statement

Let $R$ , $S$ , $T$ be relations and let $A$ , $B$ be sets. Then

(i) $T \circ (S \circ R) = (T \circ S) \circ R$ ;
(ii) $(S \circ R)^{- 1} = R^{- 1} \circ S^{- 1}$ ;
(iii) $(R^{- 1})^{- 1} = R$ ;
(iv) $dom (R^{- 1}) = ran R$ and $ran (R^{- 1}) = dom R$ ;
(v) if $R$ is a relation from $A$ to $B$ , then $Δ_{B} \circ R = R$ and $R \circ Δ_{A} = R$ .

Facts & Assumptions

Given: relations $R$ , $S$ , $T$ and sets $A$ , $B$ .

[L1]

$(b, a) \in R^{- 1}$ holds if and only if $(a, b) \in R$ ; $(a, c) \in S \circ R$ holds if and only if $(a, b) \in R$ and $(b, c) \in S$ for some $b$ (The inverse relation $R^{- 1}$ , the composite $S \circ R$ , and the restriction $R ↾ A$ ).

[L2]

A relation is a set $R$ every element of which is an ordered pair (Relation, $dom R$ , $ran R$ , $fld R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L3]

$dom R : = {a : \exists b (a, b) \in R}, ran R : = {b : \exists a (a, b) \in R}$ (Relation, $dom R$ , $ran R$ , $fld R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L4]

$(a, b) \in Δ_{A}$ holds if and only if $a = b$ and $a \in A$ (The identity relation $Δ_{A} = {(a, b) \in A \times A : a = b}$ and the membership relation $\in_{A} = {(a, b) \in A \times A : a \in b}$ ).

[L5]

$(a, b) = (c, d)$ if and only if $a = c$ and $b = d$ ( $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$ ).

[L6]

If every $z$ satisfies $z \in x$ if and only if $z \in y$ , then $x = y$ (The Axiom of Extensionality: $\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \to x = y)$ ).

[L7]

$R \subseteq A \times B$ if and only if $dom R \subseteq A$ and $ran R \subseteq B$ (Every relation $R$ satisfies $R \subseteq dom R \times ran R$ , and $R$ is a relation from $A$ to $B$ if and only if $dom R \subseteq A$ and $ran R \subseteq B$ ).

[L8]

$(a, b) : = {{a}, {a, b}}$ (The Kuratowski ordered pair $(a, b) : = {{a}, {a, b}}$ ).

Proof

technique · direct

1.1

Claim (i): every element of either side is an ordered pair, and $(a, d)$ lies in $T \circ (S \circ R)$ exactly when there is $c$ with $(a, c) \in S \circ R$ and $(c, d) \in T$ , that is, exactly when there are $b$ and $c$ with $(a, b) \in R$ , $(b, c) \in S$ and $(c, d) \in T$ . Reading the same condition with the middle pair grouped the other way gives membership in $(T \circ S) \circ R$ .

L1L2L5L6L8

1.2

Claim (ii): $(c, a) \in (S \circ R)^{- 1}$ exactly when $(a, c) \in S \circ R$ , that is, exactly when there is $b$ with $(a, b) \in R$ and $(b, c) \in S$ ; and that says exactly that $(c, b) \in S^{- 1}$ and $(b, a) \in R^{- 1}$ for some $b$ , which is $(c, a) \in R^{- 1} \circ S^{- 1}$ .

L1L2L5L6L8

1.3

Claim (iii): every element of $R$ is an ordered pair $(a, b)$ , and $(a, b) \in (R^{- 1})^{- 1}$ exactly when $(b, a) \in R^{- 1}$ , exactly when $(a, b) \in R$ ; both sides consist of ordered pairs, so they are equal.

L1L2L5L6L8

1.4

Claim (iv): $a \in dom (R^{- 1})$ exactly when $(a, b) \in R^{- 1}$ for some $b$ , exactly when $(b, a) \in R$ for some $b$ , exactly when $a \in ran R$ ; the second identity is the same argument with the coordinates exchanged.

L1L3L6

2.1

Claim (v): let $R$ be a relation from $A$ to $B$ , so $dom R \subseteq A$ and $ran R \subseteq B$ . Then $(a, c) \in Δ_{B} \circ R$ exactly when there is $b$ with $(a, b) \in R$ and $b = c \in B$ , that is, exactly when $(a, c) \in R$ and $c \in B$ ; and $(a, c) \in R$ already forces $c \in ran R \subseteq B$ , so the two sets are equal. Symmetrically $(a, c) \in R \circ Δ_{A}$ exactly when $a \in A$ and $(a, c) \in R$ , and $(a, c) \in R$ forces $a \in dom R \subseteq A$ .

L1L3L4L6L7step 1.4

3.1

Claims (i) to (v) are established, which is the statement.

step 1.1step 1.2step 1.3step 1.4step 2.1∎

Depends on

Used by

Dependency tree · two levels

17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

B. Kaya, MATH 320 Set Theory (METU), Exercises 7 and 8 (standard reference, not scraped)
Composition of relations (Wikipedia) (standard reference, not scraped)
Binary relation (Wikipedia) (standard reference, not scraped)

T∘(S∘R)=(T∘S)∘RT∘(S∘R)=(T∘S)∘R, (S∘R)−1=R−1∘S−1(S∘R)−1=R−1∘S−1, (R−1)−1=R(R−1)−1=R, dom⁡(R−1)=ran⁡Rdom(R−1)=ranR, and ΔB∘R=R=R∘ΔAΔB​∘R=R=R∘ΔA​ for a relation RR from AA to BB

Statement

Facts & Assumptions

Proof

Depends on

Used by

Dependency tree · two levels

Sources

$T \circ (S \circ R) = (T \circ S) \circ R$ , $(S \circ R)^{- 1} = R^{- 1} \circ S^{- 1}$ , $(R^{- 1})^{- 1} = R$ , $dom (R^{- 1}) = ran R$ , and $Δ_{B} \circ R = R = R \circ Δ_{A}$ for a relation $R$ from $A$ to $B$