Title: Theory / Unimportant / Math / Logic / recursion theory / Odifreddi / 4 Hierarchies and weak reducibilities
Tags: récupéré

Definition: First-order language with equality, augmented with constants \(\overline n\) for each number \(n\), binary function symbols \(+,\times\)
Page: 364
Chapter: IV
Section: 1
Notation: \(\mathcal L\)
Kind: Def

Definition: The intended structure for \(\mathcal L\), natural number with usual sum and product
Page: 364
Chapter: IV
Section: 1
Context: Arithmetic
Notation: \(\mathcal A\)
Kind: Def

Name: An \(n\)-ary relation which is definable in first-order arithmetic
Definition: An \(n\)-ary predicate \(P\) such that \(P(x_1,\dots,x_n)\) iff \(\mathcal A\models \phi(\overline x_1,\dots,\overline x_n)\).
Page: 364
Chapter: IV
Section: 1
Kind: Def

Definition: First-order language with equality, augmented with constants \(\overline n\) for each number \(n\), and \(\phi_R\) for each recursive \(n\)-ary relation \(R\).
Page: 364
Chapter: IV
Section: 1
Notation: \(\mathcal L^*\)
Kind: Def

Definition: The intended structure for \(\mathcal L^?\), natural number with \(\phi_R\) being interpreted as \(R\)
Page: 364
Chapter: IV
Section: 1
Notation: \(\mathcal A^*\)
Kind: Def

Name: A relation in the Arithmetical Hierarchy
Definition: An \(n\)-ary relation \(P\) such that \(P(x_1,\dots,x_n)\iff{}\mathcal A^*\models\phi(\overline x_1,\dots,\overline x_n)\)
Page: 365
Chapter: IV
Section: 1