Reducibilities
And other cool stuff
Co-hosted by Paul
Alien-Computability
• We saw A-computable, A-c.e. (given any set A: Alien) • 𝑃𝐴, 𝛟𝐴, 𝑊𝐴 (everything can be relativized)
𝑒𝑒𝑒
• We can have: A-Σ and A-Π (written as Σ𝐴 , Π𝐴 ) 𝑛𝑛𝑛𝑛
• A function 𝑓 is A-p.c. iff for some 𝑒 ∈ N, 𝑓 = 𝛟𝐴. 𝑒
We can say 𝑓 is A-p.c. via 𝛟𝑒
• A function 𝑓 is A-computable iff for some 𝑒 ∈ N, 𝑓 = 𝛟𝐴 and 𝛟𝐴 is
total. We also write 𝑓 ≤𝑇 𝐴. 𝑒 𝑒 • A set B is A-c.e. iff for some 𝑒 ∈ N, 𝐵 = 𝑊𝐴
𝑒
• A set B is A-computable iff 𝐼 is A-computable. We write 𝐵 ≤ 𝐴 𝐵𝑇
• We can also write 𝑓 ≤𝑇 𝑔 for functions f,g
Turing Degrees 𝓓
•If𝑆 ≤𝑇 𝐵and𝑆 ≥𝑇 𝐵,thenwewrite𝑆 ≡𝑇 𝐵andsaytheyare
Turing equivalent
• ≡𝑇 is an equivalence relation
• The equivalence classes are called Turing degrees • Also called degrees of unsolvability
Partial Order
• Let S be a set and R be a binary relation on S (i.e. 𝑅 ⊆ 𝑆 × 𝑆) R is said to be a partial order (non-strict) on S if:
1. ∀𝑎∈𝑆 𝑅𝑎,𝑎
2. ∀𝑎∈𝑆 ∀𝑏∈𝑆 𝑅 𝑎,𝑏 &𝑅(𝑏,𝑎)→𝑎=𝑏
3. ∀𝑎∈𝑆 ∀𝑏∈𝑆 ∀𝑐∈𝑆 𝑅 𝑎,𝑏 &𝑅 𝑏,𝑐 →𝑅 𝑎,𝑐
Total Order
4. ∀𝑎∈𝑆 ∀𝑏∈𝑆 𝑅𝑎,𝑏 𝑜𝑟𝑅(𝑏,𝑎) Every two elements are comparable
Every total order is a partial order, but not the converse
Examples
• Partial order: 𝑃(N) and the relation ⊆ • Total order: N and ≤
Structures
• A set equipped with relations and functions • (N, ≤) is a partial order structure
• We know also it is a total order structure
(𝓓, ≤)
• The set of Turing degrees can be equipped with a partial order
• This partial order is obtained by defining Turing reducibility on 𝓓 • Note that, so far ≤𝑇 is defined on 𝑃(N)
• Recall that, an element from 𝓓 is an equivalence class (set of sets) Thismakes𝓓⊆𝑃(𝑃 N )
Lifting ≤𝑇 to 𝓓
• For 𝐚, 𝐛 ∈ 𝓓, we write 𝐚 ≤ 𝐛 if:
forsome𝐴∈𝐚and𝐵∈𝐛wehave:𝐴≤𝑇 𝐵 • Is this well-defined?
Inotherwords,if𝐴≤𝑇 𝐵forsome𝐴∈𝐚and𝐵∈𝐛,doesthismean that𝐴≤𝑇 𝐵forall𝐴∈𝐚and𝐵∈𝐛?
• For the definition to make sense, you want the behavior of a degree to be the same as any of its sets
• One can show that (𝓓, ≤) is a partial order structure
• One can also show that it is NOT total order
• Note: I made a mistake last lecture when I said that (𝑃(N), ≤𝑇) is a partial order. Why?
• ≤𝑇 is a partial order on degrees, not on sets.
• (𝑃(N),≤𝑇) is just a preorder, also called quasiorder (reflexive and transitive binary relation)
Sad thing about Turing Reducibility
• It does not distinguish between C.e. sets and Co-c.e. sets
• This is because for any set A, A and its complement 𝐴ҧ are both of the
same Turing degree
• It is possible to have 𝐴 ≤𝑇 𝐵 where we can computably enumerate B but can’t enumerate A
m-reducibility: A stronger reducibility
• 𝐴 ≤𝑚 𝐵, A is many-one reducible to B if there is a computable
function f such that:
For all 𝑥 ∈ N, 𝑥 ∈ 𝐴 iff 𝑓(𝑥) ∈ 𝐵
• Again, ≤𝑚 is a preorder on 𝑃(N), which can induce an equivalence relation with equivalence classes called m-degrees
• If f is injective, we write 𝐴 ≤1 𝐵 and say A is 1-reducible to B
• ≤1 implies ≤𝑚 implies ≤𝑇
• Exercise: Find examples that the converse implications fail •If𝐶≤𝑚 𝐵and𝐵isA-c.e.,thenCisalsoA-c.e.
•If𝐵∈Σ𝐴(orΠ𝐴),and𝐶≤ 𝐵,then𝐶∈Σ𝐴(orΠ𝐴) 𝑛𝑛𝑚𝑛𝑛
Break
How many elements in 𝓓 ?
Example 1
•𝐾 ={𝑒,𝑥:𝜑(𝑥)↓}isinΣ 0𝑒1
•ForeveryAinΣ ,𝐴≤ 𝐾 1𝑚0
Indeed,weknowthat𝐴=𝑊 forsome𝑒∈N. 𝑒
Consider now the function f given by 𝑓 𝑥 = 𝑒, 𝑥 . Clearlyfiscomputable,and𝑥∈𝐴⟺𝑓 𝑥 ∈𝐾
• Note that f is also injective, and so 𝐴 ≤ 𝐾 10
0
C-complete
• The example we gave shows that the set 𝐾 is Σ -complete 01
• More generally, given a reducibility ≤𝑟 and a class of sets C, we say that a set B is C-complete w.r.t. ≤𝑟 if:
1. 𝐵∈𝐂
2. 𝐶≤𝑟 𝐵forevery𝐶∈𝐂
• If 1. isn’t happening, we say B is C-hard
• When we don’t specify the reducibility, we mean it is m-reducibility
Σ𝑛 -completeness (and Π𝑛 -completeness)
• When we say Σ𝑛 -complete, without a reducibility specified, we mean
with respect to 1-reducibility
• Equivalently in this case, m-reducibility
• ∅(𝑛) is Σ𝑛 -complete • ∅(𝑛) is Π𝑛 -complete
Examples 2
• Consider the set 𝐓𝐨𝐭 = {𝑒: 𝜑𝑒 is total} • 𝐓𝐨𝐭 is in Π2
•ForeveryAinΠ2 ,𝐴≤𝑚 𝐓𝐨𝐭
• This means that 𝐓𝐨𝐭 is Π2 -complete
Proof:
• A in Π2 means that there exists a computable relation R such that 𝑥∈𝐴⟺ ∀𝑦 ∃𝑧𝑅(𝑥,𝑦,𝑧)
• Consider the following function:
𝛾 𝑥,𝑢 =ቊ0 if ∀𝑦≤𝑢 ∃𝑧 𝑅(𝑥,𝑦,𝑧) ↑ 𝑜.𝑤.
•𝛾𝑥,𝑢 isclearlyp.c.
• There exists computable f such that 𝛾 𝑥, 𝑢 = 𝜑 (𝑢)
• This follows from the s-m-n theorem • Now observe the following:
𝑥 ∈ 𝐴 ⟹ 𝜑 is total 𝑓𝑥
𝑥 ∈ 𝐴ҧ ⟹ 𝜑 is NOT total 𝑓𝑥
𝑓𝑥
• This means that:
• Remark: f could be chosen injective
𝑥∈𝐴⟺𝑓𝑥 ∈𝐓𝐨𝐭
Q.E.D
Example 3
• Consider the set 𝐅𝐢𝐧 = {𝑒: 𝑊 is finite} 𝑒
• 𝐅𝐢𝐧 is Σ?
•Actually,𝐅𝐢𝐧isΣ? -complete
• Because in the proof of Example 2, we have that when 𝑥 ∈ 𝐴ҧ, the domain of 𝜑𝑓 𝑥 is finite
So, we have
• Let A be an arbitrary set from Σ2
•Then𝐴ҧ∈Π2 ,andsobytheproofofExample2,thereisa
computable (can be chosen injective) 𝑓 such that:
𝑥 ∈ 𝐴ҧ ⟹ 𝜑 is total ⟺ 𝑊 = N which is infinite 𝑓𝑥 𝑓𝑥
𝑥 ∈ 𝐴 ⟹ 𝑊 is finite 𝑓𝑥
•Inotherwords,𝑥∈𝐴⟺𝑓 𝑥 ∈𝐅𝐢𝐧
Facts:
• Bisc.e.inAiff𝐵≤1 𝐴′
• IfB≤𝑇 Athen𝐵′≤1 𝐴′
• A’ is c.e. in A
• IfBisc.e.inAthenBisc.e.in𝐴ҧ
• Σ∅(𝑚) = Σ
𝑛 𝑚+𝑛
Break
Some cool stuff: Kolmogorov Complexity
• Consider the following function: 𝐾 𝑥 = 𝜇𝑒(𝜑𝑒 0 = 𝑥)
• In some sense, this function gives the shortest program that can
output 𝑥
• This output can be regarded as the shortest description of the string
𝑔𝑛−1(𝑥)
• We say a string s is random, if 𝐾 𝑔𝑛(𝑠) ≥ 𝑔𝑛(𝑠)
Useful stuff
• Let A, B be two sets (very general)
• We denote the set of functions from A to B by 𝐵𝐴
• This notation is a cool connection with combinatorics. What is |𝐵𝐴|?
• 𝑃(𝐴) can be identified with {0,1}𝐴 (the set of characteristic functions of subsets of A)
•𝑃𝐴 =|0,1||𝐴|
Computability and real numbers
• A real number 𝑟 ∈ R is computable if when given any 𝑛 ∈ N one can compute a rational number 𝑞 ∈ Q such that 𝑟 − 𝑞 ≤ 2−𝑛
• R can be viewed as {0,1}N
• {0,1}N this is known as the Cantor space • The word space is related to topology
H10
After some experience
Remember H10 ?
• A set 𝐴 is Diophantine if there exists a polynomial 𝑃 (𝑥,𝑦 ,…,𝑦 )
such that
• A is clearly Σ1, i.e. C.E.
• Every set from Σ1 is Diophantine
• One can show that a set of positive integers is Diophantine iff it is the range of a polynomial function
𝑎∈𝐴⟺ ∃𝑦 … ∃𝑦 𝑃 𝑥,𝑦,…,𝑦 =0 1𝑛𝐴1𝑛
𝐴1𝑛
Simple examples of Diophantine sets
•≤={ 𝑥,𝑦 :(∃𝑧)𝑥+𝑧−𝑦=0}
• The set of prime numbers is the range of a polynomial function
• The record for the lowest degree of such a polynomial is 5 (with 42 variables)
• The record for fewest variables is 10 with degree about 1.6×104
The key result for H10
• The exponential function h 𝑥, 𝑦 = 𝑥 𝑦 is Diophantine. We mean by that
𝑥,𝑦,𝑧 :𝑥𝑦 =𝑧
is Diophantine
Open Problem
• Hilbert 10th over Q
• Lots of number theory, rings and fields stuff
Logic
Theories and Axioms
• You saw the partial order definition
• They form a set of sentences (logical formulas without free variables)
• Such a collection of sentences is called a theory
• A set of axioms is just a theory. Usually it is picked so they describe the basic facts about the theory without redundancy
• By describing basic facts I mean one can deduce the whole theory from the axioms by a proof
Proof system
• A list of formulas such that each formula is either an axiom, or comes from previous formulas by a rule of inference
• Example of a rule of inference: Modus ponens
𝑃 𝑃→𝑄 −−−− 𝑄
Logic: Theorems
• A theorem is a sentence that can be the end of a proof • A theorem is also called a consequence
• Example: Let PO denote the set of partial order axioms. We have
PO⊢ ∀𝑥 ∀𝑦 ∀𝑧 ∀𝑤 [𝑥≤𝑦&𝑦≤𝑧&𝑧≤𝑤→𝑥≤𝑤] (⊢ is the verb “proves”)
Theories and Computability
• A set Ax axiomatizes a theory T if every sentence in T is provable from Ax
• It is of interest sometimes to look for Ax which is computable, or c.e.
• Fact: The set of consequences (theorems) of a c.e. set of axioms is c.e.
• Craig’s Theorem: A c.e. theory has a computable set of axioms (primitive recursive actually)
Consistency
• A theory is consistent if it has a model
• Examples: The structure (N, ≤) ⊨ PO (⊨ is the verb “models”)
(𝓓, ≤𝑇) ⊨ PO
• A theory T is inconsistent if it can prove a sentence and its negations
T ⊢ 𝜑&¬𝜑
• This also means that for any sentence 𝜑, T ⊢ 𝜑
Soundness
• Suppose you have a theory T and a sentence 𝜑 such that T ⊢ 𝜑 • Soundness of the proof system means that for every model M,
𝑀⊨ T ⟹ 𝑀⊨ 𝜑
• The last line is usually abbreviated as T ⊨ 𝜑 (semantic implication)
• So basically, soundness of a proof system is: If T ⊢ 𝜑 then T ⊨ 𝜑
Completeness
• Completeness of a proof system is: If T ⊨ 𝜑 then T ⊢ 𝜑
• Gödel completeness theorem: For any first order theory T, and any
sentence 𝜑 (in the language of the theory): If T ⊨ 𝜑 then T ⊢ 𝜑
• A theory T is complete if for every sentence 𝜑 its language, either T ⊢ 𝜑 or T ⊢ ¬𝜑
Axiom Independence
• Suppose you have a consistent list of axioms A1,A2,A3,A4
• What does it mean that, say, A2 is independent from the rest? • This means {A1,A3,A4} ⊬ A2
• This also means that: There is a model M1⊨ {A1,A2,A3,A4} and there is also a model M2 ⊨ {A1,¬A2,A3,A4}
Example
A1: ∀𝑎 𝑅𝑎,𝑎
A2: ∀𝑎 ∀𝑏 𝑅𝑎,𝑏&𝑅(𝑏,𝑎)→𝑎=𝑏
A3: ∀𝑎 ∀𝑏 ∀𝑐 𝑅𝑎,𝑏 &𝑅𝑏,𝑐 →𝑅𝑎,𝑐
• PO = {A1,A2,A3}, Pre = {A1,A3}
• A2 is independent of A1, A3 because
(𝓓, ≤𝑇 ) ⊨ {A1,A2,A3} and (𝑃(N), ≤𝑇 ) ⊨ {A1,¬A2,A3}
• Pre is clearly an example of an incomplete theory since Pre⊬A2andPre⊬¬A2
Theory of Arithmetic
• The theory Th(N) of all the facts about the structure of natural numbers is LIFE
• Naturally there is a desire to capture it through a manageable set of axioms
• By manageable I mean finite, or just computable
• By capture I mean axiomatize
• Sadly, this isn’t possible (Gödel’s Incompleteness Theorem)
Gödel’s First Incompleteness
• Within the language of PA, Gödel used his numbering tricks to make sentences speak about themselves (self reference)
• The idea is to create a formula 𝑃(𝑥, 𝑦) using 0,+,x,(,),s,→,¬, … such that y is the Gödel number of a proof in PA of the sentence whose Gödel number is x
• Look now at this sentence: ¬∃𝑦𝑃(𝑒, 𝑦) where 𝑒 = 𝑔𝑛(¬∃𝑦𝑃 𝑒, 𝑦 )
• It says e (myself), not provable
• We see (as outsiders) that it is true in the model N, 0, +,×, 𝑠
Gödel’s Second Incompleteness
• Gödel decided to play more with his numbering trick and created a sentence that speaks about PA (about the system from within the system)
• The sentence said: PA is consistent
• Consis(PA): ¬∃𝑦𝑃(𝑔𝑛(0 ≠ 0), 𝑦) (there is no proof of 0 ≠ 0)
• Then Gödel showed that: PA ⊬ Consis(PA)
• In other words, PA cannot prove its own consistency
Generalizability of the Incompleteness Theorems
• All those proofs of Gödel just required that the system is powerful enough to express arithmetic
• So, he was able to prove similar facts about, e.g., set theory •∅=0, ∅ =1, ∅, ∅ =2,…,𝑛={0,1,…,𝑛−1}
In philosophical terms
• A system which is powerful (powerful enough to describe arithmetic) does not have a computable list of axioms from which every fact could follow
• Imagine yourself creating a manageable (finite or computable) list of rules (laws) from which everything in your system of interest should follow.
• Unless your system is very weak, you can’t
Factory Analogy
• Imagine you have a factory that creates machines
• You want to create a machine which can test every machine in the
factory
• It can test everything except itself
• It might be able to test certain aspects of itself, but not all of itself without external interference
Camera analogy
• A camera can’t take a picture of itself
• Maybe with the aid of an external system of mirrors
Peano Arithmetic (example of axiomatization)
• The structure of natural numbers could be described (axiomatized) by the following set of axioms PA:
1. Natural numbers not empty
2. They can be built from a special number, call it 0, and a special function s (call it successor)
3. So, for every x, if x is a natural number, then s(x) is also a natural
4. For every x, s(x) is not 0
5. m=n iff s(m)=s(n)
6. If a = b, and a is natural, then b is natural
7. If0hasapropertyP,andforeveryn,ifnhasPthens(n)hasP,thenPappliesto all natural numbers
Structure of arithmetic
We have a structure Ɲ = N, 0, +,×, 𝑠 which satisfies: 1. ∀𝑥0≠𝑠𝑥
2. ∀𝑥∀𝑦 𝑠𝑥 =𝑠𝑦 →𝑥=𝑦
3. ∀𝑥0≠𝑠𝑥
4. For each formula 𝜑 𝑥, 𝑦ത in the language of Peano Arithmetic: ∀𝑦ത[𝜑 0,𝑦ത &∀𝑥 𝜑 𝑥,𝑦ത →𝜑 𝑠 𝑥 ,𝑦ത →∀𝑥𝜑 𝑥,𝑦ത ]
That last axiom is actually an axiom schema. It unfolds into an infinite set of axioms
+,x
• ∀𝑥 𝑥 + 0 = 𝑥
•∀𝑥∀𝑦 𝑥+𝑠 𝑦 →𝑠(𝑥+𝑦)