Dear Everyone on this Wonderful Sites:

I'm so glad to participate on this site and ask the first question that mentioned on the Contest some days ago. I ran into a question that wrote this set:

  • $\{(p_i \vee $~ $p_{i+1}$$) $$: i \in \mathbb{N} \}$

and ask this question, Which of the following is False:

-) this is Satisfiable

--) this is Complete

---) this is Decidable

----) set of logical result of this set is effectively enumerable.

Solution of answer sheet is (2).

We try to solve it that without any detail is mentioned in the contest. one of our TA says, It is satisfiable because the TFTF... will satisfy it. (We couldent get it) and it is decidable because propositional logic is decidable. We read some useful website for completeness (--) and for (----), but we get stuck in it until yet. any useful hint or idea for this question will be highly appreciated.

  • 1
    $\begingroup$ What exactly does "complete" mean in this context? $\endgroup$ – mrp Mar 24 '15 at 19:54
  • $\begingroup$ @mrp, please see: math.stackexchange.com/questions/1137376/… $\endgroup$ – LoveMathContest Mar 24 '15 at 19:56
  • $\begingroup$ Then this question depends on what logic you are considering. $\endgroup$ – mrp Mar 24 '15 at 20:02
  • $\begingroup$ @mrp, we talk about propositional logic. $\endgroup$ – LoveMathContest Mar 24 '15 at 20:05
  • $\begingroup$ TFTF... will not satisfy it : $p_1 \lor \lnot p_2$ is evaluated to $T \lor \lnot F=T$ but $p_2 \lor \lnot p_3$ is evaulated to $F \lor \lnot T = F$. I think that we have to use TTTT... $\endgroup$ – Mauro ALLEGRANZA Mar 24 '15 at 20:30

Let $\Phi = \{ p_i \lor \neg p_{i+1}|i \in \mathbb{N}\}$

It is easy to see that all models of $\Phi$ are of the form $M_k$, where

$$M_k(p_i)= \left\{ \begin{array}{ll} T \quad i < k\\ F \quad \text{else}\end{array} \right. \quad k\in \omega \cup \{\omega\}$$

So in particular it is satisfiable.

It is not complete, since $M_0\models \neg p_0$ but $M_1\models p_0$

The set $\Phi^\models$of logical results of $\Phi$ is decidable, so in particular recursivly enumerable:

Let $\varphi(p_0,\dots,p_n)$ be a formula whose propositional variables are among $p_0 \dots p_n$.

$$\Phi \models \varphi \Leftrightarrow \{ p_i \lor \neg p_{i+1}|i \leq n\}\models \varphi \Leftrightarrow \bigwedge_{i\leq n}p_i \lor \neg p_{i+1} \models \varphi$$

The last can be checked by truth tables.

| cite | improve this answer | |
  • $\begingroup$ is it possible to add more detail about completeness? $\endgroup$ – LoveMathContest Mar 25 '15 at 20:16
  • $\begingroup$ @LoveMathContest A Theory $\Phi$ is complete if for every formula $\varphi$ we have $\Phi \models \varphi$ or $\Phi \models \neg \varphi$. Taking $\varphi = p_0$ we see that none of these hold since $M_0$ does not model $p_0$ and $M_1$ does not model $\neg p_0$ $\endgroup$ – Achilles Mar 25 '15 at 20:23

The question asks which of the following is False. Now, if for some propositional formula $\phi$, neither $\{(p_i \vee $~ $p_{i+1}$$) $$ $$ : i \in \mathbb{N} \}$ $\vdash$ $\phi$ nor $\{(p_i \vee $~ $p_{i+1}$$) $$ $$ : i \in \mathbb{N} \}$ $\vdash$ $\lnot$ $\phi$, then $\{(p_i \vee $~ $p_{i+1}$$) $$ $$ : i \in \mathbb{N} \}$ is not complete.

Now, note that we completeness is defined in terms of "$\vdash$" and not in terms of "|=". Thus, we simply declare that the propositional logic we have under study has no rules of inference. And thus neither $\phi$ nor $\lnot$ $\phi$ is provable, and thus $\sum$ is incomplete and it is fase that $\sum$ is complete. Or do something like set up an axiomatic propositional calculus with only conditional connectives, forbid definitions, and then indicate $\phi$ as a disjunction.

Example of such a latter calculus:

Our axiom set is {CpCqp, CCpqCCqrCpr, CCpCpqCpq} under the rules of detachment and substitution with no definitions. Thus, the set {CpCqp, CCpqCCqrCpr, CCpCpqCpq, ApNp} is not complete, since neither $\vdash$ ApNp nor $\vdash$ NApNp.

| cite | improve this answer | |
  • 1
    $\begingroup$ I get it. What about satisfiable property? or (----)? $\endgroup$ – LoveMathContest Mar 25 '15 at 19:24
  • $\begingroup$ @LoveMathContest If you can't prove anything, then the logical results of the set is empty. The empty set is enumerable since it corresponds to the ordinal 0. $\endgroup$ – Doug Spoonwood Mar 25 '15 at 20:15
  • $\begingroup$ Thanks, it's better to define all of the option to set bounty and approve. $\endgroup$ – LoveMathContest Mar 25 '15 at 20:16
  • 1
    $\begingroup$ I don't think the spirit of the question asked us to declare that we are working with a logic where nothing is provable - I think it was asking about the normal deductive system. $\endgroup$ – Carl Mummert Mar 25 '15 at 22:48
  • $\begingroup$ @CarlMummert Well, the normal deductive system isn't complete according to the definition referenced by the author in the comments, because no contingent proposition is provable, nor is it's negation provable. We can pick any propositional variable as $\phi$ there If the variable was provable, then by assigning it a truth value of "false" we could prove a false statement, and classical logic would be unsound. Similarly, if the negation of the variable was provable, then by assigning the variable a truth value of "true" we could prove a false statement, and classical logic would be unsound. $\endgroup$ – Doug Spoonwood Mar 25 '15 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.