Arabic numeral arithmetic: syntax

As our first case study, we will look at the language of Arabic numeral arithmetic (‘$L_{ANA}$’, for short). This language has expressions like $⌜5⌝$, $⌜(1 + 2)⌝$, $⌜(37 = 43)⌝$, $⌜(3 × 5) = 15⌝$, and so on.

Note that I’m using the corner brackets ($⌜$ and $⌝$), here, in order to distinguish object language expressions (i.e., of Arabic numeral arithmetic) from actual numbers, like $1$ and $2$. The first are just symbols, currently meaningless, while the second are elements of the set $ℕ$ of natural numbers. It’s important to keep these two distinct: while the former are things in the language—the set that we are trying to define and give an interpretation to—the latter will be elements of the domain of the model for the language.

$L_{ANA}$ has a few different kinds of expressions which are useful to distinguish. First, it has numerals. These are strings like $⌜1⌝$, $⌜2⌝$, $⌜57⌝$, and so on. Second, it has complex expressions. These are strings containing the symbols for the addition and multiplication operators, like $⌜(1 + 2)⌝$, $⌜((3 × 4) + 7)⌝$, and so on. Finally, it has equations. These are strings containing the “equals” symbol, like $⌜37 = (5 × 6)⌝$.

The syntax of $L_{ANA}$ can be described by the rules in (2) (based on the alphabet in (1)). Note that we have four categories total: $atom$, $n$, $np$, and $s$.

First, the alphabet:

$Σ_{ANA} = \{⌜0⌝, ..., ⌜9⌝, ⌜(⌝, ⌜)⌝, ⌜+⌝, ⌜×⌝\}$

Now, for the syntax:

Rule 1. $atom = \{⌜0⌝, ..., ⌜9⌝\}$.
Rule 2. $atom ⊆ n$.
Rule 3. If $x, y ∈ n$, then $x^{⌢}y ∈ n$.
Rule 4. $n ⊆ np$.
Rule 5. If $x, y ∈ np$, then $⌜(⌝^{⌢}x^{⌢}⌜+⌝^{⌢}y^{⌢}⌜)⌝, ⌜(⌝^{⌢}x^{⌢}⌜×⌝^{⌢}y^{⌢}⌜)⌝ ∈ np$.
Rule 6. If $x, y ∈ np$, then $x^{⌢}⌜{=}⌝^{⌢}y ∈ s$.
Rule 7. Closure clause: nothing else is in $n$, $np$, or $s$.

In words, these rules say (respectively):

that the atoms are $⌜1⌝$ through $⌜9⌝$;
that any atoms are also numerals;
that you can always take two numerals and concatenate them to make another numeral;
that any numerals are also noun phrases;
that you can always take two noun phrases and concatenate them around the addition or multiplication symbol (with parentheses) to make another noun phrase;
that you can always take two noun phrases and concatenate them around the equals symbol to make a sentence;
and finally (the closure clause), that those things exhaust what you’re allowed to do—nothing else is in the language!

We can define the language of Arabic numeral arithmetic itself as follows:

$L_{ANA} = s ∪ np$:

So, it’s just the set of sentences unioned with the set of noun phrases; in plain English, something is in the language if and only if it is a sentence or a noun phrase.

--- title: "Arabic numeral arithmetic: syntax" bibliography: ../../semantics.bib format: html: css: ../styles.css html-math-method: mathjax mathjax-config: loader: {load: ['[tex]/bussproofs','[tex]/bbox','[tex]/colorbox']} tex: packages: {'[+]': ['bussproofs','bbox','colorbox']} --- ::: {.hidden} $$ \newcommand{\expr}[3]{\begin{array}{c} #1 \\ \bbox[lightblue,5px]{#2} \end{array} ⊢ #3} \newcommand{\ct}[1]{\bbox[font-size: 0.8em]{\mathsf{#1}}} \newcommand{\abbr}[1]{\bbox[transform: scale(0.95)]{\mathtt{#1}}} \def\True{\ct{T}} \def\False{\ct{F}} $$ ::: As our first case study, we will look at the language of Arabic numeral arithmetic ('$L_{ANA}$', for short). This language has expressions like $⌜5⌝$, $⌜(1 + 2)⌝$, $⌜(37 = 43)⌝$, $⌜(3 × 5) = 15⌝$, and so on. Note that I'm using the corner brackets ($⌜$ and $⌝$), here, in order to distinguish *object language* expressions (i.e., of Arabic numeral arithmetic) from actual numbers, like $1$ and $2$. The first are just symbols, currently meaningless, while the second are elements of the set $ℕ$ of natural numbers. It's important to keep these two distinct: while the former are things in the language---the set that we are trying to define and give an interpretation to---the latter will be elements of the domain of the *model* for the language. $L_{ANA}$ has a few different kinds of expressions which are useful to distinguish. First, it has *numerals*. These are strings like $⌜1⌝$, $⌜2⌝$, $⌜57⌝$, and so on. Second, it has *complex expressions*. These are strings containing the symbols for the addition and multiplication operators, like $⌜(1 + 2)⌝$, $⌜((3 × 4) + 7)⌝$, and so on. Finally, it has equations. These are strings containing the "equals" symbol, like $⌜37 = (5 × 6)⌝$. The syntax of $L_{ANA}$ can be described by the rules in (@ex-ana-syntax) (based on the alphabet in (@ex-ana-alphabet)). Note that we have four categories total: $atom$, $n$, $np$, and $s$. First, the alphabet: (@ex-ana-alphabet) $Σ_{ANA} = \{⌜0⌝, ..., ⌜9⌝, ⌜(⌝, ⌜)⌝, ⌜+⌝, ⌜×⌝\}$ Now, for the syntax: (@ex-ana-syntax) Rule 1. $atom = \{⌜0⌝, ..., ⌜9⌝\}$. Rule 2. $atom ⊆ n$. Rule 3. If $x, y ∈ n$, then $x^{⌢}y ∈ n$. Rule 4. $n ⊆ np$. Rule 5. If $x, y ∈ np$, then $⌜(⌝^{⌢}x^{⌢}⌜+⌝^{⌢}y^{⌢}⌜)⌝, ⌜(⌝^{⌢}x^{⌢}⌜×⌝^{⌢}y^{⌢}⌜)⌝ ∈ np$. Rule 6. If $x, y ∈ np$, then $x^{⌢}⌜{=}⌝^{⌢}y ∈ s$. Rule 7. Closure clause: nothing else is in $n$, $np$, or $s$. In words, these rules say (respectively): - that the atoms are $⌜1⌝$ through $⌜9⌝$; - that any atoms are also numerals; - that you can always take two numerals and concatenate them to make another numeral; - that any numerals are also noun phrases; - that you can always take two noun phrases and concatenate them around the addition or multiplication symbol (with parentheses) to make another noun phrase; - that you can always take two noun phrases and concatenate them around the equals symbol to make a sentence; - and finally (the closure clause), that those things *exhaust* what you're allowed to do---nothing else is in the language! We can define the language of Arabic numeral arithmetic itself as follows: - $L_{ANA} = s ∪ np$: So, it's just the set of sentences unioned with the set of noun phrases; in plain English, something is in the language if and only if it is a sentence or a noun phrase.