1.5. Expressions and definable structures

Terms and formulas

Given the first two layers of a theory (a list of types and a language), an expression (that is either a term or a formula), is a finite system of occurrences of symbols, where an occurrence of a symbol in an expression is a place where that symbol is written (for example the term « x+x » has two occurrences of x and one of +). Each expression comes in the context of a given list of available free variables. In expressions of first-order theories and set theory, symbols of the following kinds may occur. Any expression will give (define) a value (either an object or a Boolean) for each possible data of In first-order logic, let us call logical symbols the quantifiers and symbols of para-operators outside the language (equality, connectives and conditional operator): their list and their meaning in each system are determined by the logical framework and the given types list, which is why they are not listed as components of individual theories.

Let us sketch a more precise description (the case of expressions with only free variables and operator symbols, called algebraic terms, will be formalized in set theory in 4.1 for only one type).

Each expression contains a special occurrence of a symbol called its root, while each other occurrence is the root of a unique sub-expression (another expression which we may call the sub-expression of that occurrence). The type of an expression, which will be the type of its values, is given by the type of result of its root. Expressions with Boolean type are formulas; others, whose type belongs to the given types list, are terms (their values will be objects).
Expressions are built successively, in parallel between different lists of available free variables. The first and simplest ones are made of just one symbol (as root, having a value by itself) : constants and variables are the first terms; the Boolean constants 1 and 0 are the simplest formulas.
The next expressions are then successively built as made of the following data:

Display conventions

The display of this list of sub-expressions directly attached to the root requires a choice of convention. For a para-operator symbol other than constants : Parenthesis can also be used to distinguish (separate) the subexpressions, thus distinguish the root of each expression from other occurring symbols. For example the root of (x+y)n is the exponentiation operator.

The role of axioms

An expression is ground if its list of available free variables is empty, so that its value only depends on the system where it is interpreted.
In first-order logic, a statement is a ground formula (which may be true or false depending on the system).

The axioms list of a theory is a set of statements, meant as stating the truth of these statements in intended model(s). Depending on intentions (discussed in 1.A), this may either mean to describe a presumably given model or range of models, or to define the range of accepted models as the class of all systems where all axioms are true, so selected from the range of all possible systems structured by the given language, (rejecting others where some axiom is false).

Variable structures

Usually, only few objects are named by the constants in a given language. Any other objects can be named by a fixed variable, whose status depends on the choice of theory to see it: The difference vanishes in generic interpretations which turn constant symbols into variables (whose values define different models).
By similarity to constants which are particular structures (nullary operators), the concept of variable can be generalized to that of variable structure. But those beyond nullary operations (ordinary variables) escape the above list of allowed symbols in expressions. Still some specific kinds of use of variable structure symbols can be justified as abbreviations (indirect descriptions) of the use of legitimate expressions. The main case of this is explained below, forming a development of the theory ; more possible uses will be introduced in 1.9 (the view of a use as an abbreviation of other works amounts to using a developed version of the logical framework).

Structures defined by expressions

In any theory, one can legitimately introduce a symbol meant either as a variable structure (operator or predicate) or a Boolean variable (nullary predicate, not a "structure"), as abbreviation of, thus defined by, the following data : The variability of this structure is the abbreviation of the variability of all its parameters.

In set theory, any function f is synonymous with the functor defined by the term f(x) with argument x and parameter f (but the domain of this functor is Dom f instead of a type).
The terms without argument define simple objects (nullary operators) ; the one made of a variable of a given type, seen as parameter, suffices to give all objects of its type.

Now let us declare (the range of) the meta-notion of "structure" in one-model theory, and thus those of "operator" and "predicate", as having to include at least all those reachable in this way: defined by any expression with any possible values of parameters. The minimal version of such a meta-notion can be formalized as a role given to the data of an expression with values of its parameters. As this involves the infinite set of all expressions, it is usually inaccessible by the described theory itself : no single expression can suffice. Still when interpreting this in set theory, more operations between interpreted types (undefinable ones) usually exist in the universe. Among the few exceptions, the full set theoretical range of a variable structure with all arguments ranging over finite sets (as interpreted types) with given size limits, can be reached by one expression whose size depends on these limits.

Invariant structures

An invariant structure of a given system (interpreted language), is a structure defined from its language without parameters (thus a constant one). This distinction of invariant structures from other structures, generalizes the distinction between constants and variables, both to cases of nonzero arity, and to what can be defined by expressions instead of directly named in the language.

Indeed any structure named by a symbol in the language is directly defined by it without parameter, and thus invariant. As will be further discussed in 4.8, theories can be developed by definitions, which consists in naming another invariant structure by a new symbol added to the language. Among aspects of the preserved meaning of the theory, are the meta-notions of structure, invariant structure, and the range of theorems expressible with the previous language.

Set theory and Foundations of Mathematics
1. First foundations of mathematics
1.1. Introduction to the foundations of mathematics
1.2. Variables, sets, functions and operations
1.3. Form of theories: notions, objects, meta-objects
1.4. Structures of mathematical systems
1.5. Expressions and definable structures
1.6. Logical connectives
1.7. Classes in set theory
1.8. Binders in set theory
1.9. Quantifiers
1.10. Formalization of set theory
1.11. Set generation principle
Philosophical aspectsTime in model theory
Time in set theory
Interpretation of classes
Concepts of truth in mathematics
2. Set theory (continued) - 3. Algebra - 4. Arithmetic 5. Second-order foundations
Other languages:
FR : 1.5. Expressions et structures définissables