3

As I understand, a theory is a set of sentences which are closed under some notion of deduction (i.e., applying deduction rules to the sentences of a theorem does not produce any new sentences) (wikipedia does not mention this notion of closure I think).

In practice, a theory is represented by a subset of its sentences called axioms such that all other sentences in the theory are deducible starting from these axioms and using deduction rules. These axioms are actually a representation of a theory, but not the theory itself. Sentences other than axioms in a theory are called theorems.

My Questions:

1) Is what I presented as a definition of theories, axioms, and theorems in the above correct? (I want to make sure that the notion of closure in the sense I defined above is necessary for the definition of theory or it is not?)

2) If we add an axiom to our existing set of axioms in a theory, does this new axiom extend the theory or it restricts it, or it depends on the axiom?

By extension of a theory $T$, I mean getting $T'$ such that $T \subset T'$ and by restriction I mean getting $T'$ such that $T' \subset T$

Bruno Bentzen
  • 3,362
qartal
  • 805

2 Answers2

5

1) As we usually define them:

  • A theory $T$ is a set of sentences such that $\varphi \in T \Leftrightarrow T \vdash \varphi$ (derivability closure).

  • A set $\Gamma$ is the axiom set of a theory $T$ iff $T = \left\{ \varphi | \Gamma \vdash \varphi \right\}$

  • If $T \vdash \varphi$, we say that $\varphi$ is a theorem of $T$ (that is, axioms are 1-line theorems)

2) Suppose you add $\alpha \notin T$ to the axiom set of $T$. The result is then a new theory $T'$, such that $\varphi \in T' \Leftrightarrow T\cup\{\alpha\} \vdash \varphi$. It is easy to see that $T'$ extends $T$, since $T \subset T\cup\{\alpha\} \subseteq T'$.

Bruno Bentzen
  • 3,362
  • Regarding a second question, is there any technique to determine if a certain subset of a theory sentences is functionally complete, in the sense that they can act as axioms for the theory. (This does not seem to be decidable in general, is it?) – qartal May 26 '15 at 18:55
  • 1
    @qartal Well, the property of functional completeness is usually said of a set of connectives, so that I don't really get what you mean by it. What you probably mean is if there is some algorithm to determine if an arbitrary subset $X \subseteq T$ is the axiom set of $T$. It's enough to check whether $X$'s deductive closure is identical to $T$, that is, if $X \vdash \varphi$, for every $\varphi \in T$. But if our theory is a (non-monotonic) first-order logic, we know there is no such a procedure to determine in general whether $T \vdash \varphi$ for any $\varphi$. – Bruno Bentzen May 27 '15 at 05:34
2

  1. This is basically all correct, except that I regard axioms as theorems (they're theorems with 0-line proofs). Ergo, the theorems of $T$ are just the elements of $T$. This is kind of like how if $V$ is a vector space, then the vectors of $V$ are just the elements of $V$.

  2. Adjoining a new axiom can never make the theory smaller, although it can potentially make it bigger.

  3. In my opinion, we should try to refrain from speaking of "axioms", since the term is basically meaningless. Admittedly, I tend to violate this recommendation all the time. Anyway, the way I see it, there are sentences. A collection of sentences can entail another sentence. If you have a collection $S$ of sentences, we can write $\mathrm{cl}(S)$ for the collection of all sentences entailed by the sentences of $S$. In words, $\mathrm{cl}(S)$ is the theory generated by $S$. That is all; in particular, calling the elements of $S$ "axioms" gains us nothing. For some reason, however, it seems very difficult to refrain from calling things axioms.

goblin GONE
  • 67,744