The following post : Prove: $ (A \times C) \setminus (B \times C) = (A \setminus B) \times C $ made me think of the question I am now asking.

Are there frequently used / well known laws for cartesian products in the context of set algebra.

In case such laws exist, can they be proved without analysing the statements in terms of membeship relation ( I mean without using set theory proper)?

Is it possible to " manipulate" cartesian products algebraically and mechanically in the same way one "manipulates" more ordinary sets using DeMorgan's Law, Idempotency Law or Domination law ( for sets) etc. ?

  • 2
    $\begingroup$ Sure there are, but you need to prove that those formulas are also true, which leads to the same type of problem that you're trying to solve. $\endgroup$ – Michael Burr Jun 3 '19 at 11:05

There indeed do exist many well-known laws for Cartesian products, such as the following:

$(A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D),$

$A \times (B \cap C) = (A \times B) \cap (A \times C)$ (distributivity of intersection),

$A \times (B \cup C) = (A \times B) \cup (A \times C)$ (distributivity of union),

$A \times (B \backslash C) = (A \times B) \backslash (A \times C)$ (distributivity of set difference),

and various other laws. For more, see here: https://en.wikipedia.org/wiki/Cartesian_product#Most_common_implementation_(set_theory)


Perhaps the following facts are useful:

$A=B$ iff $I_A=I_B$ where $I_E(x)=1$ or $0$ according as $ x\in E$ or not.

$I_{A\cap B}=I_AI_B$

$I_{E\setminus F} =I_E -I_F$ if $F \subset E$.

$I_{A\times B} (x,y)=I_A(x)I_B(y)$.


The kind of laws @auscrypt presents would generally count as relational algebra.

While one could use such rules as a vehicle for presenting mathematical arguments (in the same way that elementary set algebra is used in much ordinary mathematics), this is not very common. Except for very simple arguments, trying to phrase things as algebraic manipulations generally seem to make things more complex than ad hoc element-for-element reasoning, and then there's little point to try.

Relational algebra is, however, widely used for implementation and optimization of database operations. In that settings the manipulations need to be carried out by a computer that is incapable of coming up with ad-hoc reasoning, so it is necessary to have a formal notation that can be manipulated symbolically.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.