Friedberg splittings in Σ₃⁰ quotient lattices of

Extract

Let {W_e}_e∈ω be a standard enumeration of the recursively enumerable (r.e.) subsets of ω = {0,1,2,…}. The lattice of recursively enumerable sets, , is the structure ({W_e}_e∈ω,∪,∩). ≡ is a congruence relation on if ≡ is an equivalence relation on and if for all U, U′ ∈ and V, V′ ∈ , if U ≡ U′ and V ≡ V′, then U ∪ V ≡ U′ ∪ V′ and U ∩ V ≡ U′ ∩ V′. [U] = {V ∈ | V ≡ U} is the equivalence class of U. If ≡ is a congruence relation on , the elements of the quotient lattice / ≡ are the equivalence classes of ≡. [U] ∪ [V] is defined as [U ∪ V], and [U] ∩ [V] is defined as [U ∩ V]. We say that a congruence relation ≡ on is if {(i, j)| W_i ≡ W_j} is . Define =* by putting W_i, =* W_j if and only if (W_i − W_j)∪ (W_j − W_i) is finite. Then =* is a congruence relation. If D is any set, then we can define a congruence relation by putting W_i W_j if and only if W_i ∩ D =* W_j ∩D. By Hammond [2], a congruence relation ≡ ⊇ =* is if and only if ≡ is equal to for some set D.

The Friedberg splitting theorem [1] asserts that if A is any recursively enumerable set, then there exist disjoint recursively enumerable sets A₀ and A₁ such that A = A₀∪ A₁ and such that for any recursively enumerable set B