Computability and the Arithmetical Hierarchy

Leaky Nun

Jan 19, 2018 03:45

so we want to enquire about the natural numbers. We will use the logical operators "for all", "there exists", "and", "or", "not", "implies", as well as our operators on natural numbers +, *, <

user202729

... number theory again?

Leaky Nun

no, computability

user202729

Ok.

Leaky Nun

"n is even" will translate to "exists k, k+k=n"

so we can make all kind of questions about the natural numbers, including famous conjectures such as goldbach conjecture and Collatz conjecture

(the formulation of Collatz conjecture will be harder, as you would need to encode a sequence in a single number, but it is not impossible (see this challenge for an example))

user202729

Yes I suppose everyone had seen that answer.

Leaky Nun

Jan 19, 2018 03:49

so "for all" and "exists" are called quantifiers

and bounded quantifiers are of the form "for all n < m", "exists n < m", where m is something defined earlier in the context

so actually we can write "n is even" entirely with bounded operators: "exists k < n, k + k = n"

note that "n" is free in the sentence, i.e. not mentioned by any quantifiers before it, bounded or unbounded

we call such sentences 1-parameter sentences

now, we will introduce a sort of hierarchy to parametrized sentences (the number of parameters doesn't really matter, again see the link above for an encoding)

if a parametrized sentence is equivalent to one entirely with bounded quantifiers, then we say that it is a Δ0-sentence

if it is equivalent to a sentence that starts with unbounded "exists" followed by a parametrized Δ0-sentence, then the sentence is in Σ1.

if it is equivalent to a sentence that starts with unbounded "for all" followed by a parametrized Δ0-sentence, then the sentence is in Π1.

so Δ0 is a subset of Σ1, as well as Π1.

We call Δ1 the intersection of Σ1 and Π1.

A parametrized sentence is in Σ2 if it starts with unbounded "exists" quantifier and is followed by a parametrized Π1 sentence, i.e. it looks like "exists n1, exists n2, ..., for all m1, for all m2, ... [a Δ0 sentence]"

and the hierarchy continues onward

theorem: for a sentence φ, there is a program that proves φ or disproves φ, if and only if φ is in Δ1.

Heeby Jeeby Man

Do you mean ∑1 instead of ∏1?

Leaky Nun

where?

Heeby Jeeby Man

3 mins ago, by Leaky Nun

A parametrized sentence is in Σ2 if it starts with unbounded "exists" quantifier and is followed by a parametrized Π1 sentence, i.e. it looks like "exists n1, exists n2, ..., for all m1, for all m2, ... [a Δ0 sentence]"

Leaky Nun

no, because ∑1 would just be another bunch of "exists" quantifiers

maybe I should clarify that there can be more than one "exists" quantifiers in a row, and it doesn't affect the hierarchy

the same with "for all"

user202729

(because multiple integers can be represented as a integer)

Leaky Nun

Jan 19, 2018 04:03

precisely

Heeby Jeeby Man

Oh I see you are missing a s on the quantifier.

Leaky Nun

yes, sorry

Heeby Jeeby Man

Ok, I read that and then saw two exists (ignoring the elipse) and jumped to a conclusion.

Leaky Nun

let φ be Δ1. So, φ is equivalent to some sentence that begins with exists, and its negation is also equivalent to some sentence that begins with exists (negation of "for all x, P(x)" is "exists x, not P(x)")

so the program is simply to try substitute the variable quantified by 0, and then do the same on the negation, and then substitute 1, and then do the same on the negation, etc until either the sentence or its negation becomes "true"

for an example, let's forget for a moment that "n is even" is actually Δ0 (Δ0 is a subset of Δ1 anyway). Then, "n is even" can be written as "exists k, k+k=n", while its negation is "exists k, k+k+1=n".

So the program simply tries k=0 on the positive, k=0 on the negation, k=1 on the positive, k=1 on the negation, etc.

The other direction is harder to prove, and the proof involves essentially tracing what the program actually does and writing a sentence based on the program

Heeby Jeeby Man

Curry Howard correspondence?

Leaky Nun

Jan 19, 2018 04:18

@HeebyJeebyMan that's more like "proofs and programs correspond to each other"

Post's theorem.

more terms for reference:
if the defining parametrized sentence for a set of natural numbers is ∑1, then it is recursively enumerable, i.e. there is a turing machine that halts exactly on those numbers (and runs forever otherwise)
if it is Π1, i.e. its negation is ∑1, then it is co-recursively enumerable
if it is Δ1, then it is recursive

Classification of sentences:

- the four colour theorem (ignoring the fact that it is proved) is Π1.
- the fermat's last theorem (ignoring the fact that it is proved) is Π1.
- the Riemann Hypothesis is Π1.
- the twin prime conjecture is Π2.
- the Collatz conjecture is Π2.

note: some day maybe they will rank lower in the hierarchy. this is just up to our current knowledge.

here's the scary bit about arithmetical hierarchy: one can define a real number as an equivalence class of cauchy sequences of rational numbers (I will explain this later). Thus, let f and g be two cauchy sequences of rational numbers, i.e. a function from N to Q, which can also be a function from N to N. Assume that f and g are in Δ0. Then, the sentence "f and g represents the same real number" is actually Π3. It's even above most open conjectures.

conclusion: real number equality is super-undecidable

maybe I won't explain it, since it's more about the construction of real number, so it's more pure maths than CS

btw the sentence "f and g represent the same real number" is "for all rational epsilon > 0, exists natural N, for all natural n > N, |f(n) - g(n)| < epsilon"

Heeby Jeeby Man

Well shouldn't that make sense? I mean intuitively if we are defining real numbers with a Dedkind cut we would expect that determining the equality of two real numbers to be similar (but not identical) to determining if two unaccountably large sets are equivalent.

Leaky Nun

Jan 19, 2018 04:35

I think you get Π1 when using Dedekind cut, but I'm not sure

that's assuming the two numbers in question (two sets of rational numbers in equation) are recursive, i.e. Δ1.

Heeby Jeeby Man

I'm not sure if that is the case, but I don't know.

Leaky Nun

maybe the two sets can even be Δ0 (e.g. sqrt(2)), then still Π1 for Dedekind cut

p/q < sqrt(2) iff ((p < 0 and q > 0) or (p > 0 and q < 0) or (p*p < q*q + q*q))

Heeby Jeeby Man

I really don't think that is the case.

Leaky Nun

that looks Δ0 to me

Heeby Jeeby Man

Oh for that specific example yes

sorry I thought we were talking in general

Leaky Nun

Jan 19, 2018 04:39

3 mins ago, by Leaky Nun

that's assuming the two numbers in question (two sets of rational numbers in equation) are recursive, i.e. Δ1.

in general it doesn't work

we can only consider the real numbers that are actually in the hierarchy

Heeby Jeeby Man

Ok that would have been my suspicion

Leaky Nun

(there is only countably many Dedekind cuts that are in the hierarchy)

this is so horrifying

like we usually only use Π3 or below

Heeby Jeeby Man

Of course, because our statements are spanned by a finite grammar

Leaky Nun

but there are numbers that are not even Π100, not Π10000000000

and they are "real" numbers

The Nineteenth Byte

Participants