¿qué quiere decir

Question

Me gusta leer acerca de la lógica formal como un hobby ocasional. Sin embargo, una cosa sigue disparo de mí: me parecen incapaces de comprender lo que se refiere a cuando la palabra "tipo" (como en el tipo de teoría) es mencionado.

Ahora, yo entiendo que lo que los tipos están en la programación, y a veces me da la impresión de que los tipos de lógica son la misma cosa: queremos que nuestros sistemas formales de seguridad de modo que usted no puede agregar un entero a una proposición (por ejemplo), y los tipos son el mecanismo formal para especificar esto. De hecho, la página de Wikipedia para el tipo de teoría que más o menos dice esto explícitamente en la sección de introducción.

Sin embargo, también va a implicar que los tipos son mucho más poderoso que eso. En general, de todo lo que he leído, me da la idea de que tipos son:

• como los tipos de programación
• algo que es como un conjunto, pero diferentes en ciertos aspectos
• algo que se puede evitar paradojas
• el tipo de cosa que podría sustituir a la teoría de conjuntos, en los fundamentos de las matemáticas
• algo que no es sólo de forma análoga a la noción de una proposición, pero puede ser pensado como la misma cosa ("proposiciones como tipos")
• un concepto que es muy, muy profundo, y estrechamente relacionado con el de mayor categoría de la teoría

El problema es que tengo problemas para conciliar estas cosas. Tipos de programación me parece bastante simple, práctico cosas (alhough el tipo de sistema para cualquier lenguaje de programación puede ser muy complicado y muy interesante). Pero en la teoría tipo parece que de alguna manera los tipos son el idioma, o que ellos son responsables por su poder expresivo en una forma mucho más profunda de lo que es el caso en la programación.

Así que supongo que mi pregunta es, a alguien que entiende los tipos de (digamos) Haskell o C++, y que también entiende la lógica de primer orden y axiomático que la teoría de conjuntos y así sucesivamente, ¿cómo puedo obtener a partir de estos conceptos el concepto de tipo de teoría de la lógica formal? Lo que precisamente es un tipo de tipo de teoría, y ¿cuál es la relación entre los tipos formales de las matemáticas y de tipos en ciencias de la computación?

(Yo no estoy en busca de una definición formal de un tipo tanto como la idea central detrás de él. Me pueden encontrar varias definiciones formales, pero he encontrado que en realidad no me ayudan a entender el concepto subyacente, en parte porque están necesariamente ligados a las características específicas de un determinado tipo de teoría. Si puedo entender la motivación mejor que debería hacer que sea más fácil de seguir las definiciones).

Answer 1

tl;dr Tipos sólo tienen significado dentro de los sistemas de tipo. No es independiente de la definición de "tipo", a excepción de declaraciones vagas como "tipos de clasificar los términos". La noción de tipo de lenguajes de programación y el tipo de teoría son básicamente el mismo, pero diferente tipo de sistemas corresponden a diferentes tipo de teorías. A menudo el término "tipo de teoría" se utiliza específicamente para una determinada familia de potentes tipo de teorías descendientes de Martin-Löf Tipo de Teoría. Agda y Idris al mismo tiempo son a prueba de asistentes para este tipo de teorías y lenguajes de programación, por lo que en este caso no hay distinción alguna entre el lenguaje de programación y el tipo teórico de las nociones de tipo.

No es el "tipo" a sí mismos de que son "poderosos". En primer lugar, puede refundición de la lógica de primer orden usando los tipos. De hecho, el tipo de multi-ordenan la lógica de primer orden, son básicamente la misma cosa como tipos.

Cuando la gente habla acerca de la teoría tipo, que a menudo significa específicamente Martin-Löf Tipo de Teoría (MLTT) o algún descendiente de él, como el Cálculo de (Inductivo) Construcciones. Estas son poderosas de orden superior lógicas que pueden ser vistos como constructivo conjunto de teorías. Pero es el sistema específico(s) que son de gran alcance. El tipo simple cálculo lambda visto desde una de las proposiciones-como-tipos de perspectiva es, básicamente, la prueba de la teoría de intuitionistic lógica proposicional, que es bastante débil sistema lógico. Por otro lado, teniendo en cuenta la teoría ecuacional de los de tipo simple cálculo lambda (con algunos axiomas adicionales) le da algo que está muy cerca de la mayoría de la comprensión directa de orden superior de la lógica como una extensión de la lógica de primer orden. Este punto de vista es la base de la HOL familia del teorema provers.

