Week 2: Sets, Functions, & Relations Flashcards
1
Q
set
A
an unordered collection of distinct objects, called elements or members of the set
2
Q
elements/members
A
the distinct objects that make up a set
3
Q
N
A
natural numbers (positive whole numbers and 0)
4
Q
Z
A
positive and negative whole numbers, including 0
5
Q
Z+
A
positive numbers > 0 (exclusive)
6
Q
R
A
set of real numbers
7
Q
R+
A
set of positive real numbers
8
Q
Q
A
set of rational number
9
Q
C
A
set of complex numbers
10
Q
Set Builder Notation
A
ex. O = {x ∈ Z⁺ | x is odd and x < 10}
11
Q
Roster Method
A
ex. O = {1, 3, 5, 7, 9}
12
Q
interval notation
A
[a,b] = {x | a ≤ x ≤ b}
[a,b) = {x | a ≤ x < b}
(a,b] = {x | a < x ≤ b}
(a,b) = {x | a < x < b}
13
Q
set equality
A
Two sets are equal if and only if they have the same elements. We write A = B when A and B are equal
examples: {1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5}
14
Q
universal set
A
the set containing everything
currently under consideration
* Sometimes implicit: V = {a,e,i,o,u}, What is U?
* Sometimes explicitly stated.
15
Q
empty set
A
- Written as ∅ or {}.
- The empty set is different from a set containing the empty set.
- Notes: ∅ ≠ { ∅ }
16
Q
subsets
A
The set A is a subset of B, denoted A ⊆ B, if and only if every
element of A is also an element of B.
17
Q
proper subsets
A
If A is a subset of B, but A is not equal to B ( If A ⊂ B, but A ≠ B,)
18
Q
set cardinality
A
A set A is finite if there are n distinct elements in A, where n is a
non-negative integer.
* The cardinality of a finite set A, denoted by |A|, is the number of
(distinct) elements of A
19
Q
power sets
A
*The power set of A, denoted P(A), is
the set of all subsets of a set A
* Example: A = {a,b}
P(A) = {ø, {a},{b},{a,b}}
20
Q
If a set A has n elements, then the
cardinality of its power set P(A)
A
2^n
21
Q
cartesian product
A
- product of two sets A and B, denoted as A x B is set of ordered pairs (a, b) where a ∈ A and b ∈ B
- basically combination you can make with element in A/B
- A = {a,b} B = {1,2,3}
A × B = {(a,1),(a,2),(a,3), (b,1),(b,2),(b,3)} - B x A is NOT equal to A x B bc order is switched
22
Q
set operations: difference
A
- difference of sets A and B, denoted by A - B, is set containing the elements of A that are NOT in B
- ex. A = {1,2,3,4,5} and B = {4,5,6,7,8}
- A - B = {1,2,3}
- B - A = {6,7,8}
23
Q
set operations: complement
A
- if A is a set, complement of A (w/respect to universal set) is denoted by Ā or A^c, is the SET U - A
- If U is the positive integers less than 100 and A = {x | x > 70}.
What is the complement of A? ints from 71 to 99
24
Q
set operations: intersection
A
- intersection of A and B, denoted by A ∩ B
- if intersection is empty, A and B are disjoint
- ex. {1,2,3} ∩ {3,4,5} is {3}
- ex. {1,2,3} ∩ {4,5,6} is ∅
25
set operations: union
- denoted by U
- is the combination of the two seats
- ex. {1, 2, 3} U {3, 4, 5} is {1, 2, 3, 4, 5}
- if elements are SAME then just list it ONCE
26
principle of inclusion-exclusion
- helps to calculate the size of the union A ∪ B by including the sizes of both sets and excluding the overlap
- ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
27
identity laws
A ∩ U = A
A U ø = A
28
domination laws
A U U = U
A ∩ ø = ø
29
idempotent laws
A U A = A
A ∩ A = A
30
complementation law
(A^c) = A
(complement of A is A)
31
commutative laws
A U B = B U A
A ∩ B = B ∩ A
32
associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A U (B U C) = (A U B) U C
33
distributive laws
A U (B ∩ C) = (A U B) ∩ (A U C)
A U (B ∩ C) = (A U B) ∩ (A U C)
34
de morgan's laws
(A ∩ B)^c = (A)^c U (B)^c
(A U B)^c = (A)^c ∩ (B)^c
35
absorption laws
A U (A ∩ B) = A
A ∩ (A U B) = A
36
complement laws
A U (A)^c = U
A ∩ (A)^c = ø
37
functions
- Let A and B be nonempty sets.
- A function f from A to B,
denoted f: A → B is an assignment of each element of A to exactly one
element of B
- We write f(a) = b if b is the unique element of B assigned by the function f
to the element a of A
38
domain
- function f: A -> B is a mapping from A to B
- A is the domain of f
39
codomain
- function f: A -> B is a mapping from A to B
- B is the codomain of f
40
image
- f(a) = b
- b is called the image of a under f
41
preimage
- f(a) = b
- a is called the preimage of b
42
range
- the range of f is the set of all images of points in A under f
- denoted by f(A)
43
when two functions are equal
- when they have
- the same domain
- the same codomain, and
- map each element of the domain to the same element of the codomain
44
three ways you can represent functions
- an explicit statement of the assignment
- a formula (ex. f(x) = x + 1)
- a program (ex. a program that given int n produced nth Fibonacci number)
45
factorial function
- f: N → Z+, denoted by f(n) = n!
- is the product of the
first n positive integers f(n) = 1 x 2 ∙∙∙x n, with f(0) = 0! = 1
46
one-to-one/injective functions
- injective/one-to-one iff f(a) = f(b) implies that a = b for all a and b in the domain of f
- a function is said to be an injection if it is one-to-one
- each a has it's own unique b
47
onto/surjective functions
- function f from A to B is called onto/surjective iff for every element b ∈ B there is
an element a∈ A with f(a) = b
- called a surjection if it is onto
48
one-to-one correspondence/bijection functions
- is a bijection if it is BOTH one-to-one and onto (injective and surjective)
49
floor/ceiling functions
- floor: ex. greatest integer less than or equal to x (floor)
- ceiling: ex. greatest integer greater than or equal to x (ceiling)
50
inverse functions
- inverse of f (f^-1) is function from B to A defined as
- f^-1(y) = x iff f(x) = y
- no inverse exists unless f is a BIJECTION (surjective and injective)
51
compositions of functions
Let g be a function from the set A to the set B
* Let f be a function from the set B to the set C .
* The composition of the functions f and g , denoted for all a ∈ A by 𝑓 ∘ 𝑔 , is the function from A to C defined by
* 𝑓 ∘ 𝑔 (𝑎) = 𝑓 (𝑔(𝑎))
52
relation
- A relation represents an association of objects of one set with objects of another set
- ex. students{Chris,bob,mia} and grades{A,B} rel ex: {(Chris, A), (Mia, B), (Bob, A)}
- relations are more general than functions
- a functions is a relation where exactly one element of B is related to each element of A
53
binary relation
- A binary relation R from a set A to a set B is a subset R ⊆ A × B.
- ex. let A = {0,1,2} and B = {a, b}
- R = {(0, a), (0, b), (1,a) , (2, b)} is a relation from A to B
54
binary relation on a set
- A binary relation R on a set A is a relation from A to A
- ex. Let A = {a, b, c, d, e}. R = {(a, a), (a, b), (a, c), (e, e)} is a relation on A
55
binary relation on integers
- ex. R1 = {(a,b) | a ≤ b}, R2 = {(a,b) | a > b}, R3 = {(a,b) | a = b or a = −b}
- note: relations are on an infinite set and each relation is an infinite set
56
reflexive relations
- R is reflexive if and only if (a,a) ∊ R for every element a ∊ A
- relates every element of a set to itself
- ex. R3 = {(a,b) | a = b or a = −b}
57
symmetric relations
- R is symmetric iff (b,a) ∊ R whenever (a,b) ∊ R for all a, b ∊ A
- R3 = {(a,b) | a = b or a = −b}
58
transitive relations
- A relation R on a set A is called transitive if
(a,b) ∊ R and (b,c) ∊ R implies (a,c) ∊ R, for all a,b,c ∊ A
- ex. R4 = {(a,b) | a = b}
59
equivalence relations
- A relation on a set A is called an equivalence relation if it is
reflexive, symmetric, and transitive
- Two elements a, and b that are related by an equivalence
relation are called equivalent
- equivalence is often denoted by a ~ b
60
equivalence classes
- Let R be an equivalence relation on a set A.
- The set of all elements in A that are related to an element x of A is called the equivalence class of x
- The equivalence class of x with respect to R is denoted by [x]R;
- [x]R = {s | (x,s) ∈ R}
61
partition of a set
- A partition of a set 𝑆 is a collection of disjoint non-empty subsets of 𝑆 that
have 𝑆 as their union
62
composition of relations
* R1 is a relation from a set A to a set B.
* R2 is a relation from the set B to a set C.
* Then the composition of R1∘ R2, is a relation from A to C where
* if (x,y) is a member of R1 and (y,z) is a member of R2, then (x,z) is a
member of R1∘ R2.
63
⊂ vs. ⊆
- ⊂ is a proper subset (ex. A is a subset of B, but B is not equal to A)
- ⊆ is just a regular subset (ex. A is a subset of B, but they can equal each other)
