Corchete de Iverson

En matemáticas, el corchete de Iverson, nombrado en honor al matemático canadiense Kenneth Iverson, es una notación utilizada para generalizar la delta de Kronecker. Convierte cualquier proposición lógica en un número que es 1 si la proposición es satisfecha, y 0 si no, y es generalmente escrita colocando la proposición entre corchetes (o paréntesis) rectos:

${\displaystyle [P]={\begin{cases}1&{\text{si }}P{\text{ es verdadero;}}\\0&{\text{de otra forma}}\end{cases}}}$

donde ${\displaystyle P}$ es una declaración que puede ser verdadera o falsa.

En contexto de sumatoria, la notación puede ser utilizada para escribir cualquier suma como una suma infinita sin límites:

${\displaystyle \sum _{k}f(k)\,[P(k)]=\sum _{P(k)}f(k),}$

Si ${\displaystyle P(k)}$ es cualquier propiedad del entero ${\displaystyle k}$.

Nótese que, por esta convención, un sumando ${\displaystyle f(k)[{\textbf {falso}}]}$ debe evaluar a 0 independientemente de si ${\displaystyle f(k)}$ está definida. Igualmente para la multiplicatoria:

${\displaystyle \prod _{k}f(k)^{[P(k)]}=\prod _{P(k)}f(k).}$

La notación fue originalmente introducida por Kenneth Iverson en su lenguaje de programación APL,^[1][2] aunque limitado a operadores simples relacionales entre paréntesis, mientras que la generalización a declaraciones arbitrarias, limitada notacionalmente a paréntesis rectos, y las aplicaciones en sumatoria, defendida por Donald Knuth para evadir ambigüedades en expresiones lógicas entre paréntesis.^[3]

Propiedades

Existe una correspondencia directa entre aritmética en los corchetes de Iverson, la lógica y conjuntos de operaciones. Por ejemplo, deja a ${\displaystyle A}$ y ${\displaystyle B}$ ser conjuntos y a ${\displaystyle P(k_{1},\dots )}$ cualquier propiedad de enteros; entonces tenemos

${\displaystyle [P\land Q]=[P][Q],\qquad [\neg P]=1-[P].}$

${\displaystyle [k\in A]+[k\in B]=[k\in A\cup B]+[k\in A\cap B].}$

${\displaystyle [\forall m\ .\ P(k,m)]=\prod _{m}[P(k,m)].}$

${\displaystyle [\exists m\ .\ P(k,m)]=\min {\Bigl (}1,\sum _{m}[P(k,m)]{\Bigr )}=1-\prod _{m}{\Bigl (}1-[P(k,m)]{\Bigr )}}$.

${\displaystyle \#{\{m\mid \exists m\ .\ P(k,m)\}}=\sum _{m}[P(k,m)].}$

Ejemplos

La notación permite mover condiciones de límites de sumatorias (o integrales) como factores separados dentro del sumando, liberando espacio alrededor del operador de sumatoria, pero más importante permitiéndole ser manipulado algebraicamente.

Regla del doble recuento

Nostros mecánicamente derivamos una regla muy conocida para manipular sumas utilizando los corchetes de Iverson:

${\displaystyle {\begin{aligned}\sum _{k\in A}f(k)+\sum _{k\in B}f(k)&=\sum _{k}f(k)\,[k\in A]+\sum _{k}f(k)\,[k\in B]\\&=\sum _{k}f(k)\,([k\in A]+[k\in B])\\&=\sum _{k}f(k)\,([k\in A\cup B]+[k\in A\cap B])\\&=\sum _{k\in A\cup B}f(k)\ +\sum _{k\in A\cap B}f(k).\end{aligned}}}$

Intercambio de sumatorias

La conocida regla ${\displaystyle \textstyle \sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k)}$ es, de la misma manera, fácilmente derivada como:

${\displaystyle {\begin{aligned}\sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)&=\sum _{j,k}f(j,k)\,[1\leq j\leq n]\,[1\leq k\leq j]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq j\leq n]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq n]\,[k\leq j\leq n]\\&=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k).\end{aligned}}}$

Cálculo

Por ejemplo, la función phi de Euler, que cuenta el número de enteros positivos hasta ${\displaystyle n}$, los cuales son primos entre sí con ${\displaystyle n}$, puede ser expresada como

${\displaystyle \phi (n)=\sum _{i=1}^{n}[\gcd(i,n)=1],\qquad {\text{para }}n\in \mathbb {N} ^{+}.}$

