# How to go about proving the basic operators in relational algebra are independent of each other?

The five basic operator select, project, cross, union and diff in relational algebra are independent of each other. I'm trying to formally prove this statement but can only progress for cross product as it would have columns greater than the rest which cannot be made possible by others. But can't think of anything for Select etc.

• Select: consider the relation $\{(1),(2)\}$.
• Union: consider the database $\{(1)\},\{(2)\}$ with identical attributes.
• Use mathematical induction. The point is that you can't get $\{(1)\}$ or $\{(2)\}$ without using select. – Yuval Filmus Sep 3 '12 at 14:19
• @Tegiri You're right that $\{(1)\}$ can be obtained via the difference of $\{(1),(2)\}$ and $\{(2),(3)\}$. Fortunately, there is no row $(3)$ anywhere in the database. – Yuval Filmus Sep 4 '12 at 21:15