Proofs of Some General Identities on Sets

Definition

A set identity is a statement that two expressions involving sets are equal for every possible choice of the sets involved.

For example:

$$A \cup B = B \cup A$$

This says that the union of two sets does not depend on the order of the sets. To prove such identities, we usually show that both sides contain exactly the same elements.

Basic idea of set equality

Two sets $X$ and $Y$ are equal if and only if:

$$X = Y \iff X \subseteq Y \text{ and } Y \subseteq X$$

So, to prove a set identity, one common technique is:

1. take an arbitrary element,
2. show it belongs to the left-hand side if and only if it belongs to the right-hand side,
3. conclude that the sets are equal.

Main Content

1. Proving Set Identities by Element Method

Core idea

To prove $X = Y$, choose an arbitrary element $x$ and show: $$x \in X \iff x \in Y$$ This is the most direct and rigorous method.

Example: Commutative law of union

$$A \cup B = B \cup A$$ Proof:
Let $x$ be arbitrary. $$x \in A \cup B \iff (x \in A \text{ or } x \in B)$$ Since “or” is commutative, $$(x \in A \text{ or } x \in B) \iff (x \in B \text{ or } x \in A)$$ Hence, $$x \in B \cup A$$ Therefore, $$A \cup B = B \cup A$$

This method is highly preferred in formal proofs because it is precise and avoids ambiguity.

2. Important Laws of Set Identities

Commutative laws

$$A \cup B = B \cup A,\qquad A \cap B = B \cap A$$ These mean the order of sets does not matter in union and intersection.

Associative laws

$$(A \cup B)\cup C = A \cup (B \cup C)$$ $$(A \cap B)\cap C = A \cap (B \cap C)$$ These mean grouping does not matter.

Distributive laws

$$A \cup (B \cap C) = (A \cup B)\cap (A \cup C)$$ $$A \cap (B \cup C) = (A \cap B)\cup (A \cap C)$$ These are very important in simplifying complex expressions.

These laws are often proved using the element method or logical equivalences. For example, to prove: $$A \cap (B \cup C) = (A \cap B)\cup(A \cap C)$$ let $x$ be arbitrary: $$x \in A \cap (B \cup C) \iff x \in A \text{ and } (x \in B \text{ or } x \in C)$$ Using distributive logic: $$(x \in A \text{ and } x \in B) \text{ or } (x \in A \text{ and } x \in C)$$ which means: $$x \in (A \cap B)\cup(A \cap C)$$ Hence the identity holds.

3. Complement, Difference, and De Morgan’s Laws

Complement laws

For a universal set $U$, $$A \cup A' = U,\qquad A \cap A' = \varnothing$$ Here $A'$ means the complement of $A$ in $U$.

Difference law

$$A - B = A \cap B'$$ This means elements in $A$ but not in $B$ are exactly those in $A$ and in the complement of $B$.

De Morgan’s laws

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

Proof of De Morgan’s first law

Let $x$ be arbitrary. $$x \in (A \cup B)' \iff x \notin A \cup B$$ This means: $$x \notin A \text{ and } x \notin B$$ So, $$x \in A' \text{ and } x \in B' \iff x \in A' \cap B'$$ Therefore, $$(A \cup B)' = A' \cap B'$$

Example

If $U = \{1,2,3,4,5\}$, $A = \{1,2,3\}$, and $B = \{3,4\}$, then:

• $A \cup B = \{1,2,3,4\}$
• $(A \cup B)' = \{5\}$
• $A' = \{4,5\}$, $B' = \{1,2,5\}$
• $A' \cap B' = \{5\}$

So the identity is verified.

Working / Process

1. Understand the identity clearly

Identify the sets, operations, and what must be proved. Determine whether the identity involves union, intersection, complement, difference, or a combination of these.

2. Choose an appropriate proof technique

• Use the element method for direct and rigorous proof.
• Use subset method if the equality can be split into two inclusions.
• Use known identities such as De Morgan’s laws, distributive laws, and complement laws to simplify the expression.
• Use Venn diagrams only as a visual aid, not as the sole proof in formal mathematics.

3. Work step by step until both sides match

Convert each side into element membership statements and simplify logically. If proving by subsets, show: $$X \subseteq Y \quad \text{and} \quad Y \subseteq X$$ After simplification, conclude that both expressions contain exactly the same elements, so the identity is true.

Advantages / Applications

Helps in mathematical reasoning and theorem proving

Proofs of set identities train students to think logically and write structured proofs, which is useful in all branches of mathematics.

Used in simplifying expressions

Set identities are essential when reducing complicated expressions involving unions, intersections, and complements, especially in discrete mathematics and probability.

Important in computer science and logic

Set identities correspond closely to Boolean algebra, database queries, digital circuits, and logical reasoning in programming and algorithm design.

Summary

Set identities are equalities between set expressions that are proved using logic and element-wise reasoning. The most reliable approach is to show that each side has exactly the same elements, often by using known laws such as commutative, associative, distributive, and De Morgan’s laws. These proofs are foundational for later topics in relations, functions, and theorem proving.