Discrete Math 1: Set Theory

Photo by Gabby K from Pexels (not actually discrete math)

1. Definitions

// Set A contains elements 1,2 and 3
A = {1,2,3}
// 2 is an element of A
2∈A
// 4 is not an element of A
4∉A

2. Number Sets

Naturals    N = {1,2,3,4,...}
Integers Z = {...,-2,-1,0,1,2,...}
Rationals Q = Ratio of 2 integers. example: 1/2
Irrationals Q′= Can't be represented as ratios of integers
Real R = Q and Q′
Imaginary I = Everything not in the reals. Ex: (√x = -1)
Complex C = Reals and imaginaries

3. Set Equality

The order and repetition of elements does not matter

A = {1,2,3}
B = {2,3,2,2,3,1,2,3,2,1,1,2,3,2,2,3,1,1,3,2,1}
A = B

4. Set Builder Notation

A = {1,2,3,4,5,6,7,8,9}// B is equal to all elements of A (x∈A), such that (|), 
// the elements are less than 5 (x<5)
B = { x∈A | x<5 }
B = {1,2,3,4}

5. Types of Sets

Universal           U            
Empty {} or ϕ
Finite
Infinite
Subset

6. Cardinality

The number of distinct elements in a set.

n(A) or |A|

7. Equivalence

Sets are equivalent when their cardinality is the same. NOT to be mistaken with equality.

A = {1,2,3,4}
B = {5,6,7,8}
// A and B are equivalent
A~B

8. Subsets

Subsets: ⊆

Proper subsets: ⊂

A = {1,2,3,4}
B = {2,3}
// A is a subset of A, but not a PROPER subset of A
// ⊆
A⊆A
// B is a proper subset of AB⊂A

9. Power Sets

A power set P(A) is the set of all of the subsets of A.

A    = {1,2,3}
P(A) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

10. Ordered n_tuples / Ordered Pairs

Denoted by round brackets ( ). Unlike sets, the order matters

(a,b,c) != (c,b,a)
// but
{a,b,c} = {c,b,a}

11. Cartesian Products

The cross product between two sets.

AxB = {(a,b} | a∈A and b∈B}// So if...A   = {1,2,3} and B = {x,y,z}AxB = {(1,x),(1,y),(1,z),(2,x),(2,y),(2,z),(3,x),(3,y),(3,z)}

11.a. Cardinality of Cartesian Products

The cardinality of A multiplied by the cardinality of B

n(AxB) = n(A) * n(B)// In our case...n(AxB) = 9

11.b. Cartesian Plane

Think of it as a 2D graph. (2,1) is not the same position as (1,2).

 |   x     y     z
--------------------
1| (1,x) (1,y) (1,z)
2| (2,x) (2,y) (2,z)
3| (3,x) (3,y) (3,z)

RxR is the cartesian product of all the real numbers. In other words, every single real number point on an (x,y) graph.

12. Operations

How sets interact with each other.

12.a. Union (∪)

A∪B = {x | x∈A or x∈B}// So if...A   = {1,2,3} and B = {4,5,6}
A∪B = {1,2,3,4,5,6}

12.b. Intersection (∩)

A∩B = {x | x∈A and x∈B}// So if...A   = {1,2,3} and B = {3,4,5}
A∩B = {3}
// Another example. If...A = {x∈R | -2<x≤0}
B = {x∈R | 0<x<6}
A∪B = {x∈R | -2<x<6}
A∩B = ϕ

13. Identities 1

Rules that are always true and can help shortcut.

1. Commutative
A∪B = B∪A
2. Associative
(A∪B)∪C = A∪(B∪C)
3. Distributive
A∪(B∩C) = (A∪B)∩(A∪C)
4. Empty
A∪ϕ = A
A∩ϕ = ϕ
5. Universal
A∪U = U
A∩U = A
6. Subset
A∪A = A
A∩A = A

14. Operations 2

14.a. Compliment (c)

Everything in the universe that isn’t in A

A  = {x∈R | -2<x<0}
Ac = {x∈R | x≤-2 and 0≤x}

14.b. Difference (-)

A-B is everything in A that is NOT in B

A-B = {x | x∈A and x∉B}// So if...A   = {1,2,3,4} and B = {3,4,5}
A-B = {1,2}

15. Identities 2

1. A∪Ac  = U
2. (Ac)c = A
3. Uc = ϕ
4. ϕc = U
5. A-B = A∩Bc

16. De Morgans Law

(A∪B)c = Ac ∩ Bc// And the opposite is true...(A∩B)c = Ac ∪ Bc

17. Partitions

17.a. Disjoint

Sets are disjoint when neither have any of the same elements.

// Disjoint
A∩B = ϕ

Mutually Disjoint is where many sets all have no elements in common with each other.

17.b. Partition Definition

A collection of non-empty sets is a partition if and only if:

  1. A is the union of all the sets
  2. The sets are mutually disjoint
// Example 1
A = {1,2,3,4,5,6}
A₁ = {1,2}
A₂ = {3,4,5}
A₃ = {6}
{A₁,A₂,A₃} is a partition of A because
{{1,2},{3,4,5},{6}}
Rule 1 and 2 are satisfied
// Example 2
i = {1,2,3} and Aᵢ = {i,i²} and A= {1,2,3,4,9}
Is Aᵢ a partition of A?
Aᵢ = {{1},{2,4},{3,9}}
YES!

Engineer at Chainlink Labs.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store