Algebra of Sets and Cardinality Results

Algebra of Sets (Properties of Union and Intersection)

Just as arithmetic operations on numbers follow certain rules and properties (like the commutative property of addition or the distributive property of multiplication over addition), set operations also adhere to a set of laws. These laws form the basis of the Algebra of Sets and are essential for simplifying expressions involving set operations and proving set identities.

Let $A$, $B$, and $C$ be any sets considered as subsets of a universal set $U$. The following are the fundamental algebraic laws governing the union ($\cup$) and intersection ($\cap$) operations:

Fundamental Laws of Set Algebra

1. Commutative Laws:

   The order of the sets does not matter in the union or intersection operation.
   • For Union:

     $A \cup B = B \cup A$

   • For Intersection:

     $A \cap B = B \cap A$

2. Associative Laws:

   When performing the same operation (either union or intersection) on three or more sets, the way the sets are grouped does not affect the final result.
   • For Union:

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

   • For Intersection:

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

   Because of the associative laws, we can write $A \cup B \cup C$ and $A \cap B \cap C$ without using parentheses, as the result is the same regardless of grouping.

3. Identity Laws (or Identity Element Laws):

   There are identity elements for both union and intersection operations.
   • The empty set $\emptyset$ is the identity element for union: The union of any set $A$ with the empty set is $A$ itself.

     $A \cup \emptyset = A$

   • The universal set $U$ is the identity element for intersection: The intersection of any set $A$ with the universal set is $A$ itself.

     $A \cap U = A$

4. Idempotent Laws:

   Performing a set operation with the same set does not change the set.
   • For Union:

     $A \cup A = A$

   • For Intersection:

     $A \cap A = A$

5. Domination Laws (Laws of $\emptyset$ and $U$):

   These laws show how the empty set and the universal set behave with respect to union and intersection when they are not acting as identities.
   • The universal set $U$ dominates in union: The union of any set $A$ with the universal set $U$ is always $U$.

     $A \cup U = U$

   • The empty set $\emptyset$ dominates in intersection: The intersection of any set $A$ with the empty set $\emptyset$ is always $\emptyset$.

     $A \cap \emptyset = \emptyset$

6. Distributive Laws:

   These laws describe how union and intersection operations interact when mixed. One operation distributes over the other.
   • Intersection distributes over Union:

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

     ... (1)

   • Union distributes over Intersection:

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

     ... (2)

   These laws are analogous to the distributive law in arithmetic ($a \times (b + c) = (a \times b) + (a \times c)$), but in set theory, both intersection over union and union over intersection hold.

---

Proof of Distributive Law: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

To prove that two sets are equal, we must show that every element of the first set is in the second set (first set is a subset of the second), and every element of the second set is in the first set (second set is a subset of the first).

Part 1: Show $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$

Let $x$ be an arbitrary element belonging to the set $A \cap (B \cup C)$.

By the definition of intersection, this means $x$ is in $A$ AND $x$ is in the union of $B$ and $C$.

By the definition of union, $x \in (B \cup C)$ means $x$ is in $B$ OR $x$ is in $C$.

Combining (i) and (ii), we have ($x \in A$) AND ($x \in B$ OR $x \in C$). We can distribute the "AND $x \in A$" over the "OR" condition:

By the definition of intersection, ($x \in A$ and $x \in B$) means $x \in (A \cap B)$.

Similarly, ($x \in A$ and $x \in C$) means $x \in (A \cap C)$.

Substituting (iv) and (v) back into (iii), we get:

By the definition of union, (vi) means $x \in (A \cap B) \cup (A \cap C)$.

Thus, starting with $x \in A \cap (B \cup C)$ and logically arriving at $x \in (A \cap B) \cup (A \cap C)$, we conclude that $A \cap (B \cup C)$ is a subset of $(A \cap B) \cup (A \cap C)$.

Part 2: Show $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$

Let $y$ be an arbitrary element belonging to the set $(A \cap B) \cup (A \cap C)$.

By the definition of union, this means $y$ is in $(A \cap B)$ OR $y$ is in $(A \cap C)$.

By the definition of intersection, $y \in (A \cap B)$ means $y \in A$ and $y \in B$.

By the definition of intersection, $y \in (A \cap C)$ means $y \in A$ and $y \in C$.

