A language: automatically contains quantifiers, logical connectives,
variables. We specify a particular language by specifying whatever
additional non-logical primitives it contains: constants, function symbols,
and predicates.
You should know the definitions (usually recursive) of: atomic terms,
terms, atomic formulas, formulas, sentences.
If I give you a string of symbols, you should be able to say whether (and
why) it is a term, a sentence, etc. (Is f(x) a sentence? A term? A formula?
What about F(a,b) & G(b,x)? Etc.)
You should understand how to construct a proof by induction. (Suppose you
want to prove that every formula has a certain property. You will begin with
one or more base steps, in which you prove that atomic formulas have the
property. Then you need an inductive step, in which you prove that, if a
formula F has the property, then any compound formula containing F will have
the property. Your procedure here is basically just conditional
introduction: assume that F has the property, then use that assumption to
prove that compound formulas containing F have the property.) (A common kind
of inductive proof is mathematical induction. For instance, you might want
to prove that every natural number has a certain property. In the base step,
you prove that 0 has the property. Then in the induction step you assume
that a number n has the property, and prove on that assumption that n+1 has
the property.)
I might give you a simple inductive proof. For instance, you should be
able to prove that in a language without function symbols, every formula has
an equal number of left and right parentheses. (This is also true for
languages with function symbols, but I will probably make things as easy as
possible.)
You should know what is meant by a subformula, a bound variable, a free
variable.
You should know what L*, the language of arithmetic, is.
Semantics of First-Order Logic
you should know what an interpretation is. (An interpretation consists of:
a universe, an assignment of an element of the universe to each constant, an
assignment of an n-place function (a.k.a. a set of n+1-tuples of elements of
the universe) to each n-place function symbol, and an assignment of a set of
n-tuples of elements of the universe to every n-place predicate. (Except in
the case of one-place predicates we just take a set of elements of the
universe instead of a set of singletons.)
you should know how an interpretation gets extended from the primitives of
the language to more complex expressions. (An interpretation as described
above suffices to determine an extension for every expression in a language,
given the rules for determining the interpretation of compound expressions
in terms of simpler expressions.)
In particular, you should understand how the interpretation of a
quantifier sentence is arrived at, and understand the related notion of
satisfaction.
You should understand the notation used to express all this stuff.
Note that the double turnstile is used to indicate that an interpretation
makes a particular sentence true. That is, if M is an interpretation and F
is a sentence, then M ⊨ F means that F is true in the
interpretation M. Another way to say the same thing is that M is a model of
F.
You should know what the standard interpretation N of the language of
arithmetic is.
You should know what it means to say that a set of sentences Gamma
logically implies a sentence F. (It means that every interpretation
that makes all the sentences in Gamma true also makes F true. Another way to
say this: every model of Gamma is a model of F.)
Note that we can prove that F is not a logical consequence of Gamma if we
can find an interpretation (any interpretation!) that makes all the
sentences in Gamma true and also makes F false.
Undecidability Via Turing Machines
know the definitions of question, problem, decision problem
know what is meant by "the decision problem for first-order
logic"
You should be able to explain the broad outlines of the proof discussed in
class that first-order logic is undecidable (the one that uses first-order
logic to describe any Turing machine)
You should understand exactly how that proof depends on Turing's thesis.
(Needless to say, this means that you should remember what Turing's thesis
is!)
Models
know what a model of a sentence, or set of sentences, is.
Note that if we speak of a model of a sentence or set of sentences without
explicit reference to a language, we have in mind an interpretation of the
minimal language needed to express those sentences -- i.e. a language that
contains, in addition to logical expressions, only the nonlogical
expressions that actually occur in the set of sentences. So a model of the
sentence F(c) would be an interpretation of the language {F, c}in which F(c)
is true.
Know what is meant by the size of a model. (Answer: the size of the
universe of the model.)
You should be able to write a sentence of first-order logic that has only
models of size n for any positive integer n.
Conversely, if I give you a sentence of first-order logic, you should be
able to determine what size models it can have.
Know what it is for two interpretations to be isomorphic. If I give you
two simple interpretations, you should be able to prove that they are (or
are not, as the case may be) isomorphic.
know what an equivalence relation is
and what an equivalence class is
know what a partition is, and how partitions are related to equivalence
relations
know what the signature of a model is
are there sentences that have only infinite models?
are there sentences that have only nondenumerable models?
be able to state the Lowenheim - Skolem theorem. (You don't need to be
able to prove it! Just to say what it is.)
be able to state the Compactness theorem. (Again, you don't need to be
able to prove it!)