Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In propositional Calculus, for any proposition $\alpha$ does there always exist a set of propositions $\gamma$ such that $\gamma$ $\vdash$ $\alpha$ or $\gamma$ $\vdash$ $\neg\alpha$?

share|cite|improve this question
How about $\gamma=\{\alpha\}$? – joriki Aug 7 '11 at 5:27
@joriki: So a set has to contain the proposition in order to prove it? – Mark Aug 7 '11 at 5:30
No. You asked whether there always exists a set of propositions that proves $\alpha$ or $\neg\alpha$. I showed that there is by giving an example. That doesn't mean that all sets that prove a proposition have to be like that example. – joriki Aug 7 '11 at 5:39
The $KFC$ set theory has the Chicken Wings axiom, one of the tastier axioms of mathematics! :-) – Asaf Karagila Aug 7 '11 at 6:00
@gary: The point is that being undecidable is with respect to some theory. The question here, in a nutshell, is whether such theory exists or not. Both first order logic, and propositional calculus can be developed outside of set theory, so ZFC has nothing to do with this question. – Asaf Karagila Aug 7 '11 at 6:12
up vote 2 down vote accepted

There is a natural interpretation of your question that makes it important mathematically.

We ask: Is it true that there is a consistent set $\Gamma$ of sentences such that for any $\alpha$ in the language, we have $\Gamma\vdash \alpha$ or $\Gamma\vdash \lnot\alpha\;$?

The answer is yes, both for the predicate calculus and propositional calculi.
The following is the full statement of a result that applies equally well to the predicate calculus and to propositional calculi.

Theorem Let $\Sigma$ be any consistent set of sentences over a language $L$, propositional or predicate. Then there is a consistent set $\Gamma$ of sentences such that $\Sigma \subseteq \Gamma$, and for any sentence $\alpha$ of $L$, $\Gamma\vdash \alpha$ or $\Gamma\vdash \lnot\alpha\;$.

The usual proof for propositional calculi uses essentially the same Zorn's Lemma argument as the usual proof for the predicate calculus. Indeed the predicate calculus result can be derived from the one for propositional calculi by using a couple of tricks.

share|cite|improve this answer
why not $\Gamma$={α}? like joriki suggest? Would that violate consistency? – Mark Aug 8 '11 at 7:02
It would be fine, for a single $\alpha$, but that is a trivial fact. I was making an interpretation of the question that made it mathematically non-trivial, saying that in fact there is a consistent $\Gamma$ that simultaneously works for all $\alpha$. The $\Gamma=\{\alpha\}$ only works for a specific $\alpha$, and relatives such as $\lnot \alpha$, and the possibly limited number of sentences that can be derived from them. – André Nicolas Aug 8 '11 at 7:13
I see, then that is indeed non-trivial – Mark Aug 8 '11 at 7:15
do you think my proof for this question is correct?… I think I am bothering joriki too much. – Mark Aug 8 '11 at 7:17
I was sure that the completeness theorem was that consistency is equivalent to having a model. I can see how your statement is implied by the one I made. What about the other direction? – Asaf Karagila Aug 8 '11 at 7:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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