Mathematics Foundations/1.2 Set Operations

Introduction Set operations allow us to combine and manipulate sets in various ways, creating new sets from existing ones. These operations form the foundation of set theory and have applications throughout mathematics and computer science. Basic Set Operations Union The union of two sets and , denoted by , is the set of all elements that belong to either or or both. Example: If and , then . The union operation can be extended to multiple sets. For a collection of sets , their union is denoted by: Intersection The intersection of two sets and , denoted by , is the set of all elements that belong to both and . Example: If and , then . If , then and are said to be disjoint. The intersection operation can be extended to multiple sets: Difference The difference of two sets A and B, denoted by (or sometimes ), is the set of all elements that belong to A but not to B. Example: If and , then . Note that in general, . In our example, . Symmetric Difference The symmetric difference of two sets and , denoted by (or sometimes ), is the set of elements that belong to either or but not to their intersection. Example: If and , then . The symmetric difference has several important properties: It is commutative: It is associative: The empty set is the identity element: Each set is its own inverse: Complement The complement of a set with respect to a universal set , denoted by (or sometimes or ), is the set of all elements in that are not in . Example: If and , then . Note that the complement of a set is always defined with respect to some universal set U, which must be specified or understood from the context. Properties of Set Operations Commutative Laws Associative Laws Distributive Laws Identity Laws Complement Laws De Morgan's Laws These laws can be extended to finite collections of sets: ​ ​ Absorption Laws Idempotent Laws Venn Diagrams Venn diagrams provide a visual representation of set operations. In these diagrams: Sets are represented as regions enclosed by simple closed curves (usually circles) The universal set is represented by a rectangle containing all the circles The intersection of sets is represented by the overlap of their corresponding regions Examples of Venn Diagrams is represented by the entire shaded region of both circles is represented by the overlap between the two circles is represented by the region in circle that does not overlap with circle is represented by the regions in either circle that do not overlap is represented by the region inside the rectangle but outside circle Power Sets The power set of a set , denoted by or , is the set of all subsets of , including the empty set and itself. Example: If , then: Properties of Power Sets If has elements, then has elements https://wikimedia.org/api/rest_v1/media/math/render/svg/b09068bd2f7ba899aeb883ebe670b2ad07b0c851 if and only if , with equality if and only if or for any set Cartesian Product The Cartesian product of two sets and , denoted by , is the set of all ordered pairs where and . Example: If and , then: The Cartesian product can be extended to multiple sets. For sets , their Cartesian product is: Properties of Cartesian Products in general (unless or one of them is empty) If has elements and has elements, then has elements for any set Applications of Set Operations Set operations have numerous applications across mathematics and computer science: Database Theory Union, intersection, and difference operations form the basis of relational algebra in database systems Queries in SQL use set operations to combine and filter data Boolean Algebra Set operations correspond to logical operations in Boolean algebra Union corresponds to logical OR Intersection corresponds to logical AND Complement corresponds to logical NOT Probability Theory Events in probability theory are represented as sets Union of events represents "either event occurs" Intersection of events represents "both events occur" Complement of an event represents "the event does not occur" Computer Science Set operations are fundamental in algorithms and data structures Bit manipulation often implements set operations efficiently Search algorithms frequently use set operations Exercises Let , , and . Find: Let , , and . Verify De Morgan's laws: If and , find: Prove that for any three sets , , and : Let . Find and . For sets , , and , prove or disprove: If and , prove that . Let , , and be sets. Prove that if and only if and .