Formalización de la "no basura, no hay confusión"

Question

Goguen ha popularizado la inicial de álgebra de vista de la semántica a través de su "no hay basura, no hay confusión" eslogan. Por "no deseado", que significa que los modelos de una teoría de la presentación no debe tener elementos innecesarios, y "sin confusión" que los términos no debe ser asignada a la igualdad de valores, a menos que seguramente son iguales. A veces, "no basura" es también interpretado como cada elemento en el modelo es una denotación de un término, mientras que "sin confusión" como dos términos diferentes denotan diferentes elementos en el modelo. [Estos son clásicamente equivalente declaraciones, pero no son intuinistically equivalente, por lo menciono ambos].

Mis preguntas son:

1. ¿Qué es una "buena" de la formalización de este lema? Con esto me refiero a una declaración explícita de que "no hay basura, no hay confusión" en el meta-lógica (ya que estamos hablando de modelos), donde la lógica de la fuerza de la correspondiente declaración se entiende bien.

2. Hay lógica en que estos requisitos pueden ser internalizados?

3. ¿Cuál sería el correspondiente lema de "no hay basura, no hay confusión" para el final coalgebras?

Answer 1

Mi manera de entender cada uno de los eslóganes de la siguiente manera:

1. "No deseado" yo sólo significa que hay un principio de inducción es válido, es decir, debemos buscar modelos iniciales en la correspondiente categoría de álgebras para la teoría. Esto también implica que cada elemento de la modelo en la imagen de la interpretación de la teoría algebraica.

   Es de suponer que el dualization a coalgebras sería sólo la validez de la utilización de bisimilarity para demostrar la igualdad.

2. "Sin confusión" se interpreta tradicionalmente significa que debemos buscar modelos en los que dos elementos del modelo son semánticamente equivalentes si y sólo si el correspondiente sintaxis seguramente son iguales. Este es el bizarro requisito, ya que asciende a la necesidad de que el modelo de ser isomorfo al término de modelo! Y, sin embargo, Goguen y la especificación algebraica de la comunidad, fueron enfáticamente no contento con decretando el término modelo para ser la intención de modelo -- que trabajar muy duro para conseguir el "derecho" del modelo.

   Yo personalmente (es decir, no sé de que nadie cree esto) tome la forma en que este requisito está escrita para ser un artefacto de la historia de la especificación algebraica. Si mal no recuerdo, que comenzó con la puramente algebraica de las teorías, es decir, las teorías en las que los axiomas ecuacionales son todos puro igualdades. (E. g., los axiomas para grupos). Ahora, por supuesto, cada teoría algebraica tiene un degenerado modelo, ya que el modelo de elementos valida todas las igualdades. Entonces, la no-confusión principio es la intención de descartar esos degenerados modelos.

   En estos días, por supuesto, la especificación algebraica multitud no tiene ningún problema con las teorías con las desigualdades (por ejemplo, el campo de los axiomas), y creo que esta libertad nos permite el estado de la no-confusión principio de una mejor manera. Es decir, debemos diseñar teorías algebraicas cuyos modelos son categóricos. Es decir, queremos teorías para que todos los modelos son isomorfos. Esto implica que el tradicional no-confusión criterio, y explica también por qué la gente intenta ajustar la firma en el momento que no puedo probarlo. (Por supuesto, esto no es de primer orden de la propiedad en general, como la necesidad de orden superior de la lógica o de la teoría de conjuntos para cuantificar sobre los modelos.)

Answer 2

Tardíamente, una respuesta en base a situaciones

1. ¿Cuál sería el correspondiente lema de "no hay basura, no hay confusión" para el final coalgebras?

Dada un álgebra inicial, cualquier álgebra tendrá un especial de subobjeto que es la imagen de la estructura inicial. El subobjeto puede haber confundido a los elementos (términos) de la inicial de álgebra, y el objeto puede tener más de basura. Un mapa entre los objetos de mapa de la primera especial del subobjeto a la segunda, posiblemente más confuso. La inicial de álgebra no tiene confusión y no chatarra.

Dado un final/terminal coalgebra, los elementos de cualquier coalgebra tendrá un especial colorido en términos de imágenes en los elementos de la estructura terminal. El objeto puede tener más de un elemento con el mismo color, y el objeto no puede usar todos los colores. Un mapa entre los objetos de preservar la coloración, el dominio de la posibilidad de usar menos colores. El terminal coalgebra colores, sin ambigüedad y sin redundancia. Si dos cosas se comportan de la misma manera, son los mismos; todos los comportamientos están cubiertos.

No hay basura, no hay confusión, No hay redundancia, no hay ambigüedad.

Answer 3

El eslogan es una significativa frase en inglés. Después de la eliminación de la negación, podemos obtener esta frase: "mantenerse limpio, manténgase alejado". Entonces, aquí es un teorema de cuantificados booleano fórmulas que describen ambas cualidades formalmente:

Lineal Corolario: se Cuantificaron monotono booleano fórmulas son linealmente decidable.

Es decir, no importa cómo muchos alternando los cuantificadores son en el prefijo, cuando el cuerpo de la fórmula tiene "cero negaciones," entonces la monotonía de la fórmula hace que cualquier cuantificador prefijo linealmente decidable; enchufe T para existencialmente cuantificada variables, NIL para universalmente cuantificado las variables, a continuación, evaluar el booleano forma, totalmente lineal en el tamaño de la QBF.

Goguen también pueden disfrutar de la car/cdr Estructura de Sentido Común: las Buenas ideas Suelen tener Dos palabras.