Title: Theory / Unimportant / Math / Logic / Spectra
Tags: fromMath mathToDef closed mathToSee examplesSwitchExample1 hasSeenConjDef

Name: The spectra of \(\phi\)
Definition: The set of finite cardinalities in which \(\phi\) has a model.
Page: 4
Chapter: 2
Variables: \(\tau\) a vocabulary
\(\phi\) a sentence in some logic with equality over \(\tau\).
Kind: Def
Abbreviation: \(\text{SPEC}(\phi)\)

Definition: \(\{\text{SPEC}(\phi)\mid \phi\text{ is a first-order formula}\}\)
Page: 4
Chapter: 2
Notation: \(\text{SPEC}\)
Kind: Def

Smaller0: \(\text{SPEC}(\phi)=\emptyset\)
Greater0: \(\phi\) is not finitely satisfiable
Page: 4
Chapter: 2
Variables: \(\phi\) a sentence in some logic with equality over a vocabulary \(\tau\).
Kind: Def
Smaller to greater: iff

Name: The class of spectra
Page: 4
Section: 2
Kind: Prop
Under: union
Under2: intersection
Under3: addition, multiplication

Name: Scholz’s Problem
Definition: Characterize the sets of natural numbers that are first order spectra.
Page: 6
Chapter: 2
Index: 1
Kind: Open Question

Name: Asser’s Problem
Definition: Is the complement of a first order spectrum a first order spectrum?
Page: 6
Chapter: 2
Kind: Open Question

Name: The characteristict function of \(M\)
Definition: \(1\) if \(n\in M\), 0 otherwise.
Page: 9
Chapter: 3
Section: 1
Variables: \(M=\{m_1,m_2\dots,\}\) with \(m_i<m_{i+1}\)
\(n\in\mathbb N\)
Notation: \(\Xi_M(n)\)
Index: 1 (i)
Kind: Def

Name: The enumeration function of \(M\)
Definition: \(n\mapsto m_n\) if it exists, 0 otherwise.
Page: 9
Chapter: 3
Section: 1
Variables: \(M=\{m_1,m_2\dots,\}\) with \(m_i<m_{i+1}\)
\(n\in\mathbb N\)
Notation: \(\eta_M(n)\)
Index: 1 (ii)
Kind: Def

Name: The counting function of \(M\)
Definition: The number of elements in \(M\) strictly smaller than \(n\).
Page: 9
Chapter: 3
Section: 1
Variables: \(M=\{m_1,m_2\dots,\}\) with \(m_i<m_{i+1}\)
\(n\in\mathbb N\)
Notation: \(\gamma_M(n)\)
Index: 1 (iii)
Kind: Def

Q: [...] is [...].
A: A gap of \(M\); a pair \(g_1,g_2\in M\) such that \(g_1<n<g_2\) implies \(n\not\in M\)
Page: 9
Chapter: 3
Section: 1
Variables: \(M=\{m_1,m_2\dots,\}\) with \(m_i<m_{i+1}\) and \(n\in\mathbb N\)
Index: 1 (iv)
Kind: Def

Definition: The length of the \(n-\)th gap of \(M\), i.e. \(\eta_M(n+1)-\eta_M(n)\).
Page: 9
Chapter: 3
Section: 1
Variables: \(M=\{m_1,m_2\dots,\}\) with \(m_i<m_{i+1}\)
\(n\in\mathbb N\)
Notation: \(\delta_M(n)\)
Index: 1 (iv)
Kind: Def

Question: There is a formula \(\phi\) such that
Answer: \(\delta_\phi(n)\ge f(n)\).
Page: 513
Chapter: 3
Section: 1
Variables: \(f\) recursive monotically increasing
Index: 2
Kind: Prop

Definition: The number of ways one can interpret the relations symbols of \(\tau\) on the universe \([n]\) such that the resulting structure is in \(\mathcal C\).
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary, \(\mathcal C\) a class of finite \(\tau\)-structures.
Notation: \(f_{\mathcal C}(n)\)
Index: 4(i)
Kind: Def

Definition: The number of labelled \(\tau\)-structures of size \(n\).
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary.
Notation: \(Str(\tau)(n)\)
Index: 4 (ii)
Kind: Def

Name: \(prob_{\mathcal C}(n)\)
Definition: \(\frac{f_{\mathcal C}(n) }{Str(\tau)(n)}\); the probability that a labeled \(\tau\)-structure of size \(n\) is in \(\mathcal C\).
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary, \(\mathcal C\) a class of finite \(\tau\)-structures.
Index: 4 (ii)
Kind: Def

Definition: The number of non-isomorphic models in \(\mathcal C\) of size \(n\).
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary
\(\mathcal C\) a class of finite \(\tau\)-structures.
Notation: \(f^{iso}_{\mathcal C}(n)\)
Index: 4 (iii)
Kind: Def

Definition: The number of non-\(E\)-equivalent models in \(\mathcal C\) of size \(n\).
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary,
\(\mathcal C\) a class of finite \(\tau\)-structures
\(E\) an equivalence relation on \(\mathcal C\).
Notation: \(f^{E}_{\mathcal C}(n)\)
Index: 4 (iv)
Kind: Def

