Cuantificadores, predicados y lenguaje matemático
En los capítulos 4 y 5 trabajamos con proposiciones completas: afirmaciones que ya podían ser verdaderas o falsas. Pero la matemática real está llena de frases como “\(x\) es par”, “\(x^2<y\)”, “\(n\) divide a \(m\)” o “\(x\) tiene una raíz cuadrada”. Antes de decidir su verdad necesitamos saber qué objetos pueden ocupar esas variables y qué estamos afirmando acerca de ellos.
Aquí aparece una capa nueva del lenguaje matemático. Ya no basta con combinar proposiciones mediante \(\neg\), \(\land\), \(\lor\) o \(\Rightarrow\). Debemos aprender a manejar predicados, dominios, variables libres y ligadas, cuantificadores, alcance y dependencia.
La pregunta rectora del capítulo es:
¿Cómo convertimos una condición abierta en una afirmación matemática precisa, y cómo leemos exactamente qué promete una frase con “para todo”, “existe” o “existe un único”?
Salvo indicación contraria, los dominios que usemos serán no vacíos. No desarrollaremos todavía una teoría formal de lógica de primer orden; el objetivo es operativo y matemático: leer, escribir, negar y comparar afirmaciones cuantificadas con la precisión que exigirá todo el resto del libro.
6.1. De una expresión abierta a una afirmación
Comparemos tres escrituras:
- \(x+3\);
- \(x+3=7\);
- \(4+3=7\).
La primera es una expresión: representa un objeto numérico una vez que se conoce \(x\). La segunda es una condición abierta: según el valor que adopte \(x\), puede resultar verdadera o falsa. La tercera ya es una proposición: no queda ninguna variable sin determinar y podemos asignarle un valor de verdad.
A una condición como
\(P(x): x+3=7\)
la llamaremos predicado en la variable \(x\). Si sustituimos \(x=4\), obtenemos la proposición verdadera \(P(4)\). Si sustituimos \(x=10\), obtenemos la proposición falsa \(P(10)\).
Hay otra forma de cerrar la condición: cuantificarla. Por ejemplo,
\(\exists x\in\mathbb R\;(x+3=7)\)
dice que existe al menos un real que satisface la condición, mientras que
\(\forall x\in\mathbb R\;(x+3=7)\)
dice que todos los reales la satisfacen. La primera afirmación es verdadera; la segunda, falsa.
La lección inicial es sencilla pero decisiva:
Una fórmula con variables libres no es, en general, una afirmación completa. Para obtener una proposición debemos fijar valores o ligar las variables mediante cuantificadores.
6.2. Predicados y dominio de discurso
El predicado no vive aislado del conjunto de objetos que estamos autorizados a considerar. Ese conjunto se llama dominio, universo de discurso o simplemente universo.
Consideremos
\(P(x): x^2=2\).
La pregunta “¿existe un \(x\) tal que \(P(x)\)?” tiene respuestas distintas según el dominio:
- en \(\mathbb Z\), no hay solución;
- en \(\mathbb Q\), tampoco;
- en \(\mathbb R\), sí: \(x=\sqrt2\) y \(x=-\sqrt2\).
Por eso la escritura
\(\exists x\;P(x)\)
es incompleta si el contexto no deja claro qué objetos puede recorrer \(x\).
El dominio puede aparecer explícitamente, como en \(\forall n\in\mathbb Z\), o quedar fijado por el contexto. En un texto bien escrito, esa información nunca debería ser ambigua.
El mismo símbolo, distinta afirmación
La fórmula
\(\forall x\;(x^2\ge x)\)
es verdadera si el dominio es \(\{0,1\}\), pero falsa sobre \(\mathbb R\), pues \(x=\tfrac12\) da \(\tfrac14<\tfrac12\).
El dominio no es un detalle externo: forma parte del significado matemático de la afirmación.
6.3. Variables libres y variables ligadas
Una variable es libre cuando todavía no está controlada por un cuantificador dentro de la expresión considerada. Es ligada cuando un cuantificador determina su alcance.
Ejemplos:
- en \(x^2>0\), la variable \(x\) es libre;
- en \(\forall x\in\mathbb R\;(x^2\ge0)\), \(x\) está ligada por \(\forall\);
- en \(\forall x\,P(x,y)\), \(x\) está ligada y \(y\) queda libre;
- en \(\forall x\,\exists y\,R(x,y)\), ambas variables están ligadas.
Una fórmula puede contener simultáneamente variables libres y ligadas. Mientras quede una variable libre cuyo valor no esté fijado por el contexto, no tenemos todavía una proposición cerrada.
El nombre de la variable no es lo esencial
Las afirmaciones
\(\forall x\in\mathbb R\;(x^2\ge0)\)
y
\(\forall t\in\mathbb R\;(t^2\ge0)\)
tienen el mismo significado. Cambiar el nombre de una variable ligada es inocuo si se hace de manera coherente y no se produce una colisión con otra variable que ya tenga función distinta.
Más adelante veremos un error típico: renombrar una variable ligada con el mismo nombre de una variable libre puede cambiar el significado al capturarla.
6.4. El cuantificador universal
El símbolo \(\forall\) se lee “para todo” o “para cada”. La afirmación
\[ \forall x\in D\;P(x) \]
dice que cada elemento del dominio \(D\) satisface el predicado \(P\).
Por ejemplo,
\(\forall n\in\mathbb Z\;(n+0=n)\)
es verdadera. No afirma que exista algún entero con esa propiedad, sino que ninguno queda fuera.
Una afirmación universal es fuerte
Para establecer \(\forall x\in D\;P(x)\) no basta comprobar muchos casos. Incluso un millón de ejemplos compatibles no elimina la posibilidad de que exista un caso posterior que falle.
En un dominio finito pequeño podríamos revisar todos los elementos. En dominios grandes o infinitos, normalmente necesitaremos un argumento general. Ese repertorio de argumentos será tema de C10; aquí nos importa reconocer la estructura lógica del objetivo.
Universal con condición
Una forma extremadamente común es
\[ \forall x\in D\;[A(x)\Rightarrow B(x)]. \]
Se lee: “para todo \(x\) del dominio, si \(x\) cumple \(A\), entonces cumple \(B\)”. Los objetos que no satisfacen \(A\) no constituyen contraejemplos, porque en ellos el antecedente es falso.
6.5. Refutar un universal: el poder de un contraejemplo
Hay una asimetría fundamental entre demostrar y refutar una afirmación universal.
Para confirmar
\(\forall x\in D\;P(x)\)
necesitamos controlar todos los casos. Para refutarla basta encontrar un solo elemento \(a\in D\) tal que \(P(a)\) sea falsa.
Ese elemento se llama contraejemplo.
Consideremos la afirmación:
Para todo entero \(n\), se cumple \(n^2>n\).
Basta tomar \(n=0\). Entonces \(0^2>0\) es falso. Por tanto la afirmación universal es falsa.
Un contraejemplo debe respetar exactamente el dominio y las hipótesis. Si la afirmación dice “todo entero par mayor que \(2\)…”, un número impar o el entero \(2\) no puede refutarla.
Ejemplo no es demostración
Encontrar cinco casos en los que una propiedad funciona puede sugerir una conjetura. No demuestra una afirmación universal. En cambio, encontrar un solo caso en el que falla sí decide la cuestión en sentido negativo.
6.6. El cuantificador existencial
El símbolo \(\exists\) se lee “existe al menos uno”. La afirmación
\[ \exists x\in D\;P(x) \]
dice que hay por lo menos un elemento del dominio que satisface \(P\).
Para demostrar una afirmación existencial concreta suele bastar exhibir un testigo.
Por ejemplo,
\(\exists n\in\mathbb Z\;(n^2=49)\)
es verdadera porque \(n=7\) es un testigo. También \(n=-7\) lo es. La existencia no implica unicidad.
Existencia no significa “sé cuál es”
En matemática avanzada existen demostraciones de existencia que no construyen explícitamente el objeto. En este capítulo, sin embargo, la mayoría de nuestros ejemplos serán constructivos: producir un testigo será el modo más transparente de entender el cuantificador.
Refutar un existencial
Para mostrar que \(\exists x\in D\;P(x)\) es falsa debemos establecer que ningún elemento del dominio funciona. La mera frase “no encontré ninguno” no es un argumento.
6.7. Negar cuantificadores
Éste es uno de los núcleos del capítulo.
Negar “todos cumplen \(P\)” significa afirmar “hay al menos uno que no cumple \(P\)”. Por eso:
\[ \neg(\forall x\,P(x))\equiv\exists x\,\neg P(x). \]
Del mismo modo, negar “existe alguno que cumple \(P\)” significa afirmar “ninguno cumple \(P\)”, es decir:
\[ \neg(\exists x\,P(x))\equiv\forall x\,\neg P(x). \]
Estas leyes son los análogos cuantificados de las leyes de De Morgan de C5: al atravesar el cuantificador, la negación cambia \(\forall\) por \(\exists\) y \(\exists\) por \(\forall\).
La negación debe seguir avanzando
Supongamos
\[ \forall n\in\mathbb Z\;[E(n)\Rightarrow E(n^2)], \]
donde \(E(n)\) significa “\(n\) es par”. Su negación no es simplemente cambiar \(\forall\) por \(\exists\). Debemos negar también el contenido:
\[ \exists n\in\mathbb Z\;\neg[E(n)\Rightarrow E(n^2)]. \]
Por C5, \(\neg(A\Rightarrow B)\equiv A\land\neg B\). Así obtenemos
\[ \exists n\in\mathbb Z\;[E(n)\land\neg E(n^2)]. \]
Es decir: “existe un entero par cuyo cuadrado no es par”.
“No todos” y “ninguno” no son lo mismo
“no todos los elementos cumplen \(P\)” se traduce como \(\exists x\,\neg P(x)\).
“ningún elemento cumple \(P\)” se traduce como \(\forall x\,\neg P(x)\).
Confundir estas dos frases es uno de los errores lógicos más frecuentes.
Nota pedagógica — Cuando el dominio no contiene objetos
Aquí hacemos una excepción explícita a la convención de dominios no vacíos: permitimos \(D=\varnothing\), es decir, un dominio sin elementos. Para cualquier predicado definido sobre \(D\), \(\forall x\in D\,P(x)\) es verdadera: no hay un elemento que la refute. En cambio, \(\exists x\in D\,P(x)\) es falsa: no hay un testigo. Esto no atribuye una propiedad a un objeto inexistente; describe qué exige cada cuantificador.
| Dominio sin elementos | Valor | Razón |
|---|---|---|
| \(\forall x\in D\,P(x)\) | Verdadero | No hay contraejemplo |
| \(\exists x\in D\,P(x)\) | Falso | No hay testigo |
| \(\neg\forall x\in D\,P(x)\) | Falso | Su equivalente existencial no tiene testigo |
| \(\forall x\in D\,\neg P(x)\) | Verdadero | Tampoco hay contraejemplo para este universal |
Control resuelto. En \(D=\varnothing\), «todos los objetos satisfacen \(P\)» y «ningún objeto satisface \(P\)» son ambas verdaderas, mientras que «alguno satisface \(P\)» es falsa. No hay contradicción: los dos universales no afirman existencia. En un dominio no vacío, en cambio, no pueden ser ambos verdaderos. Al leer una cuantificación restringida, pregunta por separado si hay objetos que satisfagan la restricción y qué se afirma de ellos.
6.8. Cuantificación restringida
La notación
\(\forall x\in A\;P(x)\)
dice que sólo nos interesan los elementos de \(A\). Conceptualmente puede leerse como
\[ \forall x\;[x\in A\Rightarrow P(x)]. \]
En cambio,
\(\exists x\in A\;P(x)\)
se interpreta como
\[ \exists x\;[x\in A\land P(x)]. \]
La diferencia entre implicación y conjunción es esencial.
Para un universal restringido, un objeto que no pertenece a \(A\) no debe convertirse en contraejemplo. Para un existencial restringido, el testigo debe cumplir simultáneamente dos requisitos: pertenecer a \(A\) y satisfacer \(P\).
No desarrollaremos aún operaciones con conjuntos; C7 dará a \(\in\), subconjunto, unión, intersección y complemento un tratamiento sistemático. Aquí usamos la pertenencia sólo para expresar dominios restringidos.
Negaciones restringidas
De las reglas anteriores obtenemos directamente:
\[ \neg[\forall x\in A\;P(x)]\equiv\exists x\in A\;\neg P(x), \]
\[ \neg[\exists x\in A\;P(x)]\equiv\forall x\in A\;\neg P(x). \]
6.9. Alcance, paréntesis y variables
Todo cuantificador tiene un alcance: la parte de la fórmula sobre la cual actúa.
Comparemos:
\[ \forall x\,[P(x)\lor Q(x)] \]
y
\[ (\forall x\,P(x))\lor Q(x). \]
En la primera fórmula, las dos apariciones de \(x\) están bajo el alcance del cuantificador. En la segunda, sólo la aparición dentro de \(P(x)\) está ligada; la \(x\) de \(Q(x)\) queda libre.
Los paréntesis no son decoración. Determinan qué fragmento está cuantificado.
Renombrar sin capturar
En
\(\forall x\,P(x,y)\)
podemos cambiar la variable ligada \(x\) por \(t\) y escribir \(\forall t\,P(t,y)\). Pero no deberíamos renombrarla como \(y\) sin más, porque la \(y\) original era libre. La escritura \(\forall y\,P(y,y)\) ha ligado una variable que antes no lo estaba y, por tanto, puede expresar algo distinto.
La disciplina de alcance cumple aquí la misma función que el control de subfórmulas en C5: antes de transformar símbolos debemos saber qué estructura estamos modificando.
Nota pedagógica — Renombrar exige seguir cada aparición
Una misma letra puede tener apariciones libres y ligadas dentro de una fórmula. En \(\forall x\,[R(x,y)\land\exists y\,S(x,y,z)]\), las dos apariciones de \(x\) en los predicados están ligadas por el universal. La aparición de \(y\) en \(R\) es libre; la de \(y\) en \(S\) está ligada por el existencial. La aparición de \(z\) es libre. El cuantificador interior no alcanza hacia la izquierda fuera de su propio subenunciado.
Para renombrar con seguridad, toma letras que no aparezcan en la fórmula. Primero escribe \(\forall x\,[R(x,y)\land\exists t\,S(x,t,z)]\) y después \(\forall u\,[R(u,y)\land\exists t\,S(u,t,z)]\). Se conserva la aparición libre de \(y\) y la dependencia del testigo interior respecto de \(u\). Sustituir todas las letras iguales sin identificar su alcance puede cambiar el problema.
Control resuelto. Con \(D=\{0,1\}\) y el parámetro libre \(y=0\), \(\forall x\in D\,(x\le y)\) es falsa porque \(1\nleq0\). La sustitución indebida \(\forall y\in D\,(y\le y)\) es verdadera. Capturar el parámetro convirtió una comparación con un valor fijado en otra afirmación. El renombrado correcto es \(\forall t\in D\,(t\le y)\), que conserva el contraejemplo \(t=1\).
6.10. Dos cuantificadores: el orden importa
Cuando aparecen cuantificadores de distinto tipo, cambiar su orden puede cambiar radicalmente el significado.
Consideremos, sobre \(\mathbb R\):
\[ \forall x\;\exists y\;(y>x). \]
La afirmación es verdadera: dado un real \(x\), podemos elegir \(y=x+1\).
Comparemos con
\[ \exists y\;\forall x\;(y>x). \]
Ahora se pide un único real \(y\) que sea mayor que todos los reales. Eso es imposible.
La diferencia verbal es:
- \(\forall x\exists y\): para cada \(x\) podemos buscar un \(y\), posiblemente distinto;
- \(\exists y\forall x\): debe existir un mismo \(y\) que funcione para todos los \(x\).
Cuantificadores del mismo tipo
Bajo condiciones ordinarias,
\(\forall x\forall y\,P(x,y)\)
y
\(\forall y\forall x\,P(x,y)\)
expresan lo mismo. Análogamente ocurre con dos existenciales. El peligro aparece especialmente al intercambiar \(\forall\) y \(\exists\).
Nota pedagógica — Buscar por filas o buscar una columna común
Para una relación entre dos dominios finitos, representa cada primer objeto en una fila y cada posible testigo en una columna. Marca verdadero o falso en cada casilla. \(\forall x\,\exists y\,R(x,y)\) pide al menos una casilla verdadera en cada fila; \(\exists y\,\forall x\,R(x,y)\) pide una columna completamente verdadera. El segundo criterio exige un testigo que sirva simultáneamente a todos.
Control resuelto. Sean las filas \(a,b\) y las columnas \(p,q,r\), con esta tabla:
| \(R\) | \(p\) | \(q\) | \(r\) |
|---|---|---|---|
| \(a\) | V | F | V |
| \(b\) | F | V | V |
Cada fila tiene un testigo, y además \(r\) sirve a ambas. Las dos fórmulas son verdaderas. Si cambiamos solamente \(R(b,r)\) a falso, cada fila conserva algún testigo, pero ninguna columna sirve a ambas: la primera fórmula sigue siendo verdadera y la segunda pasa a falsa. Tener permiso para elegir según la fila no significa estar obligado a elegir testigos distintos; cuando hay una columna común, también podemos usarla en todas las filas. En dominios vacíos hay que volver a las definiciones de los cuantificadores, pues puede faltar una fila o una columna.
6.11. Dependencia entre variables y elección de testigos
En
\[ \forall x\;\exists y\;R(x,y), \]
el valor de \(y\) puede elegirse después de conocer \(x\). Por ello el testigo puede depender de \(x\).
Ejemplo:
\[ \forall x\in\mathbb R\;\exists y\in\mathbb R\;(y=2x). \]
Una elección natural es \(y=2x\). No estamos exhibiendo un único número real; estamos dando una regla de elección que produce un testigo para cada \(x\).
En cambio, en
\[ \exists y\;\forall x\;R(x,y), \]
el \(y\) debe fijarse antes de recorrer todos los \(x\). Ya no puede adaptarse a cada caso.
Esta idea anticipa un tema futuro: una regla que asigna a cada entrada una salida. C9 estudiará las funciones de forma sistemática. Aquí sólo necesitamos comprender la dependencia lógica.
Una advertencia
De \(\forall x\exists y\,R(x,y)\) no se sigue automáticamente que haya un único \(y\) para cada \(x\), ni que la elección sea canónica. La afirmación promete existencia local, nada más.
6.12. “Existe un único”: el cuantificador de unicidad
La notación
\[ \exists!x\;P(x) \]
se lee “existe un único \(x\) tal que \(P(x)\)”. Contiene dos afirmaciones distintas:
- existencia: al menos un elemento satisface \(P\);
- unicidad: no hay dos elementos distintos que satisfagan \(P\).
Una expansión útil es
\[ \exists x\,[P(x)\land\forall y\,(P(y)\Rightarrow y=x)]. \]
El primer \(P(x)\) garantiza existencia. El universal posterior dice que cualquier otro candidato \(y\) que satisfaga \(P\) debe coincidir con \(x\).
Por ejemplo,
\(\exists!x\in\mathbb R\;(x+3=5)\)
es verdadera: \(x=2\) existe y cualquier real que satisfaga la ecuación debe ser \(2\).
En cambio,
\(\exists!x\in\mathbb R\;(x^2=4)\)
es falsa. Hay soluciones, pero son dos: \(2\) y \(-2\).
Existencia y unicidad deben comprobarse por separado.
Nota pedagógica — Tres preguntas sobre los testigos
Existencia, a lo sumo un testigo y exactamente un testigo son afirmaciones distintas. La condición «a lo sumo uno» se expresa como \(\forall u\,\forall v\,[(P(u)\land P(v))\Rightarrow u=v]\). No exige que exista alguno: se cumple también cuando ningún objeto satisface \(P\). Para obtener unicidad existencial debemos añadir \(\exists x\,P(x)\).
| Número de testigos | Existe alguno | Hay a lo sumo uno | Existe exactamente uno |
|---|---|---|---|
| 0 | F | V | F |
| 1 | V | V | V |
| 2 o más | V | F | F |
Control resuelto. En \(D=\{0,1,2\}\), para \(P_a(x):x<a\), hay cero testigos si \(a=0\), uno si \(a=1\) y dos si \(a=2\). Por eso la afirmación \(\exists!x\in D\,P_a(x)\) falla por falta de existencia en el primer caso y por falta de unicidad en el tercero. Su negación dice: ningún objeto satisface \(P_a\), o hay dos objetos distintos que lo satisfacen. Si \(D\) está vacío —excepción explícita a la convención inicial—, se cumple «a lo sumo uno», pero falla «existe exactamente uno».
6.13. Traducir lenguaje matemático a símbolos
La traducción correcta comienza identificando tres cosas:
- dominio;
- cuantificador;
- predicado y conectivos internos.
Ejemplo:
Todo entero par es divisible por \(2\).
Una formalización natural es
\[ \forall n\in\mathbb Z\;[E(n)\Rightarrow D_2(n)], \]
donde \(E(n)\) significa “\(n\) es par” y \(D_2(n)\) significa “\(2\) divide a \(n\)”.
Ejemplo:
Algunos enteros no son cuadrados perfectos.
Puede escribirse
\[ \exists n\in\mathbb Z\;\neg C(n), \]
donde \(C(n)\) significa “\(n\) es un cuadrado perfecto”.
Palabras que revelan estructura
- “todo”, “cada”, “cualquiera” suelen señalar \(\forall\);
- “algún”, “existe”, “hay al menos uno” suelen señalar \(\exists\);
- “ningún” suele convertirse en \(\forall x\,\neg P(x)\) o, equivalentemente, \(\neg\exists x\,P(x)\);
- “no todos” significa \(\exists x\,\neg P(x)\);
- “exactamente uno” señala \(\exists!\).
No debemos traducir palabra por palabra: debemos traducir estructura por estructura.
6.14. Traducir símbolos a lenguaje matemático
La dirección inversa exige la misma disciplina. Consideremos
\[ \forall x\in\mathbb R\;\exists y\in\mathbb R\;(y>x). \]
Una lectura fiel es:
Para todo número real \(x\), existe un número real \(y\) mayor que \(x\).
Una lectura defectuosa sería:
Existe un real mayor que todos los reales.
Esa frase corresponde al orden inverso de cuantificadores.
Leer desde afuera hacia adentro
Una rutina segura es:
- leer el cuantificador más externo;
- fijar mentalmente su variable;
- pasar al siguiente cuantificador;
- respetar el orden;
- leer finalmente el predicado interno.
Por ejemplo,
\[ \exists m\in\mathbb Z\;\forall n\in\mathbb Z\;(m+n=n) \]
se lee: “existe un entero \(m\) tal que, para todo entero \(n\), se cumple \(m+n=n\)”. La afirmación resulta verdadera porque \(m=0\) funciona para todos los \(n\).
6.15. Diagnóstico de errores de cuantificación
Los errores más importantes de este capítulo no son de cálculo, sino de significado.
Error 1: cambiar el cuantificador al traducir
“Todo entero tiene un sucesor entero” no significa “existe un entero que es sucesor de todos los enteros”.
Error 2: negar sin cambiar cuantificador
La negación de \(\forall x\,P(x)\) no es \(\forall x\,\neg P(x)\), sino \(\exists x\,\neg P(x)\).
Error 3: ignorar el dominio
El predicado \(x^2=2\) produce afirmaciones existenciales distintas sobre \(\mathbb Q\) y sobre \(\mathbb R\).
Error 4: confundir testigo dependiente con testigo fijo
En \(\forall x\exists y\), el \(y\) puede variar con \(x\). En \(\exists y\forall x\), no.
Error 5: confundir existencia con unicidad
Encontrar un testigo prueba existencia, no existencia única.
Error 6: perder el alcance
Mover paréntesis o renombrar variables puede ligar una variable que antes era libre.
Ante una solución dudosa conviene localizar el primer paso donde cambia el significado, no sólo el lugar donde aparece un resultado falso.
6.16. Cierre — protocolo de lectura cuantificada
Cuando encuentres una afirmación con variables y cuantificadores, utiliza esta rutina:
1. ¿CUÁL ES EL DOMINIO?
2. ¿CUÁL ES EL PREDICADO?
3. ¿QUÉ VARIABLES ESTÁN LIBRES?
4. ¿QUÉ VARIABLES ESTÁN LIGADAS?
5. ¿QUÉ CUANTIFICADOR LIGA A CADA VARIABLE?
6. ¿CUÁL ES EL ALCANCE DE CADA CUANTIFICADOR?
7. ¿EN QUÉ ORDEN APARECEN?
8. ¿UN TESTIGO PUEDE DEPENDER DE VARIABLES ANTERIORES?
9. ¿CÓMO SE NIEGA LA AFIRMACIÓN COMPLETA?
10. ¿QUÉ BASTARÍA PARA REFUTARLA O PARA EXHIBIR EXISTENCIA?El paso conceptual de C6 puede resumirse así:
\[ \text{condición abierta} \longrightarrow \text{dominio + cuantificación} \longrightarrow \text{afirmación precisa}. \]
A partir de ahora, expresiones como “para todo”, “existe” y “existe un único” dejarán de ser palabras de apoyo y se convertirán en parte visible de la estructura matemática.
Ejercicios del capítulo
A — Predicados y dominios
1. Clasifica cada escritura como expresión, predicado abierto o proposición: (a) \(x+1\); (b) \(x+1=5\); (c) \(4+1=5\); (d) \(n\) es par; (e) “\(6\) es par”.
2. Sea \(P(x):x^2=2\). Decide la verdad de \(\exists x\,P(x)\) cuando el dominio es (a) \(\mathbb Z\); (b) \(\mathbb Q\); (c) \(\mathbb R\).
3. Sea \(P(x):x^2\ge x\). Decide si \(\forall x\,P(x)\) es verdadera sobre (a) \(\{0,1\}\); (b) \(\mathbb Z\); (c) \(\mathbb R\).
4. Para \(Q(x):1/x>0\), explica por qué el dominio \(\mathbb R\) exige una precisión adicional antes de evaluar \(Q(0)\).
5. Da un dominio finito \(D\) con al menos dos elementos para el cual \(\forall x\in D\;(x^2=1)\) sea verdadera, y otro dominio finito \(E\) para el cual sea falsa.
6. Sea \(R(x):x^2<4\). Compara \(\forall x\,R(x)\) y \(\exists x\,R(x)\) sobre los dominios \(\mathbb Z\) y \(\mathbb R\).
B — Variables libres y ligadas
7. Identifica las variables libres y ligadas en \(\forall x\,P(x,y)\).
8. Identifica las variables libres y ligadas en \(\exists y\,[R(x,y)\land Q(y,z)]\).
9. ¿Es una proposición cerrada \(\forall x\,\exists y\,R(x,y)\)? ¿Y \(\forall x\,\exists y\,R(x,y,z)\)?
10. Convierte el predicado \(P(x):x^2=9\) en (a) una proposición mediante sustitución; (b) una proposición existencial; (c) una proposición universal, usando dominio \(\mathbb R\).
11. En \(\forall x\,[P(x,y)\Rightarrow\exists z\,R(x,z)]\), clasifica \(x,y,z\) como libres o ligadas.
12. Reescribe \(\forall x\,P(x,y)\) cambiando el nombre de la variable ligada sin cambiar el significado. Explica por qué \(\forall y\,P(y,y)\) no es, en general, una renominación válida.
C — Universales y contraejemplos
13. Decide si \(\forall n\in\mathbb Z\;(n^2\ge0)\) es verdadera y explica qué tipo de justificación requiere.
14. Refuta \(\forall n\in\mathbb Z\;(n^2>n)\) con un contraejemplo.
15. Refuta la afirmación “la suma de dos enteros impares es impar”.
16. Un estudiante verifica que \(n^2+n+17\) es primo para \(n=0,1,\dots,15\) y concluye que es primo para todo \(n\ge0\). Explica el error y encuentra un contraejemplo.
17. La afirmación es: “para todo entero \(n\), si \(n\) es par entonces \(n^2\) es par”. ¿Puede un entero impar ser contraejemplo? Justifica.
18. Da un contraejemplo a “para todo real \(x\), si \(x^2>1\) entonces \(x>1\)”.
D — Existenciales y testigos
19. Demuestra exhibiendo un testigo que \(\exists n\in\mathbb Z\;(n^2=49)\).
20. Decide si \(\exists n\in\mathbb Z\;(2n=7)\) es verdadera.
21. Exhibe un testigo para \(\exists x\in\mathbb R\;(0<x<1\land x^2<x)\).
22. Exhibe enteros \(a,b\) que prueben \(\exists a,b\in\mathbb Z\;(a^2-b^2=15)\).
23. Demuestra que \(\exists n\in\mathbb Z\;(n>1000)\) exhibiendo un testigo. ¿Qué demuestra este ejercicio sobre el tamaño del testigo?
24. Un estudiante encuentra dos testigos distintos para \(\exists x\,P(x)\) y concluye que la afirmación era falsa porque “\(x\) no es único”. Diagnostica el error.
E — Negación de cuantificadores
25. Niega \(\forall x\in\mathbb R\;(x^2\ge0)\) sin dejar una negación delante del cuantificador.
26. Niega \(\exists n\in\mathbb Z\;(n^2=2)\).
27. Niega \(\forall n\in\mathbb Z\;[E(n)\Rightarrow E(n^2)]\), donde \(E(k)\) significa “\(k\) es par”.
28. Niega \(\exists x\in\mathbb R\;(x>0\land x^2<1)\).
29. Niega \(\forall x\in\mathbb R\;\exists y\in\mathbb R\;(y>x)\).
30. Niega \(\exists y\in\mathbb R\;\forall x\in\mathbb R\;(y>x)\).
31. Traduce simbólicamente: “No todos los enteros son positivos”.
32. Explica con un ejemplo por qué \(\neg\forall x\,P(x)\) no equivale a \(\forall x\,\neg P(x)\).
F — Cuantificación restringida
33. Reescribe \(\forall n\in\mathbb Z\;P(n)\) usando un dominio mayor \(D\) que contiene a \(\mathbb Z\) y una implicación con pertenencia.
34. Reescribe \(\exists n\in\mathbb Z\;(n^2=9)\) usando un dominio mayor \(D\) y una conjunción con pertenencia.
35. Niega \(\forall x\in A\;P(x)\).
36. Niega \(\exists x\in A\;P(x)\).
37. Un estudiante escribe “todo entero es racional” como \(\forall x\,[x\in\mathbb Z\land x\in\mathbb Q]\). Explica por qué esa forma es incorrecta y corrígela suponiendo un dominio numérico mayor.
38. Un estudiante escribe “existe un entero negativo” como \(\exists x\,[x\in\mathbb Z\Rightarrow x<0]\). Diagnostica el error y corrige.
G — Alcance y paréntesis
39. En \(\forall x\,[P(x)\Rightarrow(Q(x)\lor R)]\), ¿qué apariciones de \(x\) están ligadas?
40. En \((\forall x\,P(x,y))\lor Q(y)\), ¿qué variables quedan libres?
41. Compara \(\forall x\,[P(x)\lor Q(x)]\) con \((\forall x\,P(x))\lor Q(x)\). ¿Por qué no son la misma clase de expresión?
42. Renombra la variable ligada en \(\exists x\,[x>y\land P(x)]\) sin alterar la variable libre \(y\).
43. Explica por qué sustituir \(\forall x\,P(x,y)\) por \(\forall y\,P(y,y)\) puede cambiar el significado.
44. Distingue \(\forall x\,[P(x)\land Q(x)]\) de \((\forall x\,P(x))\land Q(x)\).
H — Orden de cuantificadores
45. Sobre \(\mathbb R\), decide la verdad de (a) \(\forall x\exists y\;(y>x)\); (b) \(\exists y\forall x\;(y>x)\).
46. Sobre \(\mathbb R\), compara \(\forall x\exists y\;(y=x+1)\) con \(\exists y\forall x\;(y=x+1)\).
47. Sobre \(\mathbb Z\), decide \(\forall n\exists m\;(m=n+2)\) y su versión con cuantificadores invertidos.
48. Sobre \(\mathbb Z\), decide (a) \(\exists n\forall m\;(n+m=m)\); (b) \(\forall m\exists n\;(n+m=m)\).
49. Sobre \(\mathbb R\), decide \(\forall x\exists y\;(xy=1)\). ¿Qué cambia si el dominio de \(x\) es \(\mathbb R\setminus\{0\}\)?
50. Sobre \(\mathbb R\), decide (a) \(\exists y\forall x\;(xy=x)\); (b) \(\forall x\exists y\;(xy=x)\).
51. Explica por qué \(\forall x\forall y\,P(x,y)\) puede reordenarse como \(\forall y\forall x\,P(x,y)\), y análogamente para dos existenciales, mientras que el intercambio \(\forall x\exists y\leftrightarrow\exists y\forall x\) no es válido en general.
52. En el dominio \(D=\{1,2\}\), sea \(R(x,y)\) la relación “\(x=y\)”. Decide \(\forall x\exists y\,R(x,y)\) y \(\exists y\forall x\,R(x,y)\).
I — Dependencia y elección de testigos
53. Para \(\forall x\in\mathbb R\exists y\in\mathbb R\;(y=2x)\), da una elección de testigo y explica su dependencia.
54. Explica por qué en \(\forall x\in\mathbb R\exists y\in\mathbb R\;(y>x)\) no puede usarse un único \(y\) fijo para todos los \(x\), aunque la afirmación sea verdadera.
55. Interpreta la dependencia en \(\forall n\in\mathbb Z\exists m\in\mathbb Z\;(m=n^2)\).
56. En \(\exists m\in\mathbb Z\forall n\in\mathbb Z\;(m+n=n)\), encuentra el testigo y explica por qué debe ser fijo.
57. ¿Implica \(\forall x\exists y\,R(x,y)\) que para cada \(x\) haya exactamente un \(y\) con \(R(x,y)\)? Justifica.
58. Sea \(M(p,q)\) el predicado “\(q\) es madre de \(p\)”. Traduce y compara: (a) “toda persona tiene alguna madre”; (b) “existe una persona que es madre de todas las personas”.
J — Existencia única
59. Decide \(\exists!x\in\mathbb R\;(x+3=5)\) y justifica existencia y unicidad.
60. Decide \(\exists!n\in\mathbb Z\;(2n=6)\).
61. Decide \(\exists!x\in\mathbb R\;(x^2=4)\).
62. Expande \(\exists!x\,P(x)\) usando sólo \(\exists\), \(\forall\), \(\land\), \(\Rightarrow\) e igualdad.
K — Traducción bidireccional
63. Formaliza: “Todo entero tiene un entero mayor”.
64. Formaliza: “Entre un entero \(n\) y su sucesor \(n+1\) no existe ningún entero”.
65. Formaliza: “Existe un real positivo cuyo cuadrado es menor que él mismo”.
66. Formaliza: “No todo número real es positivo”.
67. Traduce a lenguaje verbal: \(\forall n\in\mathbb Z\;[O(n)\Rightarrow O(n^2)]\), donde \(O(k)\) significa “\(k\) es impar”.
68. Traduce a lenguaje verbal: \(\exists m\in\mathbb Z\;\forall n\in\mathbb Z\;(m+n=n)\).
L — Diagnóstico y síntesis
69. Un estudiante niega \(\forall x\in\mathbb R\;(x^2\ge0)\) escribiendo \(\forall x\in\mathbb R\;(x^2<0)\). Localiza el primer error y repara la negación.
70. Un estudiante traduce “para cada estudiante hay un libro que ese estudiante eligió” como \(\exists b\forall e\,E(e,b)\). Explica el cambio de significado y corrige.
71. Sobre \(\mathbb R\), decide la verdad de: (a) \(\forall x\exists y\;(x+y=0)\); (b) \(\exists y\forall x\;(x+y=0)\); (c) \(\forall x\forall y\;(x+y=0)\); (d) \(\exists x\exists y\;(x+y=0)\). Niega además la afirmación (a).
72. Analiza la afirmación: “Para todo real \(x\) existe un único real \(y\) tal que \(2y+x=0\)”. (a) Escríbela simbólicamente; (b) decide su verdad; (c) identifica la dependencia de \(y\); (d) escribe su negación sin usar \(\exists!\).
M — Problemas tipo prueba
Los siguientes ejercicios están pensados como problemas de evaluación escrita. Exigen desarrollo completo, control del alcance de los cuantificadores y justificación explícita de testigos, contraejemplos o dependencias.
73. Sobre \(\mathbb R\), analiza las cuatro afirmaciones siguientes. Para cada una: (i) decide si es verdadera o falsa; (ii) si es verdadera, da una regla explícita para elegir el testigo; (iii) si es falsa, exhibe una contradicción o un contraejemplo; (iv) explica qué cambia al invertir el orden de los cuantificadores.
\(\forall x\in\mathbb R\setminus\{0\}\;\exists y\in\mathbb R\;(xy=1)\).
\(\exists y\in\mathbb R\;\forall x\in\mathbb R\setminus\{0\}\;(xy=1)\).
\(\forall x\in\mathbb R\;\exists y\in\mathbb R\;(y>x)\).
\(\exists y\in\mathbb R\;\forall x\in\mathbb R\;(y>x)\).
74. Considera la afirmación
\[ \forall x\in\mathbb R\;\Big[x\ge0\Rightarrow\exists y\in\mathbb R\;(y\ge0\land y^2=x)\Big]. \]
- Exprésala en lenguaje natural.
- Négala paso a paso hasta obtener una fórmula en la que la negación actúe sólo sobre relaciones atómicas.
- Decide la verdad de la afirmación original y de su negación.
- Explica por qué cambiar sólo \(\forall\) por \(\exists\) no produce todavía la negación correcta.
75. Estudia la afirmación
\[ \forall x\in\mathbb R\;\exists!y\in\mathbb R\;(3y-2=x). \]
- Expande \(\exists!\) usando únicamente \(\exists\), \(\forall\), conjunción, igualdad e implicación.
- Demuestra existencia y unicidad para un \(x\) arbitrario.
- Escribe una negación equivalente que exprese explícitamente las dos maneras en que puede fallar la unicidad existencial: inexistencia o existencia de dos testigos distintos.
- Compara con \(\exists!y\in\mathbb R\;\forall x\in\mathbb R\;(3y-2=x)\) y decide su valor de verdad.
76. Sobre \(\mathbb Z\), compara
\[ A:\quad \forall m\;\exists n\;\forall k\;(k\ge n\Rightarrow k>m) \]
y
\[ B:\quad \exists n\;\forall m\;\forall k\;(k\ge n\Rightarrow k>m). \]
- Decide la verdad de \(A\) y construye un testigo \(n\) en función de \(m\).
- Decide la verdad de \(B\) y da un contraejemplo que funcione para cualquier candidato \(n\).
- Niega \(A\) empujando la negación hasta la relación atómica.
- Explica en una frase qué dependencia permite \(A\) y prohíbe \(B\).
77. Para un dominio \(D\), considera
\[ S(D):\quad \forall x\in D\;\exists y\in D\;(y^2=x^2+1). \]
- Decide si \(S(\mathbb R)\) es verdadera y justifica una elección de \(y\) para cada \(x\).
- Decide si \(S(\mathbb Z)\) es verdadera. Si es falsa, encuentra el contraejemplo más simple que puedas.
- Escribe la negación de \(S(\mathbb Z)\) sin dejar una negación delante de un cuantificador.
- Explica por qué la misma fórmula sintáctica expresa afirmaciones diferentes al cambiar el dominio.
78. Sean \(E\) el conjunto de estudiantes, \(P\) el conjunto de problemas y \(S(e,p)\) el predicado “el estudiante \(e\) resolvió el problema \(p\)”. Formaliza la frase:
Todo estudiante resolvió al menos un problema que ningún otro estudiante resolvió.
- Escribe una fórmula cuantificada completa.
- Niega tu fórmula y lleva la negación hasta los predicados atómicos.
- Traduce la negación obtenida nuevamente al castellano.
- Explica por qué mover el cuantificador \(\exists p\) delante de \(\forall e\) cambia el significado.
79. Considera la fórmula abierta
\[ F(y,z):\quad \forall x\,[P(x,y)\Rightarrow\exists y\,Q(x,y,z)]. \]
- Identifica todas las apariciones libres y ligadas de variables.
- Renombra la variable ligada del cuantificador existencial para eliminar la reutilización del símbolo \(y\) sin cambiar el significado.
- Explica por qué renombrar ingenuamente el \(\forall x\) como \(\forall y\) puede capturar una variable que antes era libre.
- Forma la clausura universal de la fórmula corregida.
- Niega esa clausura universal hasta obtener una fórmula donde la negación actúe sólo sobre \(Q\).
80. Analiza la afirmación
\[ \forall x\in\mathbb R\;\exists!y\in\mathbb R\; \Big[y>x\land\forall z\in\mathbb R\,(z>x\Rightarrow y\le z)\Big]. \]
- Traduce cuidadosamente la afirmación al castellano.
- Decide si es verdadera o falsa.
- Si suponemos que un \(y\) satisface la condición para cierto \(x\), construye explícitamente un real \(z\) que destruya esa posibilidad.
- Explica si el fracaso está en la existencia, en la unicidad o en ambas.
- Escribe en lenguaje natural una negación exacta de la afirmación original.
N — Dominios, dependencia y fronteras de la unicidad
81. Para \(P(x):0<x<2\), clasifica \(\forall x\in D\,P(x)\) y \(\exists x\in D\,P(x)\) cuando \(D\) es \(\{1\}\), \(\{0,1\}\), \(\{0,2\}\) y \(\varnothing\). En el último caso se permite expresamente un dominio vacío. Justifica cada valor y compara «no todos» con «ninguno».
82. Mantén fija \(\forall x\in D\,\exists y\in D\,(y=x+1)\). Decide su verdad para \(D=\mathbb Z\), \(D=\{0,1,2\}\), \(D=\{0,1,2,\ldots\}\) y \(D=\varnothing\) (excepción expresa). Escribe su negación y explica por qué ampliar de \(\{0,1,2\}\) a los enteros no negativos cambia el resultado.
83. Para \(D=\{1,2\}\), \(\{0,1,2\}\), \(\{0\}\) y \(\varnothing\) (permitido aquí), clasifica \(\forall x\in D\,(x<0\Rightarrow x^2=1)\) y \(\exists x\in D\,(x<0\land x^2=1)\). ¿Un universal verdadero garantiza un objeto que cumpla el antecedente?
84. Para \(D=\{0,1\}\), \(\{0,1,2\}\), \(\{-1,0,1\}\) y \(\varnothing\) (excepción expresa), clasifica \(\forall x\in D\,\exists y\in D\,(x+y=1)\). En cada dominio no vacío, indica un testigo para cada \(x\) o un \(x\) sin testigo. Niega la fórmula.
85. Construye una tabla V/F con filas \(a,b,c\) y columnas \(p,q\), tal que \(\forall x\exists y\,R(x,y)\) sea verdadera y \(\exists y\forall x\,R(x,y)\) falsa. Escribe las dos negaciones y exhibe los testigos que las verifican o refutan.
86. Construye una tabla con dos filas y tres columnas donde las dos fórmulas del ejercicio 85 sean verdaderas, pero cada fila tenga al menos un testigo que no sirva a la otra. Cambia una sola casilla para hacer falsa únicamente la fórmula con testigo común. Justifica.
87. Sea \(D=\{a,b,c\}\) y sea \(R(x,y)\) verdadero exactamente cuando \(x\ne y\). Compara \(\forall x\exists y\,R(x,y)\), \(\exists y\forall x\,R(x,y)\) y \(\forall x\exists!y\,R(x,y)\). Repite para \(D=\{a,b\}\) y \(D=\{a\}\).
88. Para dominios de filas \(X\) y columnas \(Y\), se permiten aquí dominios vacíos. Determina \(\forall x\in X\exists y\in Y\,R(x,y)\) y \(\exists y\in Y\forall x\in X\,R(x,y)\) cuando: (a) \(X\) vacío e \(Y\) no vacío; (b) \(X\) no vacío e \(Y\) vacío; (c) ambos vacíos. No asignes casillas imaginarias.
89. Sobre los reales, considera \(A:\forall x\exists y\forall z\,[z>x\Rightarrow z>y]\). Niega \(A\) paso a paso, traduce ambas fórmulas y decide su verdad. ¿Es posible escoger un mismo \(y\) para todos los \(x\)?
90. Sobre los enteros, considera \(B:\exists n\forall m\exists k\,[k>m\land k<n]\). Escribe su negación sin negar una fórmula compuesta, traduce ambas y determina sus valores. Identifica de qué puede depender cada elección.
91. Un curso tiene alumnos \(a\), prácticas \(p\) y revisores \(r\) en dominios no vacíos. \(E(a,p)\) significa «\(a\) entregó \(p\)» y \(C(r,a,p)\), «\(r\) corrigió la entrega de \(a\) en \(p\)». Formaliza «para cada alumno hay una práctica que entregó y que todos los revisores corrigieron». Niega exactamente, traduce y explica por qué negar no exige una práctica entregada con una corrección ausente para cada práctica.
92. En \(D=\{0,1\}\), sea \(R(x,y,z)\) la igualdad \(z=x+y\) (suma usual de enteros). Decide \(\forall x\exists y\forall z\,R(x,y,z)\) y \(\forall x\forall z\exists y\,R(x,y,z)\). Escribe sus negaciones y explica la diferencia de dependencia aunque ambas puedan ser falsas.
93. En \(D=\{0,1,2\}\), define \(P_a(x):x<a\) para \(a=0,1,2,3\). Clasifica existencia, «a lo sumo uno» y unicidad existencial, justificando por lista de testigos. Escribe la negación de unicidad sin usar \(\exists!\).
94. Con \(D=\mathbb Z\), para cada entero \(a\) estudia \(\exists!x\in D\,(2x=a)\). Identifica cuándo falla existencia y cuándo puede fallar «a lo sumo uno». Formula ambas partes y su conjunción sin \(\exists!\).
95. Para cada real \(a\), cuenta los testigos de \(P_a(x):x^2=a\) sobre \(\mathbb R\). Determina existencia, a lo sumo uno y exactamente uno. Explica qué cambia si el dominio se restringe a los reales no negativos.
96. Se permite aquí un dominio vacío. Para \(D=\varnothing\), \(D=\{a\}\) y \(D=\{a,b\}\) con \(a\ne b\), estudia \(F:\forall x\in D\exists!y\in D\,(y=x)\) y \(G:\exists!y\in D\forall x\in D\,(y=x)\). Separa existencia y unicidad y explica el papel del cuantificador exterior.
Soluciones razonadas
Las soluciones forman parte del capítulo canónico. En los ejercicios de traducción puede haber variantes lingüísticas equivalentes; lo esencial es conservar dominio, cuantificadores, alcance y dependencia.
Soluciones — A — Predicados y dominios
Solución 1. (a) \(x+1\) es una expresión: representa un número una vez fijado \(x\). (b) \(x+1=5\) es un predicado abierto porque su verdad depende de \(x\). (c) \(4+1=5\) es una proposición y es verdadera. (d) “\(n\) es par” es un predicado abierto. (e) “\(6\) es par” es una proposición verdadera.
Solución 2. En \(\mathbb Z\) no existe entero con cuadrado \(2\), así que es falsa. En \(\mathbb Q\) también es falsa: \(\sqrt2\) no es racional. En \(\mathbb R\) es verdadera, con testigos \(\sqrt2\) y \(-\sqrt2\). El ejercicio muestra que el dominio forma parte del significado.
Solución 3. Sobre \(\{0,1\}\) es verdadera: hay sólo dos casos y ambos dan igualdad. Sobre \(\mathbb Z\) también es verdadera, pues \(x^2-x=x(x-1)\) y para todo entero \(x\) el producto es no negativo: si \(x\le0\), ambos factores son no positivos; si \(x\ge1\), ambos son no negativos. Sobre \(\mathbb R\) es falsa: \(x=1/2\) produce \(1/4<1/2\).
Solución 4. La expresión \(1/x\) no está definida en \(x=0\). Por tanto, si queremos usar \(Q\) como predicado numérico debemos restringir el dominio a valores donde tenga sentido, por ejemplo \(\mathbb R\setminus\{0\}\). No es correcto declarar simplemente \(Q(0)\) falsa: la fórmula ni siquiera está definida allí.
Solución 5. Una elección es \(D=\{-1,1\}\): ambos elementos satisfacen \(x^2=1\). Para que sea falsa basta incluir un contraejemplo; por ejemplo \(E=\{-1,0,1\}\), porque \(0^2\ne1\).
Solución 6. Sobre \(\mathbb Z\), el universal es falso porque \(x=2\) da \(4<4\), falso; el existencial es verdadero, por ejemplo con \(x=0\). Sobre \(\mathbb R\), el universal también es falso, por ejemplo con \(x=3\), y el existencial es verdadero con \(x=0\). Las dos afirmaciones conservan aquí su valor de verdad al cambiar de dominio, aunque sus conjuntos de testigos y contraejemplos cambian.
Soluciones — B — Variables libres y ligadas
Solución 7. El cuantificador \(\forall x\) liga a \(x\) dentro de \(P(x,y)\). La variable \(y\) no tiene cuantificador y queda libre. Por ello la fórmula completa sigue siendo abierta respecto de \(y\).
Solución 8. \(y\) está ligada por \(\exists y\) en todo el alcance entre corchetes. Las variables \(x\) y \(z\) quedan libres.
Solución 9. La primera es cerrada: todas las variables que aparecen, \(x\) e \(y\), están ligadas. La segunda no es cerrada porque \(z\) queda libre. Su valor de verdad puede depender del valor o interpretación de \(z\).
Solución 10. (a) Por ejemplo, sustituyendo \(x=3\) obtenemos \(3^2=9\), verdadera. (b) \(\exists x\in\mathbb R\;(x^2=9)\), verdadera. (c) \(\forall x\in\mathbb R\;(x^2=9)\), falsa. Las tres operaciones cierran la variable, pero producen proposiciones diferentes.
Solución 11. \(x\) está ligada por el cuantificador universal y su alcance incluye tanto \(P(x,y)\) como \(R(x,z)\). \(z\) está ligada por \(\exists z\) dentro del consecuente. \(y\) queda libre porque no aparece cuantificada.
Solución 12. Podemos escribir \(\forall t\,P(t,y)\): \(t\) reemplaza coherentemente a la variable ligada \(x\), mientras \(y\) permanece libre. En cambio, \(\forall y\,P(y,y)\) hace que el cuantificador ligue también la posición que antes correspondía a la \(y\) libre. Se produce captura de variable y el significado puede cambiar.
Soluciones — C — Universales y contraejemplos
Solución 13. Es verdadera. No basta una lista de ejemplos; usamos el hecho general de que el cuadrado de todo real, y por tanto de todo entero, es no negativo. La justificación debe cubrir simultáneamente todos los enteros.
Solución 14. Toma \(n=0\). Entonces \(0^2>0\) es \(0>0\), falso. Por tanto el universal queda refutado. También \(n=1\) funciona como contraejemplo.
Solución 15. Basta un par de enteros impares cuya suma sea par. Por ejemplo, \(1\) y \(3\) son impares y \(1+3=4\) es par. En realidad la afirmación correcta es la contraria: la suma de dos impares es par.
Solución 16. Comprobar finitos casos no demuestra una afirmación universal sobre todos los enteros no negativos. En \(n=16\) se obtiene \(16^2+16+17=289=17^2\), que no es primo. Éste es un contraejemplo decisivo.
Solución 17. No. La forma lógica es \(\forall n\,[E(n)\Rightarrow E(n^2)]\). Para un entero impar, el antecedente \(E(n)\) es falso; por tanto la implicación no falla allí. Un contraejemplo tendría que ser un entero par cuyo cuadrado fuera impar.
Solución 18. Toma \(x=-2\). Se cumple \(x^2=4>1\), pero \(x=-2\) no es mayor que \(1\). Por tanto el antecedente es verdadero y el consecuente falso: exactamente la forma necesaria para refutar una implicación universal.
Soluciones — D — Existenciales y testigos
Solución 19. El entero \(n=7\) sirve: \(7^2=49\). Con un solo testigo válido queda demostrada la existencia. También \(-7\) es testigo, lo que muestra que la afirmación no contiene unicidad.
Solución 20. Sería necesario \(n=7/2\), pero \(7/2\) no es entero. Por tanto ningún \(n\in\mathbb Z\) satisface la ecuación y la afirmación es falsa.
Solución 21. Toma \(x=1/2\). Entonces \(0<1/2<1\) y \((1/2)^2=1/4<1/2\). Por tanto \(x=1/2\) satisface simultáneamente todas las condiciones.
Solución 22. Elige \(a=4\) y \(b=1\). Entonces \(a^2-b^2=16-1=15\). El par \((4,1)\) es un testigo para la existencia conjunta de \(a\) y \(b\).
Solución 23. Por ejemplo \(n=1001\) es un testigo. No se necesita encontrar el “mejor” ni el menor testigo salvo que el enunciado lo exija; cualquier elemento del dominio que satisfaga el predicado basta para la existencia.
Solución 24. El cuantificador \(\exists\) significa “existe al menos uno”, no “existe exactamente uno”. Tener dos testigos refuerza la existencia; no la contradice. La unicidad requeriría \(\exists!x\,P(x)\).
Soluciones — E — Negación de cuantificadores
Solución 25. La negación es \(\exists x\in\mathbb R\;(x^2<0)\). Cambiamos \(\forall\) por \(\exists\) y negamos \(x^2\ge0\), cuya negación sobre los reales es \(x^2<0\).
Solución 26. La negación es \(\forall n\in\mathbb Z\;(n^2\ne2)\). Cambiamos \(\exists\) por \(\forall\) y negamos la igualdad.
Solución 27. Primero: \(\neg\forall n\,A(n)\equiv\exists n\,\neg A(n)\). Luego \(\neg(E(n)\Rightarrow E(n^2))\equiv E(n)\land\neg E(n^2)\). La negación completa es \(\exists n\in\mathbb Z\;[E(n)\land\neg E(n^2)]\).
Solución 28. La negación es \(\forall x\in\mathbb R\;\neg(x>0\land x^2<1)\). Por De Morgan, queda \(\forall x\in\mathbb R\;(x\le0\lor x^2\ge1)\).
Solución 29. Negamos desde afuera: \(\exists x\in\mathbb R\;\neg\exists y\in\mathbb R\;(y>x)\). Luego cambia \(\exists y\) por \(\forall y\): \(\exists x\in\mathbb R\;\forall y\in\mathbb R\;\neg(y>x)\). Por tanto, \(\exists x\in\mathbb R\;\forall y\in\mathbb R\;(y\le x)\).
Solución 30. La negación es \(\forall y\in\mathbb R\;\exists x\in\mathbb R\;\neg(y>x)\), es decir, \(\forall y\in\mathbb R\;\exists x\in\mathbb R\;(y\le x)\).
Solución 31. “No todos” niega un universal: \(\neg\forall n\in\mathbb Z\;(n>0)\). En forma positiva equivalente: \(\exists n\in\mathbb Z\;(n\le0)\). Por ejemplo \(0\) es un testigo.
Solución 32. Toma dominio \(D=\{1,2\}\) y \(P(x)\) = “\(x=1\)”. Entonces \(\neg\forall x\,P(x)\) es verdadera porque no todos los elementos son \(1\); concretamente \(2\) falla. Pero \(\forall x\,\neg P(x)\) es falsa porque \(P(1)\) es verdadera. La primera dice “al menos uno falla”; la segunda, “todos fallan”.
Soluciones — F — Cuantificación restringida
Solución 33. La forma conceptual es \(\forall n\in D\;[n\in\mathbb Z\Rightarrow P(n)]\). Los elementos de \(D\) que no son enteros no deben actuar como contraejemplos; por eso aparece una implicación.
Solución 34. La forma es \(\exists n\in D\;[n\in\mathbb Z\land n^2=9]\). Un testigo debe cumplir a la vez pertenecer a \(\mathbb Z\) y satisfacer la ecuación.
Solución 35. La negación es \(\exists x\in A\;\neg P(x)\). En palabras: existe al menos un elemento de \(A\) que no satisface \(P\).
Solución 36. La negación es \(\forall x\in A\;\neg P(x)\). En palabras: ningún elemento de \(A\) satisface \(P\).
Solución 37. La conjunción exige que todo elemento del dominio mayor sea simultáneamente entero y racional, lo cual es mucho más fuerte. La forma correcta es \(\forall x\,[x\in\mathbb Z\Rightarrow x\in\mathbb Q]\): sólo los elementos que son enteros activan la condición.
Solución 38. En un existencial restringido necesitamos que el testigo sea entero y negativo. La implicación puede ser verdadera para un objeto no entero sin demostrar lo deseado. La forma correcta es \(\exists x\,[x\in\mathbb Z\land x<0]\).
Soluciones — G — Alcance y paréntesis
Solución 39. Las dos apariciones de \(x\), en \(P(x)\) y \(Q(x)\), están dentro del alcance del cuantificador y por tanto ligadas. \(R\) no contiene \(x\).
Solución 40. Dentro de \(P(x,y)\), \(x\) está ligada por \(\forall x\) y \(y\) permanece libre. En \(Q(y)\), \(y\) también es libre. Por tanto la fórmula completa tiene a \(y\) como variable libre.
Solución 41. En la primera, todas las apariciones de \(x\) están ligadas y la fórmula puede ser cerrada. En la segunda, la \(x\) de \(Q(x)\) queda fuera del alcance del cuantificador, así que la expresión sigue abierta respecto de \(x\). Cambiar los paréntesis cambia el alcance y, por tanto, la estructura lógica.
Solución 42. Podemos escribir, por ejemplo, \(\exists t\,[t>y\land P(t)]\). El cuantificador y todas las apariciones ligadas de \(x\) se sustituyen coherentemente por \(t\); \(y\) permanece libre.
Solución 43. La \(y\) original era libre: podía representar un parámetro fijado externamente. Al renombrar \(x\) como \(y\), el cuantificador \(\forall y\) pasa a ligar ambas posiciones. Esa variable libre queda capturada. La transformación no es una mera renominación, sino un cambio de estructura.
Solución 44. La primera afirma que cada \(x\) satisface simultáneamente \(P\) y \(Q\). La segunda afirma que todos satisfacen \(P\), pero deja \(Q(x)\) como condición abierta sobre una \(x\) libre. No son expresiones equivalentes ni tienen el mismo estatus lógico.
Soluciones — H — Orden de cuantificadores
Solución 45. (a) Verdadera: dado \(x\), elige \(y=x+1\). (b) Falsa: si se propone un real fijo \(y\), tomando \(x=y+1\) obtenemos \(y>x\) falso. El cambio de orden altera la dependencia permitida.
Solución 46. La primera es verdadera: para cada \(x\), elige \(y=x+1\). La segunda es falsa: un mismo \(y\) no puede ser simultáneamente \(x+1\) para todos los reales \(x\); por ejemplo exigiría \(y=1\) cuando \(x=0\) y \(y=2\) cuando \(x=1\).
Solución 47. \(\forall n\exists m\;(m=n+2)\) es verdadera: para cada \(n\), toma \(m=n+2\). \(\exists m\forall n\;(m=n+2)\) es falsa: un entero fijo \(m\) no puede valer \(n+2\) para todos los enteros \(n\).
Solución 48. Ambas son verdaderas. En (a), el testigo fijo \(n=0\) funciona para todo \(m\). En (b), para cada \(m\) podemos elegir \(n=0\); de hecho la elección no necesita depender de \(m\). Que ambas sean verdaderas no significa que las formas lógicas sean equivalentes en general.
Solución 49. Sobre todo \(\mathbb R\) es falsa: para \(x=0\) no existe \(y\) con \(0\cdot y=1\). Si restringimos \(x\) a \(\mathbb R\setminus\{0\}\), es verdadera: dado \(x\ne0\), elige \(y=1/x\).
Solución 50. (a) Verdadera con \(y=1\), pues \(1\cdot x=x\) para todo real \(x\). (b) También verdadera; incluso puede usarse el mismo \(y=1\) para cada \(x\). Este ejemplo recuerda que invertir cuantificadores puede cambiar el significado aunque ocasionalmente ambas afirmaciones resulten verdaderas.
Solución 51. Dos universales exigen que \(P\) sea verdadera para todos los pares \((x,y)\); el orden en que recorremos los componentes no cambia esa exigencia. Dos existenciales sólo piden que exista algún par \((x,y)\) y el orden tampoco cambia eso. En cambio, \(\forall x\exists y\) permite que \(y\) dependa de \(x\), mientras \(\exists y\forall x\) exige un único \(y\) fijo; por eso no son equivalentes en general.
Solución 52. \(\forall x\exists y\,R(x,y)\) es verdadera: para \(x=1\) elige \(y=1\), y para \(x=2\) elige \(y=2\). En cambio, \(\exists y\forall x\,R(x,y)\) es falsa: ningún único \(y\) es igual simultáneamente a \(1\) y a \(2\).
Soluciones — I — Dependencia y elección de testigos
Solución 53. La elección \(y=2x\) funciona. El testigo no es un número fijo: depende del valor de \(x\) que haya sido dado. Esa dependencia es permitida porque \(\exists y\) aparece después de \(\forall x\).
Solución 54. Si fijamos cualquier real \(y\), podemos tomar \(x=y+1\) y entonces \(y>x\) falla. La afirmación sigue siendo verdadera porque permite elegir un \(y\) nuevo después de conocer cada \(x\), por ejemplo \(y=x+1\).
Solución 55. Para cada entero \(n\) podemos elegir el testigo \(m=n^2\). En general cambia cuando cambia \(n\). La afirmación no promete un único entero \(m\) que sea igual al cuadrado de todos los enteros.
Solución 56. El testigo es \(m=0\). Como \(\exists m\) aparece primero, debemos elegir un solo entero antes de considerar los distintos \(n\). Ese mismo \(m=0\) funciona para todos porque \(0+n=n\).
Solución 57. No. El cuantificador existencial sólo garantiza al menos un testigo. Puede haber varios. Por ejemplo, sobre \(\mathbb R\), si \(R(x,y)\) significa \(y>x\), para cada \(x\) hay infinitos valores de \(y\) posibles. La unicidad requeriría una condición adicional.
Solución 58. (a) \(\forall p\exists q\,M(p,q)\). El testigo \(q\) puede depender de \(p\). (b) \(\exists q\forall p\,M(p,q)\). Aquí se exige una sola persona \(q\) que satisfaga la relación con todas las personas. Las frases no tienen la misma estructura.
Soluciones — J — Existencia única
Solución 59. Existe: \(x=2\) satisface \(2+3=5\). Es único porque si \(x+3=5\), restando \(3\) en ambos lados se obtiene necesariamente \(x=2\). Por tanto la afirmación es verdadera.
Solución 60. Existe el entero \(n=3\). Si \(2n=6\), dividir por \(2\) obliga a \(n=3\), así que no hay otro entero posible. La afirmación es verdadera.
Solución 61. Es falsa. Hay existencia, pues \(x=2\) funciona, pero también \(x=-2\). Como hay dos testigos distintos, falla la unicidad.
Solución 62. Una expansión estándar es \(\exists x\,[P(x)\land\forall y\,(P(y)\Rightarrow y=x)]\). La primera parte afirma existencia; la segunda fuerza que cualquier otro candidato que cumpla \(P\) coincida con el testigo \(x\).
Soluciones — K — Traducción bidireccional
Solución 63. \(\forall n\in\mathbb Z\;\exists m\in\mathbb Z\;(m>n)\). El orden es universal-existencial porque el entero mayor puede depender del entero inicial.
Solución 64. Una forma es \(\forall n\in\mathbb Z\;\neg\exists m\in\mathbb Z\;(n<m<n+1)\). Equivalentemente, \(\forall n\in\mathbb Z\;\forall m\in\mathbb Z\;\neg(n<m<n+1)\).
Solución 65. \(\exists x\in\mathbb R\;(x>0\land x^2<x)\). También podría escribirse \(\exists x\in\mathbb R\;(0<x<1)\) si ya se ha justificado la equivalencia pertinente para positivos, pero la traducción directa conserva exactamente el enunciado dado.
Solución 66. \(\neg\forall x\in\mathbb R\;(x>0)\), equivalente a \(\exists x\in\mathbb R\;(x\le0)\).
Solución 67. “Para todo entero \(n\), si \(n\) es impar, entonces \(n^2\) es impar.” También puede decirse: “el cuadrado de todo entero impar es impar”.
Solución 68. “Existe un entero \(m\) tal que, para todo entero \(n\), se cumple \(m+n=n\).” La estructura exige un mismo \(m\) para todos los \(n\); concretamente ese entero es \(0\).
Soluciones — L — Diagnóstico y síntesis
Solución 69. El primer error es conservar el cuantificador universal. Al negar un universal debe aparecer un existencial. La forma correcta es \(\exists x\in\mathbb R\;(x^2<0)\). Luego observamos que esta negación es falsa, coherente con la verdad del enunciado original.
Solución 70. La traducción propuesta dice que existe un mismo libro \(b\) elegido por todos los estudiantes. La frase original permite que cada estudiante haya elegido un libro distinto. La forma adecuada es \(\forall e\exists b\,E(e,b)\).
Solución 71. (a) Verdadera: dado \(x\), toma \(y=-x\). (b) Falsa: un único \(y\) no puede satisfacer \(x+y=0\) para todos los reales \(x\); por ejemplo, \(x=0\) exige \(y=0\) y \(x=1\) exige \(y=-1\). (c) Falsa: basta \(x=y=1\), pues \(1+1\ne0\). (d) Verdadera: por ejemplo \(x=0,y=0\). La negación de (a) es \(\exists x\forall y\;(x+y\ne0)\), que es falsa porque para cualquier \(x\) siempre podemos elegir \(y=-x\).
Solución 72. (a) \(\forall x\in\mathbb R\;\exists!y\in\mathbb R\;(2y+x=0)\). (b) Es verdadera: dado \(x\), la ecuación obliga a \(y=-x/2\), que es real. (c) El testigo depende de \(x\) mediante la regla \(y=-x/2\); no hay un único \(y\) global para todos los \(x\). (d) Expandiendo unicidad, el original dice que para todo \(x\) existe un \(y\) con \(2y+x=0\) y cualquier \(z\) que también satisfaga \(2z+x=0\) debe ser igual a \(y\). Su negación puede expresarse conceptualmente como: \(\exists x\in\mathbb R\) tal que o bien no existe ningún \(y\) con \(2y+x=0\), o bien existen dos reales distintos \(y,z\) que satisfacen ambos la ecuación. Simbólicamente:
\[ \exists x\in\mathbb R\;\Big([\forall y\in\mathbb R\;(2y+x\ne0)]\lor[\exists y,z\in\mathbb R\;(y\ne z\land 2y+x=0\land 2z+x=0)]\Big). \]
En este caso la negación es falsa porque para cada \(x\) existe exactamente el único valor \(-x/2\).
Soluciones — M — Problemas tipo prueba
Solución 73.
Es verdadera. Dado \(x\ne0\), basta elegir \(y=1/x\). Entonces \(xy=1\). El testigo depende de \(x\).
Es falsa. Si existiera un real fijo \(y\) tal que \(xy=1\) para todo \(x\ne0\), al tomar \(x=1\) obtendríamos \(y=1\), mientras que con \(x=2\) obtendríamos \(y=1/2\). Contradicción.
Es verdadera. Para cada \(x\) podemos tomar \(y=x+1\), y entonces \(y>x\).
Es falsa. Si existiera un real \(y\) mayor que todo real \(x\), tomando \(x=y+1\) tendríamos \(y>y+1\), contradicción.
En (a) y (c), el existencial está dentro del alcance del universal: el testigo puede variar con la entrada. En (b) y (d), el testigo debe fijarse antes y funcionar para todos los valores universales.
Solución 74.
Dice: “Todo real no negativo posee una raíz cuadrada real no negativa”.
\[ \begin{aligned} &\neg\forall x\in\mathbb R\;\Big[x\ge0\Rightarrow\exists y\in\mathbb R\;(y\ge0\land y^2=x)\Big]\\ &\equiv \exists x\in\mathbb R\;\neg\Big[x\ge0\Rightarrow\exists y\in\mathbb R\;(y\ge0\land y^2=x)\Big]\\ &\equiv \exists x\in\mathbb R\;\Big[x\ge0\land\neg\exists y\in\mathbb R\;(y\ge0\land y^2=x)\Big]\\ &\equiv \exists x\in\mathbb R\;\Big[x\ge0\land\forall y\in\mathbb R\;\neg(y\ge0\land y^2=x)\Big]\\ &\equiv \exists x\in\mathbb R\;\Big[x\ge0\land\forall y\in\mathbb R\;(y<0\lor y^2\ne x)\Big]. \end{aligned} \]
La afirmación original es verdadera: si \(x\ge0\), existe \(y=\sqrt{x}\ge0\) y \(y^2=x\). Por tanto su negación es falsa.
Cambiar sólo \(\forall\) por \(\exists\) modifica el cuantificador exterior, pero no produce la negación. Para negar el universal hay que negar también todo su contenido; después se aplican las reglas de negación a la implicación y al existencial interior.
Solución 75.
\[ \forall x\in\mathbb R\;\exists y\in\mathbb R\; \Big[(3y-2=x)\land \forall z\in\mathbb R\,(3z-2=x\Rightarrow z=y)\Big]. \]
Fijado \(x\), la ecuación obliga a \(y=(x+2)/3\), que es real. Si \(z\) también satisface \(3z-2=x\), entonces \(3z-2=3y-2\), de donde \(z=y\). Hay existencia y unicidad.
La negación expresa que existe algún \(x\) para el cual o no hay solución o hay dos soluciones distintas:
\[ \exists x\in\mathbb R\; \Big( [\forall y\in\mathbb R\;(3y-2\ne x)] \lor [\exists y,z\in\mathbb R\;(y\ne z\land 3y-2=x\land 3z-2=x)] \Big). \]
- \(\exists!y\,\forall x\,(3y-2=x)\) es falsa: fijado \(y\), \(3y-2\) es un solo real y no puede coincidir con todos los reales \(x\).
Solución 76.
\(A\) es verdadera. Dado \(m\), elige \(n=m+1\). Si \(k\ge n\), entonces \(k\ge m+1>m\).
\(B\) es falsa. Para cualquier candidato fijo \(n\), toma \(m=n\) y \(k=n\). Entonces \(k\ge n\) es verdadera, pero \(k>m\) se convierte en \(n>n\), falsa.
\[ \begin{aligned} \neg A &\equiv \exists m\;\forall n\;\exists k\;\neg(k\ge n\Rightarrow k>m)\\ &\equiv \exists m\;\forall n\;\exists k\;(k\ge n\land k\le m). \end{aligned} \]
- En \(A\), \(n\) puede depender de \(m\). En \(B\), \(n\) debe elegirse una sola vez y funcionar para todos los \(m\).
Solución 77.
Es verdadera en \(\mathbb R\): dado \(x\), elige \(y=\sqrt{x^2+1}\).
Es falsa en \(\mathbb Z\). Para \(x=1\) se exigiría \(y^2=2\), imposible para un entero.
\[ \exists x\in\mathbb Z\;\forall y\in\mathbb Z\;(y^2\ne x^2+1). \]
El valor \(x=1\) es un testigo.
- Los cuantificadores recorren objetos distintos según el dominio. El mismo patrón formal puede ser verdadero en \(\mathbb R\) y falso en \(\mathbb Z\) porque cambian los testigos permitidos.
Solución 78.
\[ \forall e\in E\;\exists p\in P\; \Big[ S(e,p)\land \forall e'\in E\;(e'\ne e\Rightarrow\neg S(e',p)) \Big]. \]
\[ \begin{aligned} &\neg\forall e\in E\;\exists p\in P\; \Big[S(e,p)\land\forall e'\in E\;(e'\ne e\Rightarrow\neg S(e',p))\Big]\\ &\equiv \exists e\in E\;\forall p\in P\; \Big[\neg S(e,p)\lor \exists e'\in E\;(e'\ne e\land S(e',p))\Big]. \end{aligned} \]
“Existe un estudiante tal que, para cada problema, o bien ese estudiante no lo resolvió, o bien algún otro estudiante también lo resolvió.” Es decir, existe un estudiante que no posee ningún problema resuelto exclusivamente por él.
Mover \(\exists p\) delante de \(\forall e\) obliga a escoger un mismo problema para todos los estudiantes. La frase original permite que el problema dependa del estudiante.
Solución 79.
En \(\forall x\,[P(x,y)\Rightarrow\exists y\,Q(x,y,z)]\), \(x\) está ligada por \(\forall\). La \(y\) de \(P(x,y)\) es libre; la \(y\) de \(Q(x,y,z)\) está ligada por \(\exists\); \(z\) es libre.
Una renominación segura es
\[ \forall x\,[P(x,y)\Rightarrow\exists t\,Q(x,t,z)]. \]
Si se reemplaza ingenuamente \(\forall x\) por \(\forall y\), la \(y\) libre que aparece en \(P(x,y)\) quedaría bajo el alcance del nuevo cuantificador. Esa captura cambia el significado.
Una clausura universal es
\[ \forall y\;\forall z\;\forall x\; [P(x,y)\Rightarrow\exists t\,Q(x,t,z)]. \]
\[ \begin{aligned} &\neg\forall y\forall z\forall x\,[P(x,y)\Rightarrow\exists t\,Q(x,t,z)]\\ &\equiv \exists y\exists z\exists x\,[P(x,y)\land\neg\exists t\,Q(x,t,z)]\\ &\equiv \exists y\exists z\exists x\,[P(x,y)\land\forall t\,\neg Q(x,t,z)]. \end{aligned} \]
Solución 80.
Afirma que para todo real \(x\) existe un único real \(y\) que es estrictamente mayor que \(x\) y que es menor o igual que cualquier otro real estrictamente mayor que \(x\). Es decir, afirma que todo real tiene un menor real estrictamente mayor que él.
Es falsa.
Fijemos \(x\) y supongamos \(y>x\). Toma
\[ z=\frac{x+y}{2}. \]
Entonces \(x<z<y\). Como \(z>x\), la condición universal exigiría \(y\le z\), contradicción.
Falla ya la existencia: para ningún \(x\) existe un \(y\) con la propiedad. Por tanto la unicidad ni siquiera llega a entrar en juego.
Una negación exacta es: “Existe un real \(x\) para el cual no existe exactamente un real \(y\) que sea el menor real estrictamente mayor que \(x\)”. De hecho hemos probado algo más fuerte: para todo \(x\) no existe ninguno.
Soluciones — N — Dominios, dependencia y fronteras de la unicidad
Solución 81. En \(\{1\}\) los valores universal/existencial son V/V, pues \(1\) satisface ambas desigualdades. En \(\{0,1\}\) son F/V: \(0\) refuta el universal y \(1\) demuestra existencia. En \(\{0,2\}\) son F/F: ninguno satisface las dos desigualdades. En \(\varnothing\) son V/F: no hay contraejemplo ni testigo. «No todos» tiene valores F,V,V,F; «ninguno», equivalente a la negación del existencial, tiene F,F,V,V. Así, las dos negaciones no son intercambiables.
Solución 82. En \(\mathbb Z\) es verdadera: para cualquier \(x\), \(y=x+1\) sigue siendo entero. En \(\{0,1,2\}\) es falsa: para \(x=2\) haría falta \(y=3\), fuera del dominio. En los enteros no negativos es verdadera porque el sucesor también es no negativo. En el dominio vacío es verdadera por el universal exterior, aunque no existan testigos: no hay un \(x\) para el cual se exija elegirlos. La negación es \(\exists x\in D\,\forall y\in D\,(y\ne x+1)\). En el dominio finito \(x=2\) la demuestra; en el ampliado ya no hay un último elemento que obstruya el sucesor.
Solución 83. Todos los elementos de los tres dominios no vacíos son no negativos. Así, cada antecedente es falso y cada implicación verdadera; en el vacío tampoco hay contraejemplo. Los cuatro universales son verdaderos. Los cuatro existenciales son falsos, pues no hay ningún elemento negativo. El universal no garantiza existencia de un objeto que satisfaga el antecedente: dice qué ocurre si lo hay. Confundirlo con el existencial añadiría una exigencia ausente.
Solución 84. En \(\{0,1\}\) es verdadera: \(x=0\) admite \(y=1\), y \(x=1\) admite \(y=0\). En \(\{0,1,2\}\) es falsa porque \(x=2\) necesitaría \(y=-1\). En \(\{-1,0,1\}\) es falsa porque \(x=-1\) necesitaría \(y=2\). En el vacío es verdadera por falta de contraejemplo exterior. La negación es \(\exists x\in D\,\forall y\in D\,(x+y\ne1)\); los valores \(2\) y \(-1\) proporcionan los testigos respectivos en los dos casos falsos.
Solución 85. Toma las filas \((V,F)\), \((F,V)\) y \((V,F)\), respectivamente. Todas tienen una V, con testigos \(p,q,p\), pero la columna \(p\) falla en \(b\) y la columna \(q\) falla en \(a\). La primera negación, \(\exists x\forall y\,\neg R(x,y)\), es falsa: ninguna fila es totalmente F. La segunda, \(\forall y\exists x\,\neg R(x,y)\), es verdadera: para \(p\) elegimos \(b\) y para \(q\) elegimos \(a\). El primer objeto en la última fórmula puede depender de la columna.
Solución 86. Usa filas \((V,F,V)\) y \((F,V,V)\). La tercera columna sirve a ambas; la primera sirve sólo a la primera fila y la segunda sólo a la segunda. Cambia la casilla de la segunda fila en la tercera columna de V a F. Quedan filas \((V,F,V)\) y \((F,V,F)\): ambas conservan testigo, pero la primera columna falla en la segunda fila, la segunda en la primera y la tercera en la segunda. Por ello sólo se pierde el testigo común.
Solución 87. Con tres objetos, cada \(x\) tiene dos testigos distintos de él: las tres fórmulas valen V,F,F. La segunda es falsa porque cualquier candidato \(y\) falla al tomar \(x=y\). Con dos objetos cada \(x\) tiene exactamente el otro como testigo: los valores son V,F,V. Con un solo objeto no hay testigo distinto de \(a\); las tres fórmulas son falsas. Existencia dependiente y unicidad dependiente cambian con el dominio, pero un testigo común sigue siendo imposible en los tres dominios no vacíos.
Solución 88. (a) La primera es verdadera por su universal exterior. La segunda también: cualquier \(y\) de \(Y\) sirve, pues el universal sobre \(X\) es verdadero. (b) La primera es falsa: tomando cualquier \(x\) de \(X\), el existencial sobre \(Y\) falla. La segunda es falsa directamente porque no hay candidato \(y\). (c) La primera es verdadera y la segunda falsa, por sus respectivos cuantificadores exteriores. No se evaluó \(R\) en objetos inexistentes; bastaron las definiciones.
Solución 89. Primero \(\neg A\equiv\exists x\forall y\exists z\,\neg[z>x\Rightarrow z>y]\), y luego \(\exists x\forall y\exists z\,[z>x\land z\le y]\). \(A\) dice: para cada \(x\) hay un \(y\) que es menor que cualquier real mayor que \(x\). Es verdadera con \(y=x\). La negación dice: hay un \(x\) tal que, para cualquier \(y\), algún \(z\) es mayor que \(x\) y a la vez no mayor que \(y\); es falsa, pues elegir \(y=x\) hace imposible ese \(z\). La elección uniforme es imposible: dado un \(y\) fijo, toma \(x=y-1\) y \(z=y-1/2\). Entonces \(z>x\), pero \(z>y\) es falso.
Solución 90. La negación es \(\forall n\exists m\forall k\,[k\le m\lor k\ge n]\). \(B\) pide un entero \(n\) fijo tal que, por muy grande que sea \(m\), haya un entero entre \(m\) y \(n\) estrictamente. Es falsa: una vez propuesto \(n\), toma \(m=n\); ningún \(k\) satisface \(k>n\) y \(k<n\). La negación afirma que para cada \(n\) hay un \(m\) que impide a todos los \(k\) estar estrictamente entre ambos; es verdadera con \(m=n\). En \(B\), \(n\) precede a \(m\) y no puede depender de él; \(k\) puede depender de ambos. En la negación, \(m\) puede depender de \(n\), pero debe bloquear a todos los \(k\).
Solución 91. La fórmula es \(\forall a\exists p\,[E(a,p)\land\forall r\,C(r,a,p)]\). Su negación es \(\exists a\forall p\,[\neg E(a,p)\lor\exists r\,\neg C(r,a,p)]\), por intercambio de cuantificadores y De Morgan. Dice: hay un alumno para el que cada práctica, o no fue entregada por él, o tiene al menos un revisor que no corrigió su entrega. Si el alumno no entregó cierta práctica, el primer disyunto ya basta; no necesitamos afirmar que existe una entrega sin corregir. El alumno queda fijo para todas las prácticas; cuando se necesita un revisor que falle, éste puede depender del alumno y de la práctica.
Solución 92. La primera es falsa: para un \(x,y\) fijos, \(x+y\) no puede ser a la vez \(0\) y \(1\), de modo que falla alguno de los dos \(z\). Su negación es \(\exists x\forall y\exists z\,(z\ne x+y)\); sirve \(x=0\), eligiendo \(z=1\) para \(y=0\) y \(z=0\) para \(y=1\). La segunda también es falsa: para \(x=1,z=0\) se necesitaría \(y=-1\), fuera de \(D\). Su negación es \(\exists x\exists z\forall y\,(z\ne x+y)\), verdadera con \(x=1,z=0\). En la primera, \(y\) debe elegirse antes de conocer \(z\); en la segunda puede depender de \(x\) y de \(z\). Coincidir en falsedad en esta interpretación no vuelve equivalentes sus requisitos.
Solución 93. Las listas son vacía, \(0\), \(0,1\) y \(0,1,2\), respectivamente. Los triples existencia/a lo sumo uno/unicidad son F/V/F, V/V/V, V/F/F y V/F/F. La negación es \([\forall x\in D\,(x\ge a)]\lor[\exists u\in D\exists v\in D\,(u<a\land v<a\land u\ne v)]\). Para \(a=0\) se cumple el primer disyunto; para \(a=2,3\), el segundo con \(u=0,v=1\); para \(a=1\) ambos son falsos. Así se distingue falta de testigos de multiplicidad.
Solución 94. Si \(a\) es par, \(a=2b\) para un entero \(b\), y \(x=b\) es testigo. Si \(a\) es impar, no hay entero \(x\) con \(2x=a\). En ambos casos hay a lo sumo uno: si \(2u=a=2v\), entonces \(2u=2v\) y \(u=v\). Existencia se escribe \(\exists x\in\mathbb Z\,(2x=a)\); a lo sumo uno, \(\forall u\in\mathbb Z\forall v\in\mathbb Z\,[(2u=a\land2v=a)\Rightarrow u=v]\). La conjunción es verdadera exactamente para los \(a\) pares. Cuando falla, falla sólo existencia, nunca la condición de a lo sumo uno.
Solución 95. Si \(a<0\), no hay testigos porque un cuadrado real no es negativo: F/V/F. Si \(a=0\), sólo \(x=0\) sirve: V/V/V. Si \(a>0\), sirven los dos reales distintos \(\sqrt a\) y \(-\sqrt a\), y no otros: V/F/F. En el dominio no negativo, para \(a<0\) sigue sin haber testigos, mientras que para \(a\ge0\) hay exactamente uno, \(\sqrt a\). Por tanto a lo sumo uno es siempre verdadera en el dominio restringido y unicidad existencial vale exactamente para \(a\ge0\). La restricción eliminó el testigo negativo, no creó uno para valores negativos de \(a\).
Solución 96. En el vacío \(F\) es verdadera por el universal exterior: no se exige encontrar testigo para ningún \(x\). \(G\) es falsa porque su existencial exterior no tiene candidato, aunque la condición interior universal sería vacuamente verdadera para cualquier candidato si lo hubiera. En \(\{a\}\) las dos son verdaderas: \(y=a\) es el único testigo. En \(\{a,b\}\), \(F\) sigue siendo verdadera, porque para cada \(x\) hay exactamente un \(y=x\) en el dominio. \(G\) es falsa por falta de existencia: ningún \(y\) es simultáneamente igual a \(a\) y a \(b\). En este último caso hay a lo sumo un testigo común (de hecho cero), pero no exactamente uno. Los valores F/G son V/F, V/V y V/F.
Autoevaluación de salida
Antes de continuar a C7, deberías poder responder afirmativamente:
- ¿distingo una expresión de un predicado y de una proposición?
- ¿puedo declarar el dominio relevante?
- ¿identifico variables libres y ligadas?
- ¿leo \(\forall\), \(\exists\) y \(\exists!\) sin perder su alcance?
- ¿sé que un contraejemplo refuta un universal?
- ¿sé que un testigo establece una existencia?
- ¿puedo negar cuantificadores cambiando \(\forall\leftrightarrow\exists\) y negando el contenido interno?
- ¿distingo \(\forall x\exists y\) de \(\exists y\forall x\)?
- ¿puedo explicar cuándo un testigo depende de una variable previa?
- ¿puedo traducir afirmaciones de complejidad media en ambos sentidos?
Si alguna respuesta es negativa, vuelve primero a las secciones 6.7, 6.9–6.11 y a los ejercicios de los bloques E, G, H y L. Son los puntos de mayor transferencia del capítulo.