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., ∀x φ(x) and ∀y φ(y) denote exactly same formula.

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 is a common replacement for ¬(x = y). Thus the fourth statement can be written as

  • ∀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 (a×(b + c) = a×b + a×c), or properties (∀x [x + 0 = x]), etc.

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.)


Back to What Is Infinity?

References

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

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

Copyright © 1996-2018 Alexander Bogomolny

71491333