Friday, 7 February 2014

lo.logic - Minimal axiom system for a set of provable statements

This question certainly makes sense to ask, and the answer is no, because of how flexible the definition of "logical system" is.



First, your definition of B1 < B2 can be simplified: "T(B1) is a subset of T(B2)" is equivalent to "B2 proves B1".



Now, suppose we form a logical system whose only statement symbols are xn, where n can be an integer, and (countably many) rules of inference stating that xm implies xn when m > n. If A is the set of axioms {x1,x2,x3...}, then there is no minimal set of axioms implying A (and P(A)). This is because a set of axioms B will imply A if and only if it contains a sequence of axioms with subscripts approaching infinity, in which case we can always remove finitely many axioms from B so that it still implies A.



(FYI, systems with infinitely many axioms and/or rules of inference are typical of modern mathematics; ZFC, the most commonly accepted foundation, is itself not finitely axiomatizable.)

No comments:

Post a Comment