omega the last letter of the Greek alphabet (w). Following Cantor (1845–1911), it is used in lowercase as a proper name for the first infinite ordinal number, which is the ordinal of the natural ordering of the set of finite ordinals. By extension it is also used as a proper name for the set of finite ordinals itself or even for the set of natural numbers. Following Gödel (1906–78), it is used as a prefix in names of various logical properties of sets of sentences, most notably omega-completeness and omega-consistency. Omega-completeness, in the original sense due to Tarski, is a syntactical property of sets of sentences in a formal arithmetic language involving a symbol ‘0’ for the number zero and a symbol ‘s’ for the so-called successor function, resulting in each natural number being named by an expression, called a numeral, in the following series: ‘0’, ‘s0’, ‘ss0’, and so on. For example, five is denoted by ‘sssss0’. A set of sentences is said to be omegacomplete if it (deductively) yields every universal sentence all of whose singular instances it yields. In this framework, as usual, every universal sentence, ‘for every n, n has P’ yields each and every one of its singular instances, ‘0 has P’, ‘s0 has P’, ‘ss0 has P’, etc. However, as had been known by logicians at least since the Middle Ages, the converse is not true, i.e., it is not in general the case that a universal sentence is deducible from the set of its singular instances. Thus one should not expect to find omega-completeness except in exceptional sets. The set of all true sentences of arithmetic is such an exceptional set; the reason is the semantic fact that every universal sentence (whether or not in arithmetic) is materially equivalent to the set of all its singular instances. A set of sentences that is not omega-complete is said to be omega-incomplete. The existence of omega-incomplete sets of sentences is a phenomenon at the core of the 1931 Gödel incompleteness result, which shows that every ‘effective’ axiom set for arithmetic is omega-incomplete and thus has as theorems all singular instances of a universal sentence that is not one of its theorems. Although this is a remarkable fact, the existence of omega-incomplete sets per se is far from remarkable, as suggested above. In fact, the empty set and equivalently the set of all tautologies are omega-incomplete because each yields all singular instances of the non-tautological formal sentence, here called FS, that expresses the proposition that every number is either zero or a successor.
Omega-consistency belongs to a set that does not yield the negation of any universal sentence all of whose singular instances it yields. A set that is not omega-consistent is said to be omega-inconsistent. Omega-inconsistency of course implies consistency in the ordinary sense; but it is easy to find consistent sets that are not omega-consistent, e.g., the set whose only member is the negation of the formal sentence FS mentioned above. Corresponding to the syntactical properties just mentioned there are analogous semantic properties whose definitions are obtained by substituting ‘(semantically) implies’ for ‘(deductively) yields’.
The Greek letter omega and its English name have many other uses in modern logic. Carnap introduced a non-effective, non-logical rule, called the omega rule, for ‘inferring’ a universal sentence from its singular instances; adding the omega rule to a standard axiomatization of arithmetic produces a complete but non-effective axiomatization. An omega-valued logic is a many-valued logic whose set of truth-values is or is the same size as the set of natural numbers.
See also COMPLETENESS, CONSISTENCY, GÖDEL’ S INCOMPLETENESS THEOREM.
J.COR.