Definition: \(f^{E}_{\mathcal C}(n)\) where \(E\) is the \(k\)-equivalence from Ehrenfeucht-Fraı̈ssé games.
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary, \(\mathcal C\) a class of finite \(\tau\)-structures and \(k\in\mathbb N\).
Notation: \(N_{\mathcal C,k}(n)\)
Index: 4 (v)
Kind: Def

Definition: \(f_{\mathcal C}(n)\) for \(\mathcal C\) the set of structures satisfying \(\phi\).
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary, \(\phi\) a sentence
Notation: \(f_\phi(n)\)
Index: 4 (vi)
Kind: Def

Question: \(\lim_{n\to\infty}prob_\phi(n)\)
Answer: is either 0 or 1.
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary
\(\phi\) a \(\tau\)-sentence
Index: 5
Kind: Theo
Assuming: \(\tau\) is purely relational
Name: 0-1 Laws

Name: A categorical \(\tau\)-sentence
Definition: A \(\tau\)-sentence \(\phi\) such that \(f^{iso}_{\phi}(n)\le1\).
Page: 515
Chapter: 3
Variables: \(\tau\) a vocabulary

It is undecidable whether \(SPEC(\phi)\) is:
-finite/cofinite,
-ultimately periodic,
-\(a+b\mathbb N\) for some \(a,b\) fixed,
-\(S\) for some set \(S\).
Page: 516
Chapter: 3
Index: 6
Kind: Prop

Definition: \(a+\sum_{n}\Xi_{\phi}(n)2^{-n}\).
Page: 517
Chapter: 3
Section: 5
Variables: \(\phi\) a sentence
\(a\in\mathbb Z\)
Notation: \(r_\phi\)
Index: 7
Kind: Def

Name: A first order spectral real number
Definition: A spectral number of the form \(r_\phi\).
Page: 517
Chapter: 3
Section: 5
Index: 7
Kind: Def

Name: First order spectral real number with one function symbol only
Page: 517
Chapter: 3
Section: 5
Index: 8
Kind: Prop
Example: Rational numbers.

Name: The set of spectral reals
Page: 519
Section: 5
Chapter: 3
Index: 11
Kind: Cor
Not: not
Under: addition
Under2: multiplication

Name: Automatic real number
Definition: A real in \((0,1)\) such that the \(n-\)th bit of its binary expansion can be generated by a finite automaton from the binary representation of \(n\).
Page: 519
Chapter: 3
Section: 5

Name: The class of elementary functions
Definition: The smallest class of functions \(\mathbb N^d\to\mathbb N\),
-containing:
--zero,
--successor,
--projection,
--addition,
--multiplication,
--modified substraction
-and closed under:
--composition
--bounded sum
--product.
Page: 520
Chapter: 4
Section: 1
Notation: \(\mathcal E\)

Definition: The class of relations whose characteristict function is elementary.
Page: 520
Chapter: 4
Section: 1
Notation: \(\mathcal E_\star\)

Name: The function defined from \(g,h\) by primitive recursion
Definition: The function \(f\) sending \((0,\vec x)\) to \(g(\vec x)\) and \((n+1,\vec x)\) to \(h(n,\vec x,f(n,\vec x))\).
Page: 520
Chapter: 4
Section: 1
Variables: \(g,h\)

Name: The class of primitive recursive function
Definition: The smallest class of functions
-containing:
--the zero function,
--successor function,
--projection functions
-closed under
--componisition and
--primitive recursion.
Page: 520
Chapter: 4
Section: 1
Abbreviation: \(\mathcal PR\)

Name: A function defined by bounded recursion
Definition: A function bounded by recursion, which is bounded by another function.
Page: 520
Chapter: 4
Section: 1
Index: 3
Kind: Def

Name: Ackermann's function
Definition: \((0,y)\mapsto y+1\)
Page: 520
Chapter: 4
Section: 1
Definition2: \((x+1,0)\mapsto f(x,1)\) and
Conjdef: The function \(f\) recursively defined by sending:
Definition3: \((x+1,y+1)\mapsto f(x,f(x+1,y))\).
Abbreviation: \(Ack(x,y)\)

Definition: Let \(M\) the spectrum of \(\phi\).
\(\Xi_M\), \(\eta_M\), \(\gamma_M\), \(\delta_M\).
Page: 512
Chapter: 3
Section: 1
Variables: A sentence \(\phi\).
Notation: \(\Xi_\phi\), \(\eta_\phi\), \(\gamma_\phi\), \(\delta_\phi\)
Index: 1 (v)
Kind: Def

Smaller0: \(\tau\) is purely relational
Greater0: the language of sentences \(\phi\) such that \(\lim_{n\to\infty}prob_\phi(n)=1\)
Page: 514
Chapter: 3
Variables: \(\tau\) a vocabulary
Index: 5 (ii)
Kind: Theo
Hide middle: yes
Name: 0-1 Laws
Greater1: PSPACE-complete
Connect Greater0: is