La teoría de conjuntos es un extremadamente potente sistema lógico. La teoría de conjuntos ZFC es de primer orden de la teoría, es decir, una teoría axiomatized en la lógica de primer orden. Y lo que hace la teoría de conjuntos de lograr? ¿Por qué, es esencialmente una incrustación de orden superior de la lógica en la lógica de primer orden. En la lógica de primer orden, no podemos decir algo como $$\forall P.P(0)\land(\forall n.P(n)\Rightarrow P(n+1))\Rightarrow\forall n.P(n)$$ but, in the first-order theory of set theory, we can say $$\forall P.0\in P\land (\forall n.n\in P\Rightarrow n+1\in P)\Rightarrow\forall n.n\in P$$ Conjuntos de comportarse como "primera clase" de los predicados.

Mientras que la teoría de conjuntos ZFC y MLTT ir más allá de ser solo de orden superior de la lógica de orden superior de la lógica en sí misma es ya un poderoso y ergonómico sistema como se demuestra por el HOL teorema de provers por ejemplo. En cualquier caso, como lo que puedo decir, tener algún cuento para hacer de orden superior, la lógica, como las cosas que es necesario provocar ningún interés en algo como un marco para las matemáticas de los matemáticos. O usted puede girar alrededor de un poco y decir que es necesario algún tipo de historia para el conjunto de cosas como de "primera clase" de los predicados de hacer un transitable trabajo. Esta última perspectiva es más probable que atraigan a los matemáticos, pero para mí el orden superior de la lógica de la perspectiva capta mejor el denominador común.

En este punto se debe ser claro que no hay esencia mágica en "tipos" sí, pero algunas familias de tipo de teorías (es decir, el tipo de sistemas desde una perspectiva de programación) son muy poderosos. La mayoría de los "poderosos" de los sistemas de tipo de lenguajes de programación están estrechamente relacionadas con la polimórficos cálculo lambda también conocido como Sistema de F. De la proposición-como-tipos de perspectiva, estos corresponden a intuitionistic de segundo orden proposicional de la lógica, que no debe confundirse con la de segundo orden (predicado) de la lógica. Se permite la cuantificación más de proposiciones (es decir, nullary predicados), pero no más de los términos que no existen en esta lógica. Clásico de segundo orden, lógica proposicional es fácilmente reducido a la clásica lógica proposicional (a veces llamado zero-order logic). Esto es debido a que $\forall P.\varphi$ es reducible a $\varphi[\top/P]\land\varphi[\bot/P]$ clásico. Sistema de F es muy expresivo, pero visto como la lógica es bastante limitada y mucho más débil que MLTT. Los sistemas de tipo de Agda, Idris, y Coq son descendientes de MLTT. Idris, en particular, y Agda a un menor grado de dependencia escribió lenguajes de programación.¹ en General, el concepto de tipo en un (estático) tipo de sistema y en el tipo de teoría son esencialmente los mismos, pero el significado de un tipo depende del tipo de sistema/tipo de teoría se define dentro. No existe una verdadera definición de "tipo" por su propia cuenta. Si usted decide mirar por ejemplo, Agda, usted debe ser rápidamente desprenderse de la idea de que "los tipos son el lenguaje". Todos estos tipo de teorías, términos y los términos no son "hechos de los tipos". Normalmente sólo el aspecto funcional de los programas.

¹ no quiero dar la impresión de que "dependiente escribió" = "super poderosas" o "MLTT derivados". El LF de la familia de las lenguas por ejemplo, Elf y Twelf son intencionalmente débil dependiente escribió lenguajes de especificación que son mucho más débiles que MLTT. A partir de una de las proposiciones-como-tipos de perspectiva, que corresponden más a la lógica de primer orden.

Answer 2

He encontrado que en realidad no me ayudan a entender el concepto subyacente, en parte porque están necesariamente ligados a las características específicas de un tipo particular de la teoría. Si puedo entender la motivación mejor que debería hacer que sea más fácil seguir las definiciones.

La idea básica: En la teoría de conjuntos ZFC, sólo hay un tipo de objeto - conjuntos. En tipo de teorías, no son múltiplos tipo de objetos. Cada objeto tiene un tipo particular, que se conoce como "tipo".

Tipo de teorías suelen incluir maneras para formar nuevos tipos de viejo tipo. Por ejemplo, si tenemos los tipos de $A$ $B$ también tenemos un nuevo tipo de $A \times B$ cuyos miembros son pares $(a,b)$ donde $a$ es de tipo $A$ $b$ es de tipo $B$.

Para el tipo más simple de las teorías, tales como los de orden superior de la lógica, que es esencialmente el único cambio de ordinario la lógica de primer orden. En esta configuración, toda la información acerca de los "tipos" que se maneja en el metatheory. Pero estos sistemas son apenas "tipo de teorías", debido a que la teoría en sí misma, en realidad no sabe nada acerca de los tipos. Estamos realmente sólo mirar en la lógica de primer orden con varios tipos. Por analogía a las ciencias de la computación, estos sistemas son vagamente como los lenguajes con tipos estáticos - no es posible escribir una bien formada fórmula/programa que no está seguro del tipo, pero el programa en sí no tiene ningún conocimiento acerca de los tipos mientras se está ejecutando.

