# Completeness notions in logic

1. Feb 23, 2013

### Klungo

Is it true that the following definitions of completeness are equivalent?
$\mbox{For theory } \Sigma \mbox{ and for any sentence } A$.

$\mbox{ Either } \Sigma \vdash A \mbox{ or } \Sigma \vdash \lnot A$
and
$\mbox{ Either } A \in \Sigma \mbox{ or } (\lnot A) \in \Sigma$.

(The second clearly implies the first.)

2. Feb 27, 2013

### MLP

Did you mean to include that Ʃ was maximally consistent? If not then let Ʃ be the unit set that contains only the sentence letter p. If it is granted that we can then derive q→p, we have a situation where
(1) Either q→p is derivable from Ʃ or ~(q→p) is derivable from Ʃ (because q→p is derivable)
but
(2) neither q→p nor ~(q→p) is a member of Ʃ

No?

3. Feb 27, 2013

### Klungo

No consistency is assumed.

I'm a bit unsure here.

We assume {P} derives/turnstile Q→P and show that (1) holds while (2) fails.

(Using the rules of inference my class uses at least)

{P} derives P, and
{~Q v P} derives Q → P.

So, (while skipping some steps)

either {P} derives ~Q or {P} derives P.
hence, {P} derives ~Q v P.
hence, {P} derives Q → P.

So, either {P} derives ~(Q → P) or {P} derives Q → P.
Neither of which are in {P}.

So they are not equivalent.

Is this what you mean? (Thanks for the help)

4. Feb 27, 2013

### MLP

I think so. I was assuming that there was some way of deriving q→p from {p} without really saying what it was because systems can differ. I think what you did was show how you could get there in the system you are using.

5. Feb 27, 2013

### Klungo

There's a flaw though.

{P} does not satisfy (1). For example, neither {P} derives Q nor {P} derives ~Q. And we show that {P} doesn't satisfy (2) by example. I.e. {P} is incomplete.

6. Feb 27, 2013

### Preno

A theory is a set of formulas closed under $\vdash$. So, trivially, $\Sigma \vdash A$ and $A \in \Sigma$ mean the same thing for any theory $\Sigma$.