About the undecidability of first-order-logic

[olgerm]

I do not claim that First Order Logic is decidable, but following argument makes it hard for me understand why it is undecidable:

1. Every 1.-order-logic-formula is either contradictionary or consistent. Such 1.-order-logic-formula, which consistency would be impossible to determine does not exist.
2. Therefore it is possible to somehow determine consistency of any 1.-order-logic-formula .
3. This method of determining consistent of any 1.-order-logic-formula could be made to an algorithm.

Could anyone explain it to me?

I tried to read proof of "The Undecidability of First Order Logic" from http://kilby.stanford.edu/~rvg/154/handouts/fol.html, but I could not understand it.

 

[jedishrfu]

Perhaps you could point out in the Kilby proof where you don't understand the step or where you disagree with the step.

 

[olgerm]

Perhaps you could point out in the Kilby proof where you don't understand the step or where you disagree with the step.

There are very many things in this proof, that I do not understand. I do not know if it is even reasonable to ask about these, because it would take very long do understand all of these.

Do you completely understand this proof?
Does anyone here completely understand this proof?

 

[WWGD]

Do you accept Godel's Theorem? Edit; I believe most of Number Theory can be modeled using FOL, so that Godel would kick in.
Besides, isn't the Continuum Hypothesis definable within FOL?

 

[jedishrfu]

Sadly I don't know much about this or any proof in math except for the most basic of proofs. For the benefit of others if you started at the beginning of the proof and told us where you got stuck someone might be able to clarify the logic.

 

[WWGD]

Maybe @stevendaryl can help us here?

 

[fresh_42]

Would be an interesting experiment to discuss something on this one-level platform that has system inherent meta-levels in it. Who has the popcorn?

 

[WWGD]

Would be an interesting experiment to discuss something on this one-level platform that has system inherent meta-levels in it. Who has the popcorn?

I'll begin: Eh, I'm vegan, Walter!

 

[fresh_42]

I thought it is always a variation of Cantor's diagonalization argument, only with a more complicated alphabet.

 

[WWGD]

It seems once you can describe Number Theory, decidability breaks down. Would be nice to have a "Boundary Case" of a theory where decidability breaks down. Not with infinities involved, though. Something gets lost between Sentence Logic, where Truth Tables are enough, and FOL. I think Truth Trees may be a way of seeing why/how decidability breaks down.

 

[Jarvis323]

There are very many things in this proof, that I do not understand. I do not know if it is even reasonable to ask about these, because it would take very long do understand all of these.

Do you completely understand this proof?
Does anyone here completely understand this proof?

The methodology and jist of the proof are fairly simple, but the details of the proof involve understanding the formal definition of a Turing machine.

Here is a summary based on my understanding, if it helps.

The proof uses a technique called a reduction. This is a common proof technique in decidability theory. The way it works is you have one problem $A$ which is known to be undecidable, and prove that another problem $B$ is also undecidable by reducing $A$ to $B$. This means that if you could decide $B$ you could also decide $A$, which is a contradiction since $A$ is known to be undecidable. In the context of this thread, we can assume they are decision problems, i.e. an instance of the problem is like a yes or no question (e.g. an instance could be: is this specific formula in this logic valid).

The reduction works by specifying an algorithm $f$ which maps any problem instance $a$ of $A$ to an instance $b$ of $B$, such that $b$ is a yes instance of $B$ if an only if $a$ is a yes instance of $A$. If you've done that, then to decide $A$, just do something like,

decideA( a ) :
    return decideB( f(a) )

In this example, they chose $A$ as basically the problem of deciding if a given Turing machine $M$ gives a yes answer for a given input string $w$. E.g. imagine you are given a program and an input for the program, and are tasked with answering if the input leads to the program printing yes. This is a known undecidable problem.

