Why second order logic is more expressive that the first order logic?

Question

As far as I understand, the second order logic is more expressive than the first order logic because it can make statements about predicates. However, I do not understand why this problem (impossibility to make statements about predicates) cannot be solved within the first order logic.

Let's assume that we have a first order logic system with some predicates. For example we can have the following statements in it:

CapitalOf(Berlin, Germany)
HasBorderWith(Germany, France)
CapitalOf(Paris, France)
Country(Germany)
City(Paris)

So, in the above example we have the following predicates: CapitalOf, HasBorderWith, City, Country. Now, let's assume that we want / need to make some statements about predicates. FOL syntax does not allow it. But we can reformulate all our statements in the following way:

Relation(CapitalOf, Berlin, Germany)
Relation(HasBorderWith, Germany, France)
Relation(CapitalOf, Paris, France)
Class(Country, Germany)
Class(City, Paris)

Now, all the predicates (CapitalOf, HasBorderWith, City, Country) have the same status as entities (Germany, France, Berlin, Paris). So, what can us stop now from making statements about the predicates using FOL?

Answer 1

You're misunderstanding what second-order logic does. I think part of this is due to the use of the term "predicate," which is unfortunate since it has connotations which are not relevant here; it's better to describe second-order logic as allowing quantification over all subsets of, relations on, and fuctions on the domain. Crucially we're quantifying over all such second-order objects, not just - for example - the definable ones, or the ones specifically named in the language of the structure itself.

---

Here's a specific example of a second-order sentence with no first-order equivalent:

Every injection of the domain to itself is a surjection.

In symbols:

$\forall F[(\forall x,y(F(x)=F(y)\rightarrow x=y))\rightarrow (\forall x\exists y(F(y)=x))].$

This sentence is true in a given structure exactly when that structure is finite. However, by the compactness theorem for first-order logic there is no first-order sentence which does this: if $\varphi$ is a first-order sentence with arbitrarily large finite models, then $\varphi$ has an infinite model.

---

Here's another example. Suppose my language has two unary predicate symbols $U$ and $V$. The statement "$U$ and $V$ hold of the same number of elements" is second-order expressible ("There exists a function which restricts to a bijection from $U$ to $V$") but - again via compactness - is not first-order expressible.