7.4

Use Armstrong’s axioms to prove the soundness of the union rule. (Hint: Use the augmentation rule to show that, if \(\alpha \rightarrow \beta\), then \(\alpha \rightarrow \alpha \beta\). Apply the augmentation rule again, using \(\alpha \rightarrow \gamma\), and then apply the transitivity rule.)


To prove that:

\[ \text{if $\alpha \rightarrow \beta$ and $\alpha \rightarrow \gamma$ then $\alpha \rightarrow \beta \gamma$ } \]

Following the hint, we derive:

\[ \alpha \rightarrow \beta \quad \text{given}\\ \alpha \alpha \rightarrow \alpha \beta \quad \text{augmentation rule}\\ \alpha \rightarrow \alpha \beta \quad \text{union of identical sets}\\ \alpha \rightarrow \gamma \quad \text{given}\\ \alpha\beta \rightarrow \gamma\beta \quad \text{augmentation rule}\\ \alpha \rightarrow \beta\gamma \quad \text{transitivity rule and set union commutativity} \]