\(\Sigma^ n_ 0\)-equivalence relations (Q793716): Difference between revisions
From MaRDI portal
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
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