Fact-checked by Grok 2 weeks ago

Algebra of sets

The algebra of sets is a fundamental branch of set theory that examines the operations and structural properties of sets, treating them analogously to numerical algebra through binary operations like union and intersection, and unary operations like complementation, within a universal set.^[1] These operations satisfy axioms similar to those of Boolean algebra, enabling the manipulation of sets in a rigorous, algebraic manner to solve problems in mathematics, logic, and related fields.^[2] Key operations in the algebra of sets include union (denoted A \cup B), which combines all elements from sets A and B; intersection (denoted A \cap B), which selects elements common to both; and complement (denoted A^c or A'), which consists of all elements in the universal set U not in A.^[3] Additional operations such as set difference (A \setminus B = A \cap B^c) and symmetric difference (A \Delta B = (A \cup B) \setminus (A \cap B)) further extend the framework, providing tools for expressing relationships between sets.^[1] These operations are defined extensionally, based on element membership, and apply to both finite and infinite sets.^[2] The algebra of sets is governed by a set of axioms and theorems that mirror arithmetic and logical principles, including commutativity (A \cup B = B \cup A, A \cap B = B \cap A), associativity ((A \cup B) \cup C = A \cup (B \cup C)), and distributivity (A \cup (B \cap C) = (A \cup B) \cap (A \cup C)).^[3] Identity elements play a central role, with the empty set \emptyset acting as the identity for union (A \cup \emptyset = A) and the universal set U for intersection (A \cap U = A), while idempotence holds (A \cup A = A, A \cap A = A).^[1] De Morgan's laws provide duality between union and intersection via complements: (A \cup B)^c = A^c \cap B^c and (A \cap B)^c = A^c \cup B^c, underscoring the Boolean structure.^[2] This algebraic framework also supports inclusion relations, forming a partial order on the power set of U, and extends to more advanced concepts like σ-algebras for measure theory.^[3]

Fundamentals

Basic Definitions and Notations

A set in mathematics is defined as a well-determined collection of distinct objects, known as elements or members, which can be treated as a single mathematical entity. For instance, the finite set {1, 2, 3} consists of the elements 1, 2, and 3, while the infinite set of natural numbers \mathbb{N} = \{1, 2, 3, \dots\} includes all positive integers without bound.^[4] The algebra of sets refers to the structure formed by sets under specific operations, constituting a Boolean algebra where sets serve as the elements and the operations correspond to logical connectives such as "and" and "or." This framework provides a rigorous algebraic basis for reasoning about collections in mathematics.^[5] Standard notations in set algebra include the symbol \cup for union, \cap for intersection, A^c or A' for the complement of set A, \emptyset for the empty set, and U for the universal set. Additionally, the cardinality of a set A, denoted |A|, represents the number of distinct elements it contains, offering a measure of its size.^[6]^[7] Set algebra formalizes logical operations central to mathematics, with origins tracing to George Boole's seminal 1854 work An Investigation of the Laws of Thought, which laid the foundations for algebraic logic, and further development by Ernst Schröder in the late 19th century through his expansions on Boolean systems.^[8]^[9]

Universal Set and Empty Set

In the context of set algebra, the universal set, denoted U, is defined as the set containing all elements relevant to the discussion at hand, serving as the fixed ambient space within which all other sets are subsets. This concept allows for a bounded universe in which operations on sets are performed, avoiding the paradoxes associated with an absolute universal set in pure set theory. The empty set, denoted \emptyset, is the unique set with no elements. A fundamental property is that \emptyset \subseteq A for every set A, since there are no elements in \emptyset that fail to belong to A. Its existence is ensured as a consequence of the axioms in modern axiomatic set theory, such as in Ernst Zermelo's 1908 axiomatization, where it is derived using the axiom of separation to construct a set with no elements.^[10] The universal set U functions as the identity element for the intersection operation: for any set A \subseteq U, A \cap U = A. To verify this, consider an arbitrary element x. If x \in A \cap U, then x \in A and x \in U; since A \subseteq U, this implies x \in A. Conversely, if x \in A, then x \in U by the subset relation, so x \in A \cap U. Thus, the sets coincide. Similarly, the empty set \emptyset serves as the identity for union: A \cup \emptyset = A. Here, x \in A \cup \emptyset means x \in A or x \in \emptyset; the latter is impossible, so x \in A. Conversely, if x \in A, then x \in A \cup \emptyset. These identity properties highlight the foundational roles of U and \emptyset in preserving sets under core operations. Complements in set algebra are defined relative to the universal set U: the complement of A, denoted A^c, is the set \{ x \in U \mid x \notin A \}. This captures all elements in the ambient space excluded from A. For instance, if U = \{1, 2, 3, 4\} and A = \{1, 2\}, then A^c = \{3, 4\}, as 3 and 4 are the elements of U not in A.

Core Operations

Union and Intersection

In set theory, the union of two sets A and B, denoted A \cup B, is the set consisting of all elements that belong to A, to B, or to both. Formally, A \cup B = \{ x \mid x \in A \lor x \in B \}.^[11] For example, if A = \{1, 2\} and B = \{2, 3\}, then A \cup B = \{1, 2, 3\}.^[12] The intersection of two sets A and B, denoted A \cap B, is the set consisting of all elements that belong to both A and B. Formally, A \cap B = \{ x \mid x \in A \land x \in B \}.^[11] Continuing the previous example, A \cap B = \{2\}.^[12] These operations correspond to the logical disjunction (OR) for union and conjunction (AND) for intersection.^[13] Venn diagrams provide a visual representation of these operations using overlapping circles to depict sets within a universal set. For union, the shaded region covers the area inside either circle, including the overlap, illustrating all elements in A or B or both.^[14] For intersection, only the overlapping region is shaded, showing elements common to both sets.^[15] Unions and intersections extend to infinitely many sets indexed by a set I. The union \bigcup_{i \in I} A_i consists of all elements that belong to at least one A_i, formally \{ x \mid \exists i \in I \text{ such that } x \in A_i \}.^[16] The intersection \bigcap_{i \in I} A_i consists of all elements that belong to every A_i, formally \{ x \mid \forall i \in I, x \in A_i \}.^[16] For a countable example, consider A_n = \{n\} for each natural number n; then \bigcup_{n \in \mathbb{N}} A_n = \mathbb{N}.^[16] In probability theory, the union of events corresponds to the logical OR, representing outcomes where at least one event occurs. For instance, if E is the event of drawing a red card and F is drawing an ace from a standard deck, then E \cup F includes all red cards or aces or both.^[17]

Complement and Set Difference

In set theory, the complement of a set A relative to a universal set U, denoted A^c, is defined as the set of all elements in U that do not belong to A:

A^c = \{ x \in U \mid x \notin A \}.

This operation captures the notion of exclusion within the fixed context of U. For example, if U = \{1, 2, 3\} and A = \{1\}, then A^c = \{2, 3\}./01%3A_Set_Theory/1.02%3A_Basic_Set_Operations) The set difference, also called the relative complement of B in A and denoted A \setminus B, consists of all elements in A that are not in B:

