Question

Consider the full language \(\mathcal{L}\) with the connectives \(\wedge, \rightarrow, \perp, \leftrightarrow \vee\) and the restricted language \(\mathcal{L}^{\prime}\) with connectives \(\wedge, \rightarrow, \perp\). Using the appropriate derivation rules we get the derivability notions \(\vdash\) and \(\vdash^{\prime}\). We define an obvious translation from \(\mathcal{L}\) into \(\mathcal{L}^{\prime}\) : \(\begin{aligned} \varphi^{+} &:=\varphi \text { for atomic } \varphi \\\\(\varphi \square \psi)^{+} &:=\varphi^{+} \square \psi^{+} \text {for } \square=\wedge, \rightarrow, \end{aligned}\) \((\varphi \vee \psi)^{+}:=\neg\left(\neg \varphi^{+} \wedge \neg \varphi^{+}\right)\), where \(\neg\) is an abbreviation, \((\varphi \leftrightarrow \psi)^{+}:=\left(\varphi^{+} \rightarrow \psi^{+}\right) \wedge\left(\psi^{+} \rightarrow \varphi^{+}\right)\), $$ (\neg \varphi)^{+}:=\varphi^{+} \rightarrow \perp . $$ Show (i) \(\vdash \varphi \leftrightarrow \varphi^{+}\), (ii) \(\quad \vdash \varphi \Leftrightarrow \vdash^{\prime} \varphi^{+}\), (iii) \(\varphi^{+}=\varphi\) for \(\varphi \in \mathcal{L}^{\prime}\). (iv) Show that the full logic, is conservative over the restricted logic, i.e. for \(\varphi \in \mathcal{L}^{\prime} \vdash \varphi \Leftrightarrow \vdash^{\prime} \varphi\).

Short answer

The translation ensures \( \vdash \varphi \leftrightarrow \varphi^{+} \), \( \vdash \varphi \Leftrightarrow \vdash^{\prime} \varphi^{+}\) holds. For \(\varphi \in \mathcal{L}^{\prime}\), \(\varphi^{+}=\varphi\) and full logic is conservative over restricted logic.

Step-by-step solution

Translation in Language

The translation from the full language \( \mathcal{L} \) to the restricted language \( \mathcal{L}^{\prime} \) is defined such that \( \varphi^{+} = \varphi \) for atomic propositions. The translation for logical connectives is defined by \((\varphi \wedge \psi)^{+} = \varphi^{+} \wedge \psi^{+}\), \((\varphi \rightarrow \psi)^{+} = \varphi^{+} \rightarrow \psi^{+}\), \((\varphi \vee \psi)^{+} = eg(eg \varphi^{+} \wedge eg \psi^{+})\), \((\varphi \leftrightarrow \psi)^{+} = (\varphi^{+} \rightarrow \psi^{+}) \wedge (\psi^{+} \rightarrow \varphi^{+})\), and \((eg \varphi)^{+} = \varphi^{+} \rightarrow \perp\).

Prove \( \vdash \varphi \leftrightarrow \varphi^{+} \) (Part i)

To show \( \vdash \varphi \leftrightarrow \varphi^{+} \), consider that \( \varphi \) can be either atomic, or logically composed via connectives. For each case, due to the definition of the translation, \( \varphi^{+} \) operationalizes \( \varphi \). Thus, the formula \( \varphi \leftrightarrow \varphi^{+} \) holds as a tautology in \( \mathcal{L} \). For any atomic proposition this is trivially true, and for any compound formula, each connective's definition ensures it.

Prove \(\vdash \varphi \Leftrightarrow \vdash^{\prime} \varphi^{+}\) (Part ii)

For any formula \( \varphi \) with \( \vdash \varphi \), it follows from part (i) that \( \varphi \leftrightarrow \varphi^{+} \) is provable. Therefore, \( \vdash^{\prime} \varphi^{+} \) must be true due to the bi-interpretation between the two logics that \( \varphi^{+} \) operationalizes \( \varphi \) in \( \mathcal{L}^{\prime} \). Similarly, if \( \vdash^{\prime} \varphi^{+} \), then by the same reasoning, \( \vdash \varphi \) in \( \mathcal{L} \).

