Igualdad de Kleene

En matemáticas , igualdad de Kleene , ^{[ 1 ]} o igualdad fuerte , (${\displaystyle \simeq }$) es un operador de igualdad en funciones parciales , que establece que en un argumento dado o bien ambas funciones no están definidas, o bien ambas están definidas y sus valores en ese argumento son iguales.

Por ejemplo, si tenemos funciones parciales${\displaystyle f}$y${\displaystyle g}$,${\displaystyle f\simeq g}$significa que para cada${\displaystyle x}$: ^{[ 2 ]}

• ${\displaystyle f(x)}$y${\displaystyle g(x)}$ambos están definidos y${\displaystyle f(x)=g(x)}$
• o${\displaystyle f(x)}$y${\displaystyle g(x)}$ambos son indefinidos.

Algunos autores ^{[ 3 ]} están utilizando la "cuasi-igualdad", que se define de la siguiente manera: ${\displaystyle (y_{1}\sim y_{2}):\Leftrightarrow ((y_{1}\downarrow \lor y_{2}\downarrow )\longrightarrow y_{1}=y_{2}),}$ donde la flecha hacia abajo significa que el término a su izquierda está definido. Entonces es posible definir la igualdad fuerte de la siguiente manera: ${\displaystyle (f\simeq g):\Leftrightarrow (\forall x.(f(x)\sim g(x))).}$

• Cutland, Nigel (1980). Computabilidad: una introducción a la teoría de funciones recursivas . Cambridge University Press. pág.  251. ISBN 978-0-521-29465-2.