A \setminus B = \{ x \in A \mid x \notin B \} = A \cap B^c.

This binary operation generalizes subtraction for sets and relies on the complement of B. For instance, if A = \{1, 2, 3\} and B = \{2\}, then A \setminus B = \{1, 3\}. Key properties of the complement include the facts that A \cup A^c = U and A \cap A^c = \emptyset, establishing A^c as the precise counterpart to A within U. For the set difference, the complement satisfies (A \setminus B)^c = A^c \cup B intuitively, as it collects elements outside A or inside B, filling the space left by removing non-B elements from A./01%3A_Set_Theory/1.02%3A_Basic_Set_Operations) The double complement property states that (A^c)^c = A. To see this, suppose x \in (A^c)^c; then x \notin A^c, so x \in A. Conversely, if x \in A, then x \notin A^c, hence x \in (A^c)^c. This involution confirms the complement's reversibility.^[18] While complements are typically defined relative to a universal set U, in broader set-theoretic contexts, they can be considered relative to another set without invoking a global U, aligning with the relative complement operation and avoiding assumptions about a fixed universe.^[18]

Fundamental Properties

Properties of Union and Intersection

The union and intersection operations on sets exhibit several fundamental algebraic properties that establish them as binary operations forming semigroups on the power set of a universal set. These properties include commutativity, associativity, and idempotence, along with the existence of identity elements, which parallel the behaviors of addition and multiplication in arithmetic but are verified through element membership arguments.^[19] Commutativity states that the order of operands does not affect the result for both operations. For union, A \cup B = B \cup A. To prove this, consider an arbitrary element x. If x \in A \cup B, then x \in A or x \in B by definition of union, which implies x \in B \cup A since the disjunction is symmetric. Thus, A \cup B \subseteq B \cup A. The reverse inclusion follows similarly, establishing equality.^[19] For intersection, A \cap B = B \cap A. If x \in A \cap B, then x \in A and x \in B, so x \in B \cap A. The reverse holds by symmetry, proving equality.^[20] Associativity allows arbitrary parenthesization without changing the outcome. For union, (A \cup B) \cup C = A \cup (B \cup C). Let x \in (A \cup B) \cup C; then x \in A \cup B or x \in C. If x \in A \cup B, then x \in A or x \in B, so x \in A \cup (B \cup C). If x \in C, then x \in B \cup C, hence x \in A \cup (B \cup C). Thus, (A \cup B) \cup C \subseteq A \cup (B \cup C). The reverse inclusion follows analogously, proving equality.^[19] Similarly, for intersection, (A \cap B) \cap C = A \cap (B \cap C). If x \in (A \cap B) \cap C, then x \in A \cap B and x \in C, so x \in A and x \in B, and x \in C, implying x \in A and x \in B \cap C, hence x \in A \cap (B \cap C). The converse holds by symmetry.^[20] These proofs justify omitting parentheses in expressions involving only unions or only intersections. Idempotence means applying the operation to a set with itself yields the original set. For union, A \cup A = A. If x \in A \cup A, then x \in A or x \in A, so x \in A. Conversely, since A \subseteq A \cup A, equality holds. For example, if A = \{1, 2\}, then A \cup A = \{1, 2\} = A.^[19] For intersection, A \cap A = A. If x \in A \cap A, then x \in A and x \in A, so x \in A. The reverse inclusion is immediate. Using the same example, A \cap A = \{1, 2\} = A.^[21] The identity elements are the empty set \emptyset for union and the universal set U for intersection. For union, A \cup \emptyset = A. If x \in A \cup \emptyset, then x \in A or x \in \emptyset; since no element is in \emptyset, x \in A. Conversely, A \subseteq A \cup \emptyset. For intersection, A \cap U = A. If x \in A \cap U, then x \in A and x \in U; since every element is in U, x \in A. The reverse holds as A \subseteq U.^[19] Unlike union and intersection, not all set operations are associative; for instance, set difference is not. Consider A = \{1, 2, 3\}, B = \{2\}, C = \{3\}. Then (A - B) - C = (\{1, 3\}) - \{3\} = \{1\}, but A - (B - C) = \{1, 2, 3\} - \emptyset = \{1, 2, 3\}, showing inequality.^[22]

