## Large Infinitary Languages, Model Theory

However, human direct access to infinite formulas is unlikely in foreseeable future, so one has to work with finite representation of infinite formulas. To avoid ambiguity, the rules for representation must be formally defined, so the language is reduced to a formal language with finite formulas. Even if humans will gain an ability to work with infinite formulas, one might just as well work with sets that code the formulas and the satisfaction relation, essentially reducing the system to finite formulas plus direct access to some sets. The expressive power of a language is determined by the objects that are described by the language and the properties expressible in the language.

It turns out that in mathematics as we know it, all mathematical objects are sets or are reducible to sets, more precisely if there are other kinds of sets extensional well-founded sets built from the empty set. A discovery of a mathematical object that is not reducible to sets would be revolutionary and unlikely.

The first order language of set theory consists of first order logic and the binary relation of membership equality is definable using extensionality. That language is the de facto formal language of mathematics, and in cases of doubt meaningfulness of other formal languages is usually established by reduction to that language.

Thus, the problem of inexpressibility in mathematics is essentially the problem of how to increase expressiveness of the language of set theory, and the solution is finding and formalizing properties of sets that are not expressible in that language. The reasons above also show that incompleteness in mathematics is incompleteness in set theory. Weak extensions to the language can be formally defined by a statement in the extended language such that the statement uniquely fixes the extension.

Stronger extensions are not defined formally but are given in the human language.

One can specify the intent, argue and hope that exactly one extension satisfies the intent, and use informal reasoning to derive results. For acceptance, one needs to axiomatize enough of the intent and the results so that basic theory can be developed formally.

ampetfidddun.tk

A large class of true statements, namely reflection principles, forms a natural hierarchy. A reflection principle can usually be represented in the form that such and such natural theory has a sufficiently well behaved model, and statements of that form tend to be reflection principles. Reflection principles are ordered by strength and expression level. A reflection principle implies all reflection principles of lower strength and expression level, including the restriction of more expressive but weaker principles to lower expression level except at the expressive level of large cardinals when it is unstated whether the cumulative hierarchy reaches the cardinals.

The incompleteness addressed in this paper is at high expression level rather than high strength and is addressed using reflection principles. Let Tr be the satisfaction relation for one parameter formulas of ordinary set theory. By Tarski's theorem of undefinability of truth, Tr is not definable in ordinary set theory, so let us consider adding it to the language.

Almost self-referential logic can be seen as a generalization and iteration of this extension. We have to show that Tr is well-defined. Necessarily, the demonstration is a philosophical, not a formal mathematical one. However, the philosophical argument corresponds to a mathematical proof that the extension is well-defined when the domain is a set.

To axiomatize this extension, we add axioms to the effect that Tr is a satisfaction relation and the replacement axiom schema for formulas involving Tr. The replacement schema is true for the same reasons that ordinary replacement is true. Simple self-reference is not allowed since otherwise the utterance "This statement is false" would lead to a paradox.

Such reference is possible because the parameters are varied on a well-founded path.

A formalization of the allowed self-reference is:. The relation is an ordinary formula with markings to indicate the arguments. Let R w be the well-founded part of R: R w s, t iff R s, t and there is no infinite sequence t, t 1 , t 2 , Consider the language of set theory extended with the satisfaction relation for almost self-referential formulas.

To see that the extension is meaningful, suppose that the relation and hence a particular almost self-referential formula is not well-defined. Since R w is well-defined and well-founded, there must be a minimal x for which the formula is not well-defined. Since the formula proper is like an ordinary formula, that can only happen if an invocation of P , say with parameter y, is not well-defined. If not R w y, x , then P y is false and hence well-defined. Otherwise, R w y, x holds, so by minimality of x, the almost self-referential formula with y in place of x, and hence P y , is well-defined.

Therefore, the extension is meaningful. Whether something is well-defined is not in general well-defined, so formally existence of "a minimal x for which the formula is not well-defined" above uses an ontological assumption. The expressive power will be analyzed, and an axiomatization presented in the next section subsection Axiomatization of Extensions. The extension with almost self-referential formulas is also meaningful in other contexts provided the base theory includes basic set theory and the notion of being well-founded. For example, it is meaningful and expressible in set theory for second order arithmetic.

