Title: Theory / Unimportant / Math / Logic / recursion theory / Odifreddi / 1 Recursiveness and Computability
Tags: hasSeenConjDef
On every note of this deck, unless a note says otherwise:
Chapter: I

Name: A natural number
Definition: Either 0 or the successor of a natural number
Page: 19
Section: 1

Name: The successor of \(n\)
Page: 19
Section: 1
Variables: \(n\) a natural number
Notation: \(\mathcal S(n)\)

Name: Axiom of successor
Definition: \(\mathcal S(x)=\mathcal S(y)\) implies \(x=y\)
Page: 20
Section: 1
Definition2: \(0\ne\mathcal S y\)
Definition3: \(x\ne0\implies \exists y\ x=\mathcal S(y)\)

Name: Axiom of addition
Definition: \(x+0=x\)
Page: 20
Section: 1
Definition2: \(x+\mathcal S(y)=\mathcal S(x+y)\)

Name: Axiom of multiplication
Definition: \(x\cdot 0=0\)
Page: 20
Section: 1
Definition2: \(x\cdot\mathcal S(y)=x\cdot y+x\)

Name: The function defined from \(g\) and \(h\) by primitive recursion
Definition: The function \(f:B\times\mathbb N\) such that:
-\(f(\vec x,0)=g(\vec x)\),
-\(f(\vec x,y+1)=h(\vec x,y,f(\vec x,y))\)
Page: 20
Section: 1
Variables: \(g:B\to A\),
\(h:B\times\mathbb N\times A\to A\)
Index: 3
Kind: Def

Name: Axiom of Induction
Definition: For each formula \(\phi\) with one free variable:
\(\phi(0)\land \forall x[\phi(x)\implies \phi(\mathcal S(x))]\implies \forall y\ \phi(y)\)
Page: 20
Section: 1

Name: Axiom of complete Induction
Definition: For each formula \(\phi\) with one free variable:
\(\forall z[\forall x<z\ \phi(x)\implies\phi(\mathcal S(x))]\implies \forall y\ \phi(y)\)
Page: 21
Section: 1
Name2: Axiom of strong Induction

Name: Least number Principle
Definition: For each formula \(\psi\) with one free variable in \(\mathbb N\):
\(\exists y\ \psi(y)\implies \exists z[\psi(z)\land\forall x<z\ \neg\psi(x)]\)
Page: 21
Section: 1

Name: A regular predicate
Definition: A predicate \(R\) such that \(\forall\vec x\exists y\ R(\vec x,y)\)
Page: 21
Section: 1
Context: Modal logic
Index: 5
Kind: Def

Name: The function defined from \(R\) by \(\mu\)-recursion
Definition: The function sending \(\vec x\) to the least \(y\) such that \(R(\vec x,y)\) holds.
Page: 21
Section: 1
Variables: \(R\) a regular predicate
Notation: \(\mu yR(\vec x,y)\)
Index: 5
Kind: Def

Name: The function defined from \(g\) by \(\mu\)-recursion
Definition: The function sending \(\vec x\) to the least \(y\) such that \(R(\vec x,y)=0\).
Page: 21
Section: 1
Variables: \(g:A\times \mathbb N\to\mathbb N\) a function
Notation: \(\mu yg(\vec x,y)\)
Index: 5
Kind: Def
Assuming: \(\forall\vec x\exists y g(\vec x,y)=0\)

Name: The initial functions
Definition: The constant 0 function
Page: 21
Section: 1
Index: 6
Kind: Def
Definition2: The successor function
Conjdef: All of
Definition3: The projection function from tuples to an element

Name: A primitive recursive predicate
Definition: A predicate whose characteristic function is primitive recursive.
Page: 21
Section: 1
Index: 6
Kind: Def

Name: The class of recursive function
Definition: closed under \(\mu\)-recursion
Page: 22, 28
Section: 1
Index: 7,8
Kind: Def, THeo
Definition2: closed under composition
Conjdef: The least set
Definition3: either:
Definition4: (Containing the initial functions
Definition5: and closed under primitive recursion)
Definition6: or containing sum, product, and equality

Name: A recursive predicate
Definition: A predicate whose characteristic function is recursive.
Page: 22
Section: 1
Index: 6
Kind: Def

Name: The set of primitive recursive function
Definition: containing initial functions
Page: 21
Section: 1
Index: 6
Kind: Def
Definition2: Closed under composition, i.e. containing \(h(g_1(\vec x),\dots,g_n(\vec x))\) for \(h,g_i\) recursive
Conjdef: The least set
Definition3: closed under primitive recursion

Name: The exponent of \(k\) in the decomposition of \(y\)
Definition: \(\mu x_{\le y}[k^x\mid y\land \neg(k^{x+1}|y)]\)
Page: 26
Section: 1
Variables: \(y,k\in\mathbb N\)
Context: number theory, computability
Notation: \(exp(y,k)\)

