Proposiciones Abiertas y Cuantificadores PDF

Preview

Summary

Manuel Montalvo...

Description

1

1.5 Proposiciones Abiertas y Cuantificadores La unidad que está dedicada al estudio de los conjuntos es la siguiente; sin embargo, en este punto necesitamos introducir algunos conceptos muy básicos relacionados con conjuntos y alguna notación usada en conjuntos. El matemático alemán Georg Cantor (1845-1918) inició la teoría de los conjuntos en las décadas de 1870 y 1880. Según Cantor, “Un conjunto es cualquier colección de objetos definidos y distinguibles de nuestra intuición o nuestro intelecto para ser concebidos como un todo.” Los objetos de un conjunto se denominan elementos o miembros del conjunto. Todos los días usamos palabras que transmiten el significado de un conjunto. Por ejemplo, cuando decimos "El comité recomendó que se requiera un curso de lógica para la graduación", estamos considerando que el comité es un conjunto y los miembros del comité son los miembros (elementos) del conjunto. Cuando mencionamos una "bandada" de gansos, estamos considerando un conjunto particular de gansos como una entidad única, y cualquier ganso individual en esa bandada es miembro de ese conjunto. Por lo tanto, el punto esencial del concepto de conjunto de Cantor es que la colección de objetos debe considerarse como una entidad única. La palabra "definido" en el concepto de conjunto de Cantor significa que dado un conjunto y un objeto, es posible determinar si el objeto pertenece al conjunto o no. Y la palabra "distinguible" significa que, dados dos pares de objetos calificados para aparecer como elementos de un conjunto, uno debe poder determinar si los objetos son iguales o diferentes. Como resultado, un conjunto está completamente determinado por sus miembros . Generalmente, denotaremos los conjuntos con letras mayúsculas y usaremos la notación convencional "x ∈ A" para denotar que "x es un elemento del conjunto A" o "x es un miembro del conjunto A". Además, utilizaremos la notación "x, y ∈ A" para indicar que "x e y son elementos del conjunto A". El matemático italiano Giuseppe Peano (1858–1932) introdujo el símbolo  para "es un elemento de" en 1889. El símbolo proviene de la primera letra de la palabra griega para "es". Para indicar que "x no es un elemento del conjunto A", escribimos "x∈ / A". Por ejemplo, deje que A denote el conjunto de letras en el alfabeto inglés. Entonces b ∈ A; e, f ∈ A; a, e, i, o, u ∈ A; pero 5 ∈ / A. Los conjuntos generalmente se describen mediante una de dos notaciones: notación de lista (también llamada notación de enumeración) o notación de generador de conjuntos. En la nota de la lista, los elementos del conjunto están encerrados entre llaves, {} y separados por comas. El orden en que se enumeran los elementos dentro de las llaves es inmaterial. Por ejemplo, el conjunto de números primos de un dígito se puede escribir usando la notación de lista como {2, 3, 5, 7}, o {5, 7, 2, 3}, o {7, 3, 5, 2}, etc. Estas son solo representaciones diferentes del mismo conjunto. Por supuesto, la notación de lista es apropiada para conjuntos finitos. Sin embargo, esta notación también se puede usar para representar conjuntos infinitos. Por ejemplo, podemos representar el conjunto de enteros positivos, P, por P = {1, 2, 3,. . .}. Al representar conjuntos de esta manera los puntos. . . (llamados puntos suspensivos) indican que el patrón utilizado para obtener los elementos enumerados anteriormente se debe seguir para obtener los elementos restantes del conjunto. Esta

