Si un número finito de identidades algebraicas no implican algunos de identidad, hay siempre un número finito de contraejemplo?

Question

Esta pregunta sólo apareció, mientras que la experimentación con Prover9 y Mace4.

Digamos que tenemos un número finito de la firma y algunas conjunto finito de identidades $E_i$ en el sentido del álgebra universal, como los axiomas de grupo.

$$\left\{\begin{matrix}x\cdot(y\cdot z) = (x \cdot y) \cdot z \\ x\cdot 1 = 1 \cdot x = x \\ x\cdot x^{-1} = x^{-1} \cdot x = 1\end{matrix}\right.$$

Si alguna otra identidad $J$ hace que no se siga de la $E_i$, hay siempre un contraejemplo en un conjunto finito? Como si queremos deducir $x\cdot y = y \cdot x$, tenemos la nonabelian finito contraejemplo $S_3$ o de $x=y$ ya tenemos $\mathbb Z/(2)$.

Esto es básicamente lo que Mace4 trata de encontrar, por lo que este enfoque podría ser, en teoría siempre es exitosa? (Incluso a través de la contraejemplo sería demasiado grande para que un equipo pueda encontrar)

---

Mi sospecha inicial fue no, pero los contraejemplos que yo estaba tratando de no se ajustan a las fuertes restricciones de la pregunta.

• Como para los axiomas de un sesgo de campo, de ello no se sigue que $xy = yx$, pero no hay finito contraejemplo. Sin embargo, el sesgo de los campos no pueden ser axiomatized por solo las identidades.

• Para $\mathbb R$-espacios vectoriales, de ello no se sigue que $x=y$ y no hay finito contraejemplo. Sin embargo, la firma y el axioma establecido para $\mathbb R$-espacios vectoriales son infinitas.

Sé si $J$ no seguir a partir de la $E_i$, el conjunto de fórmulas de $\{E_i\} \cup \{\neg J\}$ es consistente, por lo tanto no tienen un modelo. Si es finito, hemos terminado. Si es infinito, podemos asumir que se trata de contables por parte de Löwenheim-Skolem. Sin embargo, en forma de pregunta, donde todos los $E_i$ son universales y sólo $\neg J$ es una negación de una identidad, es siempre un modelo finito?

Gracias por algunos pensamientos

Answer 1

Lattice-ordenó a los grupos infinita o trivial ($\forall x\forall y(x = y)$). Se pueden definir equationally mediante la adición de un mínimo de límite superior de operador $\land$ a la firma de un grupo y agregar a las identidades que caracterizan los grupos, identidades diciendo que $\land$ es idempotente, conmutativa y asociativa, y que el grupo de operación distribuye a través de ella. Incluso con un número ilimitado de memoria y el tiempo, un programa como Mace4 no sería capaz de encontrar un contra-ejemplo a $x + x = x$.

Una teoría que se caracteriza por un conjunto finito de identidades tiene la propiedad de que toda identidad es válida o tiene un contra-ejemplo en un modelo finito, luego de que la teoría es decidable: para decidir una propiedad, ejecutar un intento de encontrar una prueba de ello en paralelo con un intento de encontrar un número finito de contra-ejemplo. Siempre el calendario de las dos búsquedas bastante, el paralelo proceso de búsqueda debe terminar con una prueba o un contraejemplo.