Prove that the transitive closure of a relation is transitive without using recursion In Kunen's book Set Theory (from 2013) the transitive closure of a relation $R$ on $A$ is defined as
$$
 R^* = \{ (x,y) \in A^2 : \text{there is an $R$-path from $x$ to $y$} \}
$$
where an $R$-path from $x$ to $y$ simply is a function $s : n+1 \to A$ for some $n \in \omega$ such that $s(0) = x$ and $s(n) = y$ and $s(i) \,R\, s(i+1)$ for all $i < n$.
This is Definition I.9.4 in the book.
Now it is claimed in Lemma I.9.5 that $R^*$ is transitive, the proof being that this is "easily seen by combining paths".
However, I cannot figure out how to combine two paths without appealing to the validity of recursive definitions for $\omega$. The way it is presented in the book somehow suggests that this should be possible.
Indeed, the goal of the chapter really seems to be to prove the recursion principle for well-founded sets without having to prove recursion for $\omega$ first.
Is there a way to combine paths without having to use recursion that I am overlooking?
I would also appreciate if someone could point me to another proof of the principle of well-founded recursion where it is not assumed to already know recursion for $\omega$.
 A: The transitive closure of the binary relation $R$ is typically defined to be the following (because it does not require the axiom of infinity)
$$R^{\mathsf{t}}:=\bigcap\{S'\in\mathscr{P}(\mathrm{fld}(R)\times\mathrm{fld}(R)):R\subseteq S'\,\wedge\,S'\circ S'\subseteq S'\}$$
If we allow the axiom of infinity (i.e. the existence of $\omega$) and assume we have proven recursion on $\omega$ then by Kleene's Theorem we have $$\bigcup_{n\in\omega}R_n=R^{\mathsf{t}},$$
where $R_n$ is defined by $R_0=R$ and $R_{n+1}=R_n\cup(R_n\circ R_n)$. This is the other potential definition of the transitive closure. The definition you were provided is somewhat more complex (introducing the notion of paths).
I believe you are correct that induction and recursion on $\omega$ should be assumed if provided the complex definition of the transitive closure. To be precise, what you need is the following result (easily proven by induction) $$\omega=\{n\in\omega:n\sim(n+m)\setminus m\}\qquad(\text{for fixed }m\in\omega)$$
Here $\sim$ is the notion that two sets are equinumerous (i.e. there exists a bijection between the two sets). Of course, recursion is required to define addition $+:\omega^2\to\omega$. With that result, one can easily concatenate two paths. 
For a nice exposition of transfinite induction and recursion (without necessarily having the axiom of infinity---I recall the author giving an equivalent formulation of the definition of a binary relation to be well-founded utilizing both the axiom of choice and infinity: "there is no infinitely descending sequence"; this definition is not required and can be forgotten if not interested in the axiom of infinity) see Enderton's Elementary Set Theory Chapter 9. It is the first section titled Well-Founded Relations.