Properties of Complement

The complement operation in set algebra exhibits several key properties that highlight its role as a unary inverse-like function relative to the universal set U. One fundamental property is its involution nature, meaning that applying the complement twice returns the original set. Specifically, for any set A \subseteq U, (A^c)^c = A.^[2] This can be proven using element membership: let x \in (A^c)^c; then x \notin A^c, which means x \in A. Conversely, if x \in A, then x \notin A^c, so x \in (A^c)^c. Thus, the sets are equal by mutual containment.^[19] The complement also interacts distinctly with the identity elements of set algebra, namely the empty set \emptyset and the universal set U. The complement of the empty set is the universal set: \emptyset^c = U. To see this, consider any x \in U; since x \notin \emptyset by definition of the empty set, x \in \emptyset^c. Conversely, any x \in \emptyset^c must be in U but not in \emptyset, so x \in U. Similarly, the complement of the universal set is the empty set: U^c = \emptyset. For any x \in U^c, x \notin U, but since all elements under consideration are in U, no such x exists, hence U^c = \emptyset.^[23]^[24] These properties extend to interactions with binary operations, where the complement of a union, for instance, relates to the intersection of individual complements, providing a foundation for further algebraic manipulations. Additionally, the dominance relations A \cup U = U and A \cap \emptyset = \emptyset are inherently tied to the complement, as U = A \cup A^c implies A \cup U = U, and \emptyset = A \cap A^c implies A \cap \emptyset = \emptyset.^[19] Regarding fixed points of the complement operator—sets A such that A = A^c—no such non-trivial sets exist in a universe U with at least one element. Suppose A = A^c; then A \subseteq A^c, so A \cap A^c = A = \emptyset, implying A = \emptyset. But \emptyset^c = U, so \emptyset = U, which requires the trivial empty universe. Thus, fixed points are impossible in finite non-empty universes, adding to the operation's unique algebraic character.^[19]

Principle of Duality

