1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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!) $\endgroup$ – Discrete lizard Feb 22 at 19:03
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Does lambda terms consist of constant, application and lambda abstraction? What does the author try to explain? $\endgroup$ – zero_coding Feb 22 at 15:02
  • $\begingroup$ "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? $\endgroup$ – dkaeae Feb 22 at 15:04
  • $\begingroup$ 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 ? $\endgroup$ – zero_coding Feb 22 at 15:09
  • $\begingroup$ $\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. $\endgroup$ – dkaeae Feb 22 at 15:13
  • $\begingroup$ It seems, that I must learn first discrete math to understand all these symbols, because I haven't math background. $\endgroup$ – zero_coding Feb 22 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.