Question

2.57 Prove that there is no theory K whose models are exactly the interpretations with finite domains.

Answer 1

There is a fairly common example of a 2nd order formula that is only true in a universe with infinite domain:

∃R∧∧∧∀x∀x∃y∀x∀y∀x∀y∀z¬xRxxRyxRy⟹¬yRxxRy∧yRz⟹xRz
∃R∀x¬xRx∧∀x∃yxRy∧∀x∀yxRy⟹¬yRx∧∀x∀y∀zxRy∧yRz⟹xRz
And it is fairly easy to establish a formula that is only true in a finite universe:

∃x∀y x=y
∃x∀y x=y
which has only 1 element in the universe, or

∃x1∃x2∀y x1=y∨x2=y
∃x1∃x2∀y x1=y∨x2=y
which has no more than 2 elements in the universe. Is there a formula that only holds when the universe is finite without putting an upper finite limit on its size? In other words, it would be consistent with any formula of the form ∃x1…∃xn∀y x1=y∨⋯∨xn=y∃x1…∃xn∀y x1=y∨⋯∨xn=y ? I would be interested even if the formula was a higher order (quantified over relations or functions) formula; however, I am mostly interested in formulas with no free variables and no unquantified constants.