2 convención puede usarse para representar conjuntos finitos que también tienen un número relativamente grande de elementos. Por ejemplo, F = {2, 4, 6,. . . , 100} es una representación del conjunto de todos los enteros pares positivos menores o iguales a 100. A lo largo del curso, N denotará el conjunto de números naturales, que a veces también se denominan números de conteo o enteros positivos. Por lo tanto, N = {1, 2, 3,. . .}. El conjunto de enteros estará representado por Z,  es decir Z  = {..., - 2, −1,0,1,2, ...}. El símbolo Z proviene de la palabra alemana para número, Zählen. Los teoremas básicos para los números naturales y los enteros aparecen en la siguientes unidades y pueden usarse en pruebas que involucran números naturales o enteros. Usaremos Q para denotar el conjunto de números racionales. Recuerde que un número racional es cualquier número de la forma p/q donde p y q son enteros y q =/ 0 . El conjunto de números reales será denotado por R. Usando la notación del generador de conjuntos, el conjunto F de todos los enteros pares menores o iguales a 100 se escribiría como F = {x | x es un entero par menor o igual que 100}. La barra vertical, | , en la definición anterior se lee "tal que". Por lo tanto, la definición del generador de conjuntos del conjunto F dada anteriormente se lee "F es igual al conjunto de todas x tal que x es un entero par menor o igual que 100". Otro ejemplo de un conjunto especificado utilizando la notación de generador de conjuntos es O = {x | x es un entero par} Observe que la notación de generador de conjuntos es muy apropiada para representar conjuntos infinitos y conjuntos finitos con un número relativamente grande de elementos. El conjunto sin elementos se denomina conjunto vacío o conjunto nulo. El conjunto vacío está simbolizado por ∅. El símbolo ∅ es la última letra del alfabeto danés-noruego. El conjunto vacío no se denota con {}. El conjunto vacío no es el conjunto {0}. El conjunto {0} es un conjunto con un elemento, a saber, 0. Por lo tanto, 0 ∈ {0}. Y el conjunto vacío no es el conjunto {∅}. El conjunto {∅} es un conjunto con un elemento, a saber, ∅. Es decir, ∅ ∈ {∅}. Muchas declaraciones en matemáticas involucran una o más variables, y por lo tanto no son proposiciones. Una variable es un símbolo, se dice x, que representa un objeto específico de un conjunto dado U. El conjunto de valores, de U, que pueden ser asignados a la variable x es llamado universo, conjunto universal, o universo de discurso. Una proposición abierta en una variable es una oración que involucra una variable y que se convierte en una proposición (una oración declarativa verdadera o falsa) cuando los valores del conjunto universal se sustituyen por la variable. Una proposición abierta en la variable x se denota por P(x). Cabe señalar que una proposición abierta en una variable no es una proposición, porque la oración no es verdadera o falsa hasta que un valor específico del conjunto

3 universal se sustituye en la oración, convirtiéndola en una proposición, es decir, haciéndola verdadera o falsa. Por lo tanto, el valor de verdad de una proposición abierta permanece "abierto" hasta que un valor específico para la variable se sustituye en la declaración. Sea P(x) el enunciado abierto "El número natural x es un número primo". Observe que P(x) no es ni verdadero ni falso; la declaración P(5) es verdadera, mientras que la declaración P(4) es falsa. El conjunto de verdad de una proposición abierta es el conjunto de todos los valores del conjunto universal que hacen que la declaración abierta sea una proposición verdadera. Sea P(x) una proposición abierta con el conjunto universal U no vacío especificado. Luego, en la notación de generador de conjuntos, el conjunto de verdad de P(x) es el conjunto T

p

= {x ∈ U | P (x)}

El siguiente ejemplo ilustra que el conjunto de verdad de una proposición abierta depende de la elección del conjunto universal. Sea P (x) la declaración abierta “ x2 ≤ 9 ”. Luego {x ∈ N | x2 ≤ 9} = {1, 2, 3} , {x ∈ Z | x2 ≤ 9} = {− 3,− 2,− 1, 0, 1, 2, 3} y {x ∈ R | x2 ≤ 9} = {x ∈ R | − 3 ≤ x ≤ 3 } . Example 1.5.1 Encuentre el siguiente conjunto de verdad. a) {x ∈ N | 2x2 − x = 0} b) {x ∈ Z | 2x2 − x = 0} c)

