First-Order Logic(1)

 

Basically, we'll use below symbols.

 

Logical symbols

1. Parentheses : (, ).

2. Sentential connective symbols: $\rightarrow$, $\neg$.

3. Variables(every subscript belongs to $\mathbb{N}$;countable) : $v_1$, $v_2$, $v_3$, $\cdots$.

4. equality symbol : =.

 

Parameters

1. quantifier symbol : $\forall$ (means 'for all', 'for every' , 'for any')

2. predicate symbols : $n$-place predicate symbols which is a set of symbols.

3. constant symbols

4. function symbols : $n$-place function symbols which is a set of symbols.

 

a predicate in logic is a property of some objects. for example, 'x<1' can be predicate since this asserts x has property that $x$ is less then 1. we symbolize that as $Px1$ and $P$ the set of $x$ where $x<1$.

 

the meaning of logical symbols does not change but parameters does by structures which'll be introduced later.

 

now give some definitions simiarly as PL.

 

Terms

1. every variable is a term

2. every constant symbol is a term

3. $ft_1t_2t_3\ldots t_n$ is a term where every subscript is a term and $f$ is any $n$-place function symbol.

4. every expression which is not built up from 1-3 is not a term.

(as in PL, expression is a finite sequence of symbols)

 

Well-formed formulas(wffs)

a well-formed formula(;formula) is an expression which is built up from atomic formulas using 0 or more times connective symbols or quantifier symbols or both.

 

1. atomic formula is a $n$-place predicate symbol or the form of $t_1=t_2$ where $t$ is a term.

2. $\varepsilon_\neg(\alpha)=(\neg \alpha)$ is a wff.

3. $\varepsilon_\rightarrow(\alpha, \beta) = (\alpha \rightarrow \beta)$ is a wff.

4. $\mathscr{Q}_i(\alpha)=\forall v_i\alpha$

where $\alpha, \beta$ is any wff.

 

Free variables

think about $\forall v_1 \exists v_2 Pv_1v_2$ where predicate $Pxy$ is translated as '$\text{x has a father y}$'. then given formula is translated as 'for every v_2, v_2 has an father v_1' which can be evaluated as $T$ or $F$.

 

but $\forall v_1 Pv_1v_2$ cannot be evaluated as $T$ or $F$. that 'for every v_1, v_1 has father _____' is true or false does not make sense. the blank must be filled. we'll call variables like $v_2$ as free variables. and mathematically, free variable can be defined as;

 

$x$ is a variable, and $\alpha, \beta$ is a wff.

 

1. $x$ occurs free in atomic formula $\alpha$ iff $x$ occurs in $\alpha$.

2. $x$ occurs free in $(\neg \alpha)$ iff $x$ occurs free in $\alpha$

3. $x$ occurs free in $(\alpha \rightarrow \beta)$ iff $x$ occurs free in $\alpha$ or $\beta$ or both.

4. $x$ occurs free in $\forall v_i \alpha$ iff $x$ occurs free in $\alpha$ where $x \neq v_i$.

 

if $x$ occurs free in any wff $\alpha$, then we call $x$ a free-variable of $\alpha$.

 

if you think this is not mathematically rigorous, you can give another definition using recursion theorem; define $h(\alpha)$ = the set of free variables of atomic formula $\alpha$. then extend $h$ to $\bar{h}$.

 

if free variable does not occur in a wff $\alpha$, then we call $\alpha$ is a sentence($\bar{h}(\alpha)=\emptyset$). later on, we'll give truth value for first-order sentence.

 

 

abbreviation for another symbols

we abbreviate $\neg, \vee, \wedge, \leftrightarrow, \exists$ as

$(\alpha \vee \beta) = ((\neg \alpha) \rightarrow \beta)$

$(\alpha \wedge \beta) = \neg((\alpha \rightarrow (\neg \beta)))$

$(\alpha \leftrightarrow \beta) = ((\alpha \rightarrow \beta) \wedge (\beta \rightarrow \alpha))$

$\exists x \alpha = (\neg \forall x(\neg \alpha))$

where $\alpha, \beta$ are any wffs.