The principle of duality in the algebra of sets asserts that every valid identity or theorem involving unions, intersections, the empty set, and the universal set has a corresponding dual statement obtained by interchanging the roles of union (∪) and intersection (∩), as well as the empty set (∅) and the universal set (U), while preserving the structure of complements if present. Formally, if a statement S(∪, ∩, ∅, U) holds true, then its dual S(∩, ∪, U, ∅)—where the operations and constants are swapped—also holds true. This symmetry arises from the complementary nature of the operations within the Boolean structure of set algebra.^[25] An illustrative application of this principle is the identity A \cup \emptyset = A, which states that the union of any set A with the empty set yields A itself. The dual statement, obtained by replacing ∪ with ∩ and ∅ with U, is A \cap U = A, affirming that the intersection of A with the universal set U also results in A. Such dual pairs demonstrate how the principle generates equivalent theorems without additional proof, leveraging the foundational symmetries of set operations.^[25] In proofs and derivations within set algebra, the principle of duality plays a crucial role by simplifying the verification of symmetric laws, such as those for associativity or commutativity, where establishing one form automatically validates its counterpart through duality. This reduces redundancy in axiomatic developments and highlights the balanced structure of the algebra, allowing mathematicians to focus on one side of a dual pair while inferring the other. For instance, proving properties for unions often directly implies the corresponding intersection properties via duality, streamlining complex arguments in Boolean algebras.^[26] The origins of the duality principle trace back to George Boole's foundational work in symbolic logic, where he identified symmetric dualities between disjunctive and conjunctive forms in his 1854 treatise An Investigation of the Laws of Thought. This concept was later formalized and emphasized in set-theoretic contexts by Edward V. Huntington in his 1904 paper "Sets of Independent Postulates for the Algebra of Logic," where he explicitly used duality to derive theorems from axiomatic bases, establishing it as a core tool in the abstract treatment of Boolean structures.^[26]

Additional Laws

Distributive and Absorption Laws

The distributive laws in set algebra assert that union distributes over intersection and intersection distributes over union. Specifically, for any sets A, B, and C,

A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

and its dual,

A \cap (B \cup C) = (A \cap B) \cup (A \cap C).

These laws reflect the lattice structure of the power set under inclusion, where union and intersection act analogously to join and meet operations.^[27]^[28] To prove the first distributive law using element membership, suppose x \in A \cup (B \cap C). Then either x \in A, in which case x \in A \cup B and x \in A \cup C, so x \in (A \cup B) \cap (A \cup C); or x \in B \cap C, so x \in B \subseteq A \cup B and x \in C \subseteq A \cup C, hence x \in (A \cup B) \cap (A \cup C). Conversely, if x \in (A \cup B) \cap (A \cup C), then x \in A \cup B and x \in A \cup C. If x \in A, then x \in A \cup (B \cap C); otherwise, x \in B and x \in C, so x \in B \cap C \subseteq A \cup (B \cap C). The dual proof follows by symmetry or by applying De Morgan's laws to complements, though it can be shown directly via similar element chasing.^[27]^[29]^[28] These laws can also be verified visually using Venn diagrams, which shade the regions corresponding to each side of the equation and confirm identical coverage. For A \cup (B \cap C), the diagram shades all of A plus the overlap of B and C; the right side shades the intersections of the unions, yielding the same regions without gaps or overlaps. The dual holds similarly by reflecting the diagram across the operations.^[27]^[24] The absorption laws simplify expressions involving a set with its combination under union or intersection: A \cup (A \cap B) = A and A \cap (A \cup B) = A. These follow from the monotonicity of set operations and subset relations. To prove A \cup (A \cap B) = A, note that A \cap B \subseteq A, so A \cup (A \cap B) \subseteq A \cup A = A; conversely, A \subseteq A \cup (A \cap B) by definition of union. The dual proof uses A \cup B \supseteq A, so A \cap (A \cup B) \supseteq A \cap A = A, and A \cap (A \cup B) \subseteq A. For example, let A = \{1, 2\} and B = \{2, 3\}; then A \cap B = \{2\}, and A \cup \{2\} = \{1, 2\} = A.^[19]^[30]^[2] While union and intersection distribute over each other, other operations like set difference (relative complement) do not exhibit similar distributivity. For instance, union does not distribute over set difference: A \cup (B \setminus C) \neq (A \cup B) \setminus (A \cup C) in general. Consider A = \{1\}, B = \{2\}, C = \{3\} in the universe \{1,2,3,4\}; the left side is \{1\} \cup (\{2\} \setminus \{3\}) = \{1,2\}, while the right side is (\{1,2\} \setminus \{1,3\}) = \{2\}. This failure arises because set difference involves complements in a non-symmetric way relative to union.^[24]^[2] Set algebra under symmetric difference and intersection forms a Boolean ring, where these operations satisfy ring axioms including distributivity, connecting set operations to abstract algebraic structures.^[31]^[32]

