Transcript Twierdzenbie Trachtenbrota

Trachtenbrot’s Theorem
The following problem is undecidable
Given: A sentence 𝜑 of first order
logic
Question: Is 𝜑 satisfiable in a finite
structure?
Theorem of Matyasevich
The following problem is undecidable
Given: A polynomial 𝑊 𝑛1 , 𝑛2 , … , 𝑛𝑘 of
multiple natural varibales and integer
coefficients
Ques: Does 𝑊 have a zero, i.e., do there exist
natural numbers 𝑛1 , 𝑛2 , … , 𝑛𝑘
such that 𝑊 𝑛1 , 𝑛2 , … , 𝑛𝑘 = 0?
Proof:
Reduction of Hilbert’s 10th problem to the
problem is a given first order sentence is
satisfiable in the finite.
The form of Hilbert’s problem:
Given: Two multivariate polynomials 𝑊1 , 𝑊2 of
degree 𝑟 with all coefficients equal 1.
Question: Does the equation 𝑊1 = 𝑊2 have a
natural solution?
Reduction
• For each variable 𝑛𝑖 in the equation we create
a unary relation symbol 𝑁𝑖
For each monomial
𝛼𝑖 = 𝑛1
𝑎1
⋅ … ⋅ 𝑛𝑘
𝑎𝑘
we use:
–A constant 𝑐𝑖
–An 𝑟 + 1-ary relation symbol 𝐴𝑖
A sentence 𝜑𝑖 corresponding to 𝛼𝑖
∀𝑥0 𝑥1 … 𝑥𝑟 [𝐴𝑖 (𝑥0 , 𝑥1 , … , 𝑥𝑟 ) ↔
(𝑁1 𝑥1 ∧ … ∧ 𝑁1 𝑥𝑎1 ∧
𝑁2 𝑥𝑎1 +1 ∧ … ∧ 𝑁2 𝑥𝑎1 +𝑎2 ∧
…
𝑁𝑘 𝑥∑𝑎𝑖 −𝑎𝑘 +1 ∧ … ∧ 𝑁𝑘 𝑥∑𝑎𝑖 ∧
𝑥1+∑𝑎𝑖 = 𝑐𝑖 ∧
…
𝑥𝑟 = 𝑐𝑖 ∧
𝑥0 = 𝑐𝑖 )]
That sentence enforces
𝑎1
𝐴𝑖 = |𝑁1 |
𝑎𝑘
⋅ … ⋅ |𝑁𝑘 |
And additionally the relation 𝐴𝑖
contains only tuples beginning with 𝑐𝑖 .
We add a 2𝑟 + 2-ary relation
symbol 𝐵 and a sentence β
𝑐𝑖 ≠ 𝑐𝑗 ∧
𝑖≠𝑗
𝜑1 ∧ 𝜑2 ∧ ⋯ 𝜑𝑠 ∧
"𝐵 is a 1-1 mapping
From the set of all tuples in relations 𝐴𝑗 related to 𝑊1
Onto the set of all tuples in relations 𝐴𝑗 related to 𝑊2 "