Antes de responder a la respuesta dada (¡Gracias!) hago un par de anotaciones:
La definición de interpretación dada por el Mendelson (aún me parece un suicidio cambiar al Enderton) es:
Una interpretación \( M \) consiste en un conjunto no vacío \( D \), llamado dominio de interpretación y una asignación para cada relator \( A_j^n \) de una relación de n-espacio \( (A_j^n)^M \) en \( D \) para cada funtor \( f_j^n \) una operación de n-espacios \( (f_j^n)^M \) en \( D \), y a cada constante individual \( a_i \) algún elemento fijo \( (a_i)^M \) de \( D \).
La cosa que yo escribí para dar una definición que consideré con el mismo significado, pero se me hizo "más en español", es la siguiente:
Una interpretación \( M \) lo es si cumple con las siguientes propiedades:
1. Tiene (?) un conjunto no vacío \( D \), llamado conjunto de interpretación.
2. Denotando a \( \mathfrak{A}^n \) al conjunto de todos los relatores de la forma \( A_j^n \). Entonces, existe una (
única) función:
\( f:\mathfrak{A}^n\rightarrow P(D^n) \)
en \( M \).
3. Si \( \mathfrak{F}^n \) es el conjunto de todos los funtores de la forma \( f_j^n \). Entonces existe una (
única) función :
\( g:\mathfrak{F}^n\rightarrow \mathfrak{D}^n \)
en \( M \), donde \( \mathfrak{D}^n \) es el conjunto de todas las funciones \( t:D^n\rightarrow D \). .
4. Si \( \mathfrak{A}^n \) es el conjunto de todas las constantes existe una (
única) función:
\( h:\mathfrak{A}^n\rightarrow D \)
en \( M \).
Y bien..., esta fue la definición que "arreglé" a partir de la definición del Mendelson de tal manera que se me hiciera más "digerible" o clara, si cabe. Pero obviamente, intenté decir lo mismo. Eeeem..., la palabra única aparece en rojo porque no sé si eso sea correcto decirlo, o sea que la función que asigna, debe ser sólo una.
Para definir satisfacción, también modificando, éste menos que la definición de interpretación, hice lo siguiente (sigo usando la misma notación dada arriba):
Sea \( \Sigma \) el conjunto de todas las sucesiones del dominio \( D \) de la interpretación (¿No es lo mismo que decir \( D^\mathbb N \)?). Sea, además, \( \mathfrak{T} \) el conjunto de todos los términos. Definimos la función \( s* \) de una sucesión \( s=(s_1,s_2,...) \) de \( \Sigma \), como la función
\( s*:\mathfrak T \rightarrow D \)
que tiene como regla:
\( s*(t)=\begin{Bmatrix} s_j & \mbox{ si }&\textsf{ t es }x_j\\h(a_j) & \mbox{si}&\textsf{ t es }a_i\\g(f_j^n)(s*(t_1),..., s*(t_n))& \mbox{ si }&\textsf{ t es }f_i^n(t_1,...,t_n)\end{matrix} \)
Y a partir de esto, se da la definición de satisfacción:
Se dice que \( s=(s_1, s_2,...) \) satisface \( \mathcal A \) si se puede mostrar que lo hace de las siguientes reglas:
1. \( \mathcal A \) es una fórmula atómica de forma \( A_j^n(t_1,...,t_n) \) y \( f(A_k^n) \) es el elemento que le corresponde de \( P(D^n) \) en la intepretación. La secuencia \( s \) satisface \( \mathcal A \) si y sólo si la n-upla \( <s*(t_1), s*(t_2),..., s*(t_n)> \) está en \( f(A_k^n) \).
2. \( \mathcal A \) es \( \neg\mathcal B \). \( s \) satiface \( \mathcal A \) si y sólo si \( s \) no satisface \( \mathcal B \).
3. \( \mathcal A \) es \( \mathcal B\rightarrow \mathcal C \). \( s \) satisface \( \mathcal A \) si y sólo si \( s \) no satisface \( \mathcal B \) o satisface \( \mathcal C \).
4. \( \mathcal A \) es \( \forall x_i \mathcal B \). \( s \) satisface \( \mathcal A \) si y sólo si toda secuencia que difiere de \( s \) en a los más la \( i \)-ésima posición satisface \( \mathcal B \)
Esta es la definición de satisfacción. Que sólo le cambie algo del modo en que lo decía el Mendelson en el primer numeral. El resto son exactamente los mismo (excepto que en español). Pos, tal vez esto se vea como algo demasiado innecesario, pero considero que me ha aclarado algunas cuestiones que con el modo en que las mostraba el Mendelson, sólo lograban confundirme.
Ahora sí, con respecto a lo que me respondió usted, Carlos Ivorra

