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)}

The cardinality of A multiplied by the cardinality of B

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

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.

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}
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

Everything in the universe that isn’t in A

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

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

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.

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