Más típico de un tipo de teorías incluyen formas de razonar acerca de los tipos dentro de la teoría. En muchos tipo de teorías, tales como ML tipo de teoría, los tipos son los objetos de la teoría. Así que es posible demostrar "$A$ es un tipo" como una frase de la teoría. También es posible demostrar frases tales como "$t$ tipo $A$". Estos pueden ser expresadas en sistemas como los de orden superior de la lógica.

De esta manera, estas teorías no son sólo "de la lógica de primer orden con varios tipos", son realmente "una teoría acerca de los tipos". De nuevo, por analogía, estos sistemas se asemeja vagamente a los lenguajes de programación en la que un programa puede hacer inferencias acerca de los tipos de objetos en tiempo de ejecución (analogía: se puede razonar acerca de los tipos dentro de la teoría).

Otro aspecto clave de tipo de teorías es que a menudo tienen su propia interna de la lógica. El Curry-Howard correspondencia muestra que, en particular, la configuración, las fórmulas de proposicional o lógica de primer orden corresponden a los tipos , en particular, el tipo de teorías. La manipulación de los tipos en un modelo de tipo de teoría corresponde, a través del isomorfismo, a la manipulación de fórmulas de primer orden de la lógica. El isomorfismo se aplica a muchos de lógica/tipo de teoría pares, pero es más fuerte cuando la lógica es intuitionistic, que es una de las razones intuitionistic/lógica constructiva surge en el contexto de la teoría tipo.

En particular, las operaciones lógicas en las fórmulas de convertirse en el tipo de formación de operaciones. El operador "and" de la lógica se convierte en el tipo de producto de la operación, por ejemplo, mientras que el operador "or" se convierte en una especie de "unión" de tipo. De esta manera, cada modelo de la teoría tipo tiene su propia "lógica interna" - que a menudo es un modelo de intuitionistic lógica.

La existencia de esta lógica interna es una de las motivaciones para el tipo de teoría. Cuando nos fijamos en la lógica de primer orden, tratamos la "lógica" como estar sentada en la metatheory, y nos fijamos en el valor de verdad de cada una fórmula dentro de un modelo de uso de la clásica de las conectivas. En el tipo de teoría, que a menudo es mucho menos importante objetivo. En su lugar nos fijamos en la colección de tipos en un modelo, y estamos más interesados en la forma en que el tipo de las operaciones de formación de trabajo en el modelo que en la forma de la clásica de las conectivas de trabajo.

Answer 3

Yo no estoy en busca de una definición formal de un tipo tanto como la idea central detrás de él. Me pueden encontrar varias definiciones formales, pero he encontrado que en realidad no me ayudan a entender el concepto subyacente, en parte porque están necesariamente ligados a las características específicas de un tipo particular de la teoría. Si puedo entender la motivación mejor que debería hacer que sea más fácil seguir las definiciones.

Permítanme responder a esto desde un punto de vista filosófico, que tal vez podría ayudar a responder a sus implícita la pregunta de por qué los lógicos llaman tipo de teorías de tipo de teorías y de conjunto de las teorías conjunto de teorías.

Una teoría es un sistema que describe conjuntos, en el sentido de que un conjunto es una colección de objetos. Esto significa que la intención de universo (también llamado mundo/dominio) se divide por cada conjunto $S$ en dos partes, los miembros de $S$ y los no-miembros de $S$. Hay una gran variedad de teorías como la de ZF[C] y NF[U] y extensiones de ellos.

Un tipo de teoría es un sistema destinado a describir los tipos, donde un tipo es un tipo de categorización o clasificación de objetos. Si un objeto $x$ es de tipo $S$ o no, normalmente no es un valor booleano pregunta, en el sentido de que uno no puede formar parte de una oración que es verdadera si y sólo si $x$ es de tipo $S$. En su lugar, tipo de teorías, reglas de inferencia para la tipificación de los juicios. Muchos tipo de teorías uso de la sintaxis como "$x : S$" por la sentencia que $x$ es de tipo $S$. No es una expresión booleana; "$\neg ( x : S )$" simplemente es sintácticamente incorrecto. Una tipificación de la regla podría ser como "$x : S \ , \ f : S \to T \vdash f(x) : T$", y en cierto sentido, esta es una de las reglas fundamentales que podemos esperar de cada tipo de teoría que, de alguna u otra forma.

