Let's break it down. Consider an ordered structure (directed graph).
- $\forall x \exists y : R(x,y) \equiv$ Every vertex has at least $1$ outgoing edge.
- $\forall x \forall y : \left ( R(x,y)\implies \lnot R(y,x) \right)\equiv$ If there is a directed edge from vertex $u$ to vertex $v$, there should not be an edge back from $v$ to $u$. That is, our relation $R(x,y)$ is asymmetric.
- $\forall x \forall y \forall z : \left ( R(x,y) \land R(y,z) \implies R(x,z) \right )\equiv$ If $u \to v \to z$, then $u \to z$ is also true. That is, our relation $R(x,y)$ is transitive.
- $\forall x: \lnot R(x,x) \quad \equiv$ We cannot have a self-loop in the graph. That is, $R(x,y)$ is irreflexive.
Now, such a non-trivial $\left(\text{size} > 0\right)$ finite structure cannot exist.
Proof by contradiction:
Assume, for the sake of contradiction, that such a finite structure $\bf{S = (V,E)}$ exists. Since it is finite, let the number of vertices in this structure be $\bf{|V| = n, n \in \mathbb{N}, n>0}.$
Edit: A summarized version of the following proof is in the comments. You can directly skip to that.
Lemma $1$: $v_n$ has an incoming edge from every vertex $v_i, i < n$
Proof by Induction:
Induction Hypothesis: $P(n) = $For every $1 \leq i < j \leq n$, there is an out edge from vertex $v_i$ to vertex $v_j$, that is $v_i \longrightarrow v_j$.
Base Cases:
- Let $n = 2$.
$v_1 \longrightarrow v_2$ must be true since there has to be an out edge from $v_1$ (Property A) and the only available vertex is $v_2$ (no self loops allowed - Property D).
Hence, our hypothesis $P(2)$ is satisfied.
- Let $n = 3$.
There must be an out edge from $v_1$ to some vertex. Let's call that vertex $v_2$, that is $v_1 \longrightarrow v_2$.
Similarly, there must be an out edge from $v_2$. But due to property B, we can't have an out edge from $v_2$ back to $v_1$. Hence, the out edge from $v_2$ must lead us to a new vertex. Lets call that $v_3$.
Since $v_1 \longrightarrow v_2 \longrightarrow v_3$, due to Property C, we must have $v_1 \longrightarrow v_3$.
Hence, our hypothesis $P(3)$ is satisfied.
Inductive Step:
For $P(n+1)$: The $n$th vertex $v_n$ must have an out edge. Since $P(n)$ is true, the $n$th vertex has incoming edges from all vertices $v_i, i < n$. Hence, the out edge from $v_n$ cannot be to any of those vertices. Self loops aren't allowed either.
Hence, the out edge from vertex $v_n$ must be to the new vertex $v_{n+1}$. That is, $\substack{\searrow\\[0.5em]\longrightarrow\\[0.5em]\nearrow}\; v_n \longrightarrow v_{n+1}$
Since every vertex $v_i, i < n$ has an out edge to $v_n$, and $v_n$ has an out edge to $v_{n+1}$, due to Property C, we have that $v_i$ has an out edge to $v_{n+1}$. That is, $v_i \longrightarrow v_{n+1}, \forall i \leq n$.
This is exactly what $P(n+1)$ states.
Hence, $P(n) \implies P(n+1)$.
Q.E.D
Since $P(n)$ is true as proven above, every vertex $v_i$ must have an out edge to the vertex $v_n$.
Since the nth vertex has incoming edges from all other vertices (Lemma 1), it cannot have an out edge to any vertex. It can't have self loop either. Thus, it fails to satisfy Property A.
Hence, our assumption that S exists leads to a contradiction.
Q.E.D
The given logic formula can be satisfied by an infinite model.
For example, $R(x,y) \iff x < y, \quad x,y \in S$, where $S$ is any infinite ordered set, satisfies the given formula.
