Assume \(G = (V,E)\) is a directed graph with no oriented cycles. Today, I would like to show that one can label the vertices of \(G\) in such a way \(\phi\colon V\to \mathbb{N}\) that (1) \(\phi\) is one-to-one and (2) on every path \((v_0,\ldots,v_n)\) in \(G\) the labels are stricly increasing \(\phi(v_0)<\cdots<\phi(v_n)\).
Before venturing in solving this problem, let me start with a simple lemma I am going to need later:
Every cycle-free finite directed graph \(G = (V,E)\) contains at least one source and one sink.
I will give a proof for the source case. The proof for the existence of a sink is similar. Take an arbitrary vertex \(v_0\in V\). If it is a source, we are done. If \(v_0\) is not a source then there is another vertex \(v_1\in V\setminus\{v_0\}\) such that \((v_1,v_0)\) is a directed edge. Proceed inductively and form a sequence \(v_{n+1}\in V\setminus \{v_n\}\) such that \((v_{i+1},v_i)\) is a directed edge. Since \(G\) is finite, this process can not continue indefinitely. There are two possibilities: either we got a source at some step and we stop, or we got a repetition: we find \(v_i=v_j\) for some \(i\>j\). But the latter case is a contradiction as there are no oriented cycles. So, the process must end with a source.
I will solve the original question using induction on the number of vertices. Assume \(G\) has only one vertex. The problem is trivial as the only path is the trival path of length 0 on the single vertex. So, assume in every cycle-free directed graph on \(n\) vertices the statement is true. Take a graph on \(n+1\) vertices. We know because of the lemma that there is a source. Take such a source \(s\in V\) and remove \(s\) from the graph together with all edges starting at \(s\). The remaining graph \(G'\) contains \(n\) vertices and has no oriented cycles like \(G\). Then because of the induction hypothesis we can find a one-to-one labelling \(\psi\colon V\setminus\{s\}\to \mathbb{N}\) such that on every path in \(G'\) the labels are strictly increasing. Now define \(\phi\colon V\to \mathbb{N}\) by letting \(\phi(s) = 1\) and \(\phi(v) = \psi(v) + 2\) if \(v\neq s\).
Assume \(\phi(v)=\phi(w)\) for some vertices in \(G\). There are two cases: (1) either one of these vertices is \(s\), or (2) \(v,w\in V\setminus\{s\}\). In the first case assume without loss of generality that \(v=s\) then \(\phi(v)=1=\phi(w)\). This will yield \(w=s\) as well because in this labelling the only vertex with the label \(1\) is \(s\). In the second case \(\phi(v) = \psi(v)+2 = \psi(w)+2 = \phi(w)\) since neither elements are the source \(s\). Then we get \(v=w\) as \(\psi\) was one-to-one. This finishes the proof that \(\phi\) is one-to-one.
As for the fact that labels are stricly increasing on every path, take an arbitrary path \((v_0,\ldots,v_n)\) in \(G\). There are two cases: (1) \(v_0=s\) and (2) \(v_0\neq s\). In the first case \(v_0 = s\) and \(\phi(v_i)=\psi(v_i)+2\) for all \(i=1,\ldots,n\) and since \(\psi\) is strictly increasing on every path in \(G'\), we must have \[ 1 = \phi(v_0)<\psi(v_1)+2<\cdots<\psi(v_n)+2 \] In the second case \(\phi(v_i)=\psi(v_i)+2\) for all \(i=0,\ldots,n\) and therefore \[ \phi(v_1) = \psi(v_1) + 2 < \psi(v_2) + 2 <\cdots< \psi(v_n) + 2 \] This finishes the proof.