De Morgan's Laws

De Morgan's laws are fundamental identities in the algebra of sets that relate the complement operation to unions and intersections. These laws state that the complement of the union of two sets is equal to the intersection of their complements, and the complement of the intersection of two sets is equal to the union of their complements. Formally, for sets A and B within a universal set U,

(A \cup B)^c = A^c \cap B^c

(A \cap B)^c = A^c \cup B^c

These identities were named after the British mathematician Augustus De Morgan, who introduced them in his 1847 book Formal Logic. Their formulation was influenced by the algebraic approach to logic developed contemporaneously by George Boole.^[8]^[33] The proofs of De Morgan's laws rely on the definition of set membership and complement. For the first law, consider an element x \in U. Then x \in (A \cup B)^c if and only if x \notin A \cup B, which means x \notin A and x \notin B. This is equivalent to x \in A^c and x \in B^c, so x \in A^c \cap B^c. Thus, (A \cup B)^c = A^c \cap B^c. Similarly, for the second law, x \in (A \cap B)^c if and only if x \notin A \cap B, which means x \notin A or x \notin B. This is equivalent to x \in A^c \cup B^c.^[34]^[35] To illustrate the second law, suppose U = \{1, 2, 3\}, A = \{1, 2\}, and B = \{2, 3\}. Then A \cap B = \{2\}, so (A \cap B)^c = \{1, 3\}. Also, A^c = \{3\} and B^c = \{1\}, so A^c \cup B^c = \{1, 3\}.^[34] De Morgan's laws extend naturally to infinite collections of sets. For an indexed family \{A_i \mid i \in I\}, where I is any index set,

\left( \bigcup_{i \in I} A_i \right)^c = \bigcap_{i \in I} A_i^c

\left( \bigcap_{i \in I} A_i \right)^c = \bigcup_{i \in I} A_i^c

The proofs follow analogously: for the first, an element in the complement of the union lies outside every A_i, hence in every A_i^c, and thus in their intersection. The second follows by applying the first to the complements.^[34] These laws are essential for simplifying complex set expressions involving complements. For example, to simplify (A \cup (B \cap C))^c, apply the first law to get A^c \cap (B \cap C)^c, then the second law to (B \cap C)^c yields A^c \cap (B^c \cup C^c). This symmetry reflects the principle of duality in set algebra, where unions and intersections interchange under complementation.^[34]^[35]

Set Relations and Algebras

Algebra of Inclusion

In the algebra of sets, inclusion establishes a fundamental partial order on the collection of subsets of a given universal set U. A subset A \subseteq U is included in another subset B \subseteq U, written A \subseteq B, if every element belonging to A also belongs to B; formally, this is expressed as \forall x (x \in A \to x \in B).^[36] This definition ensures reflexivity (A \subseteq A), antisymmetry (if A \subseteq B and B \subseteq A, then A = B), and transitivity (if A \subseteq B and B \subseteq C, then A \subseteq C), confirming that \subseteq is a partial order on the power set \mathcal{P}(U).^[37] An equivalent formulation of inclusion is that A \cap B = A, since the intersection retains all elements of A precisely when no elements of A lie outside B.^[38] The power set \mathcal{P}(U), comprising all subsets of U, inherits this partial order to form a complete distributive lattice known as the Boolean lattice. In this structure, the meet operation corresponds to set intersection \cap, which yields the greatest lower bound of any two subsets (the largest set contained in both), while the join corresponds to set union \cup, providing the least upper bound (the smallest set containing both).^[39] The empty set \emptyset serves as the bottom element, being included in every subset of U, and U itself acts as the top element, containing every subset.^[40] This lattice framework unifies inclusion with the core set operations, enabling the analysis of subsets as elements in an ordered algebraic system.^[36] Inclusion induces monotonicity in the lattice operations, preserving the order structure. Specifically, if A \subseteq B, then for any subset C \subseteq U, it follows that A \cup C \subseteq B \cup C (since any element in A \cup C is either in C or in A, hence also in B \cup C) and A \cap C \subseteq B \cap C (since any element in A \cap C is in both A and C, thus in both B and C).^[41] These properties ensure that union and intersection act as order-preserving (monotone) maps on \mathcal{P}(U), facilitating proofs of more complex relations within the algebra.^[36] Within the partially ordered power set, chains and antichains highlight the order's structure. A chain is a totally ordered subset of \mathcal{P}(U) under \subseteq, where every pair of distinct elements is comparable—forming a nested sequence like \emptyset \subset \{1\} \subset \{1,2\} \subset U for U = \{1,2,3\}.^[42] In contrast, an antichain consists of pairwise incomparable elements, such as the collection of all singletons \{\{1\}, \{2\}, \{3\}\}, where no set contains another.^[42] These concepts quantify comparability in the lattice, with Dilworth's theorem relating the size of the largest antichain to the minimum number of chains needed to cover \mathcal{P}(U).^[42] Hasse diagrams offer a concise visualization of the inclusion order in small power sets, omitting transitive edges to emphasize immediate inclusions. For the power set of a singleton U = \{a\}, the diagram features two levels: \emptyset at the bottom directly connected upward to \{a\} at the top, illustrating the minimal nontrivial lattice. For U = \{a,b\}, the diagram expands to four elements across three levels—\emptyset at the base connected to both \{a\} and \{b\} in the middle level, each of which connects to \{a,b\} at the apex—revealing the diamond-shaped structure of the Boolean lattice $2^2.^[43] Such diagrams underscore the graded nature of the power set lattice, where the rank of a subset equals its cardinality.^[43]

