Completness and Set of Result of One Set ?!?

Question

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.

Answer 1

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.

Answer 2

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.