Section 3.1: Problem 6 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Show that is not finitely axiomatizable. Suggestion: Show that no finite subset of suffices, and then apply Section 2.6.
According to Theorem 26H, if were finitely axiomatizable, there would be a finite subset of such that . We show that this is not the case.
If a finite , then , and we need to show that . That is, there is a sentence true in that is not true in . At the same time, every model of is a model of , and every sentence true in will be true in such a model. Therefore, we need to find a model of that is not a model of , and a sentence true in that is not true in this particular model of .
Let us call each axioms S1-S4 as , , and for . Let , . Then, for a finite , there is some such that , and . If we show that for every , , then we will show the strict inclusion for every finite .
For , as the sentence that is true in but not in , consider . Then, obviously, is true in . We need to provide a model of such that is not true in the model. The axioms of group 4 ensure that there is no loop of any finite length. In we excluded all such axioms for the lengths of the loop greater than . In particular, says that there is no loop of length . So, our model of may have loops of any length greater than , and to ensure that is false, it has to have a loop of length . At the same time, we still need to satisfy all axioms S1-S3: has no predecessor, is one-to-one, and every element except has a predecessor. So, consider the set , and let be for , and for . Then, let . We check that all axioms S1-S4n hold for .
- S1: . Indeed, , and for every , , while for every , .
- S2: . Indeed, if for , , then either , and implies , or , and implies and (all numbers in have different residuals).
- S3: . Indeed, if , , then , and , and if , then if , , otherwise .
- S41-S4n: for every , , . Indeed, there are no loops in , and , where each element except is mapped by to the next one, while is mapped to (since is finite, one can even check the finite number of axioms S41-S4n for each element in ).
Therefore, is indeed a model of . At the same time, is not true in , as there is a loop of length in (actually, for every , , i.e. ).