Then they show how you can take any instance of $A$, which is a Turing machine and input, and from that construct a first order logic and formula (input to $B$, which is deciding if first order logic formulas are valid), such that if the formula is valid, then you know that the Turing machine would answer yes for input $w$, otherwise you know it wouldn't.

Note in the proof, the variables of the logic are defined as ranging over all strings in the alphabet (which you can intuitively think of as all possible sequences of characters). There are infinitely many values (strings) that they can take on. And the formula in the end is comprised of nested existence quantifiers, which basically imply a worst case brute force search problem in an infinite space, where the formula is valid if and only if there exists one of those infinitely many possibilities which satisfies the formula.

The proof doesn't give much intuition about why first order logic is undecidable. But I think you can basically just consider the issue that in the proof the formula depends on the existence of some values out of infinitely many possibilities, so you could keep searching forever without ever finding one that works, without knowing for sure that you won't eventually.

 

[nuuskur]

1. Every 1.-order-logic-formula is either contradictionary or consistent. Such 1.-order-logic-formula, which consistency would be impossible to determine does not exist.

A formula is either satisfiable (true in at least one interpretation) or contradictory (false in every interp.). Consistency is a characteristic of an entire theory. Roughly speaking, it means that if the axioms are assumed to be true, then they don't generate contradictory theorems.

1. Therefore it is possible to somehow determine consistency of any 1.-order-logic-formula .

There exists no universal machinery that determines satisfiability of every formula. This is implied by Church's theorem. Just as there is no general formula for solutions of higher order polynomial equations.

The proof in the notes shows that If such universal algorithm existed, then the halting problem would be decidable. But that is known to be false.

 

[SSequence]

Do you accept Godel's Theorem? Edit; I believe most of Number Theory can be modeled using FOL, so that Godel would kick in.
Besides, isn't the Continuum Hypothesis definable within FOL?

Yes, what you have said is pretty much correct I think. Some more points that I think are worth adding though:
(1) I believe what is most commonly called as "number theory" precisely corresponds to the questions [well-formed-formulas with definite truth values ... no open variables etc.] posed in a first order theory like PA. And Godel's theorems do apply to PA. So you are right about that.

(2) Regarding your second point CH, you are essentially right but I think adding some clarification might be useful. FOL by itself is quite a general term. When we talk about a specific FOL theory, such as traditional set theory, then CH is a well-posed question.
(as a separate point, note that every question of PA can also be posed in traditional set theory)Also, perhaps worth adding is that there are cases of decidable first-order theories. Few well-known ones that I have seen mentioned more often are:
(1) Presburger Arithmetic
The questions posed by it are a subset of PA.

(2) Euclidean Geometry
I am not sure (in a more precise sense) what people mean when they mention it. But I think it is probably something quite close to Euclid style proofs (which I think were later made more formalized).

(3) First-Order-Theory of Reals
Just mentioning it, but I don't have any idea about the kind of questions this theory poses.

 

[SSequence]

A formula is either satisfiable (true in at least one interpretation) or contradictory (false in every interp.). Consistency is a characteristic of an entire theory. Roughly speaking, it means that if the axioms are assumed to be true, then they don't generate contradictory theorems.

What you have written is correct but wouldn't there also be an added case for "theorems"?
(edit note: OK I see, the case of (1) and (3) below both fall under the case of "satisfiable")

