Skip to main content
edited body
Source Link
Andrew Critch
  • 11.1k
  • 1
  • 49
  • 71

This question certainly makes sense to ask, butand 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.)

This question certainly makes sense to ask, but 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.)

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.)

Source Link
Andrew Critch
  • 11.1k
  • 1
  • 49
  • 71

This question certainly makes sense to ask, but 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.)