Los ordinales infinitos ω y ω2

TEOREMA.- Los ordinales $\omega$ y $\omega +\omega =\omega 2$ no son el mismo tipo de orden; pero son equipotentes (equivalentes).

Demostración.-

Equipotencia. Como

$\omega =\left\{0,1,2,3,\dots \right\}$

y

$\omega 2=\left\{0,1,2,3,\dots ;\omega ,\omega +1,\omega +2,\omega +3,\dots \right\}$

y la aplicación $f:\omega \to \omega 2$, definida por:

$\begin{array}{c}f\left(2n\right)=\omega +n, n<\omega \\ f\left(2n+1\right)=n, n<\omega \end{array}$

es una biyección entre $\omega$ y $\omega 2$, se tiene que $\overline{\omega }=\overline{\omega 2}$.

Distinto tipo de orden.

Supongamos que $\omega \simeq \omega 2$ (similaridad). Entonces existe una aplicación biyectiva $g:\omega 2\to \omega$, tal que si $\alpha <\beta$ en el orden de $\omega 2$, entonces $g\left(\alpha \right)<g\left(\beta \right)$ en el orden de $\omega$. Y esto para cada par de ordinales distintos $\alpha ,\beta \in \omega 2$.

Sea $g\left(\omega \right)=n<\omega$. Entonces el segmento propio del conjunto de los números naturales

${\mathrm{\mathbb{N}}}_n=\left\{m\in \omega :m<n\right\}=\left\{0,1,2,\dots ,n-1\right\}$

por la supuesta similaridad entre $\omega$ y $\omega 2$ es tal que $\left\{g\left(k\right):k<\omega \right\}\subset {\mathrm{\mathbb{N}}}_n$, lo que es imposible: por ser $g$ biyectiva, ${\mathrm{\mathbb{N}}}_n$ un conjunto finito y $\left\{g\left(k\right):k<\omega \right\}$ un conjunto infinito. Q.E.D.

Lo que se verifica es que $\overline{\omega }=\overline{\omega 2}={\aleph }_0$, aunque $\omega <\omega 2$.

También se cumple que

$\omega <\omega +1<\omega +2<\cdots <\omega 2<\cdots <\omega 3<\cdots <{\omega }^2<\cdots <{\omega }^3<\cdots <{\omega }^{\omega }<\cdots <{\omega }^{{\omega }^{\omega }}<\cdots <{\omega }^{{\omega }^{{\omega }^{⋰}}}={}^{\omega }\omega ={\epsilon }_0<{\omega }_1<{\omega }_2<\cdots <{\omega }_{\omega }<{\omega }_{{\omega }_{\omega }}<\cdots <{\omega }_{{\omega }_{{\omega }_{\ddots }}}<\cdots$

y

$$\begin{gathered} \overline{\omega }=\overline{\omega +1}=\overline{\omega +2}=\cdots =\overline{\omega 2}=\cdots =\overline{\omega 3}=\cdots =\overline{{\omega }^2}=\cdots =\overline{{\omega }^3}=\cdots =\overline{{\omega }^{\omega }}=\cdots \\ =\overline{{\omega }^{{\omega }^{\omega }}}=\cdots =\overline{{\omega }^{{\omega }^{{\omega }^{⋰}}}}=\overline{{}^{\omega }\omega }=\overline{{\epsilon }_0}={\aleph }_0 \end{gathered}$$

Como demostraremos en entradas posteriores.
El número ordinal ${\omega }^{{\omega }^{{\omega }^{⋰}}}={}^{\omega }\omega ={\epsilon }_0$, que en la notación de Ackermann (${}^{\omega }\omega$) se lee "$\omega$ tetrado a $\omega$" (es decir $\omega$ elevado a $\omega$ elevado a $\omega$...-una infinidad numerable de veces), es el menor ordinal $\epsilon$ que verifica: $\epsilon ={\omega }^{\epsilon }$, y es un gran ordinal.

Para darnos cuenta de la magnitud (dentro de lo infinito) de ${}^{\omega }\omega$, en lugar de $\omega$ pongamos algunos números naturales pequeños. Por ejemplo:

${}^{2}2=4$
${}^{3}3=7625597484987$

Pero ya

${}^{4}4$
tiene

8072304726028225379382630397085399030071367921738743031867082828418414481568309149198911814701229483451981557574771156496457238535299087481244990261351117
dígitos decimales.

${}^{5}5=5^{5^n}$

donde

n =
1911012597945477520356404559703964599198081048990094337139512789246520530242615803012059386519739850265586440155794462235359212788673806972288410146915986602087961896757195701839281660338047611225975533626101001482651123413147768252411493094447176965282756285196737514395357542479093219206641883011787169122552421070050709064674382870851449950256586194461543183511379849133691779928127433840431549236855526783596374102105331546031353725325748636909159778690328266459182983815230286936572873691422648131291743762136325730321645282979486862576245362218017673224940567642819360078720713837072355305446356153946401185348493792719514594505508232749221605848912910945189959948686199543147666938013037176163592594479746164220050885079469804487133205133160739134230540198872570038329801246050197013467397175909027389493923817315786996845899794781068042822436093783946335265422815704302832442385515082316490967285712171708123232790481817268327510112746782317410985888683708522000711733492253913322300756147180429007527677793352306200618286012455254243061006894805446584704820650982664319360960388736258510747074340636286976576702699258649953557976318173902550891331223294743930343956161328334072831663498258145226862004307799084688103804187368324800903873596212919633602583120781673673742533322879296907205490595621406888825991244581842379597863476484315673760923625090371511798941424262270220066286486867868710182980872802560693101949280830825044198424796792058908817112327192301455582916746795197430548026404646854002733993860798594465961501752586965811447568510041568687730903712482535343839285397598749458497050038225012489284001826590056251286187629938044407340142347062055785305325034918189589707199305662188512963187501743535960282201038211616048545121039313312256332260766436236688296850208839496142830484739113991669622649948563685234712873294796680884509405893951104650944137909502276545653133018670633521323028460519434381399810561400652595300731790772711065783494174642684720956134647327748584238274899668755052504394218232191357223054066715373374248543645663782045701654593218154053548393614250664498585403307466468541890148134347714650315037954175778622811776585876941680908203125.

La expansión decimal de ${}^{5}5$ no cabe en el Universo, aunque notáramos a cada partícula fundamental con un dígito de la expansión decimal de ${}^{5}5$.

Y, sin embargo, para todo número natural $n$, por grande que sea, se cumple que ${}^{n}n<\omega$.

Algunos teoremas sobre reunión e intersección de conjuntos (I)

TEOREMA 1.- Si ${\left(X_{\iota }\right)}_{\iota \in I} y {\left(Y_{\iota }\right)}_{\iota \in I}$ son dos familias de conjuntos, con el mismo conjunto de índices $I$, y si $Y_{\iota }\subset X_{\iota }$ para todo $\iota \in I$, se tiene

$\underset{\iota \in I}{\cup }{Y}_{\iota }\subset \underset{\iota \in I}{\cup }{X}_{\iota }$

y si $I\ne \varnothing$

$\underset{\iota \in I}{\cap }{Y}_{\iota }\subset \underset{\iota \in I}{\cap }{X}_{\iota }$

Demostración.- Es inmediata. Q.E.D.

TEOREMA 2.- Sea ${\left(X_{\iota }\right)}_{\iota \in I}$ una familia de conjuntos tal que $I=\underset{\lambda \in L}{\cup }{J}_{\lambda }$ es la unión de una familia de conjuntos. Se tiene, entonces

$\underset{\iota \in I}{\cup }{X}_{\iota }=\underset{\lambda \in L}{\cup }\left(\underset{\iota \in J_{\lambda }}{\cup }{X}_{\iota }\right)$

y si $L\ne \varnothing$ y $J_{\lambda }\ne \varnothing$ para todo $\lambda \in L$, se cumple

$\underset{\iota \in I}{\cap }{X}_{\iota }=\underset{\lambda \in L}{\cap }\left(\underset{\iota \in J_{\lambda }}{\cap }{X}_{\iota }\right)$

Demostración.- Sea $x\in \underset{\iota \in I}{\cup }{X}_{\iota }$. Existe $\iota \in I$ tal que $x\in X_{\iota }$.
Como $I=\underset{\lambda \in L}{\cup }{J}_{\lambda }$, existe $\lambda \in L$ tal que $\iota \in J_{\lambda }$, con $x\in X_{\iota }$; luego $x\in \underset{\iota \in J_{\lambda }}{\cup }{X}_{\iota }$ y, por lo tanto, $x\in \underset{\lambda \in L}{\cup }\left(\underset{\iota \in J_{\lambda }}{\cup }{X}_{\iota }\right)$.

Supongamos ahora que $x\in \underset{\lambda \in L}{\cup }\left(\underset{\iota \in J_{\lambda }}{\cup }{X}_{\iota }\right)$. Existe $\lambda \in L$ tal que $x\in \underset{\iota \in J_{\lambda }}{\cup }{X}_{\iota }$; luego existe $\iota \in J_{\lambda }$ tal que $x\in X_{\iota }$ y, por lo tanto, $x\in \underset{\iota \in I}{\cup }{X}_{\iota }$.

Supongamos ahora que $L\ne \varnothing$ y $J_{\lambda }\ne \varnothing$ para cada $\lambda \in L$; entonces $I\ne \varnothing$.
Sea $x\in \underset{\iota \in I}{\cap }{X}_{\iota }$. Si $\lambda \in L$, se tiene $x\in X_{\iota }$ para todo $\iota \in J_{\lambda }$ (pues $J_{\lambda }\subset I$), de donde $x\in \underset{\iota \in J_{\lambda }}{\cap }{X}_{\iota }$; y como esto es verdadero para todo $\lambda \in L$, se concluye que $x\in \underset{\lambda \in L}{\cap }\left(\underset{\iota \in J_{\lambda }}{\cap }{X}_{\iota }\right)$.
Sea, recíprocamente, $x\in \underset{\lambda \in L}{\cap }\left(\underset{\iota \in J_{\lambda }}{\cap }{X}_{\iota }\right)$ y $\iota \in I$ cualquiera. Existe $\lambda \in L$ tal que $\iota \in J_{\lambda }$; puesto que $x\in \underset{\iota \in J_{\lambda }}{\cap }{X}_{\iota }$, se tiene que $x\in X_{\iota }$. Esto es verdadero para cada $\iota \in I$, luego $x\in \underset{\iota \in I}{\cap }{X}_{\iota }$. Q.E.D.

Para las familias de las partes de un conjunto, la segunda parte del teorema anterior es válida sin las restricciones $I\ne \varnothing$ y $J_{\lambda }\ne \varnothing$ para todo $\lambda \in L$.

Imágenes de una reunión y de una intersección.

TEOREMA 3.- Sea ${\left(X_{\iota }\right)}_{\iota \in I}$ una familia de partes de un conjunto $A$ y $\Gamma$ una correspondencia entre $A$ y $B$.
Se tiene, entonces

y



Demostración.-



Luego la primera fórmula queda demostrada.

$\begin{array}{c}\forall \iota \in I \underset{\iota \in I}{\cap }{X}_{\iota }\subset X_{\iota }\end{array}$
de donde . Luego . Q.E.D.

Para $\Gamma$ una correspondencia cualquiera, la fórmula es el general falsa.

TEOREMA 4.- Sea $f$ una aplicación de $A$ en $B$, y ${\left(X_{\iota }\right)}_{\iota \in I}$ una familia de partes de $B$. Se tiene entonces



Demostración.-

(i)



(ii)



Q.E.D.

COROLARIO.- Si $\begin{array}{c}f\end{array}$ es una inyección de $\begin{array}{c}A\end{array}$ en $\begin{array}{c}B\end{array}$ y si ${\left(X_{\iota }\right)}_{\iota \in I}$ es una familia de partes de $A$ tal que $I\ne \varnothing$, se tiene



Demostración.- es un caso particular del teorema 3.



Q.E.D.

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.

El Teorema de Compacidad del Cálculo Proposicional (II)

TEOREMA DE COMPACIDAD.- Si un conjunto de fbfs $\Sigma$ es finitamente satisfacible, entonces es satisfacible.

Demostración.- Por el LEMA, existe un conjunto de fbfs $\Delta$ tal que $\Sigma \subseteq \Delta$ y $\Delta$ es finitamente satisfacible y completo.
Entonces $\forall \phi \in W, \phi \notin \Delta \iff N\phi \in \Delta$ pues, por ser $\Delta$ completo, si $\phi \notin \Delta$, entonces $N\phi \in \Delta$; y, por ser $\Delta$ finitamente satisfacible, si $N\phi \in \Delta$, entonces $\phi \notin \Delta$, porque en otro caso sería $\left\{N\phi ,\phi \right\}\subseteq \Delta$ satisfacible, lo que es falso.

Sea la valoración de verdad $v:S\to \left\{0,1\right\}$, dada por $\forall p\in S, v\left(p\right)=1 syss p\in \Delta$.

Por inducción sobre fbfs demostraremos que

(*) $\overline{v}\left(\phi \right)=1 syss \phi \in \Delta$

lo cual es equivalente a $\overline{v}\left(\phi \right)=0 syss \phi \notin \Delta$.

Para los símbolos aserción del lenguaje, se cumple (*), por definición de $v$ y ser $\overline{v}\left(p\right)=v\left(p\right), \forall p\in S$.

Si $\alpha \in \Delta$ cumple (*), entonces

$\overline{v}\left(N\alpha \right)=1 syss \overline{v}\left(\alpha \right)=0 syss \alpha \notin \Delta syss N\alpha \in \Delta$

También se tiene que

$\overline{v}\left(C\alpha \beta \right)=0 syss \overline{v}\left(\alpha \right)=1 y \overline{v}\left(\beta \right)=0 syss \alpha \in \Delta y \beta \notin \Delta syss \alpha \in \Delta y N\beta \in \Delta syss C\alpha \beta \notin \Delta$

pues, en caso contrario, si $C\alpha \beta \in \Delta$, se tendría que $\left\{\alpha ,N\beta ,C\alpha \beta \right\}\subseteq \Delta$, y de $\left\{\alpha ,C\alpha \beta \right\}╞\beta$ se verificaría que $\beta \in \Delta$, lo que es imposible pues $N\beta \in \Delta$ y $\Delta$ es finitamente satisfacible, no siéndolo $\left\{\beta ,N\beta \right\}\subseteq \Delta$.
Se ha probado, pues, que la valoración $v$ satisface a $\Delta$, luego también a $\Sigma \subseteq \Delta$. Q.E.D.

El Teorema de Compacidad del Cálculo Proposicional (I)

En el lenguaje de la Lógica Proposicional (en adelante, CP), si $S$ representa al conjunto de símbolos aserción (que a su vez representa al conjunto de proposiciones simples del lenguaje ordinario, del que es modelo el CP), y $W$ denota al conjunto de las fórmulas bien formadas (fbfs, en adelante) del lenguaje, por definición una valoración de verdad o semántica en $L$ es una aplicación $v:S\to \mathcal{V}$, donde $\mathcal{V}$ es un conjunto que se denomina de los valores de verdad de la valoración.
En Lógica Bivaluada, $\mathcal{V}=\left\{0,1\right\}$; pero en Lógica Multivaluada $\mathcal{V}$ suele ser un subconjunto del intervalo real $[0,1]$, el cual contiene a $\left\{0,1\right\}$.

Se demuestra que existe una extensión única, $\overline{v}:W\to \mathcal{V}$, de $v$ al conjunto $W$ de fórmulas bien formadas del lenguaje, la cual constituye algebraicamente un homomorfismo de (1,2)-álgebras libres:

(i) el (1,2)-álgebra libre generada por el conjunto de símbolos aserción mediante las operaciones constructoras (o conectivas): $C y N$, o $F_C,F_N$, respectivamente, donde

$F_N:W\to W, F_N\left(\alpha \right)=N\alpha$

y

$F_C:W\times W\to W, F_C\left(\alpha ,\beta \right)=C\alpha \beta$

resultando la estructura $\left(W,N,C\right)$ una (1,2)-álgebra libre, y

(ii) definiendo en $\mathcal{V}$ las operaciones internas $G_N$ (unaria) y $G_C$ (binaria), de tal forma que verifican, para cualesquiera fbfs $\alpha y \beta$:

$\overline{v}\left(N\alpha \right)=G_N\left(\overline{v}\left(\alpha \right)\right), \overline{v}\left(C\alpha \beta \right)=G_C\left(\overline{v}\left(\alpha \right),\overline{v}\left(\beta \right)\right)$

siendo $\left(\mathcal{V},G_N,G_C\right)$ también una (1,2)-álgebra libre y $\overline{v}:\left(W,N,C\right)\to \left(\mathcal{V},G_N,G_C\right)$ el homomorfismo entre (1,2)-álgebras antecitado.

Se demuestra, así mismo, que $W$ (el conjunto de las fbfs del lenguaje) está libremente generado por el conjunto de símbolos aserción $S$, mediante las operaciones conectivas, y de forma análoga ocurre $\mathcal{V}$ y las operaciones unaria y binaria internas definidas sobre él.

El teorema de extensión de $v$ a $\overline{v}$ se demuestra, en su generalidad, para cualquier conjunto de valores $\mathcal{V}$, como el descrito.

DEFINICIÓN 1.- Se dice que una valoración de verdad, $v$, satisface a una fbf $\alpha$ cuando $\overline{v}\left(\alpha \right)=1$.

DEFINICIÓN 2.- Diremos que un conjunto de fbfs $\Sigma$ implica tautológicamente a una fbf $\alpha$, si cada valoración de verdad que satisface a todas las fbfs de $\Sigma$ satisface también a $\alpha$.
Escribiremos, entonces: $\Sigma ╞\alpha$. En caso contrario, se escribe: $\Sigma \cancel{╞}\alpha$.

Ejemplo: $\left\{\alpha ,C\alpha \beta \right\}╞\beta$.

Si $\Sigma =\varnothing , \varnothing ╞\alpha$ significa que $\alpha$ es verdadera en cualquier valoración, y se dice que $\alpha$ es una fbf tautológica o que es una tautología, escribiendo en ese caso: $╞\alpha$.

DEFINICIÓN 3.- Un conjunto $\Sigma$ de fbfs se dice satisfacible si existe una valoración de verdad $v$ que satisface a cada fbf de $\Sigma .$Se dice finitamente satisfacible si cualquier subconjunto finito de $\Sigma$es satisfacible.

DEFINICIÓN 4.- Un conjunto $\Delta$ de fbfs se dirá completo si para cualquier fbf $\alpha$, se tiene: $\alpha \in \Delta ó N\alpha \in \Delta$.

LEMA.- Si un conjunto $\Sigma$ de fbfs es finitamente satisfacible, entonces existe un conjunto $\Delta$ finitamente satisfacible y completo que contiene a $\Sigma$.

Demostración.- Sea $\Gamma$ un conjunto de fbfs tal que

$\Gamma =\left\{H|\Sigma \subseteq H y H es finitamente satisfacible\right\}$

Entonces $\Gamma \ne \varnothing , pues \Sigma \in \Gamma$. Además, $\left(\Gamma ,\subseteq \right)$ es un conjunto parcialmente ordenado.
Sea en él una cadena

$H_0\subseteq H_1\subseteq H_2\subseteq \cdots$

Entonces $\cup \left\{H_0,H_1,H_2,...\right\}$ es una cota superior de $\left\{H_0,H_1,H_2,...\right\}$, pues $\Sigma \subseteq \cup \left\{H_0,H_1,H_2,...\right\}$ y $\cup \left\{H_0,H_1,H_2,...\right\}$ es finitamente satisfacible, dado que cualquier subconjunto finito de $\cup \left\{H_0,H_1,H_2,...\right\}$ está contenido en algún $H_m,m\in \mathrm{\mathbb{N}}$.

Aplicando el Lema de Zorn, existe un elemento maximal $\Delta en \left(\Gamma ,\subseteq \right)$; es decir, un conjunto de fbfs $\Delta$ que satisface: $K\in \Gamma y \Delta \subseteq K implican K=\Delta$.

Como $\Delta \in \Gamma$, $\Sigma \subseteq \Delta$ y $\Delta$ es finitamente satisfacible.
Además, $\Delta$ es completo. En efecto. Dada $\alpha \in W$, si $\Delta \cup \left\{\alpha \right\}$ es finitamente satisfacible, entonces pertenece a $\Gamma$ y, por ser $\Delta$ maximal, $\alpha \in \Delta$.
Si $\Delta \cup \left\{\alpha \right\}$ no es finitamente satisfacible, entonces existe $J_1\subseteq \Delta$ tal que $J_1\cup \left\{\alpha \right\}$ no es satisfacible.
Consideremos a $\Delta \cup \left\{N\alpha \right\}$ y sea $J_2\subseteq \Delta \cup \left\{N\alpha \right\}$ un subconjunto finito cualquiera. Si $J_2\subseteq \Delta$, $J_2$ es satisfacible, y si $J_2⊈\Delta$, se tiene que $J_2=J_3\cup \left\{N\alpha \right\}$, donde $J_3\subseteq \Delta$.
El conjunto finito $J_1\cup J_3\subseteq \Delta$ es satisfacible, luego existe una valoración de verdad $v$ que satisface a $J_1 y J_3$. Entonces $\overline{v}\left(\alpha \right)=0$, pues $J_1\cup \left\{\alpha \right\}$ no es satisfacible, y por tanto $\overline{v}\left(N\alpha \right)=1$ y $v satisface a J_3\cup \left\{N\alpha \right\}=J_2$. En consecuencia, $\Delta \cup \left\{N\alpha \right\}$ es finitamente satisfacible y, como contiene a $\Sigma$, y $\Delta$ es maximal, se concluye que $N\alpha \in \Delta$. Q.E.D.