Compactness obstruction to expressing totality over an infinite codomain

ID: compactness-obstruction-to-expressing-totality-over-an-infinite-codomain

Let and let be infinite, with an injection available. In the propositional logic with variables , no finitary theory has as its models exactly all total injections , represented by their true pairs. Fix and suppose axiomatizes that entire class. Adjoin for every .
Every finite subset of these extra requirements is satisfiable together with : start with any total injection and permute so that the value at avoids the finitely many forbidden values. The propositional compactness theorem then supplies a model of in which has no value, a contradiction.
The requirement that all total injections be models is essential. A theory can certainly force totality by specifying a particular injection, with one axiom for each . What fails is a finitary axiomatization of the full unrestricted class. Conditions saying at most one value per input and at most one input per value are expressible by pairwise prohibitions.

New to topics? Read the docs here!