Show \(\varphi^{+}=\varphi\) for \(\varphi \in \mathcal{L}^{\prime}\) (Part iii)

Since \( \varphi \in \mathcal{L}^{\prime} \) implies that \( \varphi \) is only formed using the connectives \( \wedge, \rightarrow, \perp \), and the translation does not change these connectives, \( \varphi^{+} = \varphi \) holds directly from definition.

Prove Full Logic's Conservativeness over Restricted Logic (Part iv)

For any \( \varphi \in \mathcal{L}^{\prime} \), consider that from steps 3 and 4, the translation is the identity mapping, hence \( \varphi^{+} = \varphi \).Thus if \( \vdash \varphi \), it implies \( \vdash^{\prime} \varphi \), and conversely, due to \( \varphi^{+} = \varphi \). This shows that derivations in the full logic are conservative, preserving the derivability in the restricted logic.

Key concepts

Derivability

Derivability in formal logic refers to the ability to derive a conclusion from a set of premises using certain rules of inference. This is a key concept because it underpins the validity of arguments within logical systems. In the context of the exercise, we use derivability notions such as \( \vdash \) and \( \vdash' \) to represent these logical derivations in different languages. This means that a formula is deemed derivable in a language if there exists a sequence of logical steps supported by the inference rules that lead to the formula.
The challenge often is to prove that certain formulas are derivable in one logic and simultaneously in another, possibly reduced, form of logic. Here, we are concerned with translating derivability from a full logical language \( \mathcal{L} \) to a restricted logic \( \mathcal{L}' \). This exercise highlights the importance of translations and reductions in maintaining the consistency of derivability across different logical systems.
When dealing with derivability, remember that:

• You are generally tasked with proving the validity of propositions by logical deduction.
• Understanding the specific inference rules of the logic you are dealing with is crucial.

Logical Connectives

Logical connectives are the basic operations used to build compound expressions from simpler ones in a logical language. They allow us to construct complex relationships and include standard operations like conjunction (\(\wedge\)), disjunction (\(\vee\)), and others such as implication (\(\rightarrow\)) and equivalence (\(\leftrightarrow\)).
In this exercise, we are particularly interested in how these connectives behave under translation from a full language \( \mathcal{L} \) to a restricted language \( \mathcal{L}' \). For instance, in the restricted language, we reformulate disjunction (\( \vee \)) and equivalence (\( \leftrightarrow \)) using only other available connectives to ensure the language remains robust and expressive despite having fewer primitives.
Understanding logical connectives is vital because:

• They form the functional components of logical propositions.
• Correctly translating them between languages ensures semantic consistency.

Translation Between Languages

Translation between logical languages involves converting expressions from one form to another while preserving their meaning and truth values. It's a crucial aspect of formal logic, especially when working with comparative or conservative logics.
The translation involves mapping every expression in the full language \( \mathcal{L} \) to an equivalent in the restricted language \( \mathcal{L}' \). This is done by redefining expressions using the simpler or restricted set of connectives. For example, in this exercise, disjunction \((\vee)\) is expressed in terms of conjunction \((\wedge)\) and negation \((eg)\) in \( \mathcal{L}' \).
Effective translation ensures that:

• Logical equivalence is maintained across languages.
• The expressive power of a logic language is fully utilized, even with fewer connectives.

Conservative Logic

Conservative logic refers to ensuring that new additions or restrictions to a logical system do not alter the existing derivations of the original system. In this exercise, we aim to show that the full logic \( \mathcal{L} \) is conservative over the restricted logic \( \mathcal{L}' \). This means that any derivation possible in the restricted logic should still be derivable in the full logic.
To demonstrate conservativeness, it is essential to prove that if a formula is derivable in the restricted language \( \mathcal{L}' \), then it remains derivable in the full language \( \mathcal{L} \). This involves showing that any additional connectives or structures do not introduce new derivations that would not have been possible in the restricted language.
An understanding of conservative logic ensures that:

• Modifications or simplifications of logics are reliable and do not disrupt existing truths.
• The relationship between different logical systems remains clear and predictable.