A good background on infinitary logic can be found in [3]. The extension adds satisfaction relation for one-parameter infinitary formulas. Satisfaction relation for infinitary sentences is just as expressive but is less convenient for analyzing restrictions of infinitary logic. Expressive power of almost self-referential formulas can be increased by increasing the rank of the well-founded relation by approaching self-reference.

This can be done by adding a second well-founded relation and variable. In that extension, self-reference requires decreasing second variable, first variable in lexicographical order. Reference to the original formula in the first relation is now allowed provided that the second variable decreases. Nested almost self-referential formulas correspond to the second relation having finite rank; nested almost self-referential formulas without nesting in R correspond to ordinary almost self-referential formulas.

The system can be further extended by increasing the number of relations. The relations would be coded on paper by a tertiary relation, the first argument of which is the relation index. The self-referential calls use finitely many parameters, each parameter with the index of the corresponding relation; the indices must be in the decreasing order. Each call or level of recursion decreases the parameter sequence in lexicographical order; and calls placed from the j th relation must involve a decrease in index es above j.

The mechanics of these extensions resemble ordinal notation systems, and this particular extension resembles the large Veblen ordinal. Further extensions can of course be made. However, without an overarching principle, they would only add complexity and philosophical doubt while providing less and less utility. The expressive power of almost self-referential logic is best explored using transitive models.

We assume that V satisfies the replacement schema for formulas in the extension we are considering this is not needed for the theorem. The expressive power of a logic is measured by what subsets of V are definable in V using that logic, allowing parameters. For infinitary logic, we only include formulas that are in V. We now state the theorem.

For the well-founded relations used in almost self-referential formulas, the most important property is rank. For natural extensions and fragments, expressive power is linearly ordered by the allowed rank. Ranks above Ord the height of V lead to expressiveness beyond infinitary logic. The length or rank of proper class relations can be compared inductively using almost self-referential logic. The satisfaction relation of almost self-referential logic and its above-mentioned multivariable extensions is definable in second order logic about V.

Otherwise, KPi KP plus every set is inside an admissible set would suffice.

### Account Options

Such an axiomatization resolves the need for deductive apparatus for A. For typical A, variant 3 is slightly stronger than variant 2, which in turn is slightly stronger than variant 1. Variants 4 and 5 allow formalization of the idea that the class of ordinals, Ord, behaves like a large cardinal. Such formalization extends the strength of the large cardinal to the highest available level of expression. However, variant 4 with a mild strengthening of the large cardinal C implies variant 5 with unstrengthened C; for the extensions above using almost self-referential formulas and their extensions , it suffices to replace large cardinal with regular limit of stationary many of these large cardinals.

There is a close connection between the axiomatization for almost self-referential formulas, and NBG with determinacy for clopen class-length games. The later is described in [4] , where the determinacy is shown equivalent to ETR: Elementary transfinite recursion over well-founded class relations. ETR essentially corresponds to almost self-referential formulas.

To get what appears to be the exact strength and the same theorems for statements expressible in the common language , add finite iterations of the satisfaction relation for almost self-referential formulas, or work with the formulas directly but allow nested almost self-referential formulas; use variant 1 of the axiomatization above. The general idea behind the almost self-referential extensions is that restricted self-reference is meaningful when there is a guarantee that there are no contradictions and ambiguities. That idea can be formalized in a general way. The expressiveness of the extension can be varied by changing the conditions on "good".

Uncountable cofinality was used to ensure that well-foundness for S is expressible; it is unclear if that is important. By reflection, the uniqueness of S for all sufficiently well-behaved models implies uniqueness of P n , so P is unique in V. A less expressive extension is the least fixed point logic.

Even a single lfp is more expressive than almost self-referential logic and its above-mentioned multivariable extension , at least for models closed under countable sequences and satisfying basic set theory. Some variations of fixed point logic are described in [5]. About this Item: North-Holland, Condition: Good.