Definición de rango de términos en lenguaje de primer orden

Estoy leyendo Curso de lógica matemática de SM Srivastava. El autor define términos y su rango de un lenguaje de primer orden L como sigue:

El conjunto de todos los términos de una lengua. L es el conjunto más pequeño T de expresiones de L que contiene todas las variables y símbolos constantes y se cierra bajo la siguiente operación: siempre que t 1 , … , t norte ∈ T , F j t 1 … t norte ∈ T , dónde F j es cualquier norte -símbolo de función aria de L . De manera equivalente, todos los términos de un idioma se pueden definir inductivamente de la siguiente manera: las variables y los símbolos constantes son términos de rango 0 ; si t 1 , … , t norte son términos de rango ≤ k , y si F j es un norte -símbolo de función aria, entonces F j t 1 … t norte es un término de rango como máximo k + 1 . Así, el rango de un término t es el número natural más pequeño k tal que t es de rango ≤ k .

Aquí están mis preguntas:

  1. En el paso inductivo de definir el rango, el autor dice si F j es un norte -símbolo de función aria, entonces F j t 1 … t norte es un término de rango como máximo k + 1 y no asigna explícitamente ningún número como su rango. ¿Es esto válido? Por ejemplo, si C es un símbolo constante y F es un símbolo de función unaria en algún lenguaje de primer orden L entonces rango del término C es 0 por definición. ¿Cómo me permite esta definición determinar el rango del término F C o incluso F F C ?
  2. No veo cómo los términos pueden definirse de manera equivalente por la noción de rango cuando la definición misma apela al término "término" mismo. ¿Me estoy perdiendo de algo?

Respuestas (1)

Srivastava no está definiendo el rango de un término por inducción. En cambio, está definiendo el conjunto de términos de rango ≤ k por inducción en k . Entonces (implícitamente) un término es un término de rango ≤ k para algún número natural k . Finalmente, define el rango de un término t ser el menor número natural tal que t tiene rango ≤ k .

Aquí hay una forma un poco más precisa de expresar la definición de Srivastava:

Definimos el conjunto S k de términos de rango como máximo k por inducción en k . S 0 es el conjunto de todas las variables y símbolos constantes. Dado S k , definimos

S k + 1 = S k ∪ { F t 1 … t norte ∣ F  es un  norte -símbolo de función aria, y  t 1 , … , t norte ∈ S k } .
El conjunto de todos los términos es T = ⋃ k ∈ norte S k . dado un término t ∈ T , el rango de t es el menor numero natural k tal que t ∈ S k .

Tenga en cuenta que he hecho explícito el hecho de que S k + 1 contiene S k (es decir, que un término de rango como máximo k también tiene rango como máximo k + 1 ). Srivastava deja esto implícito en su definición.

Por ejemplo, considere el término F C (dónde F es un 1 -símbolo de función aria y C es un símbolo constante). C ∈ S 0 , entonces F C ∈ S 1 . Por otro lado, F C ∉ S 0 (ya que no es una variable o un símbolo constante). Entonces el rango de F C es 1 . Del mismo modo, el rango de F F C es 2 (pero para este, necesitas pensar por un segundo por qué F F C ∉ S 1 ).

¿Está el concepto de rango, tal como se define aquí, relacionado de alguna manera con los alfabetos de ordenación múltiple?
@Jason ¿Qué es un alfabeto ordenado?
Debería haber dicho muchas firmas ordenadas lo siento. Es una forma de "ordenar" qué símbolos se pueden aplicar a qué símbolos, mediante un conjunto de tipos y una función que asigna cada símbolo a un tipo.
@Jason Bueno, debe saber que dada una firma de varios tipos, puede construir el conjunto de términos en esa firma. Y la misma definición de rango se puede aplicar a estos términos. No estoy seguro de qué más hay que decir.
¡Esto tiene mucho sentido! Añadiré esta nota al margen.
Es evidente que todas las expresiones en S 1 es una constante o una variable o de la forma F z 1 z 2 … z norte dónde F es un símbolo de función n-aria y z i son constantes o variables. Así que si F F C estaba en S 1 eso obligaría F C estar en S 0 ¡lo cual claramente tampoco puede ser ese caso! ¿Es correcto este argumento?
@ashK Sí, eso es correcto.
Definición de rango de términos en lenguaje de primer orden
RespuestasAquíPolítica de privacidad1y, 0v