Algebra of Relative Complements

The relative complement, or set difference, operation in set algebra is defined as A \setminus B = A \cap B^c, where B^c denotes the complement of B with respect to the universal set U. This operation forms part of the Boolean algebra structure on sets, allowing for the construction of expressions involving exclusions, though it lacks certain algebraic properties like associativity. Unlike union and intersection, which are associative, the set difference is non-associative in general, meaning (A \setminus B) \setminus C \neq A \setminus (B \setminus C) for arbitrary sets A, B, and C. For instance, consider A = \{1,2\}, B = \{2\}, and C = \{1\}; then (A \setminus B) \setminus C = \{1\} \setminus \{1\} = \emptyset, while A \setminus (B \setminus C) = \{1,2\} \setminus \{2\} = \{1\}. Several fundamental identities govern the behavior of the relative complement operation. Notably, A \setminus A = \emptyset for any set A, as no element can be in A and excluded from itself simultaneously. Similarly, A \setminus \emptyset = A, since excluding the empty set removes nothing from A. Additionally, A \setminus U = \emptyset, because every element of A is contained in the universal set U and thus excluded entirely. The relative complement relates closely to the symmetric difference operation, defined as A \Delta B = (A \setminus B) \cup (B \setminus A), which captures elements unique to either set. This equivalence highlights how set differences can reconstruct the symmetric difference, a key operation in Boolean rings and topology. For example, with A = \{1,2,3\} and B = \{2,3,4\}, A \setminus B = \{1\} and B \setminus A = \{4\}, so A \Delta B = \{1,4\}. Under the assumption of inclusion, modular laws emerge for set differences, providing tools for simplifying nested exclusions. Specifically, if A \subseteq C, then C \setminus (A \setminus B) = (C \setminus A) \cup (A \cap B). To prove this, note that A \setminus B = A \cap B^c, so C \setminus (A \cap B^c) = C \cap (A \cap B^c)^c = C \cap (A^c \cup B) by De Morgan's laws. Since A \subseteq C, C \cap A^c = C \setminus A, and C \cap B = (C \setminus A) \cap B \cup A \cap B \subseteq (C \setminus A) \cup (A \cap B); expanding fully yields C \cap (A^c \cup B) = (C \cap A^c) \cup (C \cap B) = (C \setminus A) \cup (A \cap B), as C \cap B = (C \setminus A) \cap B \cup A \cap B and the first term absorbs into the union. These identities find practical application in relational algebra for database queries, where set difference corresponds to the EXCEPT operator, enabling the retrieval of tuples present in one relation but absent in another, such as identifying unique customers in one table excluding those in a subscription list. This use underscores the operation's role in data filtering and comparison, extending set-theoretic principles to computational efficiency in query optimization.

References

