solucao:solsup1

Vamos realizar esta demonstração através da indução na complexidade das fórmulas:

  • Vamos começar com as fórmulas atômicas $F_0$:
    • Temos três casos, $\in, \subset$ e =, vamos fazer um deles e o restante é semelhante
    • Tome $\varphi(x)= x \in y$, para algum $y$ fixado
    • Sabemos por resultados já mostrados no seminário sobre Valorações que

$$|b \in y||b=a|\leq|a \in y|$$

  • com isso conseguimos diretamente que $|\varphi(b)||a=b|\leq|\varphi(a)|$
  • Agora devemos continuar o processo de indução supondo que vale para $F_n$ com $n \in \mathbb{N}
  • Dessa forma vamos verificar que vale para $F_{n+1}$
  • Tomemos $\varphi \in {F_{n+1}}$ de maneira que $\varphi = \phi \vee \psi$ tal que $\phi,\psi \in F_n$, pela hipótese de indução sabemos que valem

$$|\phi(b)||b=a|\leq|\phi(a)| \text{ e } |\psi(b)||b=a|\leq|\psi(a)|$$

  • com isso temos :

$$ \begin{array}{ll} |\varphi(b)||a=b| &=|\phi(b)\vee \psi(b)||a=b|=(|\phi(b)| + |\psi(b)|)|a=b| \\ \\ &=|\phi(b)||a=b|+|\psi(b)||a=b| \\ \\ &\leq |\phi(a)|+|\psi(a)|=|\varphi(a)| \end{array} $$

  • Faltam os casos com os outros símbolos lógicos, porém eles são feitos de maneira bem semelhante, criando funções $\varphi$ usando esses outros símbolos, por exemplo $\varphi = \neg \phi$, se $\phi \in F_n$ $\square$
  • solucao/solsup1.txt
  • Última modificação: 2021/08/23 11:37
  • por maugsia