[\<- 1.8](1.8.md)

---

# 2.1 Sets p1

- A **Set** consists of elements, and it is **unordered**
	- "x∈S" means `x` is an element of 'S'

	- Note: {a,b,c} = {c,b,a} (order doesn't matter)
	- Note: {a,b,c} = {a,a,b,b,c,c} (number of occurences doesn't matter)

- **Definition**: Let 'S', 'T' be sets. We say 'S' is a **subset** of 'T', and write `S <= T`, if each element `x` of 'S' is also an element of 'T'
	- To prove `S ≺= T`:
		1. Let `x` be an arbitrary element of 'S'
		2. Show it follows that x∈T

- **Definition**: The set with no elements is called the **empty set**, denoted by Ø or {}
	- For any set 'S',
		1. `Ø ≺= S` (Ø is a subset of 'S')
		2. `S ≺= S` ('S' is a subset of 'S')

- **Definition**: If a set 'S' has `n` elements with n∈ℤ, `n >= 0`, then 'S' is a **finite set**. We say the **cardinality** of 'S' is `n` and write `|S| = n`
	- If 'S' is not a finite set, then 'S' is an **infinite set**
	- `(S = Ø) <-> (|S| = 0)`

---

## Power Sets

**Definition**: The **Power Set** of 'S' is the set of all subsets of 'S' and is denoted `Ꝕ(S)`

- Ex. Let 'S' = {`a`, `b`, `c`}. Write `Ꝕ(S)` in set notation.
	- `Ꝕ(s)` = 
		- Ø
		- {`a`}
		- {`b`}
		- {`c`}
		- {`a`, `b`}
		- {`a`, `c`}
		- {`b`, `c`}
		- {`a`, `b`, `c`}
		- Notice: all the elements of `Ꝕ(S)` are sets themselves (i.e. {a}∈Ꝕ(S) instead of just `a`)
	- `|Ꝕ(S)| = 8`
	- Can create elements of `Ꝕ(S)` with **bit strings** (sequence of 0's and 1's)

- Ex. `S = {a, b, c}` ... bit string of length 3 (e.g. 011)
	- 1st digit:
		- 1 if a∈subset
		- 0 if !(a∈subset)
	- 2nd digit:
		- 1 if b∈subset
		- 0 if !(b∈subset)
	- 3rd digit:
		- 1 if c∈subset
		- 0 if !(c∈subset)
	- **Possible Bit Strings**:
		- 000
			- corresponds to Ø
		- 100
			- corresponds to {`a`}
		- 010
		- 001
		- 110
		- 101
		- 011
			- corresponds to {`b`, `c`}
		- 111
		- There are 8 possible bit strings because `2^3` = 8
			- This leads to a theorem

- **Theorem**: If `|S| = n`, then `|Ꝕ(S)| = 2^n`

- **Definition**: Let 'S', 'T' be sets. The **product** of 'S' and 'T' is the set `{(s, t) | s∈S, t∈T}`
	- (`s`, `t`) = ordered pair
	- e.g. Let 'S' = {`a`, `b`, `c`} and 'T' = {1, 2}. Then,
		- `S × T = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}`
			- Notice: `|S × T|` = `6` = `3 · 2` = `|S| · |T|`

- **Theorem**: If `|S| = n` and `|T| = m`, then `|S × T| = nm`

- **Note**: (ℝ × ℝ × ℝ) = `{(a,b,c) | a,b,c∈ℝ}` is denoted ℝ^3
	- we can similarly define ℝ^n for `n>3`

---

[2.2 ->](2.2.md)