Section 2.2: Problem 27 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
Assume that the parameters of the language are and a two-place predicate symbol . List all of the non-isomorphic structures of size 2. That is, give a list of structures (where the universe of each has size 2) such that any structure of size 2 is isomorphic to exactly one structure on the list.
I actually already did something similar in Exercise 2. Consider the structure where varies. There are 16 possibilities, 10 being essentially different (there are no automorphisms between any two of them).
Given any structure of size 2, we determine , the number of pairs in . If , any bijective function will work as an isomorphism. Similarly for and . If , then either we have or in , or or in . Correspondingly, there is an isomorphism of onto or . If , then let be the number of pairs in of the form . If , then , and we are in case . If , then we have one such pair, say, , and one more either or , correspondingly we are in case or . If , then , and we are in case . Finally, if , then there is one pair missing in , and if , we are in case , otherwise, , and we are in case . Here “we are in case ” means that there is an obvious bijective correspondence between and such that preserves .