The Fundamental Laws of Set Algebra
The binary operations of set union and intersection satisfy many identities. Several of these identities or "laws" have well established names. Three pairs of laws, are stated, without proof, in the following proposition.
PROPOSITION 1: For any sets A, B, and C, the following identities hold:
- commutative laws:
-
- associative laws:
-
- distributive laws:
-
Notice that the analogy between unions and intersections of sets, and addition and multiplication of numbers, is quite striking. Like addition and multiplication, the operations of union and intersection are commutative and associative, and intersection distributes over unions. However, unlike addition and multiplication, union also distributes over intersection.
The next proposition, states two additional pairs of laws involving three specials sets: the empty set, the universal set and the complement of a set.
PROPOSITION 2: For any subset A of universal set U, where Ø is the empty set, the following identities hold:
- identity laws:
-
- complement laws:
-
The identity laws (together with the commutative laws) say that, just like 0 and 1 for addition and multiplication, Ø and U are the identity elements for union and intersection, respectively.
Unlike addition and multiplication, union and intersection do not have inverse elements. However the complement laws give the fundamental properties of the somewhat inverse-like unary operation of set complementation.
The preceding five pairs of laws: the commutative, associative, distributive, identity and complement laws, can be said to encompass all of set algebra, in the sense that every valid proposition in the algebra of sets can be derived from them.
Note that if the complement laws are weakened to the rule, then this is exactly the algebra of propositional linear logic.
Read more about this topic: Algebra Of Sets
Famous quotes containing the words fundamental, laws, set and/or algebra:
“This declared indifference, but as I must think, covert real zeal for the spread of slavery, I can not but hate. I hate it because of the monstrous injustice of slavery itself. I hate it because it deprives our republican example of its just influence in the world ... and especially because it forces so many really good men amongst ourselves into an open war with the very fundamental principles of civil liberty.”
—Abraham Lincoln (1809–1865)
“His talk was like a spring, which runs
With rapid change from rocks to roses:
It slipped from politics to puns,
It passed from Mahomet to Moses;
Beginning with the laws which keep
The planets in their radiant courses,
And ending with some precept deep
For dressing eels, or shoeing horses.”
—Winthrop Mackworth Praed (1802–1839)
“Let us speak, though we show all our faults and weaknesses,—for it is a sign of strength to be weak, to know it, and out with it,—not in a set way and ostentatiously, though, but incidentally and without premeditation.”
—Herman Melville (1819–1891)
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (1883–1955)