Consider a first order language $L$. Let $S$ be an $L$-sentence true in all finite $L$-structures but false in some infinite $L$-structure. The completeness theorem implies $S$ can not be proven by usual means. Yet, is there another way to establish $S$ is true in all finite models? Another question is whether we can write down $S$ at all. Are there some examples, say, from graph or set theory?
A sentence valid in all finite structures
logicmodel-theory
Related Solutions
Here is a simple example of a very concrete, complete, noncategorical theory.
Let $T$ be the first-order theory whose language has one unary relation symbol, $R$, and an axiom $(\forall x)R(x)$. The theory does not have the equality symbol $=$ or any symbols other than $R$ in its language.
Claim: This theory $T$ is complete: for each sentence $\phi$ in the language, the theory either proves $\phi$ or proves the negation of $\phi$.
Proof sketch: Given a sentence, we can remove all the quantifiers, and replace every term $R(z)$ in the formula with $\top$. Then the original sentence is provable in $T$ if and only if the resulting sentence is true statement in propositional logic.
Claim: The theory $T$ is not categorical.
Proof sketch: For any set $S$, we can turn $S$ into a model of $T$ by simply asserting that $R(z)$ holds for all $z \in S$. Two such models will be isomorphic if and only if they have the same number of elements.
This is also a very trivial example of the process known as quantifier elimination, which is a fundamental technique for showing that various theories are complete.
For the first question, the point is that there are basic algebraic/combinatorial phenomena which can only occur in infinite structures. The simplest example is an injective non-surjective function: in the language with a unary function symbol $f$, the sentence $$[\forall x, y(x\not=y\implies f(x)\not=f(y))]\wedge[\exists x\forall y(f(y)\not=x)]$$ does have models but does not have any finite models. Another easy example is linear orders without endpoints: in the language with a binary relation symbol $R$, the sentence asserting that $R$ is a linear order with no greatest (or least, if you prefer) element has only infinite models.
(There are also surprisingly deep examples, e.g. Wedderburn's little theorem says that the sentence saying "the universe is a non-commutative division ring" has only infinite models.)
For the second question, this is just a direct application of the theorem. Let $\mathbb{K}$ be the class of all finite structures (in some fixed language). If $\mathbb{K}$ were $EC_\Delta$, then there would be some set of sentences $\Gamma$ such that $\mathbb{K}$ is exactly the class of all models of $\Gamma$. But:
Do you see why such a $\Gamma$ must have arbitrarily large finite models? (HINT: how large can elements of $\mathbb{K}$ be?)
Do you see why such a $\Gamma$ cannot have infinite models? (HINT: how large can elements of $\mathbb{K}$ not be?)
This gives a contradiction, so our assumption that $\mathbb{K}$ was $EC_\Delta$ must have been wrong.
Best Answer
Consider the language $\mathcal{L} = \{ \leq \}$, and the sentence $S$ saying that if
then there is a $\leq$-maximum element ($\exists x. \forall y. y \leq x$).
This sentence is true in every finite $\mathcal{L}$-structure, but of course false in $\langle \mathbb{N}, \leq \rangle$ where $\leq$ denotes the standard ordering of $\mathbb{N}$.
As you note, as long as we allow arbitrary (finite or infinite) structures, Gödel's completeness theorem provides a strong correspondence between semantic validity and deductive (syntactic) provability.
Of course, the $S$ written down above is not provable in first-order logic, since it fails in some (infinite) structure.
Unfortunately, it is not possible to find similar, complete deductive rules that would allow us to prove precisely those sentences that hold in all finite structures: this follows from a well-known result in recursion theory, known as Trakhtenbroth's theorem.