Chiron

Framework

todo: Make a syntax entry for formal language, and join it with Chiron, Haskell, as well as logical theories.

chiron-moreau.jpg

Chiron is a set theory designed for writing down, reason about and do mathematics. According to its purpose, it has an unusually broad range of basic notions. It contains a rich type system and, most notably, a facility to reason about syntactic expression. So for exmaple, there is a way to express “f(x)”, a function applied to an argument. In conventional set theories, this is only a notation defined in the meta theory.

Von Neumann–Bernays–Gödel set theory can be faithfully interpreted in Chiron. The former is usually axiomatized as a theory over first-order logic (we don't repeat any set theory axioms in this entry), the latter is self-standing in the way of a type theory. This entry gives a sketch of Chirons formalization. It starts out a little like the specification of a programming language and in fact the syntax of expressions is inspired by lisp. Indeed, Chiron feels a little like a programming language where you already know that things like lists and function are do make sense. Using a theory with a small number of logical notions from which others are defined certainly also has it merits. From the pedagogical standpoint for an introduction to foundations of mathematics itself, it is probably better to start from Logic or Type theory and then pass on to Set theory or Category theory. I'm interested in Chiron because this wiki deals with several different theories which are not necessarily well suited to express each other. In any case, due to the fact that most entries are about “everyday mathematics” rather than topics close to pure logic and the logical basic don't shine though all that much.

At the moment, this is the most formal of all the foundational entries. Note that I sometimes use the sign “$\equiv$” in the meta logic to introduce abbreviations for some mathematical expressions. In these cases, some simple pattern matching is up to the human user.

Expressions

Atomic expressions

We want to work with an unending alphabet and providing it is, apart from a finite part, a task of the meta logic. So reasoning with Chiron always starts out with the specification of atomic expressions:

  1. A countably infinite collection of symbols, denoted by $\mathcal S$, which includes certain default key words. (The key words are listed in the last section of this entry. Examples are 'type', 'term', 'formula', 'if', 'op', 'op-app' and 'fun-app'.)
  2. A countable collection of operator names, denoted by $\mathcal O$, which includes certain default built-in operator names. The operator names must be assigned a signatur. That's a sequences of the key words 'type', 'term' and 'formula'. (The operator names are similar to names of typed functions, and the corresponding operators are formalized using the symbols. Examples of the built-in operator names are 'in', 'type-equal' and 'not', but also 'set' and 'class'.)

The default expressions are summarized in Key words and built-in operator names.

Compound expressions

A compound expressions is of the form “$(e_1,e_2,\dots,e_n)$” where $n\ge 0$ and the $e_i$ are atomic (from the section above) or compound expressions. So a general expression is an atomic expressions or a tree, which eventually stores atomic expressions.

Proper and improper expressions

Chiron comes with 25 formation rules. They let you construct proper expressions, which are of the form “$(\operatorname{key word}, \operatorname{foo sequence})$”, where the “$\operatorname{foo sequence}$” is specified to fulfill certain conditions. Conversely the formation rules let you check if a given expression is proper. Importantly, proper expression can contain improper expressions in their “$\operatorname{foo sequence}$”, and so Chiron can reason about those. An example of a formation rule is

$\large\frac{\text{if } x\text{ is a symbol and } \alpha \text{ is assigned 'type'}}{\text{then } (\operatorname{var},x,\alpha) \text{ is assigned 'term'}}$

Example of a proper expression

$(\operatorname{op}, \operatorname{not}, \operatorname{formula}, \operatorname{formula})$

This is what is called an operator and the point is that it stores some information about the operator name 'not'. Reflect upon the syntax: key word in the first entry, operator name in the second, etc.

$(\operatorname{op-app},(\operatorname{op}, \operatorname{not}, \operatorname{formula}, \operatorname{formula}),A)$

Semantics

In general, the overhead to capture some of the meaning of “$\neg$” inside the theory can seem a little of an overkill. But the point is that it actually makes things easier if we introduce many theories with new names and operations. For example we might specify $\in^{\text{ZFC}}$ to be an operator name, define the associated operator and formulate axioms about it as expressions.

A long discussion of the semantics is given in the link in the intro. Roughly speaking, the expressions operators, types, terms and formulas make up the “set theory objects” of Chiron. Terms denote classes (including sets), types denote superclasses (collections of classes), formulas denote truth values and operators denote operations, which construct more expressions. Other expressions are “non-denoting”. However, there is a lisp-like $\operatorname{quote}$-$\operatorname{eval}$ mechanism to map any expression to a “set-level object”. Without going into detail, one must make such an assignment to elements of $\mathcal{S}\cup\mathcal{O}$ and then recursively extend it to trees via ordered pairs.

More examples of expressions

The following link contains a list of some basic proper expression: Chiron Notation. An example for a proper expression which is not built in is the following:

Above in the example section, the expressions $\mathrm{V}$ and $\mathrm{C}$ were defined from the built-in operator 'set' and 'class' and the empty set was defined via definite description. We also have $\mathrm{T}, \mathrm{F}, \bot$ and list and set constructions. What more do you need?

Finally, some terminology: We say that assigning a sequence to operator names provides us with a language $L$ and a language together with a set of axioms $\Gamma$ is a theory in Chiron. Moreover, a bijective mapping from $\mathcal S\cup\mathcal O$ into the sets of some set theory with ordered pair induces a representation of expressions of Chiron. The representation of an expression is called construction.

Lastly, we list the key words and operator names.

Key words

Main key words:

op
type
term
formula
op-app
var
type-app
dep-fun-type
fun-app
fun-abs
if
exists
def-des
indef-des
quote
eval

Extended:

con
uni-exists
forall
set-cons
list-cons
class-abs
dep-type-prod
left-type
right-type
dep-ord-pair
dep-head
dep-tail

Built-in operator names

Names with their signatur assignments:

set             type
class           type
op-names        term
lang            type
expr-sym        type
expr-op-name    term, type
expr            term, type
expr-op         term, type
expr-type       term, type
expr-term       term, type
expr-term-type  term, term, type
expr-formula    term, type
in              term, term, formula
type-equal      type, type, formula
term-equal      term, term, type, formula
formula-equal   formula, formula, formula
not             formula, formula
or              formula, formula, formula

The signature is, roughly, “type of constant” if only one keyword is given, “function type” else. In the operators “$\mathrm{(op,myname,\dots)}$” corresponding to the operatorname $\mathrm{myname}$, the keyword 'term' is replaces by some explicit thing.

Reference

Publications about Chiron on W. M. Farmers home page

Wikipedia: Von Neumann–Bernays–Gödel set theory

Parents

Type theory, Set theory