# Logic - Member of an inductive set that is not a member of the set of theorems in a formal system?

by mraaron   Last Updated August 14, 2018 02:20 AM

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

Tags :

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.