Title: Theory / Unimportant / Math / Logic / Model theory / Spectra and satisfiability for logics - Milchior
Tags: toBinaryRelation

Question: In which logic (how many quantifier, alternation, number of varible) can \(f(g(x))=y\) be expressed ?
Answer: \(\Sigma_1[f,g,x,y]\), \(\exists z. g(x)=z\land f(z)=y\)
Page: 4
Chapter: 2
Section: 1
Variables: \(f,g\) unary function symbols
\(x,y\) variables

Question: In which logic (how many quantifier, alternation, number of varible) can \(R(f(g(x)))\) be expressed ?
Answer: \(\Sigma^2_1[f,g,x,R]\), \(\exists y. g(x)=y\land (\exists x. g(y)=x\land R(x))\)
Page: 4
Chapter: 2
Section: 1
Variables: \(f,g\) unary function symbols
\(x\) a variable
\(R\) a unary relation
Index: 11
Kind: Lem

Question: In which logic (how many quantifier, alternation, number of varible) can \(x=0\) be expressed ?
Answer: \(\Pi^2_1[x]\), \(\forall y. y+1\ne x\)
Page: 4
Chapter: 2
Section: 1
Variables: \(x\) a variable
Index: 12
Kind: Lem

Question: In which logic (how many quantifier, alternation, number of varible) can \(x=c\) be expressed ?
Answer: \(\Pi^2_2[+1,x]\), \((\forall y. y+1= x\implies y=c-1)\land(\exists y. y+1=x)\)
Page: 4
Chapter: 2
Section: 1
Variables: \(x\) a variable\(c\in\mathbb Z\), not nul
Answer2: \(\Sigma^2_2[+1,x]\), \(\exists y. y+1=x\land y=c-1\)
Index: 12
Kind: Lem

Question: In which logic (how many quantifier, alternation, number of varible) can \(R(c)\) be expressed ?
Answer: \(\Pi^2_2[+1,x]\), \(\forall x.x=c\implies R(x)\)
Page: 5
Chapter: 2
Section: 1
Variables: \(R\) a predicate\(c\in\mathbb Z\), not nul
Answer2: \(\Sigma^2_2[+1,x]\), \(\exists x.x=c\implies R(x)\)
Index: 13
Kind: Lem

Smaller0: \(\mathcal V\) has two variables
Greater0: \(\exists\mathrm{MSO}\mathcal L[\mathcal V\cup\{+1\}]\) is undecidable over \(\mathbb N\)
Page: 5
Chapter: 2
Variables: \(\mathcal V\) a vocabulary
\(\mathcal L[\mathcal V]\) a logic
Index: 14
Kind: Lem
Smaller1: \(\mathcal L\) has universal and existential quantifiers
Construction: quantify a finite set \(M\), use \(+1\) to ensure it's an interval containing 0.
Smaller2: \(\exists\mathrm{MSO}\mathcal L[\mathcal V\cup\{+1\}]\) is finitely undecidable

Question: \(\mathrm{SP}(\exists x.\psi)\)
Answer: equals \(\psi\)
Page: 5
Chapter: 2
Variables: \(\psi\) a logical formula,
\(x\) a first-order variable
Index: 16
Kind: Lem

Question: \(\mathrm{SP}(\exists R.\psi)\)
Answer: equals \(\mathrm{SP}(\psi)\)
Page: 5
Chapter: 2
Variables: \(\psi\) a logical formula,
\(R\) a second-order variable
Index: 187
Kind: Lem

Name: \(\mathrm{SP}(\mathcal L[\mathcal V])\)
Page: 5
Section: 2
Index: 187
Variables: \(\mathcal V\) a vocabulary
\(\mathcal L[\mathcal V]\) a logic
Kind: Lem
Under: union/substraction of a finite set \(F\)
Condition: \(\mathcal V\) contains +1 and \(\mathcal L\) contains \(\Pi_2^2\)
Under2: union
Condition2: the union is finite
Under3: Addition of a constant

Question: \(\mathrm{SP}(\exists\mathrm{MSO}\Pi_2^2[+1,\times b])\) contains
Answer: the set of \(b\)-recognizable set of numbers
Page: 9
Chapter: 3
Section: 1
Answer2: The set of power of \(b\)

Question: \(\mathrm{SP}(\prod\mathrm{MSO}\Sigma_2^2[+1,\times b])\) contains
Answer: the set of \(b\)-recognizable set of numbers
Page: 9
Chapter: 3
Section: 1

Definition: \(g\)'s image is not co-finite
Page: 11
Chapter: 3
Section: 1
Context: Spectra
Notation: \(\mathbb I\)
Definition2: \(g(1)>1\)
Conjdef: The set of functions \(g:\mathbb N\to\mathbb N\) such that
Definition3: \(g\) is increasing

Page: 11
Definition: the equivalence relation containing \((n,g(n))\) for each integer \(n\)
Chapter: 3
Section: 1
Variables: \(g\in\mathbb I\)
Notation: \(\cong^g\)
Context: Spectra

Question: \(\mathrm{SP}(\prod\mathrm{MSO}\sum_2^2[+1,g])\) contains
Answer: encoding of runs of 2 counter-automata, using some increasing sequence encoding
Page: 11
Chapter: 3
Section: 1
Variables: \(g\in\mathbb I\)
Context: Spectra

Question: \(\mathrm{SP}(\Pi_2[+1,f])\) contains
Answer: the \(b\)-recognizable sets
Page: 16, 23
Chapter: 4
Section: 1.2, 2
Variables: \(f\) a uninterpreted unary function
Context: Spectra
Answer2: an encoding of run of 2-counter automata
Index: , 12
Kind: Theo