:
(b) Para cualquier wf \( \mathcal A \), pruebe que existe un método efectivo para determinar si \( \mathcal A \) es verdadera para todas las interpretaciones con dominio de cadinalidad finita fija \( k \). (de este leí la respuesta, pero parecía probarlo para cierta interpretación de cardinalidad finita \( k \) y no para todos)
Bueno, una forma a lo bruto es considerarlas todas una a una, puesto que sólo hay una cantidad finita. Supongo que se podrán encontrar algoritmos más finos, pero si la cuestión es si es posible, está claro.
¡Ooooooooooooooooooooooooooooooooooooooooh! Habiendo hecho lo anterior (esa traducción medianamente 'inútil) creo que he entendido esto. La 'forma' del conjunto está dado por la interpretación, pos las propiedades. Por eso los elementos del conjunto no son importantes siempre que tenga éste k elementos.
(c) Una wf \( \mathcal A \) se le llama k-válida si es cierta para toda interpretación que tiene dominio de k elementos. Llamamos a \( \mathcal A \) precisamente k-válida si no es (k+1)-válida. Muestre que si \( \mathcal A \) es (k+1)-válida entonces \( \mathcal A \) es k-válida y dé un ejemplo de una wf que sea precisamente k-válida. (¿ein?)
Éste tengo que pensarlo. Entiendo que consideras lenguajes sin igualador, pues si no la primera parte sería falsa y la segunda inmediata.
En este momento todavía no he comenzado el capítulo con igualador, da la casualidad de que es el capítulo inmediatamente debajo de estos ejercicios. (Teorías con igualdad se llama el subcapítulo)
2. Muestre que la siguiente wf es verdadera para todo dominio finito y falso para algún domino infinito. (Y con este confirmé que no entendía mucho):
\( ((\forall x)(\forall y)(\forall z) [A_1^2(x,x)\wedge (A_1^2(x,y)\wedge A_1^2(y,z)\Rightarrow A_1^2(x,z))\wedge (A_1^2(x,y) \vee A_1^2(y,x))])\Rightarrow (\exists y)(\forall x)A_1^2(y,x) \)
Lo que dice esa fórmula es que si una relación es reflexiva, transitiva y conexa, entonces tiene un mínimo elemento. Eso es cierto en todo dominio finito, pero falso, por ejemplo, sobre el conjunto de los números naturales con la relación inversa de la usual.
Con esto que dijiste, ya puedo pensarlo, bueno, aunque ya diste un contraejemplo pero queda probarlo para todo finito. Aún me cuesta un poco interpretar que esos relatores están siendo si bien no definidos sí identificados con propiedades en ese tipo de wf. ¿Cuál es la relación inversa de la usual? ¿Cuál es la relación usual?
3. Demuestre que no existe una teoría \( K \) cuyo modelos sea exactamente una interpretación con domino finito. (Este particularmente parece importante
)
¿Es correcta mi conjetura de que tus lenguajes formales no tienen igualador? Lo digo porque con igualador es relativamente simple, si no, tendría que pensarlo, pero prefiero no darle vueltas si resulta que al final sí que podemos usar el igualador.
¡Es correcta!

Al principio tampoco entendía en absoluto el concepto de satisfacción, sin embargo me era posible demostrar algunas consecuencias de la definición; esto obviamente es perder enfoque, pero supongo que en parte, por esto mismo, pregunto.
No sé exactamente qué diferencia estableces entre interpretación y satisfacción. Sea como sea, las ideas de fondo son completamente naturales: se trata de asignar un objeto a cada constante, una relación a cada signo de relación y una función a cada signo de función, lo que a su vez te permite asociar un significada a cada fórmula del lenguaje en cuestión, de modo que cada fórmula significa lo que cualquiera que la lea entendería que significa sabiendo el significado que hay que dar a los signos básicos (constantes, relatores, etc.).
A saber en qué diferencio podría ayudar lo primero que publiqué.

¡Gracias por las respuestas, la paciencia!