Simplificación de casos especiales

Otro uso de los corchetes de Iverson es el simplificar ecuaciones con casos especiales. Por ejemplo, la fórmula

${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)}$

es válida para ${\displaystyle n>1}$ pero es cancelada por ${\displaystyle {\tfrac {1}{2}}}$ para ${\displaystyle n=1}$. Para obtener una identidad válida para todos los enteros positivos ${\displaystyle n}$ (ej. todos los valores donde ${\displaystyle \phi (n)}$ está definido), un término de corrección involucrando al corchete de Iverson puede ser agregado:

${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n(\varphi (n)+[n=1])}$

Funciones comunes

Muchas funciones comunes, especialmente aquellas con una definición natural pieza por pieza, puede ser expresada en términos del corchete de Iverson. La notación de la delta de Kronecker es un caso especial de la notación de Iverson cuando la condición es la igualdad. Esto es,

${\displaystyle \delta _{ij}=[i=j].}$

La función indicatriz, a veces denotada ${\displaystyle \mathbf {1} _{A}(x)}$, ${\displaystyle \mathbf {I} _{A}(x)}$ o ${\displaystyle \chi _{A}(x)}$, es un corchete de Iverson con correspondencia definida como su condición:

${\displaystyle \mathbf {I} _{A}(x)=[x\in A]}$.

Las funciones escalón de Heaviside, signo,^[1] y valor absoluto son fácilmente expresadas en esta notación:

${\displaystyle H(x)=[x>0]}$,

${\displaystyle \operatorname {sgn}(x)=[x>0]-[x<0]}$,

y

${\displaystyle {\begin{aligned}|x|&=x[x>0]-x[x<0]\\&=x([x>0]-[x<0])\\&=x\cdot \operatorname {sgn}(x).\end{aligned}}}$

Las funciones de comparación máximo y mínimo (que devuelve el más grande o el más chico de dos argumentos) puede ser escrita como

${\displaystyle \max(x,y)=x[x>y]+y[x\leq y]}$ y

${\displaystyle \min(x,y)=x[x\leq y]+y[x>y]}$.

Las funciones piso y techo pueden ser expresadas como

${\displaystyle \lfloor x\rfloor =\sum _{n}n\cdot [n\leq x<n+1]}$

y

${\displaystyle \lceil x\rceil =\sum _{n}n\cdot [n-1<x\leq n],}$

donde el índice ${\displaystyle n}$ de la sumatoria es entendido como que alcanza a todos los enteros.

La función rampa puede ser expresada como

${\displaystyle R(x)=x\cdot [x\geq 0].}$

La tricotomía de los reales es equivalente a la identidad

${\displaystyle [a<b]+[a=b]+[a>b]=1.}$

La función de Möbius tiene la propiedad (y puede ser definida por recurrencia) como

${\displaystyle \sum _{d|n}\mu (d)\ =\ [n=1].}$^[4]

Formulación en términos de funciones comunes

En los años 1830, Guglielmo Libri Carucci dalla Sommaja utilizó ${\displaystyle 0^{0^{x}}}$ como un reemplazo para lo que hoy día se escribiría como ${\displaystyle [x>0]}$, al igual que otras variantes como ${\displaystyle (1-0^{0^{-x}})(1-0^{0^{x-a}})}$ para ${\displaystyle [0\leq x\leq a]}$.^[3] De hecho, siguiendo las convenciones habituales, estas cantidades con iguales donde está definido que ${\displaystyle 0^{0^{x}}}$ es 1 si ${\displaystyle x>0}$, 0 si ${\displaystyle x=0}$, y de otra forma indefinido.

Referencias

1. Iverson, Kenneth (1962). A Programming Language (en inglés). John Wiley & Sons. p. 11. ISBN 978-0-471-43014-8.
2. Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994). «Section 2.2: Sums and Recurrences». Concrete Mathematics (en inglés). Addison-Wesley. ISBN 0-201-55802-5.
3. Knuth, Donald (1992). «Two Notes on Notation». American Mathematical Monthly (en inglés) (Mathematical Association of America) 99 (5): 403-422. ISSN 0002-9890. arXiv:math/9205211.
4. Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994). «Section 4.9: Phi and Mu». Concrete Mathematics (en inglés). Addison-Wesley. ISBN 0-201-55802-5.

• Datos: Q2114682