# What is a language “expressible” in second/first-order logic?

This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated.

Indeed, for first order logic they say "the language of a finite structure with a fixed signature including a linear order relation [with a suitable fixed point combinator]"; but it's not clear what this means, and it doesn't seem to be explained further.

For existential second order logic, the article just says "NP is the set of languages expressible in existential second-order logic" without any explanation: what does it mean for a language to be expressible in (existential) second-order logic ?

So my question is

What do these characterizations mean, precisely ?

To answer, you can assume I know what a formal language is, that I know what first order logic and existential second order logic, and that I know some decent amount of model theory. Note that I'm not asking for a proof of the characterization (although if there is a quick one I won't mind seeing it), just for a definition of the characterization.

• I think you should raise a comment on Wikipedia Talk that this section of the article needs references and clarification. I'm personally disinclined to try to reverse engineer something meaningful from this part of the article as its stands (although someone on MSE more attuned with this particular area than me may have the answer at their finger-tips). – Rob Arthan May 16 at 21:06
• You might have better luck looking at the page for descriptive complexity theory: en.wikipedia.org/wiki/Descriptive_complexity_theory – Ispil May 21 at 16:20
• @Ispil thank you but this page still takes for granted the notion of "expressible in such logical system". I'll try to see if the references bring any light – Max May 21 at 16:26

A word $$w$$ over a finite alphabet $$A$$ has an associated (first-order) structure defined as follows. The vocabulary has a binary relation symbol $$<$$ and unary relation symbols $$P_a$$ for each letter $$a\in A$$. The structure associated to $$w$$ has underlying set $$\{1,2,\dots,n\}$$ where $$n$$ is the length of $$w$$; $$<$$ is interpreted as the usual ordering of the natural numbers $$1,2,\dots,n$$; and each $$P_a$$ is interpreted as the set of those $$i\in\{1,2,\dots,n\}$$ such that the $$i$$-th letter in $$w$$ is $$a$$.
A language $$L$$ is said to be expressed by a formula $$\phi$$ (in some logic) if and only if $$L$$ is the set of those words $$w$$ whose associated structure satisfies $$\phi$$.