\(\Sigma^ n_ 0\)-equivalence relations (Q793716): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: On the relation provable equivalence and on partitions in effectively inseparable sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Classifying positive equivalence relations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Positive equivalences / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4146722 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The relation of <i>A</i> to Prov ˹<i>A</i>˺ in the Lindenbaum sentence algebra / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5573961 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3967526 / rank
 
Normal rank

Latest revision as of 11:53, 14 June 2024

scientific article
Language Label Description Also known as
English
\(\Sigma^ n_ 0\)-equivalence relations
scientific article

    Statements

    \(\Sigma^ n_ 0\)-equivalence relations (English)
    0 references
    0 references
    1982
    0 references
    This paper deals with the reducibility pre-order \(\leq_ m\) ranging over equivalence relations on the set of natural numbers, where \({\mathcal R}\leq_ m{\mathcal S}\) if there exists a recursive function f such that, for all x, y: x \({\mathcal R} y\) if and only if f(x) \({\mathcal S} f(y)\). For \(n\geq 1\), \(\Sigma^ 0_ n\)-precomplete equivalence relations are introduced (generalizing a notion due to Ershov). It is shown that every \(\Sigma^ 0_ n\)-precomplete \(\Sigma^ 0_ n\)-equivalence relation is complete with respect of \(\leq_ m\) restricted to \(\Sigma^ 0_ n\)-equivalence relations. Several additional features of \(\Sigma^ 0_ n\)-precomplete equivalence relations are discussed. A representation theorem is also proved: Let T be an r.e. consistent theory which satisfies specific requirements (e.g. T is Peano arithmetic) and for \(n\geq 1\) let \(T^ n\) denote the theory obtained by adding as axioms all \(\Pi_{n-1}\) true sentences; then for every \(\Sigma^ 0_ n\)-equivalence relation \({\mathcal R}\) there is a \(\Sigma_ n\) formula F of T such that for all x, y: x \({\mathcal R} y\) iff \(T^ n\vdash F(\bar x)\leftrightarrow F(\bar y).\)
    0 references
    reducibility pre-order
    0 references
    precomplete equivalence relations
    0 references

    Identifiers