Objetos bien formadoseditar

Si una colección de objetos (símbolos y secuencias de símbolos) debe considerarse «bien formada», debe existir un algoritmo para determinar, deteniéndose con una respuesta de «sí» o «no», si el objeto está bien formado o no (en matemáticas, un wff abrevia la fórmula bien formada). Este algoritmo, en el extremo, podría requerir (o ser) una máquina de Turing o una máquina equivalente a Turing que «analiza» la cadena de símbolos tal como se presenta como «datos» en su cinta; antes de que una máquina universal de Turing pueda ejecutar una instrucción en su cinta, debe analizar los símbolos para determinar la naturaleza exacta de la instrucción y/o el dato codificado allí. En casos más simples, una máquina de estado finito o un autómata de empuje pueden hacer el trabajo. Enderton describe el uso de» árboles » para determinar si una fórmula lógica (en particular, una cadena de símbolos con paréntesis) está bien formada o no. Alonzo Church 1934 describe la construcción de «fórmulas» (de nuevo: secuencias de símbolos) como está escrito en su cálculo λ mediante el uso de una descripción recursiva de cómo iniciar una fórmula y luego construir sobre el símbolo inicial mediante concatenación y sustitución.

Ejemplo: Church especificó su cálculo λ de la siguiente manera (la siguiente es una versión simplificada que deja fuera las nociones de variable libre y encuadernada). Este ejemplo muestra cómo una teoría de objetos comienza con una especificación de un sistema de objetos de símbolos y relaciones (en particular mediante el uso de concatenación de símbolos):

(1) Declare los símbolos: {,}, (,), λ, más un número infinito de variables a, b, c, …, x,… (2) Definir fórmula: una secuencia de símbolos (3) Define la noción de «fórmula bien formada» (wff) recursivamente comenzando con la «base» (3.i):

• (3.1) (base) Una variable x es un wff
• (3.2) Si F y X son wff, entonces {F}(X) es un wff; si x aparece en F o X, se dice que es una variable en {F}(X).
• (3.3) Si M está bien formado y x aparece en M, entonces λx es un wff.

(4) Definir varias abreviaturas:

• {F} abrevia a F(X) si F es un símbolo único
• F {\displaystyle {{F}}}
  

  abrevia a {F}(X,Y) o F(X,Y) si F es un símbolo único

• λx1λx2…] abrevia a λx1x2…xn•M
• λab•a(b) abrevia a 1
• λab•a(a(b)) abrevia a 2, etc.

(5) Define la noción de «sustitución» de la fórmula N para la variable x a lo largo de M (Church 1936)

Objetos indefinidos (primitivos) Editar

Ciertos objetos pueden ser «indefinidos» o «primitivos» y recibir definición (en términos de su comportamiento) mediante la introducción de los axiomas.

En el siguiente ejemplo, los símbolos indefinidos serán { ※ ,∫,∫}. Los axiomas describirán sus comportamientos.

Axiomeseditar

Kleene observa que los axiomas se componen de dos conjuntos de símbolos: (i) los objetos indefinidos o primitivos y los que se conocen previamente. En el siguiente ejemplo, se sabe previamente en el siguiente sistema (O,※,∫,∫) que O constituye un conjunto de objetos (el «dominio»), ※ es un objeto en el dominio, ↀ y ∫ son símbolos para las relaciones entre los objetos, => indica el operador lógico «SI ENTONCES», ε es el símbolo que indica «es un elemento del conjunto O», y «n» se utilizará para indicar un elemento arbitrario de conjunto de objetos O.

Después de (i) una definición de «cadena S»—un objeto que es un símbolo ※ o símbolos concatenados※, ∫ o∫, y (ii) una definición de cadenas «bien formadas» ※ (base)※ y ∫S, ∫ S donde S es cualquier cadena, vienen los axiomas:

• ↀ ※ =>※, en palabras: «SI ↀ se aplica al objeto※, ENTONCES el objeto※.»
• ∫n ε O, en palabras «SI ∫ se aplica al objeto arbitrario» n «en O, ENTONCES este objeto ∫n es un elemento de O».
• εn ε O, «SI ↀ se aplica al objeto arbitrario» n «en O, entonces este objeto ↀn es un elemento de O».
• ↀ ∫n = > n, » SI ↀ se aplica al objeto ∫n, el objeto n resulta.»
• ∫nn = > n, » SI ∫ se aplica al objeto objectn, el objeto n resulta.»

Entonces, ¿cuál podría ser la interpretación (prevista) de estos símbolos, definiciones y axiomas?

Si definimos ※ como «0», ∫ como» sucesor «y ↀ como» predecesor», entonces ↀ ※ => ※ indica» resta adecuada «(a veces designada por el símbolo∸, donde» predecesor » resta una unidad de un número, por lo tanto 0 = 1 = 0). La cadena «∫ ∫ n = > n » indica que si primero se aplica el sucesor a un objeto arbitrario n y luego el predecesor ↀ se aplica a ∫n, el resultado es el n original.»

¿Este conjunto de axiomas es «adecuado»? La respuesta adecuada sería una pregunta: «¿Adecuada para describir qué, en particular?»»Los axiomas determinan a qué sistemas, definidos desde fuera de la teoría, se aplica la teoría.»(Kleene 1952: 27). En otras palabras, los axiomas pueden ser suficientes para un sistema pero no para otro.

De hecho, es fácil ver que este conjunto de axiomas no es muy bueno, de hecho, es inconsistente (es decir, produce resultados inconsistentes, sin importar su interpretación):

Ejemplo: Define ※ como 0, ∫ ※ como 1 y ↀ1 = 0. Desde el primer axioma,※ ※ = 0, entonces ∫ ∫ ※ = ∫0 = 1. Pero el último axioma especifica que para cualquier n arbitrario, incluido ※ = 0, ∫nn => n, por lo que este axioma estipula que ∫00 => 0, no 1.

Observe también que el conjunto de axiomas no especifica que ∫n ≠ n. O, exceptuando el caso n=※, ↀn ≠ n. Si incluyéramos estos dos axiomas, necesitaríamos describir las nociones intuitivas «iguales» simbolizadas por = y no iguales simbolizadas por ≠.