{x ∈ Q | 2x2 − x = 0}

A menudo queremos indicar cuántos valores de la variable x hacen que la declaración abierta P (x) sea verdadera. Específicamente, nos gustaría saber si P (x) es verdadero para cada x en el universo U o si P (x) es verdadero para al menos una x ∈ U . Por lo tanto, introducimos dos cuantificadores. El símbolo ∀ es llamado cuantificador universal y se lee “para todo”, “para cada”. La declaración (∀x ∈ U )(P (x)) es leído “para todo x ∈ U , P (x) ” y es precisamente verdadera cuando el conjunto de verdad T

p

= {x ∈ U | P (x)} = U

El símbolo ∃ es llamado cuantificador existencial y se lee “existe”, “para algún”. La declaración (∃x ∈ U )(P (x)) es leído “existe un x ∈ U tal que P (x) ” y es precisamente verdadera cuando el conjunto de verdad T

p

= {x ∈ U | P (x)} =/ ∅

Varios comentarios están en orden. En primer lugar, para demostrar que el enunciado (∃x ∈ U) (P (x)) es verdadero, es necesario encontrar solo un valor  de x ∈ U para el cual P (x)

4 es verdadero. Por otro lado, para demostrar que la afirmación (∀x ∈ U) (P (x)) es verdadera, es necesario demostrar que P(x) es verdadera para todas las x ∈ U. Segundo, la declaración condicional (∀x ∈ U)(P (x)) ⇒ (∃x ∈ U )(P (x)) es verdadera, ya que una declaración abierta que es verdadera para todos los valores de x en un universo U es verdadera para algún (cualquier) valor de x ∈ U . Por el contrario, la declaración condicional (∃x ∈ U)(P (x)) ⇒ (∀x ∈ U )(P (x)) es falso, ya que una declaración abierta puede ser verdadera para algunas x en un universo y falsa para otras x en el universo. Y finalmente, el valor de verdad de una declaración cuantificada depende del universo, como lo muestran los siguientes ejemplos. Sea P (x) la declaración que denota “x2 > 0 ”. La declaración cuantificada (∀x ∈ N )(P (x)) es verdadero, mientras que el enunciado cuantificado (∀x ∈ Z) (P (x)) es falso, porque P(0) es falso. Ahora sea Q(x) la afirmación "x ≤ 0". El enunciado cuantificado (∃x ∈ N) (Q (x)) es falso, mientras que el enunciado cuantificado (∃x ∈ Z) (Q (x)) es verdadero, porque Q(0) es verdadero. Ejemplo 1.5.2 Traduce las siguientes oraciones a enunciados simbólicos que contienen un cuantificador. Indique el valor de verdad de cada declaración. a) Para cada número natural x, 2x + 1 > 0 . b) Para cada número entero x, 2x + 1 > 0 . c) Existe un entero x tal que 2x + 1 < 0 . d) Existe un número natural x tal que x2 + x + 41 es un número primo. e) Para cada número natural x, x2 + x + 41 es un número primo Solución Las siguientes declaraciones simbólicas son como siguen. a) ( ∀x ∈ N ) (2x + 1 > 0) . Esta afirmación es verdadera, puesto que para x ∈ N , x > 0 ;por lo tanto, 2x > 0 y 2x + 1 > 1 > 0 . b) (∀x ∈ Z )( 2x + 1 > 0 ). Esta afirmación es falsa, cuando − 1 ∈ Z and 2(− 1) + 1 =− 2 + 1 =− 1 < 0. c) (∃x ∈ Z )( 2x + 1 < 0 ). Esta afirmación es verdadera, puesto que esto es verdad para x =− 1 . Ver los cálculos en la parte b. En efecto esta afirmación es verdadera para todo entero x ≤− 1 . d) (∃x ∈ N )( x2 + x + 4 es un número primo) Esta afirmación es verdadera, puesto que para x = 1 , 12 + 1 + 41 = 43 , el cual es un número primo.

