Nonfirstorderizability

Key takeaways

Nonfirstorderizability belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Nonfirstorderizability to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Nonfirstorderizability from memory before moving on to harder problems.

Reference excerpt

In formal logic, nonfirstorderizability is the inability of a natural-language statement to be adequately captured by a formula of first-order logic. Specifically, a statement is nonfirstorderizable if there is no formula of first-order logic which is true in a model if and only if the statement holds in that model. Nonfirstorderizable statements are sometimes presented as evidence that first-order logic is not adequate to capture the nuances of meaning in natural language. The term was coined by George Boolos in his paper "To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables)". Boolos argued that such sentences call for second-order symbolization, which can be interpreted as plural quantification over the same domain as first-order quantifiers use, without postulation of distinct "second-order objects" (properties, sets, etc.).

Examples

Geach-Kaplan sentence A standard example is the Geach–Kaplan sentence: "Some critics admire only one another." If Axy is understood to mean "x admires y," and the universe of discourse is the set of all critics, then a reasonable translation of the sentence into second order logic is:

∃ X ( ( ∃ x ¬ X x ) ∧ ∃ x , y ( X x ∧ X y ∧ A x y ) ∧ ∀ x ∀ y ( X x ∧ A x y → X y ) ) {\displaystyle \exists X{\big (}(\exists x\neg Xx)\land \exists x,y(Xx\land Xy\land Axy)\land \forall x\,\forall y(Xx\land Axy\rightarrow Xy){\big )}}

In words, this states that there exists a collection of critics with the following properties: The collection forms a proper subclass of all the critics; it is inhabited (and thus non-empty) by a member that admires a critic that is also a member; and it is such that if any of its members admires anyone, then the latter is necessarily also a member. That this formula has no first-order equivalent can be seen by turning it into a formula in the language of arithmetic. To this end, substitute the formula ( y = x + 1 ∨ x = y + 1 ) {\textstyle (y=x+1\lor x=y+1)} for Axy. This expresses that the two terms are successors of one another, in some way. The resulting proposition,

∃ X ( ( ∃ x ¬ X x ) ∧ ∃ x , y ( X x ∧ X y ∧ ( y = x + 1 ∨ x = y + 1 ) ) ∧ ∀ x ∀ y ( X x ∧ ( y = x + 1 ∨ x = y + 1 ) → X y ) ) {\displaystyle \exists X{\big (}(\exists x\neg Xx)\land \exists x,y(Xx\land Xy\land (y=x+1\lor x=y+1))\land \forall x\,\forall y(Xx\land (y=x+1\lor x=y+1)\rightarrow Xy){\big )}}

states that there is a set X with the following three properties:

There is a number that does not belong to X, i.e. X does not contain all numbers. The set X is inhabited, and here this indeed immediately means there are at least two numbers in it. If a number x belongs to X and if y is either x + 1 or x - 1, then y also belongs to X. Recall a model of a formal theory of arithmetic, such as first-order Peano arithmetic, is called standard if it only contains the familiar natural numbers as elements (i.e., 0, 1, 2, ...). The model is called non-standard otherwise. The formula above is true only in non-standard models: In the standard model X would be a proper subset of all numbers that also would have to contain all available numbers (0, 1, 2, ...), and so it fails. And then on the other hand, in every non-standard model there is a subset X satisfying the formula. Let us now assume that there is a first-order rendering of the above formula called E. If ¬ E {\displaystyle \neg E} were added to the Peano axioms, it would mean that there were no non-standard models of the augmented axioms. However, the usual argument for the existence of non-standard models would still go through, proving that there are non-standard models after all. This is a contradiction, so we can conclude that no such formula E exists in first-order logic.

Finiteness of the domain There is no formula A in first-order logic with equality which is true of all and only models with finite domains. In other words, there is no first-order formula which can express "there is only a finite number of things". This is implied by the compactness theorem as follows. Suppose there is a formula A which is true in all and only models with finite domains. We can express, for any positive integer n, the sentence "there are at least n elements in the domain". For a given n, call the formula expressing that there are at least n elements Bn. For example, the formula B3 is:

∃ x ∃ y ∃ z ( x ≠ y ∧ x ≠ z ∧ y ≠ z ) {\displaystyle \exists x\exists y\exists z(x\neq y\wedge x\neq z\wedge y\neq z)}

which expresses that there are at least three distinct elements in the domain. Consider the infinite set of formulae

A , B 2 , B 3 , B 4 , … {\displaystyle A,B_{2},B_{3},B_{4},\ldots }

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Nonfirstorderizability

Start with the simplest possible case. Write down what Nonfirstorderizability claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Nonfirstorderizability before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Nonfirstorderizability ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Nonfirstorderizability

In research: Nonfirstorderizability appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Nonfirstorderizability in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Nonfirstorderizability is common in secondary-school and first-year university syllabi. It links to neighbouring topics Logic, so understanding it makes those chapters shorter.
In everyday life: Look for Nonfirstorderizability outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Nonfirstorderizability in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Nonfirstorderizability means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Nonfirstorderizability out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Nonfirstorderizability in simple terms?

In formal logic, nonfirstorderizability is the inability of a natural-language statement to be adequately captured by a formula of first-order logic. Specifically, a statement is nonfirstorderizable if there is no formula of first-order logic which is true in a model if and only if the statement ho…

Why does Nonfirstorderizability matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Nonfirstorderizability?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Nonfirstorderizability.