# Sets and Set Operations

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/sets-and-set-operations

## The Foundation of Sets

A **set** is an unordered collection of distinct objects, its **elements**. We write $x \in A$ for elementhood and $x \notin A$ otherwise. Sets have **no order** ($\{1,2\} = \{2,1\}$) and **no duplicates**.

| Relation / Set | Symbol | Meaning | Example |
| --- | --- | --- | --- |
| **Subset** | $A \subseteq B$ | Every element of $A$ is in $B$ | $\{1\} \subseteq \{1,2\}$ |
| **Empty Set** | $\emptyset$ | Has no elements; subset of all | $\emptyset \subseteq A$ |
| **Cardinality** | $|A|$ | Number of elements in $A$ | $|\{a,b,c\}| = 3$ |

## Set Operations & Logic

Operations combine sets just like boolean logic (Union=OR, Intersection=AND, Complement=NOT).

| Operation | Notation | Definition | Logic Mirror |
| --- | --- | --- | --- |
| **Union** | $A \cup B$ | In $A$ or $B$ (or both) | OR |
| **Intersection** | $A \cap B$ | In both $A$ and $B$ | AND |
| **Difference** | $A \setminus B$ | In $A$, not in $B$ | A AND NOT B |
| **Complement** | $\overline{A}$ | In universe, not in $A$ | NOT |

**De Morgan's laws**: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

**Inclusion-exclusion**: $|A \cup B| = |A| + |B| - |A \cap B|$. **Pitfall**: Do not forget to subtract the overlap, or you count it twice.

## Practice questions

4 of this lesson's 9 practice questions, with answers. The full set is in the app.

### 1. De Morgan’s laws appear in set theory as $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and in logic as $\lnot(p \lor q) = \lnot p \land \lnot q$. Why is one proof enough for both?

A. Because complementation and negation are defined to make the laws hold
B. Because the two laws were derived independently and happen to look alike
C. Because both are statements in the same Boolean algebra
D. Because set theory is a special case of logic restricted to finite collections

**Answer:** C. Because both are statements in the same Boolean algebra

**Why:** One structure, two notations. This is why a database query optimiser, a circuit simplifier and a proof assistant can all apply the same rewrite rule.

Page: https://tryals.app/practice/computer-science-i/sets-and-set-operations/de-morgans-laws-appear-in-set-theory-as-a-b-a-b-and-in-logic

### 2. A database `JOIN`, a Venn diagram and a bitwise `AND` on two bit-vectors all compute the same thing. What is the shared operation?

A. Set intersection, which is boolean AND applied per element
B. Sorting, which all three require before combining
C. Nothing, the three are analogous but compute different results
D. Counting, since all three ultimately return a cardinality

**Answer:** A. Set intersection, which is boolean AND applied per element

**Why:** 'Is x in A and in B' is one question asked once per element, so the three are one operation in three costumes. It is why sets over a fixed universe are stored as bit-vectors and intersected with a single machine instruction, set theory compiling directly to hardware.

Page: https://tryals.app/practice/computer-science-i/sets-and-set-operations/a-database-join-a-venn-diagram-and-a-bitwise-and-on-two-bit-vectors

### 3. Set operations mirror boolean logic exactly. Sort each description under the connective it behaves like.

**Answer:**

- Behaves like AND: The intersection of A and B, The elements belonging to both A and B
- Behaves like OR: The union of A and B
- Behaves like NOT: The complement of A

**Why:** x is in the intersection exactly when x is in A AND in B; x is in the union exactly when x is in A OR in B; x is in the complement exactly when x is NOT in A. This correspondence is why De Morgan's laws hold verbatim for sets: the complement of a union is the intersection of the complements.

Page: https://tryals.app/practice/computer-science-i/sets-and-set-operations/set-operations-mirror-boolean-logic-exactly-sort-each-description

### 4. The universe is {1, 2, ..., 10}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Select every number that lies in the complement of A union B.

A. 7
B. 4
C. 10
D. 6
E. 8

**Answer:** A. 7; C. 10; E. 8

**Why:** A union B is {1,2,3,4,5,6}, so its complement within {1,...,10} is {7,8,9,10}, of the options that means 7, 8 and 10. Cross-checking with De Morgan: the complement of A is {5,...,10} and the complement of B is {1,2,7,8,9,10}; their intersection is {7,8,9,10}, the same answer. Taking the union of the complements instead would wrongly give almost everything.

Page: https://tryals.app/practice/computer-science-i/sets-and-set-operations/the-universe-is-1-2-10-a-1-2-3-4-and-b-3-4-5