``The completeness theorem is an absolute highlight of all of mathematics. It's brilliant'' - Dr Leader
The number of arguments to a function is its arity.
(5.1) |
(5.2) |
(5.3) |
A poset is a set A with a relation . Conveniently is written .
(5.4) |
(5.5) |
(5.6) |
Let the set of functions and predicates be distinct sets, and let the arity function be . Then the language is the set of all formulae.
For groups, . For posets, .
A term is a subset of strings of symbols from the alphabet .
Note that the term is not the value of the function with these arguments. It is just a string. To emphasize this you can write it .
An atomic formula is one of
``not '' | ||
``p or q'' | ||
``p and q'' | ||
``exists x such that p'' |
An occurrence of a variable in a formula is free if it is not within the brackets of a ``''. Otherwise it is bound.
A sentence is a formula with no free variable (for example the axioms for groups and posets).
Let be a language. An -structure is a non-empty set , for each a function and for each a subset .
the language of groups: an -structure is a set with functions .
the language of posets: an -structure is a non-empty set with a relation .
A closed term is a term with no variables. For example , not .
The interpretation of a closed term in an -structure written is defined inductively. If , and closed terms then .
Note that if is constant symbol then is already defined.
For a sentence and an -structure the interpretation of in is a defined inductively
where we extend to by adding a new constant symbol and make an -structure by setting and for any term , is the formula obtained by replacing each free occurrence of with .
``Now forget all this nonsense and think of it only as in the original idea.'' - Dr Leader.
If we say holds in or is true in or is a model of written .
For a set of sentences (a theory) say is a model of written if .
For a theory, a sentence, say entails written if every model of is a model of .
If we say is a tautology.
What is called in propositional logic a valuation is like in predicate logic an interpretation.
Say that the members of a theory are axioms, and that the theory axiomatizes the things which are models of it.
Let be the language of groups and let
Then an -structure is a model of iff is a group. axiomatizes the class of groups.
Suppose we change the third axiom to be just to produce . Does axiomatize the class of groups? (Think about it but the answer is yes).
Let language of posets and let . Then a model for is precisely a poset.
Let . . For take
Then axiomatizes the class of fields.
Language of and . .
Then an -structure on is a -model iff is a graph.
This is called first-order logic. We can qualify over elements but not over subsets. For example we cannot say ``for all subgroups of ''.
Could have an alternative language for groups with and third element of the theory being .
Many natural theories have infinite. For example, we have fields of characteristic zero. language of fields. axioms of a field, with , etc.
Fields of non-zero characteristic. language of fields, axioms for a field. Can we axiomatize fields of charactistic ? (Exercise.)