5 e) (∀x ∈ N )( x2 + x + 4 es un número primo) Esta afirmación es falsa. ¿Puede encontrar un número natural específico x tal que x2 + x + 4 no es un número primo? La declaración simbólica ( ∀x ∈ A )( P (x) ), que se lee “Para todo ∀x ∈ A , P (x) ” también se puede indicar como “Para todo x , si x ∈ A , entonces P (x) ” y simbólicamente por (∀x)((x ∈ A) ⇒ P (x)) De la misma manera, la declaración simbólica (∃x ∈ A)P (x) puede ser escrito como (∃x) ((x ∈ A) ⇒ P (x) , que se lee “Existe un x tal que si x ∈ A , entonces P (x) .” El siguiente ejemplo ilustra estos usos. Ejemplo 1.5.3 En este ejemplo, sea el universo del discurso el conjunto de enteros, Z. Traduce las siguientes afirmaciones simbólicas que involucran un cuantificador al español e indican el valor de verdad de cada afirmación. a) ( ∀x)((x ∈ N ) ⇒ (x ∈ Z )) b) ( ∀x)((x ∈ Z ) ⇒ (x ∈ N )) c) ( ∃x)((x ∈ Z ) ⋀ (x ∈ N )) d) ( ∃x)((x ∈ Z ) ⋀ (x ∈ / N )) e) ( ∃x)((x ∈ N ) ⋀ (x ∈ / Z )) f)

(∀x) (( x es primo) ⇒ ( x no es compuesto)

Solución a) (∀x)((x ∈ N ) ⇒ (x ∈ Z )) traducidos en palabras “Para todo x, si x es un número natural entonces x es un número entero”. Esta traducción puede ser recortada como “Cada número natural es un entero”. La declaración simbólica y la traducción son verdaderas. b) (∀x)((x ∈ Z ) ⇒ (x ∈ N )) traducido como “Para todo x, si x es un número entero entonces x es un número natural”. Esta traducción puede ser recortada a “Cada entero es un número natural”. Esta declaración es falsa. Porque x =− 1 hace la declaración x ∈ Z verdadera y la declaración x ∈ N falsa. Cuando x =− 1 , la declaración condicional (x ∈ Z ) ⇒ (x ∈ N ) es falsa. c) (∃x)((x ∈ Z ) ⋀ (x ∈ N )) significa "Hay un número x que es un número entero y un número natural". Esta declaración simbólica y su traducción son verdaderas, ya que 1 es tanto un número entero como un número natural. d) (∃x)((x ∈ Z ) ⋀ (x ∈ / N )) se traduce al español como "Para algunos x, x es un número entero yx no es un número natural". Una traducción condensada es "Algún número entero no es un número natural". Esta declaración simbólica y sus traducciones son todas verdaderas, ya que x = −1 es un número entero que no es un número natural. e) (∃x)((x ∈ N ) ⋀ (x ∈ / Z )) translates as “For some x, x is a natural number and x is not an integer.” A shortened translation is “Some natural number is not an integer.” This symbolic statement and its translations are all false.

