Marker's comments on Problem Set 3 (Wehr)

Average 44.4 / 50.

Question 1: Most students did well. The most common mistake was violating
the free variable restriction for rule Forall-right or Exists-left. If
your proof was technically incorrect AND the underlying informal proof
was wrong -for example, if you didn't use the necessary equality axioms-
then you lost more marks.

Question 2: All but a few students missed this. We decided to be gentle
on the grading. The set of formulas S used in the solutions has this
property: The formula A is a logical consequence of S, and ANY model
of S must have an infinite path. Thus it suffices to use compactness
to show there exists SOME model of S.  A common incorrect construction
was an infinite set of existential formulas S, such that A is a logical
consequence of S, where the n-th formula expresses the existence of a
path of length n. The problem was that S has (infinite) models with no
infinite path, for example the graph that consists of infinitely-many
disjoint paths of arbitrary finite length. A couple students gave a
construction like in the solutions, but without the formulas that say
the nodes are distinct. You could use exercise 9 on page 50 of the notes
to argue that there is an infinite model, but that isn't sufficient:
consider the graph with infinitely many edgeless nodes, and one loop.
A couple students gave an alternate correct construction: for every n,
have a formula that expresses "For every node x, there is a path of
length n starting from x", and also a formula that says "Every node has
outdegree at most 1".

Question 3: Most students did well, though a few confused PR-expressions
and primitive recursive functions. You were not being asked to show
that PR-expressions are primitive recursive (that doesn't make sense),
but that they *represent* primitive recursive functions. Also, you lost
marks if you tried to handwave the cases for constants and variables.

Question 4: Most students did well. The most common mistake was storing
x or y in registers that could be overwritten by P_g.

Question 5: Almost everyone got this.