Números Cardinales (II)

TEOREMA 1.- El conjunto de los números reales no es enumerable.

Demostración.-

Supongamos lo contrario para el intervalo cerrado unidad del conjunto de números reales: $[0,1]$. Entonces, cada punto de dicho intervalo puede ser expresado de manera única (en base 10) mediante una sucesión de dígitos del 0 al 9, detrás de la coma (o punto decimal), suponiendo que las sucesiones de dígitos en las que, a partir de un cierto término, todos son iguales a 9, representan el mismo número real de dicho intervalo, pero con el dígito anterior al primer 9 de la sucesión aumentado en una unidad y el resto de dígitos siguientes todos 0. Ejemplo:

$0.1376499999999...=0.1376500000000...$

Además:

$0=0.00000000\cdots , 1=0.99999999\cdots$

Así podemos poner en sucesión numerable todos los números reales del intervalo $[0,1]$, mediante la siguiente tabla:

$\begin{array}{c}{a}_0=0.{\mathit{a}}_{\mathbf{00}}{a}_{01}{a}_{02}\cdots a_{0n}\cdots \\ a_1=0.a_{10}{\mathit{a}}_{\mathbf{11}}{a}_{12}\cdots a_{1n}\cdots \\ a_2=0.a_{20}{a}_{21}{\mathit{a}}_{\mathbf{22}}\cdots a_{2n}\cdots \\ a_3=0.a_{30}{a}_{31}{a}_{32}\cdots a_{3n}\cdots \\ ⋮\end{array}$

En esta tabla, cada fila representa a uno de los términos de la sucesión, en su expansión decimal, significando el primer subíndice $i$ el término citado y el segundo subíndice $j$ el $j$-ésimo dígito de la expansión decimal del $i$-ésimo término.

Construyamos ahora un número real del intervalo $[0,1]$ que no figure en la tabla, con lo que habremos incurrido en una contradicción.

Sea $b=0.b_{00}{b}_{11}{b}_{22}\cdots b_{nn}\cdots ,$ definido de la forma siguiente:

Para cada $i$, $b_{ii}=1$, si $a_{ii}=0$ y $b_{ii}=0$ si $a_{ii}\ne 0$.

Claramente, el número $b$ pertenece al intervalo $[0,1]$, y difiere, en su primera cifra decimal, de $a_0$; en su segunda cifra decimal, de $a_1$; en su tercera cifra decimal, de $a_2$; y, en general, en su $(n+1)$-ésima cifra decimal, de $a_n$. En consecuencia, $b$ no es ninguno de los números de la sucesión, lo que contradice la hipótesis. Q.E.D.

TEOREMA 2.- Sean $A,B,A_1,B_1$ conjuntos tales que $A{}_{ef}\stackrel{\phi }{~}{A}_1 y B{}_{ef}\stackrel{\psi }{~}{B}_1$; entonces $A^B{}_{ef}~{A_1}^{B_1}$.

Demostración.- Sea la aplicación $\Phi :A^B\to {A_1}^{B_1}$ y el diagrama:

