# AI News, Artificial Intelligence/Logic/Representation/Second-order logic

- On Wednesday, October 3, 2018
- By Read More

## Artificial Intelligence/Logic/Representation/Second-order logic

Second-order logic is an extension of first-order logic where, in addition to quantifiers such as “for every object (in the universe of discourse),” one has quantifiers such as “for every property of objects (in the universe of discourse).” This augmentation of the language increases its expressive strength, without adding new non-logical symbols, such as new predicate symbols.

For classical extensional logic (as in this entry), properties can be identified with sets, so that second-order logic provides us with the quantifier “for every set of objects.”

They differ on the interpretation of the phrase “for every set of objects.” Does this have some fixed meaning to which we can refer, or do we need to consider the variety of meanings the phrase might have?

0, S, <, +, ×) consisting of the set N = {0, 1, ...} of natural numbers, together with the common arithmetical operations and relations.

And we want to use a first-order language with quantifiers ∀ interpreted as “for every natural number” and ∃ interpreted as “for some natural number.” Moreover, we include in the language a constant symbol 0 for the number zero, a one-place function symbol S for the successor operation (which applied to a natural number gives the next one), a two place predicate symbol <

0, S, <, +, ×) when we interpret the predicate symbol P as being true of the numbers in some particular set—no matter what that set is—it says that the set has a least member, if it is non-empty.

In more detail, here is what is meant by a second-order language: One starts with a first-order language, and augments it by an unending supply of n-place predicate variables for each positive integer n, and an unending supply of n-place function variables for each positive integer n.

This sentence expresses the idea that X is true of all natural numbers, if it is true of 0 and its truth at some number y guarantees its truth at the successor of y, no matter what set of numbers X might be true of.

George Boolos suggested the example, “There are some critics who admire only each other.” This sentence asserts the existence of a set of individuals having a certain property;

Consider a structure M = (A, R, ...) consisting of a non-empty set A serving as the universe of discourse, and some relations and functions on A interpreting the non-logical symbols.

Then we want to count a second-order sentence of the form ∀P φ (where P is a k-place predicate variable) as being true in this structure if for every set Q of k-tuples of members of A, we have that φ is true in the structure when P is assigned the relation Q.

More formally, we need to define inductively what it means for a second-order formula φ to be satisfied in a structure M = (A, R, ...) under an assignment s of objects to the free variables in φ, which will be written M ⊨ φ[s].

In the case of a second-order sentence σ (i.e., a formula with no free variable), the assignment s is no longer relevant, and we may speak unambiguously of the truth or falsity of σ in the structure M (that is, we can say that M is or is not a model of σ).

In particular, the examples in §1 of translations from natural language into the language of second-order logic can now be seen to accomplish their intended purposes.

{¬λ∞, λ2, λ3, λ4, … }

is true in a structure (A, f, e) iff this structure is isomorphic to (N, S, 0), the natural numbers with the successor operation S and distinguished element 0.

Similarly, the ordered field of real numbers, (R, 0, 1, +, ×, <), can be characterized up to isomorphism by the first-order axioms for an ordered field, together with the second-order sentence expressing the least-upper-bound property.

The preceding examples show that two everyday mathematical structures, (N, S, 0) and (R, 0, 1, +, ×, <) are second-order characterizable.

Where π(0, S,) is the conjunction of the three Peano postulates, the sentence ∃x ∃F π(x, F) is a sentence in the second-order language of equality, that is, it has no non-logical symbols at all.

Say that a cardinal number κ is second-order characterizable if there is a sentence of the second-order language of equality that is true in cardinality κ and only there.

(The non-zero finite cardinals are all first-order characterizable.) We have seen that the countable infinite cardinal is second-order characterizable.

Where ρ(0, 1, +, ×, <) is the second-order sentence that characterizes the ordered field of real numbers up to isomorphism, the sentence

More specifically, in first-order logic with only a single 2-place predicate symbol P, we know that the set V¹(P) of valid sentences is a complete computably enumerable set (i.e., a complete recursively enumerable set).

(Here we can assign Gödel numbers and view V¹(P) as a set of natural numbers, or equivalently we can view it directly as a set of words over a finite alphabet.) And Tarski has pointed out that the set V¹(=) of valid sentences in the first-order language of equality (with no non-logical symbols at all) is decidable.

Consequently, for a sentence σ in the language of arithmetic, σ is true in arithmetic iff the conditional (π → σ) is valid.

This shows that V²(0, S, +, ×) cannot be arithmetical (i.e., cannot be first-order definable in arithmetic), lest truth in arithmetic be definable, in violation of Tarski's theorem.

The proof of Tarski's theorem, showing that the set of true first-order sentences of arithmetic is not first-order definable in arithmetic, also shows that the set of true second-order sentences of arithmetic is not second-order definable in arithmetic.

The statement that the graph can be properly colored with three colors can be expressed by a second-order sentence: there exist subsets R, G, B that partition V in such a way that two vertices connected by an edge are never the same color.

(There is a non-deterministic Turing machine M and a polynomial p such that whenever (V, E), suitably encoded, is given to M, then if (V, E) is three-colorable then some computation of M will accept the graph within p(n) steps, where n measures the size of (V, E), and if (V, E) is not three-colorable then no computation of M will ever accept the graph.)

key feature of the “standard semantics” discussed in the previous section is that, for a one-place predicate variable X, the quantifier ∀X ranges over the entire power set of the universe of discourse.

By a general pre-structure for a second-order language we mean a structure in the usual sense (a universe of discourse plus interpretations for the non-logical symbols) together with the additional sets:

For a general pre-structure M, there is a natural way to define what it means for a second-order formula φ to be satisfied in a structure M under an assignment s of objects to the free variables in φ, which again will be written M ⊨ φ[s].

