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

Iof FOR is said to beinductiveif it satisfies these two conditions: (a) Every axiom of the formal system F is inI; (b) IfA_{1}, ... ,A_{n}/Bis a rule of inference of F, and each of the hypothesesA_{1}, ... ,A_{n}are inI, thenBis also inI.

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

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.

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger