Definition:Interval/Notation/Wirth
Definition
The notation used on this site to denote an interval of an ordered set $\struct {S, \preccurlyeq}$ is a fairly recent innovation, and was introduced by Niklaus Emil Wirth:
| \(\ds \openint a b\) | \(:=\) | \(\ds \set {s \in S: \paren {a \prec s} \land \paren {s \prec b} }\) | Open Interval | |||||||||||
| \(\ds \hointr a b\) | \(:=\) | \(\ds \set {s \in S: \paren {a \preccurlyeq s} \land \paren {s \prec b} }\) | Right Half-Open Interval | |||||||||||
| \(\ds \hointl a b\) | \(:=\) | \(\ds \set {s \in S: \paren {a \prec s} \land \paren {s \preccurlyeq b} }\) | Left Half-Open Interval | |||||||||||
| \(\ds \closedint a b\) | \(:=\) | \(\ds \set {s \in S: \paren {a \preccurlyeq s} \land \paren {s \preccurlyeq b} }\) | Closed Interval |
Unbounded Intervals
In Wirth interval notation, unbounded intervals of an ordered set $\struct {S, \preccurlyeq}$ are written as follows:
| \(\ds \hointr a \to\) | \(:=\) | \(\ds \set {x \in S: a \preccurlyeq x}\) | ||||||||||||
| \(\ds \hointl \gets a\) | \(:=\) | \(\ds \set {x \in S: x \preccurlyeq a}\) | ||||||||||||
| \(\ds \openint a \to\) | \(:=\) | \(\ds \set {x \in S: a \prec x}\) | ||||||||||||
| \(\ds \openint \gets a\) | \(:=\) | \(\ds \set {x \in S: x \prec a}\) | ||||||||||||
| \(\ds \openint \gets \to\) | \(:=\) | \(\ds \set {x \in S} = S\) |
Source of Name
This entry was named for Niklaus Emil Wirth.
Historical Note
The term Wirth Interval Notation was invented by $\mathsf{Pr} \infty \mathsf{fWiki}$.
As such, it is not generally expected to be seen in this context outside $\mathsf{Pr} \infty \mathsf{fWiki}$.
The double-dot convention appears to have originated with Niklaus Emil Wirth during the course of his design of the Pascal programming language. It can be considered as either an incomplete ellipsis: "$\ldots$" or as a colon "$:$" lying on its side: $.\,.$
In Concrete Mathematics: A Foundation for Computer Science, 2nd ed. of $1994$ by Ronald L. Graham, Donald E. Knuth and Oren Patashnik, it is stated that this notation was:
- suggested by C.A.R. Hoare and Lyle Ramshaw
but little corroboration can be found on the Internet to support this.
C.A.R. Hoare had in fact adopted the ellipsis notation: $\paren {a \ldots b}$ in a $1972$ article:
- ... we introduce the following notations for open and closed intervals:
While it is left unstated who those others were in the we, it can be noted that Wirth is cited in the references, along with Robert W Floyd, Adriaan van Wijngaarden and Peter Naur.
Ramshaw's contribution appears to be rather more limited. Apart from his $1979$ thesis, in which he expands on the work of Floyd and Hoare, he appears to have had no active involvement in the invention of this notation, and appears simply to have adopted it.
It is suggested that Ramshaw's name is attached to this more strongly than is perhaps merited. Note that Ramshaw was a student of Knuth's, and the latter may have shown favouritism when attributing the notation.
Ultimately, evidence is strongly suggestive that the invention of this notation was completely the work of Wirth; the possible attribution to others may be because of their decision to adopt it.