This site is supported by donations to The OEIS Foundation.
Iverson bracket
From OeisWiki
The Iverson bracket, named after Kenneth E. Iverson, is a 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} \,](/w/images/math/9/7/1/9718add3e6207360af5c257b2d3819ea.png)
where 
is a predicate (i.e. a [first-order logic] statement that can be true or false). This notation was introduced by Kenneth E. Iverson in his programming language APL[1][2] (named after the book A Programming Language[3]), while the specific restriction to square brackets was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.[4]
Contents |
Uses
The notation is useful in expressing sums or integrals without boundary conditions. For example
![\sum_{1 \le i \le 10} i^2 = \sum_{i} i^2 \, [1 \le i \le 10]. \,](/w/images/math/d/4/3/d438ff5154ce1e2208b495f30405dfa9.png)
In the first sum, the index 
is limited to be in the range 1 to 10. The second sum is allowed to range over all integers, but where is strictly less than 1 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 formula
which is valid only for 
may be written
![\sum_{1 \le k \le n \atop (k,n) = 1} \!\! k = \frac{n \, (\varphi(n) + [n = 1])}{2}, \,](/w/images/math/8/c/2/8c20a7c5c3b91f1b0027c418f57ed599.png)
which is valid for all positive integers 
.
Special cases
The Kronecker delta notation is a specific case of Iverson notation when the condition is equality
![\delta_{ij} = [i = j]. \,](/w/images/math/b/1/7/b17d8699b618ec6e77e5d14234f9cdb3.png)
The indicator function 
(or characteristic function 
) of a set 
, another specific case, has set membership as its condition
![\mathbf{I}_A(x) = \chi_A(x) = [x \in A]. \,](/w/images/math/f/2/b/f2b7c4e45c7fd8f866daf1a74d2018d6.png)
The sign function and Heaviside step function are also easily expressed in this notation
![\sgn(x) = [x > 0] - [x < 0], \,](/w/images/math/7/a/a/7aad9e6795440aa57f5666a361c9ab2b.png)
![H(x) = [x > 0] + \frac{1}{2} [x = 0]. \,](/w/images/math/7/7/a/77a7229bfda5b29950b7901acfb47c0e.png)
And the trichotomy of the reals can be expressed
![[a < b] + [a = b] + [a > b] = 1. \,](/w/images/math/3/2/d/32d13867f592893e492637590d555ea3.png)
See also
Notes
- ↑ Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics, Section 2.2: Sums and Recurrences.
- ↑ Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (2nd ed.). Reading, MA: Addison-Wesley Publishing Company. pp. xiii+657. ISBN 0-201-55802-5.
- ↑ Iverson, Kenneth E. (1962). A Programming Language. Wiley. ISBN 0-471-43014-5.
- ↑ Graham, Knuth, and Patashnik (1994).
References
- 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.
