3
$\begingroup$

First question on this site. Hope to ask/answer many more in the future.

I'm currently self-studying An Introduction to Mathematical Logic by Richard E. Hodel and came across an interesting exercise. This is how it is introduced:

Let F be a formal system, let FOR be the set of formulas of F, and let THM be the set of theorems of F. A subset I of FOR is said to be inductive if it satisfies these two conditions: (a) Every axiom of the formal system F is in I; (b) If A1, ... , An/B is a rule of inference of F, and each of the hypotheses A1, ... , An are in I, then B is also in I.

The exercise leads one to prove that THM is a subset of any arbitrary inductive set I, and that THM is the smallest inductive subset of FOR, which I already worked out successfully.

The exercise does not imply, however, that THM = I.

So my question is then, what would be an example of a member of an inductive set that is not a member of THM? And, more generally, when does a formula fail to be a theorem, but succeed in being a member of I?

I'm still on chapter 1 of the book, so maybe my question will be answered down the line, but I am still curious and think that this would help me understand the definitions of a formal system. So any help is appreciated.

Thanks

$\endgroup$
  • 3
    $\begingroup$ All of FOR forms an inductive set; but if F is consistent, then it is not equal to THM. $\endgroup$ – Daniel Schepler Aug 14 '18 at 1:51
5
$\begingroup$

An example of an inductive set is the set FOR of all formulas. This is strictly larger than THM in most cases of interest. (I see I've just repeated Daniel Schepler's comment here.)

More generally, suppose that not every formula is a theorem, i.e. $\text{THM}\subsetneq\text{FOR}$. Then pick any formula $\varphi\in \text{FOR}\setminus \text{THM}$, and add it to $F$ as an additional axiom, obtaining a new formal system $F'$. Then the set $\text{THM}'$ of theorems of $F'$ is an inductive set which is larger than $\text{THM}$, since it includes $\varphi$.

In fact, you can add any set of formulas to $F$ as new axioms, and the resulting set of theorems will be an inductive set. The case of $\text{FOR}$ occurs when you take every formula as an axiom, or just enough axioms to make the system inconsistent.

$\endgroup$
  • $\begingroup$ Thanks for the insight. This certainly helped clear things up for me $\endgroup$ – Z_z_Z Aug 15 '18 at 11:22
3
$\begingroup$

Suppose we have any fixed model $M$ of $F$. Then the set of formulas $\phi$ such that $M \models \phi$ is an inductive set. However, unless $F$ is complete then this set will include formulas not in THM.

$\endgroup$
  • $\begingroup$ Thanks for the great and succinct answer $\endgroup$ – Z_z_Z Aug 15 '18 at 11:24

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.