On Post's canonical systems
Raymond M. Smullyan · Journal of Symbolic Logic · 1962
We assume familiarity with the canonical languages of Post (cf. [1], [2]). A set S of strings is said to be representable in a canonical system (F) if there is a string π such that for every string X, X ∈ S if and only if πX is provable in (F). Suppose that K is a finite alphabet containing at least 2 symbols, and that W is a set of strings in (the symbols of) K. If W is representable in some canonical system, is it necessarily representable in a canonical system which uses only the symbols of K ? We answer this question affirmatively. Thus, e.g., it is possible to construct a 2-sign universal system over its own alphabet.2