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.


Answers 1

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.

Alex Kruckman
Alex Kruckman
August 14, 2018 01:57 AM

Related Questions

Codification of a formal language in set theory.

Updated March 10, 2019 21:20 PM

Foundation of Formal Logic

Updated February 22, 2018 14:20 PM