 Solution

ID: past-exam-of-the-model-theory-and-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2010/b/4/f/iii/solution

n

x = s^{n} (0)

defines the singleton

{n}

in the standard successor structure. These are pairwise distinct parameter-free definable subsets. Therefore

{{n} : n \in N} is an infinite family of definable subsets .

In particular the criterion in part (e) applies already at arity one.

 New to topics? Read the docs here!