1
$\begingroup$

Are the following theories consistent? In each case, justify your answer.

(a) $\{\neg(x_1\doteq x_2)\text{, } \neg(x_2\doteq x_3) \text{, } \neg(x_1\doteq x_3)\}$

(b) $\{\exists x_1\exists x_2\exists x_3(\neg(x_1\doteq x_2)\land \neg(x_2\doteq x_3)\land \neg(x_1\doteq x_3))\}$

(c) $\{\forall x_1\forall x_2\forall x_3(\neg(x_1\doteq x_2)\land \neg(x_2\doteq x_3)\land \neg(x_1\doteq x_3))\}$

Solution:

Definition: A theory $\Gamma$ is called consistent if $\Gamma\nvdash\bot$. A theory $\Gamma$ is called inconsistent if $\Gamma\vdash\bot$

The only method I have learnt to derive is by natural deduction, but we have also learnt the completeness theorem which shortly states "$\varphi\vDash\psi\implies\varphi\vdash\psi$". My teacher said if we want to prove a theory is consistent then we just have to find a model, which is easy to see by using the soundness theorem $\varphi\vdash\bot\implies\varphi\vDash\bot$. We have also learnt that if we want to prove something is derivable then we can do this by applying the completeness theorem and show that the logical consequence must hold. But then my teacher said that if want to prove a theory is INCONSISTENT, we just have to derive false from some assumptions in the theory. But then I wonder why it isn't possible to use a similar argument in this case. Use some argument and conclude that this must always be false?

(b) is consistent. Acoording to (a), is this theory consistent? I mean, am I allowed to use this model as my example $\exists x_1\exists x_2\exists x_3(\neg(x_1\doteq x_2)\land \neg(x_2\doteq x_3)\land \neg(x_1\doteq x_3))$? That is, use $\exists$-signs?

So; my guess is that (c) is the only inconsistent theory among this. Haven't tried to derive false from this yet though. Hope someone can help me. Thanks :)

$\endgroup$
5
  • $\begingroup$ Does the $\doteq$ symbol come with logical axioms of its own, or is it just a random relation symbol? In the latter case, all three theories are satisfied by any structure where $a\doteq b$ is always false no matter what $a$ and $b$ are. $\endgroup$
    – hmakholm left over Monica
    Commented Oct 25, 2015 at 16:12
  • $\begingroup$ I don't really understand your question not that it's ill-formed more that I am new to the subject "Mathematical logic". :) But my teacher preffered to use it I guess you could see it as en equality if you would like to :) $\endgroup$
    – user231999
    Commented Oct 25, 2015 at 16:16
  • $\begingroup$ x @Joel: Go to your list of logical axioms and/or rules of inference. Does any of them mention the $\doteq$ symbol specifically? $\endgroup$
    – hmakholm left over Monica
    Commented Oct 25, 2015 at 16:20
  • $\begingroup$ Ah, I found a box, It states "When the symbol $\doteq$ is contained in an expression, it will remind that the expression is an element of Form. When the symbol = is in an expression, it is an informal assertion, if anything. We can, for instance, write ϕ = ($x_0 \doteq x_0$) to mean that ϕ is the formula $x_0 \doteq x_0$" $\endgroup$
    – user231999
    Commented Oct 25, 2015 at 16:23
  • $\begingroup$ x @Joel: Good. So it is intended to represent equality in the formal system. But we still need to figure out if the logic you're working with knows how $\doteq$ works, or (on the other hand) the theory is supposed to supply these facts as axioms. Either of these conventions appear in textbooks by different authors. So my question about whether the rules and logical axioms mention $\doteq$ still stands. $\endgroup$
    – hmakholm left over Monica
    Commented Oct 25, 2015 at 16:26

1 Answer 1

Reset to default
2
$\begingroup$

There are two main ways to prove that a theory is consistent:

i) Show a model that satisfies the theory.

ii) Show that every valid proof in the theory concludes something that is different from $\bot$.

Conversely, there are also two main ways to prove that a theory is inconsistent:

iii) Show that every structure in the language of the theory fails to be a model.

iv) Show a valid proof in the theory whose conclusion is $\bot$.

Among these, strategy (i) and (iv) are usually easier to carry out, because they only require you to exhibit one thing with particular properties. On the other hand for (ii) and (iii) you would need to argue about all possibilities for either proofs or structures -- or, in other words, you'd need to argue that something is impossible.

It is easier to prove that something is possible (just doing it constitutes a proof) than to argue that something is impossible (you would need to convince the reader that your argument works in all kinds of corner cases).

Therefore (i) and (iv) are usually the preferred ways to do this kind of proofs. Of course it might be that for a particular theory you can see a straightforward way of arguing (ii) or (iii), and in that case it is entirely valid to do so.

$\endgroup$

You must log in to answer this question.