First-Order Arithmetic

Question 1

How does FOA relate to FOL?

Answer 1

FOA is a “subcase” (not right phrase) of FOL

Question 2

What is the langauge of first order arithmetic?

Answer 2

(1) Function Symbols: 0 (a 0-ary function - constant), (2) unary function symbol S (successor) and (3) binary function symbols + (addition) and X (multiplication)

Question 3

What are the terms of FOA?

Answer 3

1. Exery variable x0, x1 … is a term
2. 0 is a term. If t and u are terms, then so is St, (t + u), and (t x u)
3. Nothing else is a term

Syntax (part of alphabet and wff)

Terms are like names, consisting of variables and function symbols.
In the standard interpretation (see below) they stand for numbers

Question 4

What is SSS0 in standard interpretation?

Answer 4

Formal representation of 3

Another structure: 0 + (S0 x (S0 + SS0))

Question 5

What are formulas in FOA?

Answer 5

1. If t and u terms, then t = u is an (atomic) formula
2. If A and B are formulas, then so are the connective formulas
3. If A and B are formulas and x is a variable, then (∀x: A) and (∃x: A) are formulas
4. Nothing else is a formula

Syntax (part of alphabet and wff)

Formulas are like statements.

They consist of predicate symbols, connectives, quantifiers.
They can be true or false.

Question 6

What is the interpretation (valuation) of FOA?

Answer 6

Algebraic statements

Question 7

Goal of semantics in the context of FOA?

Answer 7

Give meaning to non-logic symbols to determine which formulas are true

Question 8

How does interpretation in FOA differ from propositional logic?

Answer 8

Since language of FOL there are formulas and terms, cannot interpret directly with T or F, as in the propositional logic. Must use a structure.

• a non-empty domain or universe of discourse over which the variables range, with
• some designated elements for the constants, and
• an n -ary operation on this domain for each n -ary function symbol, and
• an n -ary relation on the domain for each n -ary predicate symbol in our language

Question 9

What is structure in FOL?

Answer 9

• a non-empty domain or universe of discourse over which the variables range, with
• some designated elements for the constants, and
• an n -ary operation on this domain for each n -ary function symbol, and
• an n -ary relation on the domain for each n -ary predicate symbol in our language

Recall, in the language of first-order arithmetic we had the following extra-logical symbols: 0 ,S , + , and ×. Thus, any structure that interprets this language must contain one designated element, one unary operation, and two binary operations.

Question 10

What is interpretation?

Answer 10

An interpretation consists of a structure together with a mapping from the non-logical symbols in the language to elements in the structure.

Question 11

What is “standard interpretation?”

Answer 11

Standard interpretation for FOA is based structure domain are natural number (including num designated zero) and unary successor function, binary addition and multiplication functions:

Question 12

How is the mapping of standard interpretation σ from the language of FOA to natural number structure defined?

Answer 12

σ(0) is 0 and σ(+) is +, etc.
The logical symbol “=” always interpreted by the identity relation.

Question 13

What is σ?

Answer 13

Part of structure
σ maps formulas to truth values and terms to elements of the domain
* (T1-T2) define mapping from set of terms to universe U of σ
* (F1-F4) define mapping from the set of formulas to {T, ⊥} the truth values

Note: F4 is non-effective - not provide method to find the truth value if the universe if the universe of discourse in infinite

Valuation: simply an interpretation that also assigns elements from the domain to variables, where σ is the valuation in a structure with universe U.

Question 14

How does interpretation relate to meaning in FOL?

Answer 14

Interpreation does not assign meaning to individual variables. Need to use valuation

Question 15

Define valuation:

Answer 15

Valuation: simply an interpretation that also assigns elements from the domain to variables, where σ is the valuation in a structure with universe U.

Question 16

What are the rules for valuation for complex terms(Tarski’s Basic Semantic Definition)?

Rules allow to interpret complex terms (T1-T2) and formulas (F1-F4)

Answer 16

