5
$\begingroup$

This question was inspired by this question.

Does it really make sense to say that a formal system has some number of axioms, say three, or ten, etc? E.g., take a formal system that admits conjuction elimination and has axioms $ A_1, A_2,..., A_n $. But a formal system that has the single axiom $ A_1\wedge A_2\wedge ...\wedge A_n $ is essentially the same formal system!

So, is the concept of number of axioms in a formal system subjective, just as there is no objective difference between a lemma and a theorem?

P.S. I'm indeed talking about finitely axiomatizable formal systems only. I.e. when I say "axioms", I mean it - no axiom schemata allowed.

$\endgroup$
  • 1
    $\begingroup$ With 'subjective' do you mean that different numbers of axioms can deduce the same theorems? That is obvious. $\endgroup$ – Git Gud Nov 19 '14 at 16:04
  • $\begingroup$ ZF has infinitely many axioms. Some "axioms" are really axiom schemas that say that for any given formula, there's a corresponding axiom. There's no inherent rule that says the number of axioms must be finite. en.wikipedia.org/wiki/Axiom_schema_of_replacement $\endgroup$ – user4894 Nov 19 '14 at 20:26
  • 1
    $\begingroup$ What matters is whether there is a finite set of axioms (which can then be phased as a single axiom, as you stated), or whether there is no finite set of axioms (in which case that method doesn't work). $\endgroup$ – Carl Mummert Nov 19 '14 at 20:27
7
$\begingroup$

Certainly if I give you a formal system with an explicit list of axioms, say 42 of them, then it makes sense to say that the system has 42 axioms. It's hard to dispute that.

But you make a good observation, that there many equivalent formal systems with all sorts of different numbers of axioms. To be precise, say two formal systems (using the same symbols) are equivalent if they prove exactly the same theorems. It's often useful consider formal systems only up to equivalence, when what we care about is the theorems they prove, not their presentations.

So the question is really about whether by formal system you mean "explicitly defined formal system" or "formal system up to equivalence". The former has a well-defined number of axioms, the latter does not.

$\endgroup$
2
$\begingroup$

If you step out of boolean logic and look at multivalued logics, there are places where having a conjuction (for example in BL (http://en.wikipedia.org/wiki/BL_%28logic%29) if you conjunct the axioms with what is known as strong conjunction) is different from having the axioms separately (i.e. the sets of deductions won't match up properly).

In the boolean case, the number of axioms (I'm talking about finite axiomatizations as asked in the question) doesn't really matter if you are interested in the theorems. But the derivation of a proof (in a formal system) will be different. However there is good reason to split up the axioms and talk about them separately; the human mind just deals with that approach better.

$\endgroup$
  • $\begingroup$ True as well. Also, applicable to any artificial exotic logic that significantly differs from classical logic. $\endgroup$ – user132181 Nov 20 '14 at 10:31
-2
$\begingroup$

First off, let's make things clear and point out that not all theorems are the same even from a syntactic point of view. Some theorems can serve as a single axiom for some logical system in the sense that under some rule of inference, some theorem can get generated from that axiom which is not a substitution instance of the axiom. Other theorems can't generate anything under that same rule.

For instance, in some systems with detachment as the rule of inference, CCpqCCqrCpr is a theorem. If the system has countably infinite variables, the system {CCpqCCqrCpr} under detachment and substitution has countably infinite theorem which are not substitution instance of CCpqCCqrCpr. On the other hand, in some systems CCCpqpp is a theorem. But, the system {CCCpqpp} only has substitution instance of CCCpqpp as theorems.

Now one part of a formal system, according to Wikipedia consists of its deductive apparatus. The deductive apparatus consists of the axioms and/or rules of inference of the formal system. Thus, if the axioms differ, we have a different deductive apparatus. Consequently, even though the consequences of two deductive apparatuses may end up the same, the deductive apparatuses differ and consequently the formal systems differ. Axioms also differ from theorems in that they belong to the deductive apparatus, while theorems do not (at least according to the Wikipedia definition). Additionally, in terms of proving certain theorems, or what can/has gotten called the development of a formal system, the systems can differ in that some theorem might come as provable in fewer steps in system A than in system B.

So, no, the concept of the number of axioms in a formal system is not subjective. And yes it makes sense to say that a formal system has a certain natural number of axioms.

$\endgroup$
  • $\begingroup$ I strongly disagree with the third paragraph - check out Asaf's answer to this question. Also, I definitely should have mentioned I was talking about finitely axiomatizable formal systems (that is I didn't say anything about ZF(C) at all). $\endgroup$ – user132181 Nov 19 '14 at 20:58
  • $\begingroup$ @user132181 I guess you're referring to Asaf's comment " The choice of axiomatization usually doesn't matter." Well, in terms of formally proving a theorem, the choice of axioms can make a theorem more readily proved by a method or more difficult to prove by that method. Also, if the concept of the number of axioms were subject, then a 1 axiom system would in general behave in the same way metalogically speaking as a theory with the same consequence with a very large number of axioms. However, it is clear that the axiom is independent for the 1 axiom system, but not so much for the other. $\endgroup$ – Doug Spoonwood Nov 20 '14 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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