0
$\begingroup$

A set $\sum$ of formulas in propositional logic is complete if for each propositional formula $\phi$ either $\sum \vdash \phi$ or $\sum \vdash \neg \phi$. Clearly every inconsistent set of formulas is complete because of the following lemma

Lemma: Let $\sum$ be an inconsistent set, then for every propositional formula $\phi$ , $\sum \vdash \phi$

So the important thing is determining whether a consistent set of formulas is complete or not. I would like to know is there any method to find out whether a consistent set of formulas is complete or not? and Is this method decidable or not?

As an example the following sets are complete ($\downarrow$ means NOR)

$\{p_1,p_1 \leftrightarrow p_2,p_2 \leftrightarrow p_3,p_3 \leftrightarrow p_4,... \}$

$\{p_1 \downarrow p_2,p_2 \downarrow p_3,p_3 \downarrow p_4,p_4 \downarrow p_5,...\}$

But this one is not

$\{\neg p_1 , p_1 \vee p_2,p_1 \vee p_2 \vee p_3,p_1 \vee p_2 \vee p_3 \vee p_4 , ... \}$

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Incompleteness is equivalent to having at least two satisfying assignment, hence it is NP-complete by a trivial reduction from SAT. $\endgroup$
    – Emil Jeřábek
    Commented Feb 28, 2015 at 13:29
  • 4
    $\begingroup$ I have voted to put this on-hold because it is not about research level mathematics - this question would be a better fit on mathematics.stackexchange.com. In any event: when we have a finite set of variables and a finite set of formulas, it is trivially decidable whether the set is complete, by using truth tables. When the set of formulas may be infinite, it is not decidable whether a given set is complete, by a simple diagonalization argument. $\endgroup$
    – Carl Mummert
    Commented Feb 28, 2015 at 13:35
  • 1
    $\begingroup$ @Drupalist For a consistent theory $\Sigma$, it is incomplete if and only if there are at least two rows in the truth table that satisfy $\Sigma$. Or, equivalently, if $\Sigma\cup\{p\}$ and $\Sigma\cup\{\neg p\}$ are both satisfiable for some propositional variable. In other words, it suffices to consider the case that $\phi$ in your statement is a propositional variable, since if $\Sigma$ settles the values of all variables, it settles all the sentences as well. $\endgroup$
    – Joel David Hamkins
    Commented Feb 28, 2015 at 14:01
  • 5
    $\begingroup$ @Drupalist: The process is thinking. You have the set, you have the definition of completeness, so try to prove or disprove that the set satisfies the definition, or something equivalent. How to do that depends entirely on what you know about the set, there is no generally applicable answer. $\endgroup$
    – Emil Jeřábek
    Commented Feb 28, 2015 at 14:08
  • 1
    $\begingroup$ Well, your best bet then is to look at the kind of problems the entrance committee likes to give, and train how to solve them. There really isn’t a deterministic method. A case in point: let $\Sigma$ be the set of formulas in variables $p_n$, $n\ge2$, axiomatized by $\{p_n:n\text{ prime}\}\cup\{\neg p_n:n\text{ odd composite}\}\cup\{p_n\land p_m\to p_{n+m}:n,m\text{ odd}\}$. Is it complete? (This is a rhetorical question.) $\endgroup$
    – Emil Jeřábek
    Commented Feb 28, 2015 at 14:44

1 Answer 1

Reset to default
3
$\begingroup$

Given a finite propositional theory, one can decide completeness by checking the truth table. As Emil mentions, in general completeness for a finite theory will be NP-complete.

But your examples are infinite. In this case, one needs to take more care with the precise formulation of the question. For the decidability question, how are we to give the theory as input? If the theory is given by means of a program that will enumerate the sentences of the theory, then the problem of determining whether or not it is complete will not be computable, basically because of Rice's theorem. If there were an algorithm that decided completeness, we could start enumerating a complete theory until the algorithm output the answer, and then switch to an incomplete theory to get a contradiction, using the recursion theorem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ You mentioned the Rice theorem. it says any non-trivial attribute of algorithms is undecidable. Undecidable means both semi-decidable which equals to recursively enumerable sets and non recursively enumerable sets. Semi decidable problems have an algorithm. I would like to know if this problem is semi-decidable is there any partial algorithm (partial function) to solve the problem? $\endgroup$
    – M a m a D
    Commented Feb 28, 2015 at 13:59
  • $\begingroup$ Inconsistency is semi-decidable, since we can find it by checking a finite part of the truth table and a finite part of the theory. Incompleteness looks to have complexity $\Sigma^0_2$, since a theory is incomplete if there is some $p$ such that the theory is satisfiable with $p$ and also with $\neg p$, and satisfiability is $\Pi^0_1$. I expect these bounds are sharp, and in this case, neither completeness nor incompleteness would be semi-decidable. $\endgroup$
    – Joel David Hamkins
    Commented Feb 28, 2015 at 14:08
  • $\begingroup$ I'll have PhD entrance exam in the next week and they ask the completeness of a set of formulas problem every year. sounds I should give it up! $\endgroup$
    – M a m a D
    Commented Feb 28, 2015 at 14:13
  • 1
    $\begingroup$ I see, you just have to solve one instance! So you don't need a general algorithm. The true meaning of the undecidability result is that one must be creative to decide any given instance---there is no general rote algorithm. $\endgroup$
    – Joel David Hamkins
    Commented Feb 28, 2015 at 14:15
  • $\begingroup$ Yes, sounds I need a trick more than an algorithm! The examples I mentioned in the question was the problem of the last year. $\endgroup$
    – M a m a D
    Commented Feb 28, 2015 at 14:18

Not the answer you're looking for? Browse other questions tagged .