Iverson bracket

From Wikipedia, the free encyclopedia

In mathematics, the Iverson bracket is a convenient notation that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise. More exactly,

$[P] = \begin{cases} 1; & \mbox{if } P \mbox{ is true;} \\ 0; & \mbox{otherwise.} \end{cases}$

where P is a statement that can be true or false. This notation was introduced by its namesake Kenneth E. Iverson in his programming language APL.^[1]

1 Uses
2 Special Cases
3 References
4 External links

[edit] Uses

The notation is useful in expressing sums or integrals without boundary conditions. For example

$\sum_{0\le i \le 10} i^2 = \sum_{i} i^2[0 \le i \le 10]$

In the first sum, the index $i$ is limited to be in the range 0 to 10. The second sum is allowed to range over all integers, but where i is strictly less than 0 or strictly greater than 10, the summand is 0, contributing nothing to the sum. Such use of the Iverson bracket can permit easier manipulation of these expressions.

Another use of the Iverson bracket is to simplify equations with special cases. For example, the Fibonacci numbers satisfy the identity $F n = F n - 1 + F n - 2$ for all $n$ except $n = 1$ (if $F n$ is defined to be 0 for negative $n$ ). This identity can be made general using the Iverson bracket:^[2]

F n = F n - 1 + F n - 2 + [n = 1]

[edit] Special Cases

The Kronecker delta notation is a specific case of Iverson notation when the condition is equality. That is,

$\delta_{ij} = [i=j]\,$

The indicator function, another specific case, has set membership as its condition:

$\mathbf{I}_A(x) = [x\in A]$

The sign function is also easily expressed in this notation:

sgn(x) = [x > 0] - [x < 0]

[edit] References

^ Ronald Graham, Donald Knuth, and Oren Patashnik. "Concrete Mathematics." Section 2.2: Sums and Recurrences.
^ Ronald Graham, Donald Knoth, and Oren Patashnik. "Concrete Mathematics." Section 7.3: Solving Recurrences.

[edit] External links

Donald Knuth, "Two Notes on Notation", American Mathematical Monthly, Volume 99, Number 5, May 1992, pp. 403–422. (TeX, arXiv:math/9205211)
Kenneth E. Iverson, "A Programming Language", New York: Wiley, p. 11, 1962.