6 f) (∀x) ((x es primo)⇒ (x no es compuesto) translates as “For all x, if x is a prime, then x is not a composite.” A shortened translation is “No prime is a composite.” This symbolic statement and its translations are all true. La lógica tradicional enfatizaba cuatro tipos básicos de enunciados que implican un cuantificador único: la afirmativa universal, la negación universal, la afirmativa particular y la negación particular. Los ejemplos de estos cuatro tipos de declaraciones aparecen en el ejemplo 1.5.3. Ahora proporcionamos un resumen general para este tipo de declaraciones. Deje que se especifique un universo para la variable x y deje que P (x) y Q (x) sean declaraciones apropiadas. Entonces la declaración simbólica y la traducción al inglés de las cuatro declaraciones de la lógica tradicional son las siguientes. 1. Afirmativo Universal. ( ∀x)(P (x) ⇒ Q(x)). 2. Negación universal. 3. Afirmativo particular

( ∀x)(P (x) ⇒ (¬Q(x))). ( ∃x)((P (x) ⋀ Q(x)).

4. Negación particular

( ∃x)((P (x) ⋀ (¬Q(x))).

Todo P (x) son Q(x) No P (x) son Q(x) Algún P (x) son Q(x) Algún P (x) no son Q(x)

Si el enunciado (∃x ∈ U) (P(x)) es verdadero, entonces sabemos que hay al menos una x en el universo U tal que P (x) es verdadero. Sin embargo, en matemáticas, a menudo se da el caso de que existe exactamente una x en el universo para la cual P(x) es verdadera. Por ejemplo, para el conjunto de enteros existe exactamente una identidad aditiva, a saber, el número 0. (Es decir, el número 0 es el número único en Z tal que x + 0 = 0 + x = x para todo x∈Z.) Para el conjunto de números naturales existe exactamente una identidad multiplicativa, es decir, el número 1. (El número 1 es el número único en N tal que x · 1 = 1 · x = x para todo x ∈ N.) Para indicar que existe un elemento único en un universo con una propiedad específica, definimos el cuantificador existencial único, ∃!, de la siguiente manera. El símbolo ∃! se llama el cuantificador existencial único y representa la frase "existe un único" o "existe exactamente uno". La proposición (∃! X ∈ U) (P(x)) se lee "existe una única x ∈ U tal que P(x)" o "existe exactamente una x ∈ U tal que P(x)". La afirmación (∃! X ∈ U) (P(x)) es verdadera precisamente cuando la verdad establece T p = {x ∈ U | P (x)} tiene exactamente un elemento. Se sigue directamente de las definiciones de los cuantificadores ∃ y ∃! que la proposición condicional (∃! x ∈ U) (P (x)) ⇒ (∃x ∈ U) (P (x)) es verdadera, mientras que la proposición condicional (∃x ∈ U) (P (x)) ⇒ (∃! X ∈ U) (P (x)) es falso. Encuentre el valor de verdad de las siguientes afirmaciones que contienen el cuantificador existencial único. a. b.

(∃! x ∈ N )(|x + 4| = 1) (∃! x ∈ N )(|x − 4| = 5)

c.

(∃! x ∈ N )(|x − 4| = 3)

Solución

7 Observe que una ecuación de la forma |y | = a donde a es positivo aparece en a, by c. Recordemos del álgebra que en el conjunto de números reales, si |y| = a donde a es positivo, entonces y = a o y =− a. a. De la discusión anterior se deduce que si x| + 4| = 1, entonces x + 4 = 1 ó x + 4 =− 1. Sumando − 4 a ambos miembros de las dos últimas ecuaciones, encontramos / N y −5∈ / N ,la declaración |x + 4| = 1, luego o x =− 3 ó x =− 5. Como − 3 ∈ (∃! x ∈ N ) ( x| + 4| = 1) es falsa, porque el conjunto de verdad de {x ∈ N / | x + 4| = 1 } es el conjunto vacío, que no contiene ningún elemento. b. Si |x − 4| = 5 , entonces o x − 4 = 5 ó x − 4 =− 5 . Sumando 4 a ambos miembros de las dos últimas ecuaciones, encontramos que si |x − 4| = 5 ,entonces ó x = 9 ó x =− 1 . Puesto que 9 ∈ N y − 1 ∈ / N ,la declaración (∃! x ∈ N ) ( |x + 4| = 1) es verdadera porque el conjunto de verdad de, {x ∈ N / x| − 4| = 5} = {9} , que contiene exactamente un elemento. c. Si x| − 4| = 3 , entonces x − 4 = 3 o x − 4 =− 3. Sumando 4 a ambos miembros de las dos últimas ecuaciones, encontramos x| − 4| = 3, entonces o x = 7 o x = 1. Como 7 ∈ N y 1 ∈ N ,la declaración (∃! x ∈ N ) ( x| − 4| = 3) es falsa, porque el conjunto de verdad de {x ∈ N / x| − 4| = 3} = {7, 1}, que contiene dos elementos. Observe que si el conjunto universal en a, b y c se cambiara del conjunto de números naturales, N, al conjunto de enteros, Z, el conjunto de números racionales, Q o el conjunto de números reales, R, entonces las tres declaraciones a, b y c que contienen el cuantificador existencial único serían falsas, ya que cada conjunto de verdad correspondiente contendrá exactamente dos elementos. El ejemplo 1.5.4 ilustra que la afirmación (∃! X ∈ U) (P (x)) se puede demostrar que es falsa al mostrar que el conjunto de verdad de {x ∈ U P (x)} es el conjunto vacío o un conjunto con dos o más elementos. Para demostrar que la afirmación (∃! X ∈ U) (P (x)) es verdadera, es necesario demostrar que el conjunto de verdad de {x ∈ U | P (x)} contiene exactamente un elemento. En matemáticas, es muy importante poder negar proposición cuantificadas tales como definiciones y teoremas. Sin embargo, antes de que podamos negar las proposición cuantificadas, es necesario definir la equivalencia para dos proposición cuantificadas. Sean P (x) y Q (x) dos enunciados cuantificados con universo no vacío U. Dos enunciados P (x) y Q (x) son equivalentes en el universo U si y sólo si P(x) y Q(x) tienen el mismo valor de verdad para todos x ∈ U. Es decir, P(x) y Q(x) son equivalentes en el universo U si y sólo si (∀x ∈ U) (P (x) ⇔ Q (x)). Las dos declaraciones cuantificadas P(x) y Q(x) son equivalentes si y sólo si son equivalentes en cada universo U. Si A(x) denota la afirmación “x2 = x ” y B(x) denota “ x = 1 ”. La proposición cuantificada (∀x)(A(x)) es equivalente a la proposición cuantificada (∀x)(B (x)) en el universo de los números naturales, N ya que en N

8 {x | x2 = x } = {1} = {x | x = 1} Sin embargo, la declaración cuantificada (∀x)(A(x)) no es equivalente a la declaración cuantificada (∀x)(B(x)) en el universo de los números enteros, Z, ya que en Z {x | x2 = x } = {0, 1} =/ {1} = {x | x = 1} Consecuentemente, la declaración cuantificada (∀x)(A(x)) y (∀x)(B (x)) no son equivalentes. Sea P(x) y Q(x) proposiciones abiertas en x con universo no vacío U. Dado que la proposición condicional P⇒Q es lógicamente equivalente a ¬ P∨ Q para cualquier universo no vacío U (∀x ∈ U )((P(x) ⇒ Q(x)) ⇔ (¬P(x) ∨ Q(x))). Por lo tanto, las declaraciones cuantificadas (∀x) ((P(x) ⇒ Q(x)) y (∀x) (¬P(x) ∨Q(x)) son equivalentes. Otras declaraciones equivalentes importantes son 1. 2. 3. 4. 5.

(∀x)((P(x) ∧ Q(x)) and (∀x)(Q(x) ∧ P(x)) (∀x)((P(x) ∨ Q(x)) and (∀x)(Q(x) ∨ P(x)) (∀x)((P(x) ⇒ Q(x)) and (∀x)(¬Q(x) ⇒ ¬P(x)) (∀x)(¬(P(x) ∨ Q(x))) and (∀x)((¬P(x)) ∧ (¬Q(x))) (∀x)(¬(P(x) ∧ Q(x))) and (∀x)((¬P(x)) ∨ (¬Q(x)))

Se pueden obtener pares equivalentes adicionales de declaraciones cuantificadas reemplazando cada aparición de ∀ en las declaraciones anteriores por ∃ ...