$\begin{array}{ccc}B& \stackrel{f}{\to }& A\\ \psi \downarrow & & \downarrow \phi \\ B_1& \stackrel{f\text{'}}{\to }& A_1\end{array}$

de tal forma que, si $f\in A^B$, entonces $f\text{'}=\Phi \left(f\right)=\phi \circ f\circ {\psi }^{-1}\in {A_1}^{B_1}$.
La aplicación $\Phi$ es biyectiva. En efecto.

Inyectividad.

Sean $f_1,f_2\in A^B$ tales que $f_1\ne f_2$. Entonces existe un $b\in B$ tal que $f_1\left(b\right)\ne f_2\left(b\right)$.
Por ser $\psi$ biyectiva (luego serlo también su inversa: ${\psi }^{-1}$), existe un único $a\in B_1$ para el que se cumple ${\psi }^{-1}\left(a\right)=b$; luego

$f_1\left({\psi }^{-1}\left(a\right)\right)\ne f_2\left({\psi }^{-1}\left(a\right)\right) (*)$

y como $\phi$ es biyectiva (luego inyectiva), de (*) se obtiene que $\phi \circ f_1\circ {\psi }^{-1}$ es inyectiva.

Sobreyectividad.

Sea $f\text{'}\in {A_1}^{B_1}$; entonces la aplicación $f={\phi }^{-1}\circ f\text{'}\circ \psi \in A^B$, es tal que $\Phi \left(f\right)=f\text{'}$. Q.E.D.

Números Cardinales (I)

Introducción.

Dividimos los conjuntos en clases asignando dos conjuntos a la misma clase si y solo si son equivalentes. La relación de equivalencia, igualdad, equipotencia o potencia está definida como aquella que existe entre dos conjuntos para los que se puede establecer una aplicación biyectiva.
Los símbolos que sirven para denotar esas clases se llaman números cardinales.

DEFINICIÓN 1.- Dos conjuntos $A,B$ son equivalentes (lo que se denota mediante la expresión $A~B$) si y solo si existe una biyección entre $A$ y $B$.

DEFINICIÓN 2.- Dos conjuntos $A,B$ son efectivamente equivalentes (lo que se denota mediante la expresión $A{}_{ef}~B$) si y solo si se ha dado una aplicación biyectiva entre $A$ y $B$.

Como es inmediato demostrar, la equivalencia efectiva implica la equivalencia.

Tarski define el número cardinal o la potencia de un conjunto $A$ como la clase de equivalencia de todos los conjuntos $X$ tales que $X~A$.
Russell y Whitehead consideran a un número cardinal como la clase de todos los conjuntos equivalentes (o de la misma potencia que) un conjunto dado.
Otros autores entienden por número cardinal o potencia del conjunto $A$ al propio conjunto $A$ y cualquier conjunto equivalente a él.
Otros matemáticos, como Mostowski, restringen el concepto de número cardinal a una familia $F$ de conjuntos, particionada en clases de equivalencia (clases de la misma potencia). Pero esta definición es dependiente de la particular familia $F$ de conjuntos elegida.

Alfred Tarski, en otra obra, introduce los números cardinales por medio de axiomas:

1. Cualquier conjunto está asociado con un objeto el cual es su número cardinal.
2. Dos conjuntos son equivalentes (de la misma potencia) si y solo si les corresponde el mismo número cardinal.

Si $M$ es un conjunto dado y $\mathfrak{m}$ el número cardinal que sirve para denotar la clase de los conjuntos equivalentes a $M$ (clase a la que $M$ pertenece), entonces decimos que el conjunto $M$ es de potencia $\mathfrak{m}$, y escribimos:

$\overline{\overline{M}}=\mathfrak{m}$

y

$\mathfrak{m}=\text{Card}M$

Por lo tanto, conjuntos equivalentes (de la misma potencia) tienen el mismo número cardinal, y viceversa.
Como para conjuntos finitos el concepto de conjuntos equivalentes es sinónimo de conjuntos con el mismo número de elementos, es más simple y conveniente adoptar los números naturales como los respectivos símbolos de los números cardinales finitos, y entonces para un conjunto finito con $n$ elementos, el número $n$ denota al cardinal de dicho conjunto.
De esta forma, los números naturales son un caso particular de los números cardinales. Como el número cardinal del conjunto vacío adoptamos el símbolo $0$.

El número cardinal correspondiente a conjuntos enumerables es denotado, desde Cantor, por el símbolo ${\aleph }_0$ (álef cero), y el número cardinal correspondiente a conjuntos de la potencia del continuo es denotado por la letra gótica $\mathfrak{c}$.

Suma de números cardinales.

Sean $M,N$ dos conjuntos cuyos números cardinales son, respectivamente, $\mathfrak{m},\mathfrak{n}$. Si $M,N$ no son disjuntos, podemos elegir los conjuntos $M\text{'}=\left\{(m,1):m\in M\right\}$, con $M\text{'}~M$, y $N\text{'}=\left\{(n,2):n\in N\right\}$, con $N\text{'}~N$.
Definimos la suma de $\mathfrak{m}$ y $\mathfrak{n}$, $\mathfrak{s}$, como el cardinal del conjunto suma, unión o reunión de $M$ y $N$:

$\overline{\overline{M+N}}=\overline{\overline{M}}+\overline{\overline{N}}=\mathfrak{m}+\mathfrak{n}=\mathfrak{s}$

En lo que sigue supondremos que los componentes de la suma de dos o más conjuntos son disjuntos dos a dos. Es decir, que si $S=\sum _{A\in F}A$, siendo $F$ una familia de conjuntos, entonces para cualesquiera $A,B\in F$, se verifica que $AB=0$.

PROPOSICIÓN 1.- Si $M~M_1,N~N_1$, entonces $M+N~M_1+N_1$ y, por lo tanto, $\overline{\overline{M+N}}=\overline{\overline{M_1+N_1}}$.

Demostración.- Es inmediata, teniendo en cuenta que al ser $M~M_1,N~N_1$, y $MN=0,M_1{N}_1=0$, se cumple que $M+N~M_1+N_1$; luego como $\overline{\overline{M}}=\overline{\overline{M_1}},\overline{\overline{N}}=\overline{\overline{N_1}}$, se verifica, finalmente, que $\overline{\overline{M+N}}=\overline{\overline{M_1+N_1}}$.Q.E.D.

Lo que nos indica la Proposición anterior es que la suma de números cardinales está bien definida: no depende de los representantes de las respectivas clases de cada componente de la suma.

Por inducción sobre $n$, el teorema puede ser demostrado para la suma de cualquier familia finita de conjuntos $A_1,A_2,\dots ,A_n$, con $\overline{\overline{A_1}}={\mathfrak{m}}_1,\overline{\overline{A_2}}={\mathfrak{m}}_2,\dots ,\overline{\overline{A_n}}={\mathfrak{m}}_n$:

$\overline{\overline{A_1+A_2+\cdots +A_n}}=\overline{\overline{A_1}}+\overline{\overline{A_2}}+\cdots +\overline{\overline{A_n}}={\mathfrak{m}}_1+{\mathfrak{m}}_2+\cdots +{\mathfrak{m}}_n$

La asociatividad y conmutatividad de la suma de cardinales, es inmediata, pues: $(M+N)+P=M+(N+P)$, y $M+N=N+M$, cumpliéndose para cualquier familia finita de componentes de la suma. Probaremos la asociatividad.

$\overline{\overline{\left(M+N\right)+P}}=\overline{\overline{M+N}}+\overline{\overline{P}}=\left(\overline{\overline{M}}+\overline{\overline{N}}\right)+\overline{\overline{P}}=\left(\mathfrak{m}+\mathfrak{n}\right)+\mathfrak{p}$

pero

$\left(M+N\right)+P=M+\left(N+P\right)$

luego

$\overline{\overline{\left(M+N\right)+P}}=\overline{\overline{M+\left(N+P\right)}}=\overline{\overline{M}}+\overline{\overline{\left(N+P\right)}}=\overline{\overline{M}}+\left(\overline{\overline{N}}+\overline{\overline{P}}\right)=\mathfrak{m}+\left(\mathfrak{n}+\mathfrak{p}\right)$

Y de la primera y tercera ecuaciones anteriores se deduce que

$\left(\mathfrak{m}+\mathfrak{n}\right)+\mathfrak{p}=\mathfrak{m}+\left(\mathfrak{n}+\mathfrak{p}\right)$

PROPOSICIÓN 2.- ${\aleph }_0+{\aleph }_0={\aleph }_0 , {\aleph }_0+\mathfrak{c}=\mathfrak{c}, \mathfrak{c}+\mathfrak{c}=\mathfrak{c}$.

Demostración.- Sean $M=\left\{a_1,a_2,a_3,\dots \right\}, N=\left\{b_1,b_2,b_3,\dots \right\}$ dos conjuntos enumerables disjuntos. Entonces

$M+N=\left\{a_1,b_1,a_2,b_2,a_3,b_3\dots \right\}$

es también un conjunto enumerable, luego:

${\aleph }_0=\overline{\overline{M+N}}=\overline{\overline{M}}+\overline{\overline{N}}={\aleph }_0+{\aleph }_0$

Sea $P$ tal que $\overline{\overline{P}}=\mathfrak{c}$. Como $P$ es infinito (y no enumerable), contiene un subconjunto propio enumerable, $Q$. Entonces $P-Q$ no es enumerable, pues, en caso contrario, $P$ lo sería, contra la hipótesis. Luego como $P=\left(P-Q\right)+Q$, se cumple que

$\mathfrak{c}=\overline{\overline{P}}=\overline{\overline{\left(P-Q\right)+Q}}=\overline{\overline{P-Q}}+\overline{\overline{Q}}=\mathfrak{c}+{\aleph }_0={\aleph }_0+\mathfrak{c}$

Sean ahora $P_1,P_2$ dos conjuntos arbitrarios disjuntos, ambos de la potencia del continuo. Entonces podemos escribir

$P_1~[0,1[ y P_2~[1,2[$

Como

$P_1+P_2~[0,1[+[1,2[=[0,2[, y \overline{\overline{[0,2[}}=\mathfrak{c}$

se concluye (puesto que $P_1,P_2$ son conjuntos arbitrarios, cada uno de la potencia del continuo) que $\mathfrak{c}+\mathfrak{c}=\mathfrak{c}$. Q.E.D.

Por inducción sobre $n$, es fácil demostrar ahora que, para cualesquiera números cardinales ${\mathfrak{m}}_1,{\mathfrak{m}}_2,\dots ,{\mathfrak{m}}_n$, tales que ${\mathfrak{m}}_1,{\mathfrak{m}}_2,\dots ,{\mathfrak{m}}_n\in \left\{{\aleph }_0,\mathfrak{c}\right\}$:

1. Si todos los ${\mathfrak{m}}_i$ son iguales a ${\aleph }_0$, entonces la suma es ${\aleph }_0$.
2. Si todos los ${\mathfrak{m}}_i$ son iguales a $\mathfrak{c}$, entonces la suma es $\mathfrak{c}$.
3. Si algún ${\mathfrak{m}}_i$ es igual a $\mathfrak{c}$, entonces la suma es $\mathfrak{c}$.

Un sistema deductivo de la Lógica Proposicional (I)

Para representar, en un lenguaje formal general, el concepto de la lógica ordinaria de "cadena deductiva" o "razonamiento", debemos definir el concepto de "Sistema Deductivo" para un Cálculo Proposicional.

DEFINICIÓN 1. Una regla de inferencia es una función n-aria parcial $f$ de un subconjunto del conjunto de las fbfs del lenguaje del CP, $W$ en $W$: $f:\mathfrak{W}\subset W^n\to W$, tal que la imagen $f\left({\alpha }_1,...,{\alpha }_n\right)$ no depende del orden en que estén las ${\alpha }_i$, sino solamente del conjunto $\left\{{\alpha }_1,\dots ,{\alpha }_n\right\}$.

Si $\alpha =f\left({\alpha }_1,\dots ,{\alpha }_n\right)$, se dice que $\alpha$ es consecuencia directa de las fbfs ${\alpha }_1,\cdots ,{\alpha }_n$ mediante la regla $f$.

EJEMPLO.- La regla Modus Ponens (MP), que es una regla de inferencia binaria del lenguaje proposicional:

$f\left(\alpha ,\alpha \to \beta \right)=\beta , f\left(\alpha ,\alpha \to \beta \right)=\beta$

O, en la notación prefijada o polaca, de la que hacemos uso aquí:

$f\left(\alpha ,C\alpha \beta \right)=f\left(C\alpha \beta ,\alpha \right)=\beta$

DEFINICIÓN 2.- Sea ahora $\mathfrak{R}$ un conjunto de reglas de inferencia y $\text{Δ}$ un conjunto de fbfs. Se llama deducción desde $\text{Δ}$ mediante $\mathfrak{R}$ a una sucesión finita de fbfs, tal que cada fbf ${\alpha }_i$ cumple una de dos:

(i) ${\alpha }_i$ es una fbf de $\text{Δ}$.
(ii) ${\alpha }_i$ es consecuencia directa de fbfs ${\alpha }_{j_1},\cdots ,{\alpha }_{j_r}$ anteriores a ${\alpha }_i$ en la sucesión, mediante una regla de $\mathfrak{R}$.

Se dice que una fbf $\phi$ es deducible de $\text{Δ}$ mediante $\mathfrak{R}$, si es el último término de una deducción desde $\text{Δ}$ mediante $\mathfrak{R}$.

DEFINICIÓN 3.- Un sistema deductivo $\mathcal{D}$ del lenguaje está formado por dos conjuntos:

(i) Un conjunto $\text{Λ}$ de fbfs llamadas axiomas de $\mathcal{D}$, que puede ser vacío.
(ii) Un conjunto $\mathfrak{R}$ de reglas de inferencia, no vacío.

Dado un conjunto $\text{Γ}$ de fbfs, diremos que una fbf $\alpha$ es un teorema de $\text{Γ}$ en $\mathcal{D}$ si es deducible de $\text{Λ}\cup \text{Γ}$ mediante $\mathfrak{R}$. esto se expresa describiendo ${\text{Γ├}}_{\mathcal{D}}\alpha$, o simplemente $\text{Γ├}\alpha$, cuando se sabe con qué sistema deductivo se opera. Las fbfs $\text{Γ}$ se suelen llamar premisas del teorema.

Si $\text{Γ}\subseteq \text{Λ}$ (todas las premisas son axiomas), se suele escribir $├\alpha$, y entonces se dice que $\alpha$ es un teorema lógico del sistema.