Chapter 1: Definitions

Question 1

Definition 1.1.

The set of formulae in the general first order predicate language is denoted by L, and is defined inductively as follows:

Answer 1

(1) If P is an n-ary predicate symbol and x1, · · · xn are variable symbols, then P x1 · · · xn is a formula.
(2) If α is a formula, then so is ¬α.
(3) If α, β are formulae, then so is ⇒ αβ.
(4) If x is a variable symbol and α is a formula, then ∀xα is a formula.

Question 2

Definition 1.5.

If α is a formula (α ∈ L), then the degree of α, or deg(α), is the non-negative integer obtained by (starting from 0 and):

Answer 2

1) adding 1 each time ¬ occurs in α;
2) adding 2 each time ⇒ occurs in α;
3) adding 1 each time ∀ occurs in α.

Question 3

Definition 1.7.

For s a string in Lstring, the weight of s, written as weight(s), is the integer obtained by taking the sum of:

Answer 3

1) −1 for each (occurrence of a) variable symbol in s;
2) n − 1 for each (occurrence of an) n-ary predicate symbol in s;
3) 0 for each (occurrence of) ¬ in s;
4) +1 for each (occurrence of) ⇒ in s;
5) +1 for each (occurrence of) ∀ in s.

Question 4

Definition 1.11.

The set of formulae in the general conventional functional first order predicate
language is denoted by Lmath, and is defined inductively as follows:

Answer 4

0) Each variable symbol is a variable.
1) If F is an n-ary functional symbol and x1, · · · xn are variables, then F x1 · · · xn is a variable.
2) If P is an n-ary predicate symbol and x1, · · · xn are variables, then P x1 · · · xn is a formula.
3) If α is a formula, then so is ¬α.
4) If α, β are formulae, then so is ⇒ αβ.
5) If x is a variable symbol and α is a formula, then ∀xα is a formula

Question 5

Lmath Conversions

Answer 5

α ⇒ β’ to denote ⇒ αβ
‘α ∨ β’ to denote (¬α) ⇒ β (or ⇒ ¬αβ in L)
‘α ∧ β’ to denote ¬ (α ⇒ (¬β)) (or ¬ ⇒ α¬β in L)
‘α ⇔ β’ to denote (α ⇒ β) ∧ (β ⇒ α)
‘∃xα’ (or ‘(∃x)α’) to denote ¬∀x¬α.

Question 6

describe the set of symbols used in general first order predicate language

Answer 6

The symbols of the general first order predicate language consist of:
1) A countably infinite set of variable symbols: {x1,x2,x3 ···}or{w,x,y,z,w′,x′,y′,z′,···}.
2) For each non negative integer n, a countably infinite set of predicate symbols{P1,P2,P3···} or{P,Q,R,P′,Q′,R′,···}, each of which has arity n. If P is a predicate symbol of arity
n, then we call P an n-ary predicate symbol.
3) The symbols ¬, ⇒, ∀.