1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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)
|
