Week 2: Sets, Functions, & Relations Flashcards
set
an unordered collection of distinct objects, called elements or members of the set
elements/members
the distinct objects that make up a set
N
natural numbers (positive whole numbers and 0)
Z
positive and negative whole numbers, including 0
Z+
positive numbers > 0 (exclusive)
R
set of real numbers
R+
set of positive real numbers
Q
set of rational number
C
set of complex numbers
Set Builder Notation
ex. O = {x ∈ Z⁺ | x is odd and x < 10}
Roster Method
ex. O = {1, 3, 5, 7, 9}
interval notation
[a,b] = {x | a ≤ x ≤ b}
[a,b) = {x | a ≤ x < b}
(a,b] = {x | a < x ≤ b}
(a,b) = {x | a < x < b}
set equality
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}
universal set
the set containing everything
currently under consideration
* Sometimes implicit: V = {a,e,i,o,u}, What is U?
* Sometimes explicitly stated.
empty set
- Written as ∅ or {}.
- The empty set is different from a set containing the empty set.
- Notes: ∅ ≠ { ∅ }
subsets
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.
proper subsets
If A is a subset of B, but A is not equal to B ( If A ⊂ B, but A ≠ B,)
set cardinality
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
power sets
*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}}
If a set A has n elements, then the
cardinality of its power set P(A)
2^n
cartesian product
- 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
set operations: difference
- 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}
set operations: complement
- 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
set operations: intersection
- 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 ∅
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
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∣
identity laws
A ∩ U = A
A U ø = A
domination laws
A U U = U
A ∩ ø = ø
idempotent laws
A U A = A
A ∩ A = A
complementation law
(A^c) = A
(complement of A is A)
commutative laws
A U B = B U A
A ∩ B = B ∩ A
associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A U (B U C) = (A U B) U C
distributive laws
A U (B ∩ C) = (A U B) ∩ (A U C)
A U (B ∩ C) = (A U B) ∩ (A U C)
de morgan’s laws
(A ∩ B)^c = (A)^c U (B)^c
(A U B)^c = (A)^c ∩ (B)^c
absorption laws
A U (A ∩ B) = A
A ∩ (A U B) = A
complement laws
A U (A)^c = U
A ∩ (A)^c = ø
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
domain
- function f: A -> B is a mapping from A to B
- A is the domain of f
codomain
- function f: A -> B is a mapping from A to B
- B is the codomain of f
image
- f(a) = b
- b is called the image of a under f
preimage
- f(a) = b
- a is called the preimage of b
range
- the range of f is the set of all images of points in A under f
- denoted by f(A)
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
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)
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
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
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
one-to-one correspondence/bijection functions
- is a bijection if it is BOTH one-to-one and onto (injective and surjective)
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)
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)
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
* 𝑓 ∘ 𝑔 (𝑎) = 𝑓 (𝑔(𝑎))
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
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
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
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
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}
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}
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}
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
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}
partition of a set
- A partition of a set 𝑆 is a collection of disjoint non-empty subsets of 𝑆 that
have 𝑆 as their union
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.
⊂ 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)