From (x) and (xi), in either case ($y \in (A \cap B)$ or $y \in (A \cap C)$), $y$ must be in $A$.

Also, from (x), if $y \in (A \cap B)$, then $y \in B$. From (xi), if $y \in (A \cap C)$, then $y \in C$. So, based on (ix), $y$ is in $B$ OR $y$ is in $C$.

By the definition of union, (xiii) means $y \in (B \cup C)$.

From (xii) and (xiv), we have $y \in A$ AND $y \in (B \cup C)$. By the definition of intersection, this means $y \in A \cap (B \cup C)$.

Thus, starting with $y \in (A \cap B) \cup (A \cap C)$ and logically arriving at $y \in A \cap (B \cup C)$, we conclude that $(A \cap B) \cup (A \cap C)$ is a subset of $A \cap (B \cup C)$.

From (viii) and (xvi), since each set is a subset of the other, they must be equal.

The proof of the second distributive law $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ follows a similar logical structure, using the definitions of union and intersection and the logical connectives 'or' and 'and'.

De Morgan's Laws

De Morgan's laws are two important set identities that relate the operations of union, intersection, and complementation. They show how the complement of a union or intersection can be expressed in terms of the complements of the individual sets.

Let $A$ and $B$ be subsets of a universal set $U$.

De Morgan's First Law

The complement of the union of two sets is equal to the intersection of their complements.

In words: "Not (A or B)" is the same as "(Not A) and (Not B)".

De Morgan's Second Law

The complement of the intersection of two sets is equal to the union of their complements.

In words: "Not (A and B)" is the same as "(Not A) or (Not B)".

These laws can be extended to more than two sets.

---

Proof of De Morgan's First Law: $(A \cup B)' = A' \cap B'$

We prove this equality by showing mutual containment: $(A \cup B)' \subseteq A' \cap B'$ and $A' \cap B' \subseteq (A \cup B)'$.

Part 1: Show $(A \cup B)' \subseteq A' \cap B'$

Let $x$ be an arbitrary element such that $x \in (A \cup B)'$.

By the definition of complement, $x$ belongs to the universal set $U$ and $x$ does not belong to the union $A \cup B$.

If an element $x$ is not in the union of $A$ and $B$, it means $x$ is neither in $A$ nor in $B$.

From (a) and (b), we have $x \in U$ and $x \notin A$, which by the definition of complement means $x \in A'$.

Also from (a) and (b), we have $x \in U$ and $x \notin B$, which by the definition of complement means $x \in B'$.

From (c) and (d), since $x$ is in $A'$ and $x$ is in $B'$, by the definition of intersection, $x$ is in $A' \cap B'$.

Therefore, if $x \in (A \cup B)'$, then $x \in A' \cap B'$. This shows that $(A \cup B)'$ is a subset of $A' \cap B'$.

Part 2: Show $A' \cap B' \subseteq (A \cup B)'$

Let $y$ be an arbitrary element such that $y \in A' \cap B'$.

By the definition of intersection, $y$ is in $A'$ AND $y$ is in $B'$.

By the definition of complement, $y \in A'$ means $y \in U$ and $y \notin A$.

And $y \in B'$ means $y \in U$ and $y \notin B$.

From (i) and (j), since $y$ is not in $A$ and $y$ is not in $B$, $y$ cannot be in their union $A \cup B$.