Write A^σ for a value that σ asigns to A (or σ(A)):

(T1) If x is a variables then x^σ is already defined (What does σ map x to?) (by the def of valuation)

(T2) If f is an n-ary function sumbol and t1,…,tn terms, then: (f(t1 … tn))^σ = f^σ(t1^σ … t2^σ)

Question 17

What are the rules for valuation for formulas (Tarski’s Basic Semantic Definition)?

Rules allow to interpret complex terms (T1-T2) and formulas (F1-F4)

Answer 17

(F1) P(t1 … tn))^σ and (s = t)^σ
(F2) (~A)^σ
(F3) (A ⊃ B)^σ
(F4) (∀x : A)^σ

Question 17

What is F4:

Answer 17

(∀x : A)^σ =
T, if A^σ(u/x) = T for every u ∃ U
⊥, if i.e., A^σ(u/x) = ⊥ for some u ∃ U

Note: F4 is non-effective - not provide method to find the truth value if the universe if the universe of discourse in infinite

Question 18

Why does the order of quantifiers matter?

Answer 18

Must be evaluated in order

Question 19

What is the difference between ∀x1: ∃x2: (Sx1 = x2) and ∃x1: ∀x2: (Sx1 = x2)?

Answer 19

For all values of x1 there exists of value of x2 such that the conclusion is true (tautology)

For some value x1, all values of x2 are such that the conclusion is true.

Question 20

Semantic concepts of σ: (formulas and a set of formulas)

Answer 20

σ satisfies A: A is a formulas and σ a valuation, such that A^σ = T.

σ satisfies T: T is a set of formulas and σ is a valuation that satisfies every member of T

Question 21

A is logically true (valid) written …

Answer 21

** ⊨ A**

The formula A is satisfied by every valuation

Question 22

A is logical consequence of T written …

Answer 22

T ⊨ A
The formula A is satisfied by every valuation that satisfies T. Every valuation that makes T true makes A true.

Question 23

T is unsatisfiable if …

Answer 23

No valuation that satisfies each formula in T

Question 24

Define a model

Answer 24

A model of a set of formulas T is an interpretation in a structure, such that all the formulas in T are true in the structure.

Question 25

Bound variable:

Answer 25

A variable x is bound if it falls inside the scope (where A is the scope of ∀x:A) of a quantifier that has x as its variable of quantification

Free variables: Variables that are not bound

x1 bound in …
- P(x1, Px2) - no
- ∀x1: P(x1, Px2) - yes
- ∃x2: P(x1, Px2) - no but x2 is bound

Question 26

Free variable:

Answer 26

Variables that are not bound

Recursive definition:
1. α is an atomic formula (predicate): All occursances of x in α are free.
2. If α is ~A: x is free if its in free in A
3. If α is free in the conjuction variables, x is free is α, if it is free in either A or B
4. If α is (∃x: A) or (∀x:A) - All occurances of x in A are bound. If y is not the variable of quantification, then y is free in α, if it is free in A

A variable x is bound if it falls inside the scope (where A is the scope of ∀x:A) of a quantifier that has x as its variable of quantification

Question 27

When is a term closed?

Answer 27

A term is closed if it contains no variables (otherwise - open)

Question 28

What is a sentence?

Answer 28

A sentence is a formula without free variables

Question 29

What is substitution and what are the conditions for substitution?

Answer 29

Given a formula A and a variable x, say that
“a term t is free for an occurance of x in A”

if (1) that occurance of x is free in A and does (2) not lie in the scope of any quantifier ∃y or ∀y (where y is a variable that appears in t). Hence, by substituting t for the occurence of x, no new variable becomes bound.

If t is free for all occurences of x in A, we can substitute t for x in A, i.e. replace all free occurences of x in A simualtaneously by t.

Write: A(t/x)

Question 30

Difference between interpretation and valuation:

Answer 30

Interpretations only assign meaning to function symbols and constants, while valuations also assign meaning to variables.