Lógica II
Notas de clase 2
Conceptos Básicos de Teoría de Conjuntos
— Un conjunto es una colección de cosas (objetos, números, otros
conjuntos, etc.), que son sus elementos.
Ejemplos:
(i) los jugadores del
Manchester United,
(ii)
los jueces del Tribunal Supremo,
(iii)
los números naturales pares menores que 8,
(iv)
el conjunto compuesto por los conjuntos (i), (ii) y (iii),
(v) el
conjunto compuesto por los elementos de (i), (ii) y (iii),
(vi) Simon y Garfunkel, etc.
— ¿Cómo nos referimos o nombramos a los conjuntos?
Podemos referimos a un
conjunto de dos formas, intensional y extensionalmente (i.e., por comprensión o por enumeración).
Es decir, podemos nombrarlo o bien haciendo uso de una propiedad que tienen todos
sus elementos y solo ellos, o bien enumerando todos sus elementos.
— La referencia a los
conjuntos (i)-(vi), ¿es extensional o intensional?
— En el caso de conjuntos con
infinitos miembros (p.e., el conjunto de los números
primos), no podemos referirnos a ellos más que intensionalmente
(en el ejemplo, “el conjunto formado por los números solamente divisibles por
sí mismos y por 1”)
— Los conjuntos finitos
pueden nombrarse de ambas formas. Por ejemplo, (iii)
están referido intensionalmente, pero podemos
nombrarlo también “el conjunto formado por 2, 4 y 6”, extensionalmente.
— La abreviatura con la que
nombramos un conjunto es {...}, que se lee “el conjunto formado por...”
— {2, 4, 6} es un nombre
extensional del conjunto (iii)
— {x / x es par menor que 8}
es un nombre intensional de (iii)
— Se dice de los elementos de
un conjunto que pertenecen a él. El símbolo utilizado para la pertenencia es Î. La no pertenencia se simboliza con
Ï.
Así, por ejemplo, podemos
escribir:
2 Î {2, 4, 6} [el número 2 es elemento del conjunto
formado por 2, 4 y 6]
2 Î {x / x es par} [el número 2 pertenece al conjunto de
los números pares]
2 Ï {3, 5} [el 2 no es elemento del conjunto formado por
3 y 5]
2 Ï {x / x es impar} [el 2 no pertenece al conjunto de
los números impares]
— Identidad de conjuntos. Dos conjuntos son idénticos si y solo si
[syss; sii; iff] tienen los
mismos elementos (axioma de extensionalidad). La identidad se simboliza con el
signo de igualdad, =. El criterio de identidad de conjuntos es, por tanto,
extensional, no intensional. Formalmente:
A = B ↔ "x ( x Î A ↔ x Î B)
- La desigualdad se expresa
con el signo, ≠, o anteponiendo el operador de negación a un enunciado: ¬.
Así, “A ≠ B” es equivalente a “¬ A = B”. La igualdad y desigualdad es una
relación entre objetos, sean estos conjuntos o no. Por ejemplo, puede
escribirse “el profesor de Lógica II = Manolo Pinedo”,
“{2, 4} = {x / x es par menor que 6}”, “¬
Lola Flores = William Shakespeare”, “{x / x es par} ≠
{x / x es un perro}”.
- Supongamos, por ejemplo,
que solo las criaturas con corazón tienen pulmones y viceversa. Entonces,
independientemente de que la propiedad de tener corazón es distinta a la de
tener pulmones, los conjuntos P y C son el mismo [P = C]:
P = {x / x tiene pulmones}
C = {x / x tiene corazón}
- El orden en que aparecen
los elementos en una notación extensional de un conjunto (o su repetición) no
afecta a la identidad del conjunto. Por ejemplo,
{2, 4, 7} = {7, 2, 4}
{2, 4, 7} = {2, 4, 4, 7}
— El conjunto vacío. Un conjunto vacío es un conjunto sin elementos. El
conjunto vacío se denota generalmente con Ø. Sin embargo, hay muchas formas de
referirse a él. Por ejemplo, todos estos son nombres del conjunto vacío:
{x /
x ≠ x}
{x /
x es una persona viva nacida en el siglo X}
{x /
x es mayor que x}
{x /
x es un círculo cuadrado}
— Formalmente:
A = Ø ↔ "x (x Ï A)
— Dado el axioma de extensionalidad, solo hay un conjunto vacío (dado que dos
conjuntos son iguales si tienen los mismos elementos, todos los conjuntos sin
ningún elemento son el mismo).
— Conjuntos y clases. La
paradoja de Russell. Hemos visto que podemos referirnos a un conjunto por
enumeración y por comprensión. En el segundo caso nos referimos a un conjunto
señalando una propiedad que todos los elementos del conjunto, y solo ellos,
comparten.
- En general, “{x / φ(x)}”
se lee “el conjunto de objetos que son φ”. Sin embargo, esto no significa
que para cada propiedad φ haya un conjunto de cosas que la tienen. Si así
fuera, aparecerían paradojas en la teoría de conjuntos.
- Pensemos, por ejemplo, en
la propiedad “no ser miembro de sí mismo” y supongamos que existe el conjunto C
de las cosas que no son miembros de sí mismas: {x / x Ï x}. Cosas con esta propiedad incluirían a cualquier
perro, que no es un conjunto y por tanto no tiene elementos, pero también a
muchos conjuntos, por ejemplo el de los jueces del Tribunal Supremo que no
pertenece a sí mismo al ser un conjunto y no un juez. También parece que hay
cosas que la tienen. Por ejemplo {x / x no es un juez} pertenecería a sí mismo.
O el conjunto universal, o conjunto de todas las cosas [{x / x = x}]. ¿C Î C? Si C pertenece a C, entonces C no es miembro de sí
mismo (i.e., C Î C → C Ï C). Si C no pertenece a C, entonces C es miembro de sí mismo (i.e., C Ï C → C Î C). C pertenece a sí mismo si no pertenece a sí mismo
y no pertenece a sí mismo si pertenece a sí mismo:
- C Î C ↔ ¬ C Î C, que es una contradicción.
- Soluciones a la paradoja de
Russell: la teoría de tipos; la separación entre conjuntos y clases (o entre
conjuntos normales y conjuntos anormales / clases últimas). Los conjuntos
pueden ser miembros de otros conjuntos o clases. Las clases últimas no.
- Con esta restricción
podemos decir que, dado cualquier conjunto A y
cualquier propiedad φ, existe el conjunto de los elementos de A que tienen
la propiedad φ.
- Tanto los conjuntos como
las clases tienen elementos (0 elementos en el caso límite del conjunto vacío).
Sin embargo, los conjuntos, a diferencia de las clases, pertenecen a, al menos,
otro conjunto. Formalmente, conjunto se define:
C x ↔ $y (x Î y)
— Otras ideas básicas:
- Un objeto no es igual al
conjunto unitario de ese objeto:
"x (x ≠ {x})
- En particular,
Ø ≠ {Ø}
x Î y → x ≠ y
— Subconjuntos e inclusión. Cuando todos los elementos de un conjunto
A lo son también del conjunto B, decimos que A está incluido en B.
- Formalmente: A Í B ↔ "x (x Î A → x Î B)
- Si A está incluido en B
decimos que A es un subconjunto de B. Podemos ver que todo conjunto es un
subconjunto de sí mismo: A = B → A Í B. Por otra parte, si A es un subconjunto de B y B de A, entonces A y
B son el mismo conjunto: A Í B
& B Í A ↔ A = B.
Por ejemplo:
{2, 3} Í {2, 3, 4}
{2, 4} Í {x / x es par}
— Decimos que un conjunto A
es un subconjunto propio de otro B,
si A está incluido en B pero no son iguales (i.e., B tiene elementos que A no
tiene):
A Ì B ↔ A Í B & A ≠ B
o, de otra forma:
A Ì B ↔ A Í B & ¬ B Í A
o, de otra:
A Ì B ↔ ("x (x Î A → x Î B) & $y (y Î B & y Ï A))
Por ejemplo,
{1} Ì {1, 2}
{1, 2} Ë {1, 2}
{x /
x es primo} Ì {x / x es impar v x =
2}
— Conjunto potencia. Es el conjunto de las partes de un conjunto,
i.e., el conjunto de todos los subconjuntos de un conjunto dado. Al de un
conjunto A lo nombramos “Pot A”. Pot
A = {B / B Í A}
Por ejemplo,
Pot {1, 2} = {Ø, {1}, {2}, {1, 2}}
Pot Ø = {Ø}
— Relaciones y funciones.
- Hemos visto que, dado un
conjunto A y una propiedad φ podemos definir el conjunto de los miembros
de A que la tienen: {x / x Î A & φ(x)}. En general el orden en que aparecen los elementos
de un conjunto en su enumeración no importa: {1, 2} = {2, 1}. A veces, sin
embargo, el orden importa. Mientras que un nombre extensional de los objetos
que poseen la propiedad “ser francés” contendrá una enumeración de objetos
franceses en cualquier orden, un nombre extensional de la relación “ser mayor
que” contendría (de no ser un conjunto infinito) una enumeración de un tipo
especial de objetos, pares ordenados.
- El símbolo que usamos para
los pares ordenados es “<...>”. Por ejemplo, <2, 1> sería miembro
del conjunto {<x, y> / x es mayor que y}.
- Dado un conjunto A = {1, 2, 3}, <2, 1> Î {<2, 1>, <3, 1>, <3, 2>}, que es el conjunto de los pares de elementos de A que cumplen “ser mayor que”.