Editing Second-order logic (section)

==Expressive power==
Second-order logic is more expressive than first-order logic. For example, if the domain is the set of all [[real number]]s, one can assert in first-order logic the existence of an additive inverse of each real number by writing ∀''x'' ∃''y'' (''x'' + ''y'' = 0) but one needs second-order logic to assert the [[Supremum|least-upper-bound]] property for sets of real numbers, which states that every bounded, nonempty set of real numbers has a [[supremum]]. If the domain is the set of all real numbers, the following second-order sentence (split over two lines) expresses the least upper bound property:
: {{math|1= (&forall; A) ([{{color|#800000|(&exist; ''w'') (''w'' &isin; A)}} &and; {{color|#008000|(&exist; ''z'')(&forall; ''u'')(''u'' &isin; A &rarr; ''u'' &le; ''z'')}}] }}
:: {{math|1=&rarr; {{color|#800080|(&exist; ''x'')(&forall; ''y'')([(&forall; ''w'')(''w'' &isin; A &rarr; ''w'' &le; ''x'')] &and; [(&forall; ''u'')(''u'' &isin; A &rarr; ''u'' &le; ''y'')] &rarr; ''x'' &le; ''y'')}})}}
This formula is a direct formalization of "every {{color|#800000|nonempty}}, {{color|#008000|bounded}} set A {{color|#800080|has a least upper bound}}." It can be shown that any [[ordered field]] that satisfies this property is isomorphic to the real number field. On the other hand, the set of first-order sentences valid in the reals has arbitrarily large models due to the compactness theorem. Thus the least-upper-bound property cannot be expressed by any set of sentences in first-order logic.  (In fact, every [[real-closed field]] satisfies the same first-order sentences in the signature <math>\langle +,\cdot,\le\rangle</math> as the real numbers.)

In second-order logic, it is possible to write formal sentences that say "the domain is [[finite set|finite]]" or "the domain is of [[countable set|countable]] [[cardinality]]." To say that the domain is finite, use the sentence that says that every [[surjective]] function from the domain to itself is [[injective]]. To say that the domain has countable cardinality, use the sentence that says that there is a [[bijection]] between every two infinite subsets of the domain. It follows from the [[compactness theorem]] and the [[upward Löwenheim–Skolem theorem]] that it is not possible to characterize finiteness or countability, respectively, in first-order logic.

Certain fragments of second-order logic like ESO are also more expressive than first-order logic even though they are strictly less expressive than the full second-order logic. ESO also enjoys translation equivalence with some extensions of first-order logic that allow non-linear ordering of quantifier dependencies, like first-order logic extended with [[Henkin quantifier]]s, [[Hintikka]] and Sandu's [[independence-friendly logic]], and Väänänen's [[dependence logic]].