diff options
Diffstat (limited to '2.1.md')
| -rw-r--r-- | 2.1.md | 87 |
1 files changed, 87 insertions, 0 deletions
@@ -0,0 +1,87 @@ +[\<- 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) |