En cualquier caso, la noción de un tipo que sólo se hace precisa a través de un tipo de teoría, así como la noción de un conjunto sólo es preciso a través de una teoría de conjuntos. Tenga en cuenta que ZFC y NFU son incompatibles, y por lo que describen incompatible nociones de conjuntos. Asimismo, hay numerosos incompatible tipo de teorías que describen las diferentes nociones de tipos. En el peor de los casos, una noción de conjuntos o tipos pueden ser incoherentes, que por supuesto tiene que descartar. Idealmente, nos gustaría filosóficamente coherente justifica o noción.

[Tipos de] algo que se puede evitar paradojas

No hay nada inherente en los tipos que se pueden evitar las paradojas. Como se ha señalado, algunos intentos fundacionales tipo de teorías se ha vuelto inconsistente de manera similar a como lo ingenuo de la teoría de conjuntos.

Pero en la teoría tipo parece que de alguna manera los tipos son el lenguaje, o que ellos son responsables por su poder expresivo en una forma mucho más profunda de lo que es el caso en la programación.

Tipos de programación son muy "débil" en el sentido de que cada lenguaje de programación moderno tiene un tipo de sistema con decidable escribir, porque el compilador debe terminar y regresar el éxito o el fracaso de la compilación, y por lo tanto debe ser capaz de realizar cualquier tipo de comprobación está garantizada por el idioma. Algunos lenguajes (como Javascript) han duck typing, que significa que ningún tipo de comprobación. Otros lenguajes (como Java) tienen bastante estricto, y todo tipo de sistema (con los genéricos) es decidable (si no el tipo de uso de la fundición), por lo que cada programa Java puede ser estática comprueba el tipo de corrección (no habrá tiempo de ejecución error de tipo).

En contraste, en el clásico de matemáticas que no tienen decidable escribiendo en general, porque queremos ser capaz de realizar clásica de la aritmética, que nos permite construir y la razón sobre los programas arbitrarios (equivalentemente, máquinas de Turing), y el teorema de la incompletitud de Gödel las fuerzas de nuestro lado. Por lo tanto, en cada tipo de teoría que apoya la construcción de funciones parciales que representan programas, no se puede computably determinado por general $x,S$ si la sentencia "$x : S$" es comprobable o no.

El trade-off siempre está ahí. Usted nunca puede tener tanto decidable comprobación del tipo y la capacidad para manejar arbitraria (clásica) razonamiento aritmético. En el tipo de la teoría de los términos, usted no puede tener tanto la normalización de cada término y la capacidad para construir programas arbitrarios antes de demostrar sus propiedades.

Sin embargo, el tipo de orden superior, la lógica puede ser visto como tipos simples tipo de teoría, y a su vez los tipos de función de tipo simple teoría podría ser entendido a través alarmada como los tipos de programas.

Answer 4

Puedo recomendar un (texto)libro para usted? Tipos y Lenguajes de Programación, por Benjamin C. Pierce. Yo vengo de una experiencia en las matemáticas y el trabajo como programador. Cogí este libro, porque me gustaría ver en los papeles por científicos de la informática (creo que Felipe Wadler cuando él no se molesta en ser principiante-friendly) y una sensación rara, porque yo no sabía la base para lo que iba a decir, y sin esa base, todo parecía un poco afloja-goosey.

El texto está escrito en el nivel de un buen primer año de la escuela de posgrado curso en el tipo de teoría, y me pareció que para ser claro y bien escrito, una agradable lectura. Y aunque yo no trabajo mi camino a través de casi ninguno de los ejercicios me siento mucho más cómodo ahora, cuando leo las cosas que uso o tipos de referencia.

Para ser claro, el libro no responder a las preguntas esenciales que usted pidió, pero creo que va a poner en una posición mucho mejor para la comprensión de las preguntas y respuestas, además de que tendrá un montón de ejemplos concretos de anclaje de todo.

Answer 5

Los tipos de tipo de teoría son los mismos que los tipos de la informática teórica. En el tipo de la teoría de objetos habita un tipo pero no comparten los tipos. Lo importante acerca de los tipos es que existe una correspondencia entre los tipos y intuistic lógica.

Suma/tipos de Unión que en Haskell se definen por el uso de la | corresponden a la lógica or.

data Either x y = Left x | Right y

Los tipos de productos que corresponden a la lógica y

data Both x y = Both x y

Finalmente, la lógica implica que se corresponde con el tipo de función

 data Implies x y = x -> y

Usted puede traducir cualquier enunciado matemático en una especie de usar el producto, suma, función y un par de otros tipos adicionales. Si usted puede, a continuación, escribir un programa de ordenador que puede aplicar el tipo de dado que el programa de ordenador es una prueba de la afirmación matemática.