Prove or disprove: if Γ ⊢ α and Γ ⊆ ∆ then ∆ ⊢ α

Solution 1:

First order logic has three (often overlooked) structural rules -- weakening, contraction, and permutation as follows:

$$\frac{\Gamma \vdash A}{\Gamma,B\vdash A}(\text{Weakening})$$ $$\frac{\Gamma, B, B\vdash A}{\Gamma, B\vdash A}(\text{Contraction})$$ $$\frac{\Gamma_1, B,C,\Gamma_2\vdash A}{\Gamma_1,C,B,\Gamma_2\vdash A}(\text{Permutation})$$

The weakening rule lets you arbitrarily add hypotheses.

So formally, you would write $\Delta-\Gamma = \{A_1,\ldots,A_n\}$ and proceed by induction.

In practice, however, we usually ignore them by assuming that the context is a multiset instead of an ordered list.