# For any $\alpha$, does a set $\gamma$ always exist so $\gamma\vdash\alpha$ or $\gamma\vdash\lnot\alpha$?

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$?

-
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
show 8 more comments

## 1 Answer

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.

-
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? math.stackexchange.com/questions/56069/… 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
show 11 more comments