By the completeness of FOL, one can show that a sentence $S$ in FOL is valid, i.e. that it holds true in every model, by exhibiting a proof of $S$. Such a proof string is a certificate of the validity of $S$.
To show that $S$ is not valid, one can either exhibit a counterexample model in which $S$ doesn't hold, or find a proof that such a model exists, either of which would serve as a certificate.
However, do I understand correctly that while a "certificate of validity" will always exist, that "certificates of invalidity" do not exist in the general case?
In other words, that there can exist $S$ which are not tautologies, and for which a counterexample model exists, but for which one cannot actually construct a counterexample, or a proof of its existence?
This is not a question about the ability of FOL to formalize arithmetic (which Godel proved is impossible), but simply whether or not, in a very foundational sense, it is possible to prove counterexamples exist to FOL sentences in general.