Ejercicio 1. Un conjunto de fórmulas proposicionales \(\Gamma\) se dice independiente si y sólo si para toda \(\phi \in \Gamma\) sucede que \(\Gamma - \{\phi\} \nvdash \phi\).
Demostrar que \(\Gamma\) es independiente si y sólo si todo subconjunto finito de \(\Gamma\) es independiente.
Ejercicio 2. Se dice que una función tiene un valor infinitamente alcanzable si existe un elementeo \(e\) de la imagen de \(f\) tal que el conjunto \(\{x : f(x) = e \}\) es infinito.
Mostrar que no es expresable en primer orden la proposición "\(f\) tiene un valor infinitamente alcanzable".
Ejercicio 3. Decidir si cada una de las siguientes afirmaciones es verdadera o falsa y justificar.
i) Si \(\Gamma\) es un conjunto insatisfacible de fórmulas proposicionales, entonces \(\Gamma' = \{ \neg \alpha : \alpha \in \Gamma \}\) es satisfacible.
ii) Si \(\Gamma\) es un conjunto insatisfacible de fórmulas proposicionales tal que \(\Gamma' = \{ \neg \alpha : \alpha \in \Gamma \}\) es satisfacible, entonces en \(\Gamma\) hay al menos una contradicción.
Ejercicio 4. Sea \(\mathcal{N} = \langle \mathbb{N};0_{\mathbb{N}};\leq_{\mathbb{N}} \rangle\) el modelo usual de los números naturales con la constante cero y la relación "es menor igual a". Considerar un lenguaje de primer orden con igualdad \(\mathcal{L}\) con un símbolo de constante 0 y un símbolo de predicado \(\leq\). Sea la siguiente axiomatización \(SQ_{\mathcal{N}}\) que extiende \(SQ\) con los siguientes axiomas:
S1 \((\forall x) (0 \leq x)\)
S2 \((\forall x) (x \leq x)\)
S3 \((\forall x) (\forall y) (\forall z) ((x \leq y \wedge y \leq z ) \rightarrow x \leq z)\)
S4 \((\forall x) (\forall y) ((x \leq y \wedge y \leq x) \rightarrow x = y)\)
S5 \((\forall x) (\exists y) (\neg (x = y) \wedge x \leq y)\)
a) Demostrar que el axioma S4 es válido en \(\mathcal{N}\).
b) Demostrar que \(SQ_{\mathcal{N}}\) no es completo respecto a \(\mathcal{N}\).