Un omnipresente patrón de preguntas

Question

Hay un omnipresente patrón de preguntas relativas supuestamente cualquier tipo de objeto matemático o estructura: grupos, gráficos, números, categorías, y así sucesivamente. Va como esta (de manera informal):

Puede una clase de objetos o estructuras de un tipo dado de X que se caracteriza por algunos como "condición externa" Y se define por una condición de Z en sus respectivos "interno" idioma, y si es así: ¿cómo?

Ejemplos bien conocidos ("condición externa" = "estado interno"):

1. grupos de $G$ isomorfo a un subgrupo del grupo simétrico de a $G$ = todos los grupos (del teorema de Cayley)

2. gráficos embebidos en el plano = gráficos no contiene un subgrafo que es una subdivisión de $K_5$ o $K_{3,3}$ (el teorema de Kuratowski)

3. los números n de los árboles de k vértices etiquetados = números de n = k^k-2 para algunos k > 1 (del teorema de Cayley en los árboles)

4. los números de n con sólo un grupo de orden n = números de n = p₁ · p₂ · ... · p_k para algunos k > 0, donde p_i son distintos de los números primos y no p_j-1 es divisible por cualquier p_i (cíclico de los números, ver Sloane del A003277)

Más ejemplos de MO:

• Que los gráficos son de Cayley gráficos?

• Podemos reconocer cuando una categoría es equivalente a la categoría de modelos de un primer orden de la teoría?

• Puede determinar si un grafo es el 1-esqueleto de un polytope?

Pregunta #1: ¿Cuál es la forma correcta de caracterizan a este patrón de preguntas? ¿Cuál es el común contexto y justificación?

---

Pregunta #2: ¿Cómo es la pregunta introductoria a ser plantea correctamente?

Answer 1

Hay tres hermanos teoremas de la lógica que garantiza que tales caracterizaciones están obligados a pasar.

• El Craig Teorema De Interpolación De
• El Robinson Conjunta Consistencia Teorema De
• El Beth Definability Teorema De

[Las entradas de wikipedia necesita algo de trabajo. Yo sugiero que busque en marcha de estos teoremas en buena lógica libro, por ejemplo Hodges Modelo de la Teoría o de su más accesible, más Corto el Modelo de la Teoría.]

Me voy a centrar en el Beth Definability Teorema, aunque los otros dos hermanos conducen a conclusiones similares en contextos ligeramente diferentes.

Supongamos que usted tiene un de primer orden lenguaje L₀ y un mayor lenguaje L. sea T una teoría en L y dejar que φ(x) es una fórmula de la más grande lenguaje L con la siguiente propiedad. Cada vez que Un₁ y Un₂ son los dos modelos de T que tienen el mismo universo Una y la misma interpretación para todas las partes de la pequeña lenguaje L₀, entonces₁ ⊧ φ(a) iff Un₂ ⊧ φ(a) para todo a ∈ A. Beth Definability Teorema dice que debe de ser una fórmula f₀(x) de los más pequeños lenguaje L₀ tal que T ⊦ ∀x(f(x) ↔ f₀(x)).

La relación con su pregunta es la siguiente. El idioma base L₀ es la 'interna' lenguaje de las estructuras que realmente le interesan, mientras que el lenguaje L adicionales a las del 'exterior' de datos. La teoría T que caracteriza a las estructuras con datos externos a los que te importan, y φ(x) es una propiedad de este tipo de estructuras en la que está interesado. Si φ(x) es lo suficientemente independiente de los datos externos, entonces φ(x) debe ser equivalente a una fórmula de uso interno φ₀(x).

No todos los ejemplos que se dan son fácilmente echado en este formalismo, pero el sabor es el mismo. Por desgracia, el Beth Definability Teorema (y su prueba) no dice mucho sobre cómo encontrar la fórmula de uso interno φ₀(x), pero, al menos, se dice que la búsqueda no será en vano.