Problem 4. (12 points) Suppose L=(f_(1),f_(2),g,\phi ,c) is a first-order language
where f_(1),f_(2) are binary function symbols, g is a unary function symbol, \phi is a
binary predicate symbol and c is a constant symbol. Consider the usual structure of
the number theory as an L-structure
N=(N,+,\times ,S,<,0)
by the following interpretations: f_(1)^(N) is + (the addition function), f_(2)^(N) is \times (the
multiplication function), g^(N) is S (the successor function), \phi ^(N) is < (the usual order
relation) and c^(N) is the number 0 .
(a) What is the interpretation of the term f_(1)(g(g(c)),f_(2)(g(x),y)) in N, where
x^(N) is 2 and y^(N) is 3? Show your work.
(b) Find the value of the A^(N), where A is the L-formula
(EEx)(AAy)f_(2)(x,y)=y
(c) Write an L-formula B(x) with a free variable x such that N|==B(n) iff n
is an odd number.
