A set is a collection of unique (no duplicate) objects, physical or abstract,
called elements or members.
{a, b, c} No order, so same set as {c, a, b}. Think bag.
finite: {red,green,blue}, {9, 3, -2, 0}. Size is the number of elements.
infinite: {0,2,4,6,...}, ℕ, ℤ, ℚ, ℝ, the set of prime numbers
empty set: {} = ∅
A set can be an element: {1,2,{cat,dog}}
A set can be given a name: A = {1,2,3}, B = {1,2,3,4,5}
2 ∈ A, 4 ∈ {1,2,3,4,5}
An algebraic variable, e.g. x, can be any number from some set of numbers.
Intervals of real numbers.
interval: [a,b] all numbers between a and b, inclusive: a≤x≤b
interval: [a,b) all numbers between a and b. includes a but not b: a≤x<b
Ex. (2,6] "sandwiched" between endpoints 2 and 6: 2<x≤6
interval: [b,∞) x≥b
interval: (-∞,b) x<b
interval: (-∞,∞) = R
Complement of an interval is all the other numbers of R
Ex. complement of (2,6] is (-∞,2]∪(6,∞)
A subset of a set is a selection of any number of the set's elements.
A ⊂ B if every element of A is also an element of B.
Ex. {1,3,4} ⊂ {1,2,3,4,5}
Ex. {1,3,4} ⊂ ℕ
Ex. {1,2,3,4,5} ⊂ {digits}
Exs. ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ
A superset is the opposite: a set that contains all of this set, plus more.
The empty set, ∅, is a subset of every set, including itself.
Ex. ∅ ⊂ {1,3,4}
The set is a (non-proper) subset of itself.
Ex. {a,b,c} has the subsets ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, and {a,b,c}.
A finite set of size (cardinality) n has 2n subsets.
The number of subsets of size k of a set of size n is
n! / k!(n-k)!
this is the number of combinations of size k.
The powerset of a set is the set of all its subsets.
Ex. the powerset of {a,b,c} is {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}.
Set operations:
union of two sets: elements that are in either set. OR
Ex. {1,2,3} ∪ {2,3,4,5} = {1,2,3,4,5}
intersection of two sets: elements that are in both sets. AND
Ex. {1,2,3} ∩ {2,3,4,5} = {2,3}
complement of a set is all the other elements from the "universe" of elements. NOT
Ex. Say U={1,2,3,4,5,6,7,8,9}. Then {2,3,4,5} = {1,6,7,8,9}
DeMorgan's Laws: A∪B = A∩B and A∩B = A∪B
The Cartesian product of two sets is the set of all ordered pairs of the elements
of the two sets.
Example: if set one X={a,b} and set two Y={1,2,3},
then their Cartesian product is:
X × Y = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}.
Cartesian product is a set operation, like union and intersection are, but is not commutative:
Y × X = {(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)}.
If the sizes of the two sets are n and m,
then the size of their Cartesian product is nm.
Ex. R × R = set of all (x,y) points in the Cartesian plane.
A relation is any subset of the Cartesian product of two sets.
Example relations between the two above sets: {(a,2),(a,3),(b,1)}, {(a,2),(b,2)}, {(b,1),(b,2),(b,3)},
{(a,1)}, ...
If the sizes of the two finite sets are m and n,
then there are 2mn relations between them.
A function from one set (the domain) to another set (the codomain) is a pairing/mapping that assigns to each element of the domain exactly one element of the codomain.
A function is a restricted relation in which each element of the domain can only be "used" once.
Ex. All the functions from X to Y: {(a,1),(b,1)}, {(a,1),(b,2)}, {(a,1),(b,3)}, {(a,2),(b,1)}, {(a,2),(b,2)}, {(a,2),(b,3)}, {(a,3),(b,1)}, {(a,3),(b,2)}, {(a,3),(b,3)}
From a set of size m to a set of size n there are nm functions.
If |domain|≤|codomain| (m≤n), a one-to-one (injective) function: elements of the codomain are only used at most once.
Ex. All the one-to-one functions from X to Y: {(a,1),(b,2)}, {(a,1),(b,3)}, {(a,2),(b,1)}, {(a,2),(b,3)}, {(a,3),(b,1)}, {(a,3),(b,2)}
There are n! / (n-m)! injections.
If |domain|≥|codomain| (m≥n), an onto (surjective) function: every element of the codomain is used.
Ex. Swapping the roles of the two sets above,
All the functions from Y to X: {(1,a),(2,a),(3,a)}, {(1,a),(2,a),(3,b)}, {(1,a),(2,b),(3,a)}, {(1,a),(2,b),(3,b)}, {(1,b),(2,a),(3,a)}, {(1,b),(2,a),(3,b)}, {(1,b),(2,b),(3,a)}, {(1,b),(2,b),(3,b)}
Ex. All the onto functions from Y to X: {(1,a),(2,a),(3,b)}, {(1,a),(2,b),(3,a)}, {(1,a),(2,b),(3,b)}, {(1,b),(2,a),(3,a)}, {(1,b),(2,a),(3,b)}, {(1,b),(2,b),(3,a)}
The number of surjections is complicated:
= n! · S(m, n)
where S(m, n) is the Stirling number of the second kind.
If |domain|=|codomain| (m=n), a bijective function: both injective (one-to-one) and surjective (onto).
AKA a one-to-one correspondence.
Ex. Z = {a,b,c} [how many functions from Z to Y?, how many injections, surjections?]
Ex. All the bijective functions from Z to Y: {(a,1),(b,2),(c,3)}, {(a,1),(b,3),(c,2)}, {(a,2),(b,1),(c,3)}, {(a,2),(b,3),(c,1)}, {(a,3),(b,1),(c,2)}, {(a,3),(b,2),(c,1)}
There are n! bijections between two finite sets each of size n.
For finite sets of the same size, each bijection is also one of the n! injections
and one of the n! surjections. The bijections, injections, and surjections are the same set of functions.
Exercises:
|X|=4, |Y|=3
How many functions,injections,bijections from X to Y?
How many functions,injections,bijections from Y to X?
|X|=4, |Y|=4
How many functions,injections,surjections,bijections from X to Y?
How many functions,injections,surjections,bijections from Y to X?
From an infinite set to a finite set of one element there is only one function.
From an infinite set to a finite set of two or more elements there are an uncountably infinite number of functions.
From a finite set to a countably infinite set (e.g. ℕ) there are a countably infinite number of functions.
From a finite set to a uncountably infinite set (e.g. ℝ) there are an uncountably infinite number of functions.
From any infinite set to any infinite set there are an uncountably infinite number of functions.