Can the composite of two smooth relations fail to be smooth? Definition 0. Let $A$ and $B$ denote smooth manifolds. Then a smooth relation $A \rightarrow B$ is a smooth submanifold of $A \times B$.
Definition 1. Given relations $P : A \rightarrow B$ and $Q : B \rightarrow C$, define a relation $Q \circ P : A \rightarrow C$ in the usual way:
$$(a,c) \in Q \circ P \leftrightarrow \exists b \in B((b,c) \in Q \wedge (a,b) \in P)$$

Question. Do there exist smooth relations $P : A \rightarrow B$ and $Q : B \rightarrow C$ such that $Q \circ P$ fails to be smooth?

I suspect the answer is "yes", for the following reason: given submanifolds $P \subseteq A \times B$ and $Q \subseteq B \times C$, my geometric intuition tells me that the submanifolds $P \times C$ and $A \times Q$ don't necessarily intersect transversally. For instance, think of $A=B=C=\mathbb{R}$. Assume $P$ and $Q$ are the unit circle. Then $P \times \mathbb{R}$ and $\mathbb{R} \times Q$ are cylinders at right angles to each other. There should be points where these don't intersect transversally. Maybe that helps.
 A: Your conjectured counterexample works perfectly.
Let $P = \{(a,b): a^2+b^2=1\}$ and $Q=\{(b,c):b^2+c^2=1\}$.
Then
$$\begin{align}
(a,c)\in Q\circ P &\iff \exists b:a^2+b^2=1 \text{ and }  b^2+c^2=1 \\
&\iff \pm\sqrt{1-a^2} = \pm\sqrt{1-c^2} \\
&\iff a^2=c^2 \text{ and } a^2,c^2\le 1.
\end{align}$$
Thus $Q\circ P$ looks like an X, which is not a manifold. Consider the top view of this figure:

Paul Bourke, "Intersecting cylinders", 2003
A: First, let me make sure I understand. Let $A$ and $B$ be manifolds. By a relation $A \to B$, you mean a subset of $A \times B$, and such a relation you call smooth if that subset is a smooth submanifold. If it is okay, I would prefer to stick with the subset terminology—calling a subset of a manifold smooth if it is a smooth submanifold.


*

*Given a subset of manifold $A$ and a subset of manifold $B$, their product is a subset of $A \times B$, and if those subsets are smooth, so is their product.

*$A$ itself is a smooth subset of $A$.

*Given a subset of $A \times B$, its projection to $A$ is the collection of $a$ in $A$ such that, for some $b$ in $B$, $(a, b)$ is in the given subset. It is false in general that the projection of a smooth subset is a smooth subset.

*Given two subsets of $A$, their intersection is a subset of $A$, but it is false in general that the intersection of two smooth subsets is smooth.


In terms of these, we can describe your construction as follows. Let there be given a subset $P$ of $A \times B$, and a subset $Q$ of $B \times C$. First, take $P \times C$—a subset of $A \times B \times C$—and $A \times Q$—also a subset of $A \times B \times C$. Second, intersect those two subsets. And third, project that intersection to $A \times C$. That is, we get from relations $A \to B$ and $B \to C$ to a relation $A \to C$. Now, in the case in which $P$ and $Q$ are smooth, the first step above will result in smooth subsets, but the second and third, in general, will not. So, your construction would not be expected to yield a smooth subset.