Also from (h), $y$ must be in the universal set $U$ (since it's in both $A'$ and $B'$).

From (k) and (l), by the definition of complement, $y$ is in the complement of $A \cup B$.

Therefore, if $y \in A' \cap B'$, then $y \in (A \cup B)'$. This shows that $A' \cap B'$ is a subset of $(A \cup B)'$.

Since we have shown both containment relationships [from (f) and (n)], the two sets must be equal.

The proof for De Morgan's Second Law $(A \cap B)' = A' \cup B'$ follows a similar structure, using the definitions of union, intersection, and complement, and the logical equivalences between "not (P and Q)" and "(not P) or (not Q)".

---

Answer:

---

Some Basic Results about Cardinal Number of Sets (Inclusion-Exclusion Principle)

Beyond the algebraic manipulation of sets, we are often interested in the number of elements in sets resulting from set operations. The Principle of Inclusion-Exclusion and related formulas provide ways to calculate the cardinal numbers of combined sets based on the cardinal numbers of the original sets and their intersections.

Cardinality of Union

For any two finite sets $A$ and $B$, the number of elements in their union ($|A \cup B|$) is given by the sum of the number of elements in $A$ and $B$, minus the number of elements in their intersection ($|A \cap B|$).

Derivation and Explanation:

Consider the elements in $A \cup B$. These are the elements that are in $A$ or in $B$ or in both.

When we simply add $|A|$ and $|B|$, the elements that are in both $A$ and $B$ (i.e., the elements in $A \cap B$) are counted twice: once as members of $A$ and once as members of $B$.

To correct for this double counting, we must subtract the number of elements in the intersection $|A \cap B|$ exactly once.

(Imagine a Venn diagram with two overlapping circles A and B. Shade A completely, then shade B completely. The overlap region is shaded twice. The formula $|A| + |B| - |A \cap B|$ corresponds to (Area of A) + (Area of B) - (Area of Overlap)).

If sets A and B are disjoint, they have no elements in common. Their intersection is the empty set, $A \cap B = \emptyset$, so the number of elements in their intersection is $|A \cap B| = 0$. In this special case, the formula simplifies to:

For any three finite sets $A$, $B$, and $C$, the Principle of Inclusion-Exclusion extends as follows:

Explanation for Three Sets:

When we sum $|A| + |B| + |C|$:

• Elements in only one set are counted once.
• Elements in exactly two sets (e.g., in $A \cap B$ but not C) are counted twice (e.g., in $|A|$ and $|B|$).
• Elements in all three sets (in $A \cap B \cap C$) are counted three times (in $|A|$, $|B|$, and $|C|$).

Subtracting $|A \cap B| + |A \cap C| + |B \cap C|$ corrects for the double counting:

• Elements in exactly two sets were counted twice, now subtracted once, so net count is 1.
• Elements in all three sets were counted three times, now subtracted three times (once in each pairwise intersection), so net count is 0.

We still need to count the elements in all three sets. So, we add back $|A \cap B \cap C|$ once.

The final formula gives the correct count of elements in the union of three sets.

---

Cardinality of Difference and Complement

Related formulas can be derived for the cardinality of set differences and complements based on the Principle of Inclusion-Exclusion or direct definition.

Let $A$ and $B$ be finite sets, and $U$ be a finite universal set containing $A$ and $B$ as subsets.

1. Cardinality of Difference:

   The set $A$ can be divided into two disjoint parts: elements in $A$ but not $B$ ($A-B$) and elements in both $A$ and $B$ ($A \cap B$). So, $A = (A - B) \cup (A \cap B)$ and $(A - B) \cap (A \cap B) = \emptyset$.

   Therefore, $|A| = |A - B| + |A \cap B|$. Rearranging gives:

   $\mathbf{|A - B| = |A| - |A \cap B|}$

   Similarly, $|B - A| = |B| - |A \cap B|$.

   Using $|A \cup B| = |A - B| + |B - A| + |A \cap B|$, we can also derive:

   $|A - B| = |A \cup B| - |B|$

   And $|B - A| = |A \cup B| - |A|$.

2. Cardinality of Complement:

   The universal set $U$ can be divided into two disjoint parts: elements in $A$ and elements not in $A$ (which is $A'$). So, $U = A \cup A'$ and $A \cap A' = \emptyset$.

   Therefore, $|U| = |A \cup A'| = |A| + |A'|$. Rearranging gives:

   $\mathbf{|A'| = |U| - |A|}$

   This formula is fundamental for calculating the number of elements outside a given set within a finite universal set.

3. Cardinality of Symmetric Difference:

   The symmetric difference $A \Delta B$ consists of elements in $A-B$ or $B-A$. Since $A-B$ and $B-A$ are disjoint, its cardinality is the sum of their cardinalities:

   $|A \Delta B| = |A - B| + |B - A|$

   Substituting $|A - B| = |A| - |A \cap B|$ and $|B - A| = |B| - |A \cap B|$:

   $|A \Delta B| = (|A| - |A \cap B|) + (|B| - |A \cap B|)$

   $|A \Delta B| = |A| + |B| - 2|A \cap B|$

   Alternatively, using the definition $A \Delta B = (A \cup B) - (A \cap B)$, and the difference formula $|S - T| = |S| - |S \cap T|$ (applied with $S = A \cup B$ and $T = A \cap B$), and noting that $(A \cup B) \cap (A \cap B) = A \cap B$:

   $|A \Delta B| = |A \cup B| - |A \cap B|$

   ... (Using $(A \cup B) \cap (A \cap B) = A \cap B$)

---

Answer:

---

Answer:

---

Answer:

Practical Problems on Sets (Word Problems)

Set theory concepts, particularly the formulas for cardinality derived from the Principle of Inclusion-Exclusion, are very useful in solving word problems involving overlapping groups or categories. These problems typically require finding the number of elements in unions, intersections, or differences of sets based on given information.

The standard approach to solving these problems involves:

1. Identifying the sets involved and assigning them symbols (e.g., A, B, C).
2. Identifying the universal set, if necessary, based on the total number of items/people in the context.
3. Translating the given information from the word problem into set notation using cardinality ($|A|$, $|A \cap B|$, $|A \cup B|$, $|A'|$, etc.).
4. Using the appropriate cardinality formulas (especially Inclusion-Exclusion for 2 or 3 sets, or complement formula) to find the required unknown quantities.
5. Drawing a Venn diagram can often help visualize the problem and verify the formulas being used.

---

Answer:

---

Practical Problems on Sets (Word Problems)

The theoretical concepts of set operations and their associated cardinality formulas are widely applied to solve real-world problems, often presented in the form of word problems. These problems typically involve surveying a group of individuals or items and determining the number of elements that fall into various overlapping categories. The Principle of Inclusion-Exclusion is the primary tool used here.

Systematic Approach to Solving Word Problems on Sets

Solving word problems involving sets can be streamlined by following a systematic approach:

1. Define Sets:

   Clearly identify the different categories or groups mentioned in the problem and assign a distinct capital letter (e.g., $A, B, C$) to represent each set. For instance, if a problem is about students studying different subjects, you might define S for Science students, M for Mathematics students, etc.

2. Identify the Universal Set:

   Determine the total number of items or people in the entire group being surveyed or considered. This total represents the cardinality of the universal set, $|U|$. The sets defined in step 1 are typically subsets of this universal set.

3. Translate Given Information into Set Notation:

   Carefully read the problem statement and convert the given numerical information into the language of sets and cardinalities.
   • "Total number of people/items" $\rightarrow |U|$
   • "Number who belong to category A" $\rightarrow |A|$
   • "Number who belong to category B" $\rightarrow |B|$
   • "Number who belong to both A and B" $\rightarrow |A \cap B|$
   • "Number who belong to A or B (or both)" or "at least one of A or B" $\rightarrow |A \cup B|$
   • "Number who belong to A but not B" or "only A" $\rightarrow |A - B|$
   • "Number who belong to neither A nor B" $\rightarrow |(A \cup B)'|$ or $|U| - |A \cup B|$
   • "Number who belong to exactly one of A or B" $\rightarrow |(A - B) \cup (B - A)|$ or $|A \Delta B|$
   Extend this to three sets as needed (e.g., $|A \cap B \cap C|$, $|(A \cup B \cup C)'|$, etc.).

4. Draw a Venn Diagram (Optional but Recommended):

   For problems involving two or three sets, sketching a Venn diagram is highly beneficial. Draw a rectangle for the universal set $U$ and overlapping circles for the sets involved. Use the translated information to fill in the cardinality of each disjoint region in the diagram. It's often easiest to start from the innermost intersection ($|A \cap B|$ or $|A \cap B \cap C|$) and work outwards. This visual representation helps organize the data and can sometimes directly reveal the answer or make the application of formulas clearer.

5. Choose and Apply Formula(s):

   Based on the given information and what needs to be found, select and apply the appropriate cardinality formulas, primarily the Principle of Inclusion-Exclusion for two or three sets. Formulas for set difference, complement, etc., may also be necessary.

6. Calculate:

   Perform the necessary calculations using the formulas and the given numbers.

7. State the Final Answer:

   Present the result clearly in the context of the original word problem, ensuring you answer the specific question asked.

---

Answer:

---

Answer:

---