A set is a collection of distinct, unordered elements.
α∈A means that the element α is contained within the set A.
α∈A is a negation of the above
A set T is a subset of S if every element in T is also in S
Can be restated as If the statement “if x∈T then x∈S” is true, then…
Denoted T⊆S
T⊆S is a negation of the above
Both sides of the ⊆ symbol must be sets
Every set is a subset of itself
A set T is a proper subset of S if T⊆S and T=S
Denoted as T⊂S
The empty set is the set containing no elements.
Denoted as {} or ϕ (Greek letter phi)
It is a subset of every set, other than itself
Set syntax and examples
S={2,3}={3,2}
S={1,2,3,…,100}
Not recommended, it’s very ambiguous
S={n≤100∣n∈N}
Vertical line (∣) means “such that”, or “where”
N is the set of natural numbers
S={2,4,6,…,58}
The set of even numbers from 1 to 58
Not recommended, very ambiguous,
These formats are more preferable:
{2n∣n∈N,n≤29}
The comma indicates an additional condition
We want to minimize the number of conditions
{n∣n∈N,n even}
Important Sets to Know
N
The set of all natural numbers
Integers greater than and NOT equal to Zero
{1,2,3,…}
Z
The set of all integers
{…,−2,−1,0,1,…}
Q
The set of all rational numbers
{nm∣m,n∈Z,n=0}, if you’re fancy
R
The set of all real numbers
Set Operations
Union — A∪B
Returns a set containing elements that are in either or both sets
Commutative and associative
If A⊆B then A∪B=B
For all sets A,B:A⊆A∪B, and B⊆A∪B
Intersection — A∩B
Returns a set containing elements that are strictly in both sets
Commutative and associative
If A⊆B then A∩B=A
For all sets A,B:A∩B⊆A, and A∩B⊆B
Conclusion:
A∩B⊆A⊆A∪B
A∩B⊆B⊆A∪B
Difference — A−B or A∖B
Returns a set containing all of the elements in A that were not found in B
Not commutative or associative
Symmetric Difference — A△B or A⊕B
Returns a set containing all of the elements in either A or B, but not both
Commutative and associative, surprisingly
A⊕B=(A∪B)−(A∩B)
Complement — A or Ac
Often, every set we consider is seen as a subset of a larger set, called the universal set, such as N or R. We denote this universal set as U.
For any set A,A is the set of all elements in U that are not in A.
A=U−A
Properties of Set Operators
A∩(B∪C)=(A∩B)∪(A∩C)
A∪(B∩C)=(A∪B)∩(A∪C)
A∪B=A∩B
A∩B=A∪B
Venn Diagrams
I found this material to be useful but not worth me drawing up my diagrams. If you would like to send me a diagram to put in here, create a diagram using Excalidraw, and send me the link to the diagram. I will add it to the notes and credit you.
Proofs
How to formally prove that A=B?
Proofs must use 2-directional inclusion, i.e: A=B iff A⊆B and B⊆A.
We must show that both of the following are true:
If x∈A, then x∈B
If x∈B, then x∈A.
Dec. 31
Power Set
Definition: The power set of a set S (denoted P(S)) is the set of all subsets of S.
The only elements of a power set are sets.
There will be no elements of a power set that are not sets.
{1}∈P({1,2}), but 1∈/P({1,2})
Power Set Theorem
For any finite set S,∣P(S)∣=2∣S∣, where ∣S∣ is the number of elements in S.
This means that the number of elements in the power set of a set is equal to 2 raised to the number of elements in the set.
Infinite Unions and Intersections
Unions: ⋃i=1∞Ai
The union of all sets Ai for i=1,2,3,…
The set of all elements that are in at least one of the sets Ai
In English: “The union of Ai for all i”
Example: ⋃i=1∞{i}=N
Example: ⋃i=1∞[i1,i+11)=(0,1]
Explanation: The union of all intervals [i1,i+11) for i=1,2,3,… is the interval (0,1] (open on the left, closed on the right)
Intersections: ⋂i=1∞Ai
The intersection of all sets Ai for i=1,2,3,…
The set of all elements that are in every one of the sets Ai
In English: “The intersection of Ai for all i”
Example: ⋂i=1∞{i}={1}
Example: ⋂i=1∞[i1,i+11)={0}
Explanation: The intersection of all intervals [i1,i+11) for i=1,2,3,… is the set {0} because the only number that is in every interval is 0.
Cartesian Products
Definition: An ordered pair is a pair of elements (a,b) in which the order of the elements matters. (a,b)=(b,a).
Definition: An ordered n-tuple is an ordered list of n elements (a1,a2,…,an) in which the order of the elements matters. (a1,a2,…,an)=(a2,a1,…,an).
Familiar examples of ordered pairs and ordered n-tuples:
Point in the plane: (x,y)
Point in space: (x,y,z)
Definition:
Let A,B be sets. The Cartesian product of A and B (denoted A×B) is the set of all ordered pairs (a,b) where a∈A and b∈B.
Formally, A×B={(a,b)∣a∈A,b∈B}
Cartesian Product Example
A={1,2} B={3,4,5}
A×B={(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)}
Note how each element of A is paired with each element of B.
Properties of Cartesian Products
Unlike previous set operations (∪,∩,,∖ ), the elements of A×B are new elements, not elements of A or B.