# Formal Languages

Mathematics, as a human endeavor, is much more than a formal language processing. However modern mathematics would not be possible without the development of a special, relatively formal language. Mathematical expositions are written in a mixture of a common and that special mathematical language. The proportion of each depends on the level of complexity of the subject, the level of sophistication of the intended audience, and the taste of the writer. A presentation made exlusively in the mathematical language would be well nigh incomprehensible even to specialists, see, for example, a page from Russell and Whitehead's *Principia Mathematica*.

The *Model Theory* which is the foundation of the *Non-standard Analysis* is one of the branches of mathematics where employment of formal languages is unescapble. A (formal) language consists of an alphabet of symbols that combine into formulas (also called statements or sentences) and the rules of building the formulas. All languages of interest are extensions of a basic logical language. The alphabet of that language consists of

individual variables: | a, b, ..., y, z, ... (may be indexed, they all are called propositional variable) | ||
---|---|---|---|

logical connectives: | ¬ (not), ∨ (or, disjunction), ∧ (and, conjunction), → (implication), ↔ (equivalence), ... | ||

logical quantors (or quantors): | ∀ (for all, universal quanatifier), ∃ (exists, existential quantifier) | ||

equality: | = (equal) | ||

parentheses | (, ), [, ], {, }, ... (grouping symbols and precedence modifiers) | ||

constants | 0, 1, e, π, ω - could be anything(this is just an example of possible constants. Different theories introduce different constants as needed.) |

The rules of a language specify the manner in which formulas may be constructed. For example,

- variables are formulas,
- if φ and ψ are formulas, then so are ¬φ, ¬ψ, φ∧ψ, φ∨ψ, ..., (φ), [ψ], ...
- if φ is a formula that includes a variable x, then
∀x φ(x) and∃x φ(x) are formulas.

A variable in a formula to which a quantor has been applied is called *bound*; otherwise, the variable is *free*. A bound variable is just a place holder. There is no significance of a particular symbol used to specify the variable. E.g.,

Here are examples of formulas:

- x = (y ∨ z),
- ∀ (x = x),
- ∀x∀y∀z [(x = y) ∧ (y = z) → (x = z)],
- ∀x∀y∃z {¬(z = x) ∧ ¬(z = y)}.

The first does not say much, except that, if need be, x can be used in lieu of y ∨ z. The second asserts reflexivity of equality; the third stipulates the transitivity of equality. The fourth asserts that there are at least three objects. In the first formula all the variables are free; in the rest, all the variables are bound.

In mathematics, one often extends the language with *convenience* symbols. For example, *x ≠ y*

- ∀x∀y∃z {(z ≠ x) ∧ (z ≠ y)}.

Languages, like the one defined above, underlie every attempt at formalization of mathematical theories, each getting associated with a language extension. Extensions may augment the alphabet with new symbols, of which some may be said to be *constant*. Extensions also
add rules for formula construction.

The language of arithmetic extends the above language with two symbols "0" and "1" (constants), two operations "+" and "×" and a relation "<". The notion of *formula* is subsequently extended to include individual constants, operations, like x + 1, comparisons, like 0 < 1, and (implied) rules

To define the language of Group theory one does not need that much. For multiplicative groups, we may only add symbol "1" and operation "×"; for additive groups, the addons are "0" and "+". In general, we need a constant for a special, *unity* element, say, *e*, and a symbol of operation, say, "•". In a group language we encounter formulas like

- ∀x {[x •
*e*= x] ∧ [*e*• x = x]}, - ∀x∀y∀z {(x • y) • z = x • (y • z)},
- ∀x∃y {[x • y =
*e*] ∧ [y • x =*e*]}.

Both multiplicative and additive groups are models of Group theory.

The language, as defined above, falls into the category of *first-order* languages. It only allows binding of variables, as above, but not formulas (nor functions or predicates that were omitted altogether from the specifications.)

[an error occurred while processing this directive]

### References

- D. Marker,
__Logic and Model Theory__, in T. Gowers (ed.),*The Princeton Companion to Mathematics*, Princeton University Press, 2008, pp. 635-646 - A. Robinson,
*Non-standard Analysis*, Princeton University Press (Rev Sub edition), 1996 - R. M. Smullyan,
*First-Order Logic*, Dover, 1995

|Contact| |Front page| |Contents| |Up| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny