Infelizmente, o primeiro passo para começar a fazer lógica é aceitar a Teoria Ingênua dos Conjuntos.
O segundo passo é usar a Teoria Ingênua dos Conjuntos para construir um conjunto que será a linguagem da lógica que você quer fazer.
O que farei aqui é exatamente isso, isto é, construirei a linguagem da Lógica Proposicional. Para isso, assumirei que você, leitor, conhece os axiomas da Teoria Ingênua dos Conjuntos.
(chamarei a Lógica Proposicional de CPC ao longo do post)
Conteúdo do post
Alfabeto
Comecemos definido o alfabeto $\mathcal{A}$ do CPC como sendo qualquer conjunto infinito e enumerável. Como conjuntos assim existem na Teoria de Conjuntos, segue que o alfabeto do CPC existe. Mas para facilitar a comunicação, denotaremos os elementos de $\mathcal{A}$ como:
\[ \mathcal{A} = \mathcal{B} \cup \{(, ), \nao, \e, \ou, \imp \} \]
Onde $\mathcal{B} = \{p_n / n \in \mathbb{N} \}$ é um conjunto disjunto do conjunto $\{(, ), \nao, \e, \ou, \imp \}$. Os elementos do alfabeto são chamados de símbolos. A única propriedade que esses símbolos realmente precisam ter é serem distintos e que nenhum deles possa ser uma sequência dos outros (caso contrário, uma expressão poderia ter duas representações). Então pense neles como elementos primitivos distintos. $\mathcal{B}$ só precisa ser um conjunto enumerável infinito e o conjunto da direita só precisa ser um conjunto com 6 elementos distintos entre si e distintos dos elementos de $\mathcal{B}$.
As vezes também denotaremos os elementos de $\mathcal{B}$ com letras minúsculas ($p$, $q$, $r$, …).
Expressão
Agora que definimos o alfabeto, definiremos o que é uma expressão do alfabeto (ou só expressão). Definirei expressões como sequências finitas de símbolos do alfabeto (sequência aqui sendo empregada com seu significado restrito da Teoria Ingênua dos Conjuntos). Denotarei o conjunto de todas as expressões por $\mathcal{A}^*$. No entanto, como estamos definindo tudo em termos da Teoria dos Conjuntos, precisamos mostrar que $\mathcal{A}^*$ existe.
Assumindo os axiomas da Teoria Ingênua dos Conjuntos, é possível criar o conjunto dos números naturais $\mathbb{N}$. Por isso assumirei que $\mathbb{N}$ existe (uma prova disso pode ser vista no livro do Halmos). Então, por definição de sequência, uma sequência de n elementos do alfabeto é uma função
\[ \begin{aligned}
s \colon I_n &\to \mathcal{A} \\
n &\mapsto x
\end{aligned} \]
E essa função, por definição, é um subconjunto de $\mathbb{N} \times \mathcal{A}$. Logo, todas as sequências finitas pertencem ao conjunto $P(\mathbb{N} \times \mathcal{A})$ (note que $P(\mathbb{N} \times A)$ possui elementos que não são sequências também). Seja $\{a_\lambda \}$ a família de todos os subconjuntos de $P(\mathbb{N} \times \mathcal{A})$ que contém todas as sequências finitas de elementos de $\mathcal{A}$. Definirei $\mathcal{A}^*$ como a interseção dessa família. Isto é,
\[ \mathcal{A}^* = \bigcap_{\lambda \in \Lambda} a_\lambda \]
Defino assim para que o conjunto de expressões seja o menor conjunto que contenha todas as expressões.
Essa não é única forma de definir o $\mathcal{A}^*$. O Ederton por exemplo define expressão como uma upla ordenada, e não como uma sequência. A vantagem é não precisar dos números naturais na definição.
Obs: De forma análoga ao que fizemos para construir o conjunto de todas as expressões da linguagem do CPC podemos fazer para construir o conjunto de todas as expressões do português. Isto é,denotando $E^*$ como o conjunto de todas as sequências finitas de símbolos do alfabeto português, teríamos que $E^* \subset P(\mathbb{N} \times \{a, b, c, d, …, z, ,, ., \text{~}, …\})$.
Linguagem
Agora que criamos o conjunto $\mathcal{A}^*$ de todas as expressões do CPC, construiremos o conjunto $\mathcal{L}$, que será a linguagem da Lógica Proposicional, como um subconjunto de $\mathcal{A}^*$.
Para isso, vamos apenas eliminar as sequências de $\mathcal{A}^*$ que não terão significado, como por exemplo: “$A \rightarrow \rightarrow \e B$”.
Como $\mathcal{A}^*$ existe, segue do axioma das partes que a função
\[ \begin{aligned}
\epsilon_\nao \colon & \mathcal{A}^* \to \mathcal{A}^* \\
& \alpha \mapsto (\nao \alpha)
\end{aligned} \]
existe, pois essa função é um subconjunto de $\mathcal{A}^* \times \mathcal{A}^*$.
Análogamente, as funções
\[ \begin{aligned}
\epsilon_\e \colon & \mathcal{A}^* \times \mathcal{A}^* \to \mathcal{A}^* \\
& (\alpha, \beta) \mapsto (\alpha \e \beta)
\end{aligned} \]
\[ \begin{aligned}
\epsilon_\ou \colon & \mathcal{A}^* \times \mathcal{A}^* \to \mathcal{A}^* \\
& (\alpha, \beta) \mapsto (\alpha \ou \beta)
\end{aligned} \]
\[ \begin{aligned}
\epsilon_\cond \colon & \mathcal{A}^* \times \mathcal{A}^* \to \mathcal{A}^* \\
& (\alpha, \beta) \mapsto (\alpha \imp \beta)
\end{aligned} \]
existem, pois são subconjuntos de $(\mathcal{A}^* \times \mathcal{A}^*) \times \mathcal{A}^*$. (Cuidado, do lado esquerdo da função o parênteses é um metasímbolos, e do lado direito ele é um símbolo dentro da teoria!)
Seja $\{b_\lambda \}$ a família de todos os subconjuntos de $\mathcal{A}^*$ que sejam fechados para as funções acima restringidas a eles e que contenham o conjunto das variáveis proposicionais $B$. Definirei $\mathcal{L}$ como sendo a interseção dessa família. Isto é,
\[ \mathcal{L} = \bigcap_{\lambda \in \Lambda} b_\lambda \]
E esta é a linguagem da lógica proposicional!
Novamente, a definição da linguagem usando interseção de famílias é para que o conjunto que chamamos de linguagem seja o menor conjunto possível que contenha todas as “frases” bem formadas.
Agora que criamos a linguagem do CPC, podemos dizer que ela será nossa linguagem objeto e o português (no qual uso para falar sobre $\mathcal{L}$) será nossa metalinguagem. E a metateoria da metalinguagem que usamos para provar que $\mathcal{L}$ existe é a Teoria Ingênua de Conjuntos. No futuro, conseguiremos expressar até a Teoria Ingênua dos Conjuntos numa linguagem artificial, então não precisaremos do português para nada (ao menos no meu mundo ideal).
Diário de Estudos
A graça de fazer essa construção é perceber que se quisermos provar algo sobre a Lógica Proposicional, precisamos usar a Teoria dos Conjuntos. Por exemplo, usando o que foi feito conseguimos provar que a linguagem da Lógica Proposicional é única, que uma conjunção não pode ser uma implicação, e muito mais. Inclusive, essas provas serão conteúdo de algum post futuro.
Uma coisa chata da construção que fizemos é que precisamos de uma teoria já pronta (a Teoria Ingênua dos Conjuntos) para começar a fazer Lógica, que deveria ser a nossa ferramenta para provar coisas a Teoria dos Conjuntos! Acho que sempre precisaremos de uma teoria para provar resultados sobre outra teoria, então essa “circularidade” é inevitável.
Uma dúvida que eu tenho é se a linguagem da Lógica Proposicional é enumerável. Eu acho que é mas não sei provar.