[\<- 2.1](2.1.md)

---

# 2.2 Set Operations p1

We can represent sets in a **Venn Diagram** as circles/ellipses that lie inside some **universal set**

```
+----------+
|          |
|  +--+  u |
|  | s|    |
|  |  |    |
|  +--+    |
+----------+
```

- "rectangle is universal set `u`

- Ex.
	- Let `u` = ℤ
	- 'A' = `{2k | k∈ℤ}`
	- 'B' = `{3l | l∈ℤ}`
	1. Draw a Venn Diagram and write at least on element in each "region"

```
+---------------------+
|                     |
|  +-------+      u   |
|  | A     |          |
|  |    +-------+     |
|  |    |  |    |     |
|  +----|--+    |     |
|       |     B |     |
|       +-------+     |
+---------------------+
```

- `u` is representing ℤ
- Examples that belong in each region:
	- Inside 'A', outside 'B'
		- 2
		- 4
	- Inside 'B', outside 'A'
		- 3
		- -9
	- Inside both 'A' and 'B'
		- 6
		- 0
		- -18
	- Outside of both 'A' and 'B' (but inside `u`)
		- 7
		- 5

- **Definitions**: If 'A', 'B' are sets, the
	1. **Intersection** of 'A' and 'B', written `A∩B`, is the set of all elements in 'A' **and** 'B'
	2. **Union** of 'A' and 'B', written `A∪B`, is the set of all elements in 'A' **or** 'B'
		- the "or" is inclusive, btw

### Intersection Venn Diagram

```
+---------------------+
|    A↓               |
|  +-------+      u   |
|  |       |          |
|  |    +-------+     |
|  |    |██|    |     |
|  +----|--+    |←    |
|       |       |B    |
|       +-------+     |
+---------------------+
```

- `A∩B` = shaded

### Union Venn Diagram

```
+---------------------+
|    A↓               |
|  +-------+      u   |
|  |███████|          |
|  |████+-------+     |
|  |████|██|████|     |
|  +----|--+████|←    |
|       |███████|B    |
|       +-------+     |
+---------------------+
```

- `A∪B` = shaded

|Words|Logic|Sets|
|-----|-----|----|
|and  |^    |∩   |
|or   |∨    |∪   |

- Describe `A∩B`, `A∪B` in the earlier example
	- `A∩B` = multiples of 2 **and** 3
		- multiples of 6
	- `A∪B` = multiples of 2 **or** 3
		- 2, 3, 4, 6, 8, ...

---

- **Definition**: If `A∩B` = Ø, we say 'A' and 'B' are **disjoint**

```
+---------------------+
|                     |
|  +-------+      u   |
|  | A     |          |
|  |       |          |
|  |       |   +----+ |
|  +-------+   | B  | |
|              |    | |
|              +----+ |
+---------------------+
```

- Notice how 'A' and 'B' don't overlap at all

- **Definition**: Fix a universal set `u`, and `S ≺= u`. The **complement** of 'S', written s̅ or s^c, is the set of elements `u` not in 'S'

**complement**

```
+---------------------+
|█████████████████████|
|██+-------+██████u███|
|██| S     |██████████|
|██|       |██████████|
|██|       |██████████|
|██+-------+██████████|
|█████████████████████|
|█████████████████████|
+---------------------+
```

- Everything outside of 'S' and inside `u` is shaded
	- the shaded region is s̅

- **Definition**: The **difference** of 'A' and 'B', written `A-B` or `A\B`, is the set of elements **in 'A' but not 'B'**

```
+---------------------+
|    A↓               |
|  +-------+      u   |
|  |███████|          |
|  |████+-------+     |
|  |████|  |    |     |
|  +----|--+    |←    |
|       |       |B    |
|       +-------+     |
+---------------------+
```

- The shaded region is `A-B`

- **Note**: `A-B` = `A∩¯(B̄̄̄̄̄̄̄̄̄)`
	- (line above 'B' -> complement of B)

---

## Set Identities

| | | |
|-|-|-|
|**Commutative**|`A∪B` = `B∪A`|`A∩B` = `B∩A`|
|**Associative**|`A∪(B∪C)` = `(A∪B)∪C`|`A∩(B∩C)` = `(A∩B)∩C`|
|**De Morgan (for sets)|`¯(A∩B)` (not in ('A and 'B')) = `¯(A)∪¯(B)`|`¯(A∪B)` (not in ('A or 'B')) = `¯(A)∩¯(B)`|

---

# 2.2 Set Operations p2

Ex: Let `A ≺= B`. Prove that `A∪B ≺= B`
- Proof: Let x∈A∪B. Then, x∈A or x∈B.
	- Case 1: If x∈A, then x∈B since `A ≺= B`
	- Case 2: If x∈B, then we are done 
	- ∴ x∈B which implies `A∪B ≺= B` ▣
	
- **Theorem**: Let 'A', 'B' be sets. 'A' = 'B' iff `A ≺= B` and `B ≺= A`