Return to Answer

In this MO answer, I mentioned Arnold Miller's lecture notes, where he gives an entertaining account of the MM proof system (for Micky Mouse), having as axioms all validities and modus ponens as the only rule of inference. Although it is easy to prove the Completeness theorem from Compactness in this system, it is nevertheless a kind of joke system, since the set of validities is not a decidable set, and so we would be fundamentally unable to recognize whether something is a proof or not in this system. Miller uses this example to illustrate the point as follows:

The poor MM system went to the Wizard of OZ and said, “I want to be more like all the other proof systems.” And the Wizard replied, “You’ve got just about everything any other proof system has and more. The completeness theorem is easy to prove in your system. You have very few logical rules and logical axioms. You lack only one thing. It is too hard for mere mortals to gaze at a proof in your system and tell whether it really is a proof. The difficulty comes from taking all logical validities as your logical axioms.” The Wizard went on to give MM a subset Val of logical validities that is recursive and has the property that every logical validity can be proved using only Modus Ponens from Val.

And he then goes on to describe how one might construct Val, and give what amounts to a traditional proof of Completeness.

In this MO answer, I mentioned Arnold Miller's lecture notes, where he gives an entertaining account of the MM proof system (for Micky Mouse), having as axioms all validities and modus ponens as the only rule of inference. Although it is easy to prove the Completeness theorem from Compactness in this system, it is nevertheless a kind of joke system, since the set of validities is not a decidable set, and so we would be fundamentally unable to recognize whether something is a proof or not in this system. Miller uses this example to illustrate the point as follows:

The poor MM system went to the Wizard of OZ and said, “I want to be more like all the other proof systems.” And the Wizard replied, “You’ve got just about everything any other proof system has and more. The completeness theorem is easy to prove in your system. You have very few logical rules and logical axioms. You lack only one thing. It is too hard for mere mortals to gaze at a proof in your system and tell whether it really is a proof. The difficulty comes from taking all logical validities as your logical axioms.” The Wizard went on to give MM a subset Val of logical validities that is recursive and has the property that every logical validity can be proved using only Modus Ponens from Val.

And he then goes on to describe how one might construct Val, and give what amounts to a traditional proof of Completeness.

In this MO answer, I mentioned Arnold Miller's lecture notes, where he gives an entertaining account of the MM proof system (for Micky Mouse), having as axioms all validities and modus ponens as the only rule of inference. Although it is easy to prove the Completness theorem from Compactness in this system, it is nevertheless a kind of joke system, since the set of validities is not a decidable set, and so we would be fundamentally unable to recognize whether something is a proof or not in this system. Miller uses this example to illustrate the point as follows:

The poor MM system went to the Wizard of OZ and said, “I want to be more like all the other proof systems.” And the Wizard replied, “You’ve got just about everything any other proof system has and more. The completeness theorem is easy to prove in your system. You have very few logical rules and logical axioms. You lack only one thing. It is too hard for mere mortals to gaze at a proof in your system and tell whether it really is a proof. The difficulty comes from taking all logical validities as your logical axioms.” The Wizard went on to give MM a subset Val of logical validities that is recursive and has the property that every logical validity can be proved using only Modus Ponens from Val.

And he then goes on to describe how one might construct Val, and give what amounts to a traditional proof of Completeness.

In this MO answer, I mentioned Arnold Miller's lecture notes, where he gives an entertaining account of the MM proof system (for Micky Mouse), having as axioms all validities and modus ponens as the only rule of inference. Although it is easy to prove the Completeness theorem from Compactness in this system, it is nevertheless a kind of joke system, since the set of validities is not a decidable set, and so we would be fundamentally unable to recognize whether something is a proof or not in this system. Miller uses this example to illustrate the point as follows:

The poor MM system went to the Wizard of OZ and said, “I want to be more like all the other proof systems.” And the Wizard replied, “You’ve got just about everything any other proof system has and more. The completeness theorem is easy to prove in your system. You have very few logical rules and logical axioms. You lack only one thing. It is too hard for mere mortals to gaze at a proof in your system and tell whether it really is a proof. The difficulty comes from taking all logical validities as your logical axioms.” The Wizard went on to give MM a subset Val of logical validities that is recursive and has the property that every logical validity can be proved using only Modus Ponens from Val.

And he then goes on to describe how one might construct Val, and give what amounts to a traditional proof of Completeness.

In this MO answer, I mentioned Arnold Miller's lecture notes, where he gives an entertaining account of the MM proof system (for Micky Mouse), having as axioms all validities and modus ponens as the only rule of inference. Although it is easy to prove the Completness theorem from Compactness in this system, it is nevertheless a kind of joke system, since the set of validities is not a decidable set, and so we would be fundamentally unable to recognize whether something is a proof or not in this system. Miller uses this example to illustrate the point as follows:

The poor MM system went to the Wizard of OZ and said, “I want to be more like all the other proof systems.” And the Wizard replied, “You’ve got just about everything any other proof system has and more. The completeness theorem is easy to prove in your system. You have very few logical rules and logical axioms. You lack only one thing. It is too hard for mere mortals to gaze at a proof in your system and tell whether it really is a proof. The difficulty comes from taking all logical validities as your logical axioms.” The Wizard went on to give MM a subset Val of logical validities that is recursive and has the property that every logical validity can be proved using only Modus Ponens from Val.

And he then goes on to describe how one might construct Val, and give what amounts to a traditional proof of Completeness.

In this MO answer, I mentioned Arnold Miller's lecture notes, where he gives an entertaining account of the MM proof system (for Micky Mouse), having as axioms all validities and modus ponens as the only rule of inference. Although it is easy to prove the Completness theorem from Compactness in this system, it is nevertheless a kind of joke system, since the set of validities is not a decidable set, and so we would be fundamentally unable to recognize whether something is a proof or not in this system. Miller uses this example to illustrate the point as follows:

The poor MM system went to the Wizard of OZ and said, “I want to be more like all the other proof systems.” And the Wizard replied, “You’ve got just about everything any other proof system has and more. The completeness theorem is easy to prove in your system. You have very few logical rules and logical axioms. You lack only one thing. It is too hard for mere mortals to gaze at a proof in your system and tell whether it really is a proof. The difficulty comes from taking all logical validities as your logical axioms.” The Wizard went on to give MM a subset Val of logical validities that is recursive and has the property that every logical validity can be proved using only Modus Ponens from Val.

And he then goes on to describe how one might construct Val, and give what amounts to a traditional proof of Completeness.