Rekurzivně neoddělitelné sady - Recursively inseparable sets

v teorie vypočítatelnosti se nazývají dvě disjunktní množiny přirozených čísel rekurzivně neoddělitelné pokud je nelze „oddělit“ pomocí a rekurzivní množina.^[1] Tyto sady vznikají při studiu samotné teorie vypočítatelnosti, zejména ve vztahu k Π⁰
₁ třídy. Rekurzivně neoddělitelné množiny také vznikají při studiu Gödelova věta o neúplnosti.

Definice

Přirozená čísla jsou množina ω = {0, 1, 2, ...}. Vzhledem k nesouvislým podmnožinám A a B ω, a oddělovací sada C je podmnožina ω taková, že A ⊆ C a B ∩ C = ∅ (nebo ekvivalentně, A ⊆ C a B ⊆ C). Například, A sám o sobě je oddělovací sadou pro tento pár ω B.

Pokud pár disjunktních sad A a B nemá žádnou rekurzivní oddělovací sadu, pak jsou dvě sady rekurzivně neoddělitelné.

Příklady

Li A je pak nerekurzivní množina A a jeho doplněk jsou rekurzivně neoddělitelné. Existuje však mnoho příkladů sad A a B které jsou disjunktní, nekomplementární a rekurzivně neoddělitelné. Navíc je možné pro A a B být rekurzivně neoddělitelné, disjunktní a rekurzivně spočetné.

• Nechť φ je standardní indexování částečné vypočítatelné funkce. Pak sady A = {E : φ_E(0) = 0} a B = {E : φ_E(0) = 1} jsou rekurzivně neoddělitelné (William Gasarch 1998, s. 1047).
• Nechť # je standard Gödelovo číslování pro vzorce z Peano aritmetika. Pak sada A = {# (ψ): PA ⊢ ψ} prokazatelných vzorců a množiny B = {# (ψ): PA ⊢ ¬ψ} vyvratitelných vzorců je rekurzivně neoddělitelných. Neoddělitelnost sad prokazatelných a vyvratitelných vzorců platí pro mnoho dalších formálních teorií aritmetiky (Smullyan 1958).

Reference

• Cenzer, Douglas (1999), "Π⁰
  ₁ třídy v teorii vypočítatelnosti ", Příručka teorie vypočítatelnosti, Stud. Logika nalezena. Matematika., 140, Amsterdam: Severní Holandsko, s. 37–85, doi:10.1016 / S0049-237X (99) 80018-4, PAN  1720779
• Gasarch, William (1998), „Průzkum rekurzivní kombinatoriky“, Příručka rekurzivní matematiky, sv. 2, Stud. Logika nalezena. Matematika., 139, Amsterdam: Severní Holandsko, s. 1041–1176, doi:10.1016 / S0049-237X (98) 80049-9, PAN  1673598
• Monk, J. Donald (1976), Matematická logika„Postgraduální texty z matematiky, Berlín, New York: Springer-Verlag, ISBN  978-0-387-90170-1
• Smullyan, Raymond M. (1958), „Nerozhodnutelnost a rekurzivní neoddělitelnost“, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 4: 143–147, doi:10,1002 / malq.19580040705, ISSN  0044-3050, PAN  0099293