Discrete Mathematics· Note 01

Sets

Year 2 · Semester ILast updated

Dec. 25

Sets

Definitions, Notations, and Symbols

  • A set is a collection of distinct, unordered elements.
  • α∈A\alpha\in A means that the element α\alpha is contained within the set AA.
    • α∉A\alpha\not\in A is a negation of the above
  • A set TT is a subset of SS if every element in TT is also in SS
    • Can be restated as If the statement “if x∈Tx\in T then x∈Sx\in S” is true, then…
    • Denoted T⊆ST\subseteq S
    • T⊈ST\not\subseteq S is a negation of the above
    • Both sides of the ⊆\subseteq symbol must be sets
    • Every set is a subset of itself
  • A set TT is a proper subset of SS if T⊆ST\subseteq S and T≠ST\not= S
    • Denoted as T⊂ST\subset S
  • The empty set is the set containing no elements.
    • Denoted as {  }\set{} or ϕ\phi (Greek letter phi)
    • It is a subset of every set, other than itself
Set syntax and examples
  • S={ 2,3 }={ 3,2 }S=\set{2, 3} = \set{3, 2}
  • S={ 1,2,3,…,100 }S=\set{1,2,3,\dots,100}
    • Not recommended, it’s very ambiguous
  • S={ n≤100∣n∈N }S=\set{n\le100\mid n\in\N}
    • Vertical line (∣\mid) means “such that”, or “where”
    • N\N is the set of natural numbers
  • S={ 2,4,6,…,58 }S=\set{2,4,6,\dots,58}
    • The set of even numbers from 1 to 58
    • Not recommended, very ambiguous,
    • These formats are more preferable:
      • { 2n∣n∈N, n≤29 }\set{2n\mid n\in\N,\ n\le29}
        • The comma indicates an additional condition
        • We want to minimize the number of conditions
      • { n∣n∈N, n even }\set{n\mid n\in\N,\ n\text{ even}}

Important Sets to Know

  • N\N
    • The set of all natural numbers
    • Integers greater than and NOT equal to Zero
    • { 1,2,3,… }\set{1,2,3,\dots}
  • Z\Z
    • The set of all integers
    • { …,−2,−1,0,1,… }\set{\dots,-2,-1,0,1,\dots}
  • Q\Q
    • The set of all rational numbers
    • { mn∣m,n∈Z, n≠0 }\set{\frac mn\mid m,n\in\Z,\ n\neq0}, if you’re fancy
  • R\R
    • The set of all real numbers

Set Operations

  • Union — A∪BA\cup B
    • Returns a set containing elements that are in either or both sets
    • Commutative and associative
    • If A⊆BA\subseteq B then A∪B=BA\cup B=B
    • For all sets A,BA,B: A⊆A∪BA\subseteq A\cup B, and B⊆A∪BB\subseteq A\cup B
  • Intersection — A∩BA\cap B
    • Returns a set containing elements that are strictly in both sets
    • Commutative and associative
    • If A⊆BA\subseteq B then A∩B=AA\cap B=A
    • For all sets A,BA,B: A∩B⊆AA\cap B\subseteq A, and A∩B⊆BA\cap B\subseteq B
    • Conclusion:
      • A∩B ⊆A⊆ A∪BA\cap B\ \subseteq A\subseteq \ A\cup B
      • A∩B ⊆B⊆ A∪BA\cap B\ \subseteq B\subseteq \ A\cup B
  • Difference — A−BA - B or A∖BA \setminus B
    • Returns a set containing all of the elements in AA that were not found in BB
    • Not commutative or associative
  • Symmetric Difference — A△BA\bigtriangleup B or A⊕BA\oplus B
    • Returns a set containing all of the elements in either AA or BB, but not both
    • Commutative and associative, surprisingly
    • A⊕B=(A∪B)−(A∩B)A\oplus B = (A\cup B) - (A\cap B)
  • Complement — A‾\setcomp A or AcA^\mathsf{c}
    • Often, every set we consider is seen as a subset of a larger set, called the universal set, such as N\N or R\R. We denote this universal set as UU.
    • For any set AA, A‾\setcomp A is the set of all elements in UU that are not in AA.
    • A‾=U−A\setcomp A = U - A

Properties of Set Operators

  1. A∩(B∪C)=(A∩B)∪(A∩C)A\cap(B\cup C)=(A\cap B)\cup(A\cap C)
  2. A∪(B∩C)=(A∪B)∩(A∪C)A\cup(B\cap C)=(A\cup B)\cap(A\cup C)
  3. A∪B‾=A‾∩B‾\setcomp{A\cup B}=\setcomp A\cap\setcomp B
  4. A∩B‾=A‾∪B‾\setcomp{A\cap B}=\setcomp A\cup\setcomp 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=BA=B?
Proofs must use 2-directional inclusion, i.e:
A=BA=B iff A⊆BA\sseq B and B⊆AB\sseq A.
We must show that both of the following are true:

  • If x∈Ax\in A, then x∈Bx\in B
  • If x∈Bx\in B, then x∈Ax\in A.

Dec. 31

Power Set

Definition: The power set of a set SS (denoted P(S)\pset S) is the set of all subsets of SS.

Power Set Examples

A={ 1,2 }A=\set{1,2}
P(A)={ {  },{ 1 },{ 2 },{ 1,2 } }\pset A=\set{\set{},\set{1},\set{2},\set{1,2}}
P(A)={ ϕ,{ 1 },{ 2 },{ 1,2 } }\pset A=\set{\phi,\set{1},\set{2},\set{1,2}}, alternatively

For any set SS, ϕ∈P(S)\phi\in\pset S and S∈P(S)S\in\pset S.

Remember!

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 })\set{1}\in\pset{\set{1,2}}, but 1∉P({ 1,2 })1\notin\pset{\set{1,2}}

Power Set Theorem

For any finite set SS, ∣P(S)∣=2∣S∣|\pset S|=2^{|S|}, where ∣S∣|S| is the number of elements in SS.

This means that the number of elements in the power set of a set is equal to 22 raised to the number of elements in the set.

Infinite Unions and Intersections

  • Unions: ⋃i=1∞Ai\bigcup_{i=1}^\infty A_i
    • The union of all sets AiA_i for i=1,2,3,…i=1,2,3,\dots
    • The set of all elements that are in at least one of the sets AiA_i
    • In English: “The union of AiA_i for all ii”
    • Example: ⋃i=1∞{ i }=N\bigcup_{i=1}^\infty\set{i}=\N
    • Example: ⋃i=1∞[1i,1i+1)=(0,1]\bigcup_{i=1}^\infty[\frac1i,\frac1{i+1})=(0,1]
      • Explanation: The union of all intervals [1i,1i+1)[\frac1i,\frac1{i+1}) for i=1,2,3,…i=1,2,3,\dots is the interval (0,1](0,1] (open on the left, closed on the right)
  • Intersections: ⋂i=1∞Ai\bigcap_{i=1}^\infty A_i
    • The intersection of all sets AiA_i for i=1,2,3,…i=1,2,3,\dots
    • The set of all elements that are in every one of the sets AiA_i
    • In English: “The intersection of AiA_i for all ii”
    • Example: ⋂i=1∞{ i }={ 1 }\bigcap_{i=1}^\infty\set{i}=\set{1}
    • Example: ⋂i=1∞[1i,1i+1)={ 0 }\bigcap_{i=1}^\infty[\frac1i,\frac1{i+1})=\set{0}
      • Explanation: The intersection of all intervals [1i,1i+1)[\frac1i,\frac1{i+1}) for i=1,2,3,…i=1,2,3,\dots is the set { 0 }\set{0} because the only number that is in every interval is 00.

Cartesian Products

Definition: An ordered pair is a pair of elements (a,b)(a,b) in which the order of the elements matters. (a,b)≠(b,a)(a,b)\not=(b,a).

Definition: An ordered n-tuple is an ordered list of nn elements (a1,a2,…,an)(a_1,a_2,\dots,a_n) in which the order of the elements matters. (a1,a2,…,an)≠(a2,a1,…,an)(a_1,a_2,\dots,a_n)\not=(a_2,a_1,\dots,a_n).

Familiar examples of ordered pairs and ordered n-tuples:

  • Point in the plane: (x,y)(x,y)
  • Point in space: (x,y,z)(x,y,z)

Definition:
Let A,BA, B be sets. The Cartesian product of AA and BB (denoted A×BA\times B) is the set of all ordered pairs (a,b)(a,b) where a∈Aa\in A and b∈Bb\in B.

Formally, A×B={ (a,b)∣a∈A, b∈B }A\times B=\set{(a,b)\mid a\in A,\ b\in B}

Cartesian Product Example

A={ 1,2 }A=\set{\textcolor{red}{1},\textcolor{orange}{2}}
B={ 3,4,5 }B=\set{\textcolor{green}{3},\textcolor{pink}{4},\textcolor{lightblue}{5}}

A×B={ (1,3),(1,4),(1,5),(2,3),(2,4),(2,5) }A\times B=\set{(\textcolor{red}{1},\textcolor{green}{3}),(\textcolor{red}{1},\textcolor{pink}{4}),(\textcolor{red}{1},\textcolor{lightblue}{5}),(\textcolor{orange}{2},\textcolor{green}{3}),(\textcolor{orange}{2},\textcolor{pink}{4}),(\textcolor{orange}{2},\textcolor{lightblue}{5})}

Note how each element of AA is paired with each element of BB.

Properties of Cartesian Products

  • Unlike previous set operations (∪,∩, ‾,∖\cup,\cap,\setcomp\ , \setminus ), the elements of A×BA\times B are new elements, not elements of AA or BB.
    • A∩(A×B)=ϕA\cap (A\times B)=\phi
  • The product is not commutative
    • In general, A×B≠B×AA\times B\not=B\times A
  • For finite sets A,BA,B, ∣A×B∣=∣A∣⋅∣B∣|A\times B|=|A|\cdot|B|

Distributivity of Cartesian Products

  1. A×(B∪C)=(A×B)∪(A×C)A\times(B\cup C)=(A\times B)\cup(A\times C)
  2. A×(B∩C)=(A×B)∩(A×C)A\times(B\cap C)=(A\times B)\cap(A\times C)