User:Physis/Language base

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Although we ofter refer to the “text” of object language as “finite sequences” over a set of “letters”, but sometimes we axiomatize this explicitly. A language base declares the set of “letters” axiomatizes sequencing operations. This mini-theory formalizes what we think of informally as as “finite sequences”. Language base talks almost nothing of the syntax of the object languege (althoght the letters may coincide with those of the object languge, but also this is not necessary): treatment of syntax must be built upon it. See the notion in [1], but also — with somewhat different terminology — at Tarski).

For better readability, let us denote the respective singleton sequences with underlining:

For better readability, let us denote the respective singleton sequences with underlining:


Now we axiomatize the notion of sequence. Well-chosen axioms provide appropriate distinctions and indentifications, unambiguity, and exclude alien objects.

Let us use to denote empty sequence. Now we have more ways to step further.


One approach uses a similar terminology as the concept of list in functional programming: we can use a : operation, making form a letter and an (already made) sequence (possibly also the empty one) a new sequence. We can begin the axiomatization like this:

we can define concatenation by recursion.

Concatenation and singletons[edit]

In another approach concatenation is a primitive (mainly denoted by ). Also a new operaration may be introduced: singleton sequece building, let us denote it here e.g. by . Axiomatization would begin than like this:

A specific care must be taken of concatenation:

  • associativity
  • unambiguity

must be declared by appropriate axioms.


We resorted many-sorted logic in the above things. Mybe this can be avoided. But then, each letter must be regarded as a standlone case at the axioms discussing distinctions:

Failed to parse (syntax error): {\displaystyle \0 \neq \underline s}


Modelling sequences[edit]

We can skip this level: we can choose a more denotational approach, and refer to sequences as directly building their set-theoretic models. E.g. somethng like where


with sequencing operations defnied e.g. something like


Syntax tree[edit]

Another alternative way: to build syntax tree directly, not resorting to an underlying representation with sequences.


  1. ^ Ruzsa, Imre: Logikai szintaxis es szemantika