Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Completeness notions in logic

  1. Feb 23, 2013 #1
    Is it true that the following definitions of completeness are equivalent?
    [itex]\mbox{For theory } \Sigma \mbox{ and for any sentence } A[/itex].

    [itex]\mbox{ Either } \Sigma \vdash A \mbox{ or } \Sigma \vdash \lnot A [/itex]
    [itex]\mbox{ Either } A \in \Sigma \mbox{ or } (\lnot A) \in \Sigma[/itex].

    (The second clearly implies the first.)
  2. jcsd
  3. Feb 27, 2013 #2


    User Avatar

    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)
    (2) neither q→p nor ~(q→p) is a member of Ʃ

  4. Feb 27, 2013 #3
    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)
  5. Feb 27, 2013 #4


    User Avatar

    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.
  6. Feb 27, 2013 #5
    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.
  7. Feb 27, 2013 #6
    A theory is a set of formulas closed under [itex]\vdash[/itex]. So, trivially, [itex]\Sigma \vdash A[/itex] and [itex]A \in \Sigma[/itex] mean the same thing for any theory [itex]\Sigma[/itex].
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook