Difference between revisions of "Complexity and classification of countable models"

From Peano's Parlour
Jump to: navigation, search
Line 1: Line 1:
 
== Borel classification questions ==
 
== Borel classification questions ==
  
Let $T$ be a completion of $PA$. It is not hard to see that the isomorphism problem for finitely generated models of $T$, $\cong^{fg}_T$, is Borel.
+
This question is about the complexity of the classification problem for finitely generated models of a given completion $T$ of $PA$.
  
$\cong^{fg}_T$, is essentially countable and $E_0\leq_B \cong^{fg}_T$ i.e. $\cong^{fg}_T$ is not  smooth  <cite> coskeykossak2010:thecomplexity </cite>.  
+
Let us denote the space of finitely generated models of $T$ by $X^{fg}_T$.  (More precisely: if $A$ is a fixed countable set, then we can identify the set of models of $T$ whose underlying set is $A$ with a subset of $A^{A^6}$, where each model is represented by its addition and multiplication functions.)  Letting $\cong^{fg}_T$ denote the isomorphism relation on $X^{fg}_T$, it is not hard to see that $\cong^{fg}_T$ is Borel, considered as a subset of $X^{fg}_T\times X^{fg}_T$.
  
Problem: Is $\cong^{fg}_T$ hyperfinite? In other words, is $\cong^{fg}_T$ Borel reducible to $E_0$?
+
The complexity of $\cong^{fg}_T$ can be analyzed more closely using the concept of Borel reducibility.  Here, if $E,F$ are equivalence relations on standard Borel spaces $X,Y$, then $E$ is said to be Borel reducible to $F$ iff there is a Borel function $f\colon X\to Y$ such that
 +
\[x\mathrel{E}x'\iff f(x)\mathrel{F}f(x')\]
 +
 
 +
It was shown in <cite> coskeykossak2010:thecomplexity </cite> that $\cong^{fg}_T$ is Borel reducible to $E_\infty$, the universal countable equivalence relation.  It was furthermore shown that $E_0$, the almost equality relation on the set of infinite binary sequences, is Borel reducible to $\cong^{fg}_T$.
 +
 
 +
'''Problem''': What is the precise complexity of $\cong^{fg}_T$?  There is a wide gap between $E_0$ and $E_\infty$.  Is $\cong^{fg}_T$ bireducible with $E_\infty$?  Is $\cong^{fg}_T$ bireducible with $E_0$?
  
 
{{References}}
 
{{References}}

Revision as of 10:26, 4 February 2013

Borel classification questions

This question is about the complexity of the classification problem for finitely generated models of a given completion $T$ of $PA$.

Let us denote the space of finitely generated models of $T$ by $X^{fg}_T$. (More precisely: if $A$ is a fixed countable set, then we can identify the set of models of $T$ whose underlying set is $A$ with a subset of $A^{A^6}$, where each model is represented by its addition and multiplication functions.) Letting $\cong^{fg}_T$ denote the isomorphism relation on $X^{fg}_T$, it is not hard to see that $\cong^{fg}_T$ is Borel, considered as a subset of $X^{fg}_T\times X^{fg}_T$.

The complexity of $\cong^{fg}_T$ can be analyzed more closely using the concept of Borel reducibility. Here, if $E,F$ are equivalence relations on standard Borel spaces $X,Y$, then $E$ is said to be Borel reducible to $F$ iff there is a Borel function $f\colon X\to Y$ such that \[x\mathrel{E}x'\iff f(x)\mathrel{F}f(x')\]

It was shown in [1] that $\cong^{fg}_T$ is Borel reducible to $E_\infty$, the universal countable equivalence relation. It was furthermore shown that $E_0$, the almost equality relation on the set of infinite binary sequences, is Borel reducible to $\cong^{fg}_T$.

Problem: What is the precise complexity of $\cong^{fg}_T$? There is a wide gap between $E_0$ and $E_\infty$. Is $\cong^{fg}_T$ bireducible with $E_\infty$? Is $\cong^{fg}_T$ bireducible with $E_0$?

References

  1. Samuel Coskey and Roman Kossak. The complexity of classification problems for models of arithmetic. Bull. Symbolic Logic 16(3):345--358, 2010. www   MR   bibtex
Main library