⊨ ∀P φ[s] iff for every k-ary relation Q in the k-place relation universe, we have M ⊨ φ [s′] where

⊨ ∀F φ[s] iff for every k-place function G in the k-place function universe, we have M ⊨ φ [s′] where

In the case of a second-order sentence σ (i.e., a formula with no free variable), the assignment s is no longer relevant, and we may speak unambiguously of the truth or falsity of σ in the general pre-structure M (that is, we can say that M is or is not a model of σ).

Thus in the situation just described, it is reasonable to expect M's 2-ary relation universe to contain the binary relation that φ defines from parameters in the pre-structure.

In Section 5, we consider alternatives to “full comprehension.”) Among the general structures are those in which the 1-place relation universe is the actual power set of the individual universe, and so forth.

A sentence that is valid in the standard semantics is true in those general structures for which the 1-place relation universe is the full power set of the individual universe, and so forth.

The main feature of the general semantics is a result of the “nothing but” type: Second-order logic with the general semantics is nothing but first-order logic (many-sorted) together with the comprehension axioms.

Moreover, a deductive calculus can be given for second-order logic (adapted from first-order logic and augmented by the comprehension axioms) that will be complete for the general semantics.

We have seen that, although the set V¹ of valid formulas of first-order logic is computably enumerable, the corresponding set V² for second-order logic (with the standard semantics) is vastly more complex.

Consider a language with a one-place predicate symbol I (for individuals), a one-place predicate symbol S (for sets), and a two-place predicate symbol E (for the membership relation).

Clearly σ is true in any structure whose universe is the disjoint union of a set A and its power set P(A) and which assigns A to I, assigns P(A) to S, and assigns the membership relation ∈ to E.

Then f is an isomorphism from M to a structure whose universe is the disjoint union of a set A and its power set P(A) and which assigns A to I, assigns P(A) to S, and assigns the membership relation ∈ to E.

More specifically, we have the following result of Hintikka (1955): For each formula φ of higher-order logic (in a language with finitely many non-logical symbols), we can effectively find a sentence ψ of second-order logic (in the language of equality) such that φ is valid if and only if ψ is valid.

The sentence ψ is constructed by first expanding the language by adding symbols for universes of various types (individuals, sets of individuals, ...) and for membership in these universes.

The fact that we can express the power-set operation in second-order logic (and can iterate the procedure) gives second-order logic some large part of the expressiveness of set theory.

The foregoing reduction of higher-order logic yields Π-1-2 sentences, so we can conclude that the set of valid Π-1-2 sentences in the language of equality is computably isomorphic to the full V²(=).

And to a Turing machine we can effectively assign an elementary sentence having models of every finite size iff the machine never halts.) The set of valid Σ-1-2 sentences in the language of equality is also computably isomorphic to the full V²(=), but this fact requires a different sort of proof.

We can also find general models of the Peano postulates in which the universe of sets is less than the full power set of the individual universe (i.e., general models that are not absolute).

That is, define an ω-model of analysis to be a model of analysis in which the individual universe is the actual set of natural numbers and the symbols 0 and S have their usual interpretations.

(Consequently, the symbols <, +, and × have their usual interpretations.) The set universe of an ω-model of analysis must therefore be some part (possibly all) of the power set of the natural numbers, but it must be such that full comprehension is satisfied.

That is, an ω-model M of analysis is a β-model if every ordering relation (on the natural numbers) in M with the property that non-empty sets in M always have least members, is in fact a well-ordering.

A2 ⊆ Aω ⊆ Aβ ⊆ True Second-Order Arithmetic.

- On Sunday, March 24, 2019

**Truth Table Tutorial - Discrete Mathematics Logic**

Here is a quick tutorial on two different truth tables. If you have any questions or would like me to do a tutorial on a specific example, then please comment down ...

**What is FIRST-ORDER LOGIC? What does FIRST-ORDER LOGIC mean? FIRST-ORDER LOGIC meaning & explanation**

What is FIRST-ORDER LOGIC? What does FIRST-ORDER LOGIC mean? FIRST-ORDER LOGIC meaning - FIRST-ORDER LOGIC definition - FIRST-ORDER ...

**How Can One Greek Letter Help Us Understand Language? Lambda Calculus**

How can we capture the meanings of transitive sentences? How do we match our syntax trees to our semantics? In this week's episode, we talk about lambda ...

**How Logical is Language? Sentential Logic**

How much does logic structure our sentences, and what kind of logic should we use? In this week's episode, we talk about sentential logic: where it came from, ...

**How Do We Build Meaning with Math? Set Theory and Adjectives**

How do we form sets of different elements? How do those collections contribute to meaning? In this week's episode, we talk about set theory: the basics of how it ...

**Java Programming Tutorial - 6 - Getting User Input**

Facebook - GitHub - Google+ .

**READING COMPREHENSION in Exams, Tests - Strategies, Tips and Tricks - Building Reading Skills**

In this lesson, you will learn strategies for READING COMPREHENSION exercises in exams and tests. Also see - MOST COMMON MISTAKES IN ENGLISH ...

**The benefits of a bilingual brain - Mia Nacamulli**

Check out our Patreon page: View full lesson: ..

**Kant & Categorical Imperatives: Crash Course Philosophy #35**

Our next stop on our tour of ethics is Kant's ethics. Today Hank explains hypothetical and categorical imperatives, the universalizability principle, autonomy, and ...

**How Can Sentences Work Like Adjectives? The Syntax and Semantics of Relative Clauses**

We can put whole clauses inside other phrases, but what does that do to their structure and their meaning? In this week's episode, we take a look at the syntax ...