ShaughanLavine? - 28 Aug 2008 - 04:27 - 1.24" class="twikiLink">TWiki> Discussion Web>ProofThatPrimitiveRecursionIsEssentialToolTip (23 Feb 2007, ShaughanLavine)EditAttach
For example, the structure formed as a disjoint sum of $\langle\mathbb{N},0,S,+,\cdot\rangle$ and $\langle\mathbb{Z},+\rangle$ is a model of PA$^{(+)U}\cup G^{U'}$ that has an obvious expansion to a model of PAPR$^{(+)U}\cup G^{U'}$, and the set of prime integers is definable in the expanded model but not in the original one. (Every subset of $\mathbb{Z}$ definable in the disjoint sum of $\langle\mathbb{N},0,S+,\cdot\rangle$ and $\langle\mathbb{Z},+\rangle$ is already definable in $\langle\mathbb{Z},+\rangle$—that is just an elementary fact about disjoint sums that can be proved by a straightforward induction. By the elimination of quantifiers, the primes are not definable in $\langle\mathbb{Z},+\rangle$, (Presburger), and they are therefore not definable in the disjoint sum of $\langle\mathbb{N},0,S+,\cdot\rangle$ and $\langle\mathbb{Z},+\rangle$. But the set of primes of $\mathbb{Z}$ is easily seen to be definable in the expanded structure—since the prime natural numbers are definable in $\langle\mathbb{N},0,S+,\cdot\rangle$—by using a primitive recursive definition of an injection from $\mathbb{N}$ into $\mathbb{Z}$.) Thus, the expansion is not an expansion by definitions.

-- ShaughanLavine - 16 Mar 2005

Edit | Attach | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | Wysiwyg edit | More topic actions
Topic revision: r6 - 23 Feb 2007 - 07:16:36 - ShaughanLavine

 
Powered by TWiki
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback