Wikipedia:Reference desk/Archives/Mathematics/2021 April 14

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 14

Translation in classical logic?

Is there something like the Gödel–Gentzen translation for a translation from Many-valued logic in classical logic?--82.82.233.47 (talk) 20:05, 14 April 2021 (UTC)

It depends a bit on what you demand of the translation and which version of many-valued logic is taken as the source logic of the translation. I assume we want the translation to be compositional. To explain what I mean by this, let $\odot$ stand for any logical operator of the source logic – for simplicity I only consider the case of a dyadic (binary) operator, taking two logical formulas $\varphi$ and $\psi$ as operands to form a new formula $\varphi \odot \psi .$ Denoting translation by a superscript "${}^{\mathsf {T}}$", for this translation to be compositional it should be the case that $(\varphi \odot \psi )^{\mathsf {T}}=\varphi ^{\mathsf {T}}\odot ^{\mathsf {T}}\psi ^{\mathsf {T}},$ where $\odot ^{\mathsf {T}}$ denotes an operation that is definable using the target logic, here classical logic. It is a must that the translation is representation insensitive, meaning that it maps equivalent formulas in the source formalism to equivalent results in the target formalism. I also assume that we exclude trivial translations, such as the one that defines $\varphi ^{\mathsf {T}}=\mathrm {T}$ for all $\varphi .$ I'll concentrate on Kleene's $K_{3}.$ The translation has to be a bit more complicated, since a propositional formula in the source logic – excluding trivial translations that map every formula to the same classical formula – cannot simply be mapped compositionally to a formula in the target language. Proof of this impossibility is by showing that a compositional translation is trivial. Let ${}^{\mathsf {T}}$ be any compositional translation. Put $\mathrm {T} ^{\mathsf {T}}=\mathrm {X} ,$ $\mathrm {I} ^{\mathsf {T}}=\mathrm {Y} ,$ and $\mathrm {F} ^{\mathsf {T}}=\mathrm {Z} .$ Since $\neg ^{\mathsf {T}}\mathrm {Y} =\neg ^{\mathsf {T}}\mathrm {I} ^{\mathsf {T}}=(\neg \mathrm {I} )^{\mathsf {T}}=\mathrm {I} ^{\mathsf {T}}=\mathrm {Y} ,$ the operation $\neg ^{\mathsf {T}}$ has a fixpoint. There are three classical logical operation that have a fixpoint, constant $\mathrm {T} ,$ constant $\mathrm {F} ,$ and the identity. If $\neg ^{\mathsf {T}}$ is the identity, $(\neg \varphi )^{\mathsf {T}}=\neg ^{\mathsf {T}}\varphi ^{\mathsf {T}}=\varphi ^{\mathsf {T}}$, so $\mathrm {X} =\mathrm {T} ^{\mathsf {T}}=(\neg \mathrm {T} )^{\mathsf {T}}=\mathrm {F} ^{\mathsf {T}}=\mathrm {Z} .$ Then also $\mathrm {Y} =\mathrm {I} ^{\mathsf {T}}=$ $(\mathrm {I} \land \mathrm {T} )^{\mathsf {T}}=$ $\mathrm {Y} \land ^{\mathsf {T}}\mathrm {X} =$ $\mathrm {Y} \land ^{\mathsf {T}}\mathrm {Z} =$ $(\mathrm {I} \land \mathrm {F} )^{\mathsf {T}}=$ $\mathrm {F} ^{\mathsf {T}}=\mathrm {Z} .$ The constant operations can likewise be excluded. However, a translation is possible if we translate a source formula $\varphi$ to a pair of formulas as follows:

$\mathrm {T} ^{\mathsf {T}}=(\mathrm {T} ,\mathrm {F} );$

$\mathrm {I} ^{\mathsf {T}}=(\mathrm {F} ,\mathrm {F} );$

$\mathrm {F} ^{\mathsf {T}}=(\mathrm {F} ,\mathrm {T} );$

$\neg ^{\mathsf {T}}(\varphi _{0},\varphi _{1})=(\varphi _{1},\varphi _{0});$

$(\varphi _{0},\varphi _{1})\land ^{\mathsf {T}}(\psi _{0},\psi _{1})=(\varphi _{0}\land \psi _{0},\varphi _{1}\lor \psi _{1}).$

The other operations follow from the usual identities, such as $\varphi \to \psi \equiv (\neg \varphi )\lor \psi .$ The first component of the pair can be interpreted as "definitely true", and the second as "definitely false". Then $(\mathrm {F} ,\mathrm {F} )$ means: "neither definitely true nor definitely false".  --Lambiam 00:38, 15 April 2021 (UTC)