[1]
[PDF] A Little Set Theory (Never Hurt Anybody)
The fundamental ideas of set theory and the algebra of sets are probably the most important concepts across all areas of mathematics other than the algebra ...
[2]
Sets:Operations - Department of Mathematics at UTSA
Feb 4, 2022 · The algebra of sets is the set-theoretic analogue of the algebra of numbers. Just as arithmetic addition and multiplication are associative and ...Missing: definition | Show results with:definition
[3]
[PDF] Set Theory - ScholarWorks@GVSU
In Section 5.3, we studied certain properties of set union, set intersection, and set complements, which we called the algebra of sets. We will now begin some-.
[4]
Set Theory - Stanford Encyclopedia of Philosophy
Oct 8, 2014 · Set theory is the mathematical theory of well-determined collections, called sets, of objects that are called members, or elements, of the set.
[5]
The Mathematics of Boolean Algebra
Jul 5, 2002 · Boolean algebra is the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and ...
[6]
Comprehensive List of Set Theory Symbols | Math Vault
A comprehensive collection of the most notable symbols in set theory, categorized by function into tables along with each symbol's meaning and example.
[7]
Meaning, Symbol, Examples | Cardinality of a Set - Cuemath
The cardinality of a set means the number of elements in it. For any set A, its cardinality is denoted by n(A) or |A|. But for infinite sets: The cardinality is ...
[8]
The Algebra of Logic Tradition - Stanford Encyclopedia of Philosophy
Mar 2, 2009 · The algebra of logic, as an explicit algebraic system showing the underlying mathematical structure of logic, was introduced by George Boole (1815–1864)
[9]
The Mathematical Origins of Nineteenth-Century Algebra of Logic
Special emphasis will be laid on the systems of George Boole (1815–1864) and above all of his German follower Ernst Schröder (1841–1902). Keywords: symbolic ...
[10]
1.4: Set Operations with Two Sets - Mathematics LibreTexts
Jan 2, 2025 · In this section, we will explore the operations of union and intersection as it relates to two sets.
[11]
10.2: Union, Intersection, and Complement - Mathematics LibreTexts
Sep 27, 2020 · The intersection of two sets contains only the elements that are in both sets. ... The union contains all the elements in either set: A ⋃ B = {red ...Union, Intersection, and... · Example 5
[12]
4.3: Set Operations - Mathematics LibreTexts
Sep 5, 2021 · The logical connectors ∧ and ∨ correspond to the set-theoretic notions of union ( ∪ ) and intersection ( ∩ ) . The symbols are designed to ...<|control11|><|separator|>
[13]
1.2: Operations with Sets - Mathematics LibreTexts
Dec 12, 2024 · Union and Intersection. The union of two sets contains all the elements contained in either (or both) sets. A Venn diagram shows the union of ...
[14]
1.2: Venn Diagrams - Mathematics LibreTexts
Jan 13, 2025 · To find the intersection of two sets, you might try shading one region in a given direction, and another region in a different direction. Then ...
[15]
1.6: Sequences - Mathematics LibreTexts
Jun 8, 2022 · In calculus we think of a sequence as a (possibly infinite) list of objects. We shall expand on that idea somewhat, and express it in the language of functions.
[16]
8.2: Mutually Exclusive Events and the Addition Rule - Math LibreTexts
Jul 17, 2022 · The union of two events E and F, E ∪ F, is the set of outcomes that are in E or in F or in both. · The intersection of two events E and F, E ∩ F, ...
[17]
[PDF] Naive set theory. - Whitman People
A more important way in which the naive point of view predominates is that set theory is regarded as a body of facts, of.Missing: universal | Show results with:universal
[18]
[PDF] CMSC 250: Set Theory and Proofs - UMD MATH
Mar 13, 2023 · We say that two sets A and B are equal and write A = B if they have exactly the same elements. More specifically A = B iff A ⊆ B and. B ⊆ A. D.
[19]
[PDF] Set Theory - Stony Brook Computer Science
Algebraic proofs of set identities. Algebraic proofs = Use of laws to prove new identities. Commutativity: A ∪ B = B ∪A and A ∩ B = B ∩A. Associativity ...
[20]
[PDF] Chapter 3 Set Theory - The University of Arizona
Commutativity expresses that the order of arguments is irrelevant for union and intersection. (3.10) Commutativity. X ∪ Y = Y ∪ X. X ∩ Y = Y ∩ X.
[21]
Sets
... set difference (−) is neither commutative nor associative: Property, Explanation. − is not commutative, X−Y ≠Y−X for some X and Y. − is not associative, (X ...
[22]
Geneseo Math 239 01 Set Operations - SUNY Geneseo
A conjecture coming out of our discussion of complement: if U is the universal set, then ∅C = U. Proof strategy: show that every element of ∅C is in ...<|separator|>
[23]
4.2 Laws of Set Theory
Basic set laws include Commutative, Associative, Distributive, Identity, Complement, Idempotent, Null, Absorption, DeMorgan’s, and Involution laws.
[24]
4.4: The Duality Principle - Mathematics LibreTexts
Aug 16, 2021 · It gives us a whole second set of identities, theorems, and concepts. For example, we can consider the dual of minsets and minset normal form.
[25]
Sets of Independent Postulates for the Algebra of Logic - jstor
* Theorems 21b, 22b, and 23b may also be inferred directly from 21a, 22a, and 23a, by the aid of the principle of duality established in 20a and 20b. Page 13 ...
[26]
Real Analysis: Proposition 1.1.3: Distributive Law for Sets
Proof: · If x is in A, then x is also in A union (B intersect C). · If x is in B, then it must also be in C. Hence, x is in B intersect C, and therefore it is in ...
[27]
[PDF] Review of Set Theory - UCSB Math
Mar 30, 2009 · As long as the set operations are all unions or all intersection, there is no trouble with moving parentheses (i.e. we have associativity).
[28]
[PDF] Theorem 1.2.A. Distributive Laws
Aug 7, 2019 · For any sets (events) A, B, and C we have. An (BUC) = (ANB) U (ANC) and AU (CNC) = (AUB) N (AUC). These are the distributive laws. Proof. We ...Missing: algebra | Show results with:algebra
[29]
[PDF] Set Theory - Stony Brook Computer Science
The difference of B minus A (relative complement of A in B): B−A (or B\A) is the set of all elements that are in B and not A.
[30]
[PDF] Lecture 7: Set Theory and Logic - Harvard Mathematics Department
One can calculate with sets as with numbers. They form a ”Boolean ring”. Addition: A + B = A∆B with the zero element ∅. Multiplication: A · ...
[31]
[PDF] Boolean rings and Boolean algebra - MIT Mathematics
Any Boolean algebra gives rise to a Boolean ring as follows. Define the operation ∨ (same as “or” or “union”) on {0,1} as the ones used in a truth table in ...
[32]
Formal logic (1847) : De Morgan, Augustus, 1806-1871
Aug 9, 2019 · Formal logic (1847) : De Morgan, Augustus, 1806-1871 : Free Download, Borrow, and Streaming : Internet Archive.Missing: source | Show results with:source
[33]
de Morgan's laws for sets (proof) - PlanetMath.org
Mar 22, 2013 · Namely, we show that S⊂T S ⊂ T and T⊂S T ⊂ S . For the first claim, suppose x x is an element in S S . Then x∉∪i∈IAi x ∉ ∪ i ∈ I A i , so x∉Ai x ...
[34]
https://planetmath.org/demorganslawsforsetsproof
[35]
[PDF] Introduction to Lattices and Order
Definition. Let X be any set. The powerset P(X) consists of all subsets of X. It is ordered by set inclusion: For A,B ∈ P(X), we define A ≤ B if and only if.
[36]
[PDF] Math 2513: About “Element-wise Proofs” in Set Theory
An “element-wise proof” is a method for showing that one set is a subset of another set. This is the most convincing technique to use for proving subset ...
[37]
[PDF] Sets and Set Operations - University at Buffalo
The complement of set A, denoted by A, is the set that contains exactly all the elements that are not in A. Formally, A = {x | x 6∈ A}. Suppose U is the ...
[38]
[PDF] Preliminary Notes on Lattices 1 Partially ordered sets - P.J. Healy
The power set P(X) is a lattice under set inclusion ⊃. Indeed A∨B = A ∪ B ... It is a lattice under set inclusion, where the join of two sets is ...
[39]
[PDF] Lattice theory - Stanford Concurrency Group
The power set of a set, ordered by inclusion, forms an upper semilattice with ∨ as union, and a lower semilattice with ∧ as intersection. 3. The set of all ...
[40]
[PDF] B1.2 Set Theory - People
H : P(X) → P(X) is monotone if A ⊆ B implies H(A) ⊆ H(B) (for. A, B ⊆ X) ... Also A ⊆ C, so H(A) ⊆ H(C) by monotonicity. So A ⊆ H(C). • H(C) ⊆ C ...
[41]
[PDF] Chains and Antichains
Suppose P = C1 ∪⋯∪ Ck, where Ci is a chain. Let A be any antichain. Since #(Ci ∩ A) ≤ 1, we have k ≥ #A. Thus: Proposition. Let k be the least integer such ...
[42]
Hasse Diagram of Power Sets - Wolfram Demonstrations Project
The power set of a set A is the set of all subsets of A. The power set can be ordered to obtain a distributive lattice bounded by A and the empty set.