(1) Those questions posed by a theory that are theorems (proved by theory as true). These are those true in every interpretation (model).
(2) Those questions posed by a theory proved by theory as false. These are those that are false in every interpretation (model).
(3) Those questions posed by a theory which it can't prove to be true/false (i.e. undecidable in the given theory). These are those that might be true in some interpretations and false in others.Edit:
I think another issue is that of soundness. As I understand (though I don't know the detailed working on it), a proof of undecidability that uses halting problem (instead of constructing the godel sentence) would normally go along these lines (PA used as a specific example):
"Suppose PA was decidable. Then given any machine or program of specific index, we can find an algorithm that takes as input the index and, as output, finds the corresponding sentence (in PA) that is true iff the given program halts . Hence PA is not decidable."

However, this kind of outline assumes that the theory is sound in its truth/falsity of number-theoretic statements w.r.t. the actual natural numbers [on the very least, those that are about halting]. If we only assume that the theory is consistent then the above outline wouldn't work.

It seems, apparently, that more generality is achieved with rosser sentence, but I don't know about the detail well enough. The link below seems relevant:
https://en.wikipedia.org/wiki/Rosser's_trick

 

[olgerm]

A formula is either satisfiable (true in at least one interpretation) or contradictory (false in every interp.). Consistency is a characteristic of an entire theory. Roughly speaking, it means that if the axioms are assumed to be true, then they don't generate contradictory theorems.

I think that using word "consistent" instead of "satisfiable" here would not be incorrect, but for better communication let's use "satisfiable" instead of "consistent".

There exists no universal machinery that determines satisfiability of every formula. This is implied by Church's theorem. Just as there is no general formula for solutions of higher order polynomial equations.

If such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist, then being given any 1.-order-logic-formula it must be possible to somehow determine satisfiability of it. Do you agree with that?

Such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist. Do you agree with that?

 

[SSequence]

The problem is that (for an undecidable theory) the machinery of the theory (based on the rules of inference of fol) does not determine the truth and falsity of every true/false sentence it poses.

 

[olgerm]

The problem is that (for an undecidable theory) the machinery of the theory (based on the rules of inference of fol) does not determine the truth and falsity of every true/false sentence it poses.

What do you call "machinery of the theory"? Is this term used somewhere else or you created it yourself?

 

[SSequence]

Regarding post#16, note that we are assuming the given theory to be consistent. Regarding the question in previous post, it isn't a fully formal term. There are two aspects how a specific theory (say first-order) would function:
(1) The theory would "formulate/pose some questions". This is informal terminology, but it def. has a precise meaning. These questions are (syntactically) well-formed-formulas [based upon predicates/functions/constants/domains of quantification etc. that the theory allows] which don't have any free variables. Usually these terms are fully well-defined in introductory/intermediate logic texts, but description of these requires some length.
(2) The theory has certain axioms (and sometimes "axiom schemata"), which I suppose in some sense can be thought of as primitive truths within the theory.Now when I wrote "machinery of the theory", I used it in a fairly informal sense. Nevertheless, what I meant was there are certain (very specific) rules of deduction that are specific to "fol". This is what we mean when we say that this theory proves or disproves such and such statement [the statements in point-(1)].

For a specific first-order-theory, the rules of deduction gives rise to certain statements that it proves(as true) and disproves(as false) [which is the same as the theory proving the negation of that statement as true]. Let's call the statements that the theory proves as true as the "theorems" of the given theory. Now I don't have good familiarity with the general notion of first-order-theories (so I don't talk about this generally), but when one takes specific theories such as PA, their theorems are computably enumerable (c.e.) [same is true for traditional set theory]. For example, it is highly likely that most statements that one would encounter in some introductory number theory book would be theorems of PA.

So what incompleteness (for a first-order-theory) means is the following:
"There are certain statements that a consistent first-order-theory poses, but can't prove or disprove."
When we write the "theory can't prove or disprove", the reference is to the specific rules of deduction given the axioms in point-(2) above [and the godel sentence in first-incompleteness theorem also refers to proveability in this specific sense]. Not all first-order-theories are incomplete (see post#13). However, many theories (if consistent) such as PA or traditional set theory are incomplete.

 

[olgerm]

A formula is either satisfiable (true in at least one interpretation) or contradictory (false in every interp.). Consistency is a characteristic of an entire theory. Roughly speaking, it means that if the axioms are assumed to be true, then they don't generate contradictory theorems.

You were correct "satisfiable" is the correct term here. I explain how I understand terms:
"1.-order-logic-formula" aka "1.-order-logic-statement": any claim between predicates, that can be expressed by using only quantifiers, fictive variables of quantifiers, predicates, boolean-operators(any functionally complete set boolean operator is sufficent) and braces is a "1.-order-logic-formula" aka "1.-order-logic-statement". For example

• $\exists_{x_1}(A(x_1))\land \neg \exists_{x_1}(A(x_1))$
• $\exists_{x_1}(\exists_{x_2}(A(x_1,x_2)\land \exists_{x_3}(A(x_2,x_3)\land A(x_2,x_2))))\land \neg \exists_{x_1}(\exists_{x_2}(\exists_{x_3}( A(x_2,x_1)\land A(x_1,x_3)\land A(x_1,x_1))))$
• $\exists_{x_1}(m(x_1) \land \neg\exists_{x_2}(M(x_1, x_2) \land \exists_{x_3}(M(x_1, x_3) \land \neg M(x_2, x_3) \land M(x_3, x_1)) \land \exists_{x_3}(M(x_1, x_3) \land M(x_2, x_3)) \land \neg \exists_{x_3}(M(x_2, x_3) \land M(x_3, x_3))))\land \exists_{x_1}(\exists_{x_2}(m(x_2)\land M(x_2,x_1)\land \exists_{x_3}(M(x_1,x_3)\land M(x_2,x_3))\land \exists_{x_3}(M(x_2,x_3)\land M(x_3,x_2)\land \neg M(x_1,x_3)))\land \neg \exists(M(x_2,x_1)\land M(x_2,x_2)))\lor\exists_{x_1}(M(x_1,x_1)\land \neg \exists_{x_2}(M(x_1,x_2)\land M(x_2,x_2)\land M(x_2,x_1)))$

are logical 1.-order-logic-formulas. These make different claims about predicates A, m and M.
"theory": Theory consist of a logic-formula and namespace. By namespace I mean that variables with same name mean always same thing in context of the same theory, but variables with same name may mean different thing in contexts of different theories.
"axiom": some specific consistent logic-formulas are named and called axioms. Which one are called so and how these are named is historic and arbitrary.
"satisfiable": A 1.-order-logic-statement is satisfiable if it can not be simplified to False without knowing anything about the predicates, that it contains. Also a 1.-order-logic-statement is satisfiable if the 2.-order-logic-formula, that is obtained by replacing all predicates in it with fictive variables of existential quantifiers, that are put around the 1.-order-logic-statement, is not false. Note, that since this 2.-order-logic-formula does not contain any predicates it can be only True or False. For example:

• $\exists_{x_1}(\exists_{x_2}(A(x_1,x_2)\land \exists_{x_3}(A(x_2,x_3))))\land \neg \exists_{x_1}(A(x_1,x_1) \lor \exists_{x_2}(A(1,2)\land A(2,1)))$ is satisfiable because $\exists_{x_1}(is\_booleanfunction(x_1) \land ( \exists_{x_2}(\exists_{x_3}(x_1(x_2,x_3)\land \exists_{x_4}(x_1(x_3,x_4))))\land \neg \exists_{x_2}(x_1(x_2,x_2) \lor \exists_{x_3}(x_1(x_2,x_3)\land x_1(x_3,x_2))))$ is not false but true.
• $\exists_{x_1}(\exists_{x_2}(A(x_1,x_2)\land \exists_{x_3}(A(x_2,x_3)\land A(x_2,x_2))))\land \neg \exists_{x_1}(\exists_{x_2}(\exists_{x_3}( A(x_2,x_1)\land A(x_1,x_3)\land A(x_1,x_1))))$ is not satisfiable because $\exists_{x_1}(is\_booleanfunction(x_1) \land \exists_{x_2}(\exists_{x_3}(x_1(x_2,x_3)\land \exists_{x_4}(x_1(x_3,x_4)\land x_1(x_3,x_3))))\land \neg \exists_{x_2}(\exists_{x_3}(\exists_{x_4}(x_1(x_3,x_2)\land x_1(x_2,x_4)\land x_1(x_2,x_2)))))$ is false.

"consistent": A 1.-order-logic-statement is consistent if it can not be simplified to False even with using "outside information" about the predicates, that it contains. For example:

• formula $\exists_{x_1} (\neg \exists_{x_2} (is\_bigger\_than(x_1,x_2) \land is\_real-number(x_1) \land is\_real-number(x_2)))$ claims that there is a real number x_1 so that there were no other real-number x_2, that were bigger than it. This formula is satisfiable because it can not be simplified to False without having any "outer information" about real-numbers, but not consistent because it can be simplified to False by having some outer information about real numbers.

I know this is the "official" terminology but to me it seems unintuitive and misleading. It would more intuitive to call
satisfiable statements consistent statements
unsatisfiable statements inconsistent statements
and
inconsistent statements false statements.

If such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist, then being given any 1.-order-logic-formula it must be possible to somehow determine satisfiability of it. Do you agree with that?

Such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist. Do you agree with that?

@nuuskur , do you agree with these statements or not?

 

[olgerm]

Regarding post#16, note that we are assuming the given theory to be consistent. Regarding the question in previous post, it isn't a fully formal term. There are two aspects how a specific theory (say first-order) would function:
(1) The theory would "formulate/pose some questions". This is informal terminology, but it def. has a precise meaning. These questions are (syntactically) well-formed-formulas [based upon predicates/functions/constants/domains of quantification etc. that the theory allows] which don't have any free variables. Usually these terms are fully well-defined in introductory/intermediate logic texts, but description of these requires some length.

No, I think a theory does not pose questions.

(2) The theory has certain axioms (and sometimes "axiom schemata"), which I suppose in some sense can be thought of as primitive truths within the theory.

Theory only makes some claims about some predicates (or constant-symbols) and has some namespace assosiated with it, that determines how are which things named in context of this theory. The claim about predicates can be divided to different number of different axioms, which are logically conjuncated with each other. So to describe the theory it is not reasonable to talk about axioms, but about a single logic-statement from which all the axioms of the theory can be derived.

So what incompleteness (for a first-order-theory) means is the following:
"There are certain statements that a consistent first-order-theory poses, but can't prove or disprove."
When we write the "theory can't prove or disprove", the reference is to the specific rules of deduction given the axioms in point-(2) above [and the godel sentence in first-incompleteness theorem also refers to proveability in this specific sense]. Not all first-order-theories are incomplete (see post#13). However, many theories (if consistent) such as PA or traditional set theory are incomplete.

I did not ask about incompleteness, but wether it is decidable if any given 1.-order-logic-formula is satisfiable or not(aka if it is possible to make an algorithm that takes any 1.-order-logic-formula as argument and returns if is satisfiable or not).

 

[nuuskur]

I know this is the "official" terminology but to me it seems unintuitive and misleading. It would more intuitive to call
satisfiable statements consistent statements

You can regard them as synonyms in model theoretic sense. A theory is satisfiable (i.e has a model) if and only if the theory is consistent (i.e does not prove "False").

If such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist, then being given any 1.-order-logic-formula it must be possible to somehow determine satisfiability of it. Do you agree with that?

This is a tautology.

Such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist. Do you agree with that?

A set of FOL formulae is called a theory. Any formula is a theory as a singleton. Any member of a given theory is also called a theorem of that theory.

If a theory has finite models, then it's possible to check them in finite time and return "yes" or "no" for satisfiability. There exist theories in FOL with only infinite models. In fact, most of them have (only) infinite models. How to check all possible infinite models in finite time? Not going to happen.

 

[Jarvis323]

Just like to add consistency is undecidable. Specifically it is co-RE meaning if the theory is inconsistent then you can eventially find an inconsistency, but you can't rule out that an inconsistency exists. It is not knowable, for example, if ZFC is inconsistent or not except in the case someone finds an inconsistency.

In FOL theories, satisfiability is equivalent to consistency. This is something new I learned. It means that like consistency deciding satisfiablity of FOL theories is co-RE, and so there is a general algorithm which can prove a theory is not satisfiable, but not a general algorithm that can prove a theory is satisfiable.

 

[SSequence]

I did not ask about incompleteness, but wether it is decidable if any given 1.-order-logic-formula is satisfiable or not(aka if it is possible to make an algorithm that takes any 1.-order-logic-formula as argument and returns if is satisfiable or not).

Consistency is assumed below through-out. I don't know about the general scenario, but I think for traditional set theory (as in ZF+C axioms), the answer is still no. I am fairly certain about this. Suppose one had an algorithm that took any statement and gave the answer that it is satisfiable or not. First number the statements as follows:
0,1,2,3,4,5,...
0',1',2',3',4',5',...

For example, 1' denotes the negation of 1, 2' denotes the negation of 2 and so on. Now if a statement and its negation both are satisfiable then it is independent of our theory. The converse of the implication in previous sentence is true as well.

Now [given the assumption that there is an algorithm that decides satisfiability] we can show that the set of all proveable statements, for our given theory, is a computable set (in addition to being a c.e. set). So suppose we are given a statement $n$ and we want to determine whether it is proven by the theory or not. So we do the following steps :
(1) Check whether the statement $n$ and its negation $n'$ are both satisfiable or not?
(2) Enumerate all true statements of the theory (re-call this a c.e. set)

If the answer to step-(1) above is positive (i.e. both $n$ and $n'$ are satisfiable) the return "$n$ is not proveable". That's because if a statement and its negation are both satisfiable then it is independent of the given theory. For example, in case of PA, think of con(PA). In case of ZFC, think of CH.

If the answer to step-(1) is negative then proceed to step-(2). At some point either $n$ or $n'$ (but of not both of them) will get enumerated. If $n$ is enumerated then return "$n$ is proveable". If $n'$ is enumerated then return: "$n$ is not proveable".

A very similar idea holds for $n'$ too. Therefore the set of all proveable statements is a computable set.

===============================

However, the set of all proveable statements is known to not be a computable set (for the given theory) [however, I don't know the reasoning why this specific point holds]. In other words, set of proveable statements is supposed to be c.e. but not computable. Therefore there is no algorithm to determine satisfiability either.

The following two threads also seem to come up when searching for similar results. Hopefully they will be useful as a reference:
https://math.stackexchange.com/questions/904589/
https://mathoverflow.net/questions/81429

 

[olgerm]

Such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist. Do you agree with that?

@nuuskur, I can't understand from your post

A set of FOL formulae is called a theory. Any formula is a theory as a singleton. Any member of a given theory is also called a theorem of that theory.

If a theory has finite models, then it's possible to check them in finite time and return "yes" or "no" for satisfiability. There exist theories in FOL with only infinite models. In fact, most of them have (only) infinite models. How to check all possible infinite models in finite time? Not going to happen.

if you agree with that statement or not. Do you agree with that or not?
Wnat theory are you talking about? Word "theory" is not in my question. Since we have some confusion about what that word means, answer without using that word if it is possible.

 

[olgerm]

I don't

You do not agree that such 1.-order-logic-formula, which satisfiability would be impossible to determine, does not exist. So you think that such 1.-order-logic-formula, which satisfiability is impossible to determine, does exist. Can you write an example of a 1.-order-logic-formula, which satisfiability is impossible to determine?

 

[nuuskur]

Actually nevermind. I can't. We seem to be arguing over definitions than results.

 

[jedishrfu]

It seems like this is a good time to close this thread. The question looks like its answered to the best of our ability and now we are quibbling over definitions which may have little bearing on the original question.

Thanks go to everyone who contributed here.

Jedi