¿Es la informática teórica una rama / subconjunto propio de las matemáticas?

A2A.

Dado que CS usa ampliamente definiciones teóricas de conjuntos como la máquina de Turing, el autómata pushdown, DFA, etc., y dado que CS implementa aparatos de (por ejemplo) álgebra (por ejemplo, un conjunto de todas las cadenas finitas construidas sobre un alfabeto finito produce un monoide). Se puede considerar como parte de las matemáticas. Además, la Clasificación de asignaturas de Matemáticas incluye la informática como una rama de las matemáticas.

Sin embargo, hay un problema en su pregunta. Las matemáticas (incluso las matemáticas clásicas, y existen otros paradigmas matemáticos, por ejemplo, las matemáticas intuitivas) no son la colección de todas las implicaciones de los axiomas ZF (o incluso ZFC) (incluso emparejados con la lógica clásica). La teoría del tipo de homotopía, la teoría de la categoría e incluso algunas áreas de la teoría de conjuntos no son deducibles de ZFC. En realidad, dado que ZFC no es la base fundamental de las matemáticas (debido al primer teorema de incompletitud, no puede haber ninguna base coherente definitiva de las matemáticas), aunque es la más común de ellas.

En cuanto a su segunda pregunta (si es posible proporcionar axiomas que impliquen todos los teoremas de CS), diría que sí. Tome cualquier libro de texto sobre, digamos, teoría de autómatas y verá cómo se construye: algunas definiciones básicas introducidas, luego algunas propiedades (teoremas) se prueban en base a esas definiciones y teoremas previamente probados (no solo de CS). Así es como funcionan las matemáticas hoy en día: desde definiciones convencionales hasta propiedades más sofisticadas que deben ser probadas.

Ninguno. Las ciencias de la computación teórica y las matemáticas son ambas ciencias formales, y ninguna subsume a la otra.

La informática teórica es un subconjunto de la informática y las matemáticas.

Eso no quiere decir que el CS teórico no sea profundo, o que no valga la pena estudiarlo. Es solo que, bueno, casi todas las ciencias se reducen a matemáticas y / o lógica en última instancia. (Como ejemplo, la psicología es biología aplicada, que es química aplicada, que es física aplicada, que es matemática aplicada). Básicamente, todo se reduce a que las matemáticas son más abstractas que la CS teórica.

Fuente: Wikipedia: informática teórica

Es a la vez matemática aplicada y lógica aplicada. Sin embargo, la teoría de las funciones computables puede considerarse como una rama de la matemática teórica.