First Order Languages

It is a triple where is a countable set of relation symbols is a countable set of function symbols C is a countable set of constant symbols , : arity of , , indicating how many arguments the symbol takes

is a countable set of variables.

Terms

The set of terms over is the smallest set satisfying the following conditions: - Every constant symbol is a term - Every variable is a term - Let be terms over L and let be a function symbol of arity n, then is a term

A term which does not contain any variables is called a closed term.

Think of a term as a name.

Expressions

Any finite sequence of elements of L and basic symbols (connectives, quantifiers) forms an expression. Terms are meaningful expressions,

Atomic formulas

  • Let and let be terms over L. Then is an atomic formula.
  • Let terms over L. Then is an atomic formula

Second type of atomic formula asserts that these two terms/names are equivalent.

Relation symbols are also called predicates. So atomic formulas act as atomic propositions or basic facts about the first order logic. A relation will be either true or false after some structure is given to the first order language. Similarly, will be either true or false.

So atomic formulas, in an essence, capture how the terms are/can be related to each other in our language. For example, a relation symbol could be with arity two. It takes in 2 names and tells if they are married.

Structures

A structure for is a pair where is a non empty set and is an operation with domain such that, writing :

  • , n-ary, then
  • , n-ary, then
  • then

So , the predicates/relation symbols get assigned the proper “elements” that constitute each relation. The functions are also made precise, that is, proper definition is given to each function because of the structure. And the constants are given their values.

Assignment

An assignment in is a function with the domain set of variables of and range a subset of .

First order Formulas

They form the smallest set of expressions containing the atomic formulas and closed under the following formation rules:

Formation rules If are formulas , variable i) the expressions are also formulas. ii) are also formulas.

We associate parantheses to the right in strings where the sane symbol is repeated. (right associativity within same symbols)

First Order sentence

A formula without any free variables.

Satisfaction

Let be an structure. We define the relation

(to be read as : the assignment satisfies the formula in ) for all assignments s and for all formulas as follows:

i)

From Propositional Logic to First Order Logic

In Propositional Logic, we have atomic propositions, and the assignment of truth values is to these atomic props. Whereas, in FOL, we have a lot of structure first. We start with any set, which we call our universe of discourse or universe of discussion. Note that - this set is not the set of atomic propositions. It can be any set of objects, for example - natural numbers. We then have functions on this set. This is how we give this set some structure. In these functions also we do not have any truth assignment yet. We have not talked about any truth or falsity till now. We are just giving it some structure.

We also have a set of variables and constants. These constants ( as the name suggests ) are concrete elements from our universe of discourse and they do not change.

Now, we will talk about relations. This is where truth assignment comes in “indirectly”. We have a bunch of relation “names”, and each relation name is a subset of for a fixed n, where U is our universe of discourse.

Note that relations make up the set of atomic formulas which do not contain the equality symbol. Since we do not have atomic props, we can see atomic formulas kind of taking up the role of atomic props.

We can make more formulas using variables, In propositional logic, we consider assignments. Assignments of what? assignments of the truth values to the atomic props. Here, we consider assignment of variables to the elements of the universe.