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$?
For any $\alpha$, does a set $\gamma$ always exist so $\gamma\vdash\alpha$ or $\gamma\vdash\lnot\alpha$?
-
3How about $\gamma=\{\alpha\}$? – 2011-08-07
-
0@joriki: So a set has to contain the proposition in order to prove it? – 2011-08-07
-
4No. 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. – 2011-08-07
-
0By propositional calculus, do you mean predicate/sentential calculus, or first-order logic? In the first case, the answer is yes, since sentencial calculus is complete. In the second case, I think Godel's theorem says that the answer is no; there are sentences that are true, but not provable, i.e., the undecidable statements. I think a specific example would be with $\gamma$ being the continuum hypothesis in $KFC$, which is undecidable, i.e., neither $\gamma$ nor $~\gamma$ are provable within the system, so that there is no derivation that has CH as its conclusion. – 2011-08-07
-
11The $KFC$ set theory has the Chicken Wings axiom, one of the tastier axioms of mathematics! :-) – 2011-08-07
-
0@gary: Also, how the proposition $p$ (an atomic proposition) is provable from the proposition $q$ (a different atomic proposition)? Can $CH$ be derived from $ZFC+V=L$? (Answers: No on the first, yes on the second). – 2011-08-07
-
0@Asaf: you definitely do chicken --and ZFC+V=L-- right! . I guess I meant/should have said that Sentential Calculus is decidable instead of complete. Still, is my point valid, that, given the undecidability of CH (within ZFC ), that would imply that neither CH nor ~CH can be derived (within ZFC )? – 2011-08-07
-
0As a note of the weird, I did for a while try to convince people that , in the original Czech spelling , Zermelo should be spelled as 'Kermelo', trying to turn ZFC into KFC, but no one really bought into it. – 2011-08-07
-
1@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. – 2011-08-07
-
0I don't understand this entire discussion. (Perhaps that's because I'm a vegetarian?) As far as I can tell, @gary made (at least) two mistakes, one by switching quantifiers (the question asks whether for all $\alpha$ there is $\gamma$ such that ... whereas gary addressed the question whether there is $\gamma$ such that for all $\alpha$ ...), the other by assuming consistency, which wasn't specified -- even under the assumptions of Gödel's theorem, such a $\gamma$ still exists; it just has to be inconsistent. – 2011-08-07
-
0@gary: As for your side note, Zermelo is, if anything, the original *German* spelling. – 2011-08-07
-
0@Asaf: so what is then the precise relation between CH and ZFC? I had (mis-) understood that CH was independent of ZFC, meaning that both $ZFC\cup$ {CH} and $ZFC \cup$ {$\neg $ CH} were consistent. Am I off ? ( If so, I will just drop it) – 2011-08-07
-
0@gary: You are correct. This, however, has nothing to do with *the original question*. Your confusion is that in this question the theory is not specified. This is getting highly off topic, so if you have further questions please ask them in a separate thread. – 2011-08-07
1 Answers
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.
-
0why not $\Gamma$={α}? like joriki suggest? Would that violate consistency? – 2011-08-08
-
0It 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. – 2011-08-08
-
0I see, then that is indeed non-trivial – 2011-08-08
-
0do you think my proof for this question is correct? http://math.stackexchange.com/questions/56069/question-about-maximal-consistency I think I am bothering joriki too much. – 2011-08-08
-
0I 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? – 2011-08-08
-
0@Asaf: what does it mean to say a set $\Gamma$ implies a proposition $\alpha$? Does it just mean that there is a proposition or proposition(s) in the set that is equivalent to $\alpha$? – 2011-08-08
-
0@Mark: I have read your proof. Yes, it is correct. – 2011-08-08
-
0Awesome, thank you so much! – 2011-08-08
-
0@Mark: It means that whenever *all* the propositions in $\Gamma$ are evaluated as true, then so does $\alpha$. – 2011-08-08
-
0@Mark: In your question, "implies" is being used informally, for $\Gamma\vdash \alpha$. – 2011-08-08
-
0oh, I see. I should have said "proves". – 2011-08-08
-
0@Mark: The proof was carefully done. You should not have doubted! – 2011-08-08
-
0@Asaf: What if I said $\Gamma \vdash \alpha$ ? what does it mean syntactically and semantically? – 2011-08-08
-
0@Mark: I suggest you go to the office hours of your teacher and go over these things with him. – 2011-08-08
-
0@Asaf Karagila: Thank you, I have modified the post. From looking at questions that Mark has asked, it looks as if his course is completely syntactic to this stage. I prefer to mix syntax and semantics from the beginning. – 2011-08-08
-
0@Andre: I haev a serious deja vu about your comment :-) – 2011-08-08