Name: Dovetailing
Definition: \((x,y)<(x',y')\) if \(x+y<x'+y'\) or if \(x+y=x'+y'\) and \(x<x'\)
Page: 26
Section: 1
Definition2: the element \((x,y)\) is in position \(\left(\sum_{i<x+y}(i+1)\right)+x=\frac{(x+y)^2+3x+y}{2}\)
Conjdef: The enumeration of \(\mathbb N^2\)

Definition: [$]\defFun{\mathbb N^2}{\mathbb N}{(n,m)}{\left(\sum_{i<n+m}(i+1)\right)+n=\frac{(n+m)^2+3n+m}{2}}[/$]
Page: 26
Section: 1
Context: Dovetailing
Notation: \(\mathcal J\)

Question: Example of onto coding of finite sequence
Answer: Encoding \((x_1,\dots,x_n)\) by the number encoded by the concatenation of \(10\dots0\) with \(x_i\) 0's
Page: 26
Chapter: I
Section: 1

Question: How to encode a primitive recursive function \(f\) (using \(\mu\)-recursion and arithmetic)
Answer: instead of \(f(b,n)\) use \(\beta(a,n)\), and ensure that \(\beta(a,0)=g(b)\), \(\beta(a,i+1)=h(\beta(a,i),i)\), where \(\beta\) is a function used to encode finite tuple, and \(a\) is an existentially quantified variable
Page: 28
Chapter: I
Section: 1
Variables: \(g:B\to A\),
\(h:B\times\mathbb N\times A\to A\)
\(f\) defined by primitive recursive function from \(g\) and \(h\)

Definition: \(((c,d),i)\mapsto c\mod 1+(1+i)\mod d\)
Page: 29
Section: 1
Context: Recursion theory
Notation: \(\beta\)
Abbreviation3: The function which encodes finite sequence

Question: How to encode \(a_1,\dots,a_n\) into a number \(N\) such that \(\beta(N,i)=a_i\)
Answer: Take
\(s\ge\max(n,a_1,\dots,a_n)\),
\(d=s!\)
\(d_i=1+(i+1)d\)
\(c\) such that \(a_i\equiv c\mod d_i\)
Take \(N=(c,d)\)
Page: 29
Chapter: I
Section: 1
Variables: \(\beta((c,d),i)=c\mod 1+(1+i)\mod d\)
\(a_1,\dots,a_n\in\mathbb N\)
Context: Recursion theory

Name: Symbols
Definition: \(=\)
Page: 32
Section: 2n
Context: Recursion theory
Definition2: 0 and S
Conjdef: All of
Definition3: ( ) and ,
Definition4: variables \(x_i\)
Definition5: \(n\)-ary functions \(f_i^n\)

Name: Numerals
Definition: 0
Page: 32
Section: 2n
Context: Recursion theory
Definition2: \(S(a)\) where \(a\) is also this kind of object
Conjdef: All of

Definition: 0 if \(n=0\), \(S(\overline {n-1})\) otherwise
Page: 32
Section: 2n
Variables: \(n\in\mathbb N\)
Context: Recursion theory
Notation: \(\overline n\)

Name: Terms
Definition: Numerals
Page: 32
Section: 2
Context: Recursion theory
Definition2: variables
Conjdef: All of
Definition3: \(n\)-ary functions applied to \(n\) elements of the same kind

Name: Equation
Typ: A pair of terms
Page: 32
Section: 2
Chapter: I
Denoted by: \(t=s\)
Context: Recursion theory

Name: System of equation
Definition: A finite set of equation
Page: 32
Section: 2
Context: Recursion theory

Definition: A system of equations whose functional letters and numerical variables are all among \(f_i\) and \(\vec z\)
Page: 32
Section: 2
Variables: \(f_1,\dots,f_n\) functions
\(\vec z\) a set of vectors
Context: Recursion theory
Notation: \(\mathcal E(f_1,\dots,f_n;\vec z)\)

Name: A function defined by \(\mathcal E\)
Definition: A function \(f\) such that, if \(f_1\) is interpreted as \(f\), then for each \(f_2,\dots,f_n\) for all \(\vec z\), \(\mathcal E(f,f_2,\dots,f_n;\vec z)\)
Page: 33
Section: 2
Variables: \(f_1,\dots,f_n\) functions
\(\vec z\) a set of vectors
\(\mathcal {E=E}(f_1,\dots,f_n;\vec z)\)
Context: Recursion theory
Index: 1
Kind: Def
Assuming: This function is unique

Name: A function definable by a system of equation
Definition: The function defined by some system of equation \(\mathcal E\)
Page: 33
Section: 2
Context: Recursion theory
Index: 1
Kind: Def