I am trying to figure out under which condition would such a statement be true:
$∀x ∃y$ $(x > y)$
where the domain $U$ is a subset of $\mathbb{N}$
If I translate this into english,
For every $x$, there is a $y$ where $x > y$.
If I take for instance $x = 0$, this statement would be false as there exists one value of $x$ for which no value of $y$ would be true.
$0 \not\gt y$
I would conclude in that case that such proposition is false for any subset $U \subseteq \mathbb{N}$.
However, would that statement not be true if the subset $U$ was empty? Is my initial conclusion incorrect?
You've definitely got the gist of the problem; the only catch is that you can't assume that $0$ is in your subset $U$.
If your subset $U$ is nonempty, then it has a smallest element. Call that element $x$; then the statement is disproven by your $x$. You are also right that if $U$ is empty, then the statement is actually true, because there's no $x$ which can disprove it.