# what are first and second order logics? [duplicate]

The only knowledge I have on logic is due to a book I read a couple of years ago called Introduction to logic: and to the methodology of deductive sciences by Alfred Tarski. And in it he talks about free variables and sentences and quantifiers. But he never says what order logic he is talkig about or anything.

My question is this:

What is the difference between the two order logics and how can I tell if a statement is in one or the other.

-

## marked as duplicate by Julian Kuelshammer, Adriano, Hagen von Eitzen, Start wearing purple, Andrey RekaloJul 7 '13 at 8:45

The question you say it is a duplicate already assumes knowledge of what first order and second order logics are. – Carry on Smiling Jul 7 '13 at 7:59
The links in the linked question may have definitions. – user83622 Jul 7 '13 at 8:01
This isn't really a duplicate of the question linked to below. That question focuses on set theory, this on elementary logic. That's different!!! – Peter Smith Jul 7 '13 at 8:56

In first-order logic we are allowed to put a quantifier only on first-order variables. This means that when we interpret the language and ask whether or not a sentence is true or false, then we can only quantifier on elements of the universe. In second-order logic, however, we are allowed to quantify over relations, or subsets of the universe as well.

For example, the statement "Every bounded set of real numbers has a least upper bound" is a second-order statement. We quantified over all the sets of real numbers, and we say "If $A$ is a bounded set, then $\sup A$ exists".

On the other hand, "$\sqrt2$ exists" is a first-order statement (in the language containing $+,\cdot,0,1$, that is) because we can characterize $\sqrt2$ as an element $x$ such that $x\cdot x=1+1$.

Second-order logic, if so is a much stronger way to write things. It allows us to express a lot more in comparison to first-order logic.

So why are we mostly interested in first-order logic? First of all, there is a lot of research into other strong logics (logics which allow us to express more than first-order itself, but usually less than second-order logic). Secondly, first-order logic got the completeness theorem and the compactness theorem, as well the Lowenheim-Skolem theorems. These mean that we have a great model theory with first-order logic. On the other hand, we don't have those for stronger logics (either we don't have one of them, or we don't have both) which means that proof theory and model theory are going to be harder to work with.

Moreover second-order logic has several variants. For example we may allow only to quantify over subsets of the universe, not general relations; or we may interpret the second-order logic in a way that the subsets we are interested in were all definable by a first-order formula (Henkin semantics). These are weaker than just full-on quantification and so on. The Henkin semantics version of second-order logic is equivalent to first-order logic in a very good sense.

I feel that I'm already confusing you enough. So let's stop here.

-
you beat me to it by a couple of minutes... I'm glad my answer is sort of complimentary to yours though :) (+1, anyhows). – Ittay Weiss Jul 7 '13 at 8:12
@Ittay: With my trusty mechanical keyboard (Unicomp Ultraclassic, blank keys) I can type as fast as the wind! – Asaf Karagila Jul 7 '13 at 8:13
so then if I want to say any multiple of 9 is a multiple of 3 it is a second order logic sentence? – Carry on Smiling Jul 7 '13 at 8:17
@Omnitic: First of all, it depends on the language. Do you have a symbol for $\cdot$? For $9$? For $3$? Suppose that you have $0,1,+,\cdot$. Then you can define $9$ and $3$. Now you can define the relation "$x$ is a multiply of $y$" simply by saying that for some $z$, $x=y\cdot z$. Now you just say, every element which is a multiple of $9$ is a multiple of $3$. – Asaf Karagila Jul 7 '13 at 8:19
@awllower: I asked Omnitic about language and structure, because there seems to be a confusion between syntax and semantics here. In the real numbers, if we quantify over integers then we are using second-order logic. But in the integers all our objects are integers so quantifying over them is first-order. MSE is a nice place to clarify small things, but it's not a place to learn something as big as basic logic. – Asaf Karagila Jul 7 '13 at 8:43

The difference is in the interpretation of quantification. In first order logic, any variable that is bound to a quantifier (that is $\forall x(...)$ or $\exists x(...)$) is only allowed to range, or be replaced by, elements of the model. In higher order logic, quantification is also allowed over subsets of elements, functions, relations etc. In particular, second order logic allows quantification over subsets of elements.

Much of mathematics can be stated in first order logic and, crucially, some things are distinctively second order. For instance, in number theory, Peano's axioms except for induction are first order, but the principle of induction is second order. In the theory of the real numbers, all field axioms except completeness are first order, but completeness is second order. Interestingly, it is precisely these second order properties that make the theories categorical (meaning all models are isomorphic).

-
Not just completeness, but also the Archimedean property! – Asaf Karagila Jul 7 '13 at 8:12
Archimedean follows from completeness, so I did not include it in the standard list for axiomatizing the reals, but rather it's a consequence. – Ittay Weiss Jul 7 '13 at 8:14
Of course, but it is worth mentioning. – Asaf Karagila Jul 7 '13 at 8:16
most certainly. – Ittay Weiss Jul 7 '13 at 8:17

The difference is in what you can quantify over. First-order logic lets you quantify over elements, for example

$$\exists x.\ \forall y.\ x \leq y$$

while second-order logic allows you to quantify over relations, e.g.

$$\exists L.\ \forall x.\ \forall y.\ x \leq y \iff L(x,y)$$

observe that $x$ and $y$ belong to the universe, while $L$ belongs to $\mathcal{P}({U\times U})$. Second order logic has strictly greater expressive power and some say that it is too expressive - in fact you can define the natural numbers in it, and as a result second-order logic does not admit a complete proof theory (see Godel's incompletness theorem).

I hope this helps ;-)

-