First-Order Arithmetic Flashcards
How does FOA relate to FOL?
FOA is a “subcase” (not right phrase) of FOL
What is the langauge of first order arithmetic?
(1) Function Symbols: 0 (a 0-ary function - constant), (2) unary function symbol S (successor) and (3) binary function symbols + (addition) and X (multiplication)
What are the terms of FOA?
- Exery variable x0, x1 … is a term
- 0 is a term. If t and u are terms, then so is St, (t + u), and (t x u)
- 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
What is SSS0 in standard interpretation?
Formal representation of 3
Another structure: 0 + (S0 x (S0 + SS0))
What are formulas in FOA?
- If t and u terms, then t = u is an (atomic) formula
- If A and B are formulas, then so are the connective formulas
- If A and B are formulas and x is a variable, then (∀x: A) and (∃x: A) are formulas
- 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.
What is the interpretation (valuation) of FOA?
Algebraic statements
Goal of semantics in the context of FOA?
Give meaning to non-logic symbols to determine which formulas are true
How does interpretation in FOA differ from propositional logic?
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
What is structure in FOL?
- 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.
What is interpretation?
An interpretation consists of a structure together with a mapping from the non-logical symbols in the language to elements in the structure.
What is “standard interpretation?”
Standard interpretation for FOA is based structure domain are natural number (including num designated zero) and unary successor function, binary addition and multiplication functions:
How is the mapping of standard interpretation σ from the language of FOA to natural number structure defined?
σ(0) is 0 and σ(+) is +, etc.
The logical symbol “=” always interpreted by the identity relation.
What is σ?
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.
How does interpretation relate to meaning in FOL?
Interpreation does not assign meaning to individual variables. Need to use valuation
Define valuation:
Valuation: simply an interpretation that also assigns elements from the domain to variables, where σ is the valuation in a structure with universe U.
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)
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^σ)
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)
(F1) P(t1 … tn))^σ and (s = t)^σ
(F2) (~A)^σ
(F3) (A ⊃ B)^σ
(F4) (∀x : A)^σ
What is F4:
(∀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
Why does the order of quantifiers matter?
Must be evaluated in order
What is the difference between ∀x1: ∃x2: (Sx1 = x2) and ∃x1: ∀x2: (Sx1 = x2)?
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.
Semantic concepts of σ: (formulas and a set of formulas)
σ 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
A is logically true (valid) written …
** ⊨ A**
The formula A is satisfied by every valuation
A is logical consequence of T written …
T ⊨ A
The formula A is satisfied by every valuation that satisfies T. Every valuation that makes T true makes A true.
T is unsatisfiable if …
No valuation that satisfies each formula in T
Define a model
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.
Bound variable:
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
Free variable:
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
When is a term closed?
A term is closed if it contains no variables (otherwise - open)
What is a sentence?
A sentence is a formula without free variables
What is substitution and what are the conditions for substitution?
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)
Difference between interpretation and valuation:
Interpretations only assign meaning to function symbols and constants, while valuations also assign meaning to variables.
