# What do the symbols M and N mean in this definition of lambda terms?

I am learning lambda calculus from the book https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and do not understand the meaning of the following symbols.

The definition of the lambda terms is:

Lambda terms: $$\mathit{M,N} ::= x | (M N) | (λx.M)$$

The question is, what do $$\mathit{M}$$ and $$\mathit{N}$$ mean?

• @dkaeae I've seen you add Mathjax into titles in a few edits, where I do not think it was nessecary. I recommend against using Mathjax in titles unless nessecary: titles appear in quite a few places where Mathjax is not rendered, for one. Please have a look at my advice on this, thanks. (Do not see this as a discouragement to editing, btw. Your edits usually are good and your effort is much appreciated!) – Discrete lizard Feb 22 '19 at 19:03

I suggest you read the page following the supposedly cryptic notation:

The above Backus-Naur Form (BNF) is a convenient abbreviation of the following equivalent, more traditionally mathematical definition:

Definition. [...]

In said definition, it is stated that $$M$$ and $$N$$ are simply arbitrary lambda terms. (In a nutshell, it is an inductive definition.)

As to why the author prefers this notation, it is stated right after the definition:

Comparing the two equivalent definitions, we see that the Backus-Naur Form is a convenient notation because: [...] the use of distinct meta-symbols for different syntactic classes ($$x$$, $$y$$, $$z$$ for variables and $$M$$, $$N$$ for terms) eliminates the need to explicitly quantify over the sets [of variables and lambda terms].

• Does lambda terms consist of constant, application and lambda abstraction? What does the author try to explain? – zero_coding Feb 22 '19 at 15:02
• "Does lambda terms consist of constant, application and lambda abstraction?" Yes, this follows directly from the definition (since, as I have mentioned, it is an inductive definition). "What does the author try to explain?" I am afraid I do not understand your question. To which part of the text are you referring to? – dkaeae Feb 22 '19 at 15:04
• what is the meaning of the symbol $\mathit{Λ}$ in The set of lambda terms is the smallest subset $Λ ⊆ A∗$ on the page 12 at very beginning ? – zero_coding Feb 22 '19 at 15:09
• $\Lambda$ denotes the set of lambda terms (since $\Lambda$ is a subset of $A^\ast$ and it is the smallest subset with the properties that follow). This kind of phrasing is pretty standard in mathematical texts. – dkaeae Feb 22 '19 at 15:13
• It seems, that I must learn first discrete math to understand all these symbols, because I haven't math background. – zero_coding Feb 22 '19 at 15:17