Udemy | Introductory Programming Course | Math Prerequisite
Sets and Relations
Prerequisites for Programming and Algorithms
Namaste and Hello!
This will be a brief brush-up on your math skills. If you want to learn these concepts in depth, you can check out various books and courses online. But for now I will be talking about these Math concepts to the extent that is required for building a strong foundation in Designing and Understanding Algorithms.
Sets can be defined as a collection of well-defined distinguishable objects and Relations as a subset of the cartesian product of two sets.
To better understand sets go through this example:
A = {0,1,2,4,6,8,10}, ∅ = {} (Empty Set)
B = {0,1,2,3,5,7,9}, C = {0,2,4,8}, D = {1,2,3,4}, E = {-1,-2,-3,-4}
Operations and Results on Sets A and B
Union -> A∪ B = {1,2,3,4,5,6,7,8,9,10}
Intersection -> A ∩ B = {0,1,2}
Difference -> A — B = {4,6,8,10} and B - A = {3,6,7,9}
Empty set Laws -> A ∩ ∅ = ∅ and A∪ ∅ = A
Idempotency Laws -> A ∩ A = A and A∪ A = A
Commutative Laws -> A ∩ B = B ∩ A and B∪ A = A∪ B
Associative Laws -> A ∩ (B ∩ C) = (A ∩ B) ∩ C and A∪ (B∪ C) = (A∪ B)∪ C
Distributive Laws -> A ∩ (B∪ C) = (A ∩ B)∪ (A ∩ C) and A∪ (B ∩ C) = (A∪ B) ∩ (A∪ C)
Absorption Laws -> A ∩ (A∪ B) = A ∩ (A∪ C) = A = A∪ (B ∩ A) = A∪ (A ∩ C)
DeMorgan’s Laws ->
A — (B∪ C) = (A — B) ∩ (A — C) and
A — (B ∩ C) = (A — B)∪ (A — C)
Complement Operations:
(A’)’ = A and A ∩ A’ = ∅
(B ∩ C)’ = B’ ∪ C’ and (B ∪ C)’ = B’ ∩ C’
The number of elements in a set is the cardinality of the set. And is represented as | A |. To find the cardinality of a set you can follow this formula. Here |A| is 7
| A ∪ B | = | A | + | B | — | A ∩ B |
Cartesian Product of two sets A and B (A × B), is the set of all ordered pairs such that the first element of the pair is an element of A and the second is an element of B.
A × B = {(a, b): a ∈ A and b ∈ B}
and the cardinality is
| A × B | = | A | ⋅ | B |
Relations R
Now you will be able to understand why Relations are a subset of the Cartesian product of two sets. Binary Relations or relations between two sets are of many types. Here is a list of the relations and their mathematical representations and definitions.
Reflexive: a R a where a ∈ A here aRa will be {(0,0), (1,1), (2,2), (4,4), (6,6), (8,8), (10,10)}
Symmetric: a R b where a ∈ A and b ∈ B ∀ a,b here aRb {(0,0), (1,1), (2,2), (4,3), (6,5), (8,7), (10,9), (3,4), (5,6), (7,8), (9,10)}
Transitive: e R c and c R d imply e R d where e ∈ E, c ∈ C, d ∈ D
Equivalence: Relation that is Reflexive, Symmetric and Transitive. It is same as a partition.
Antisymmetric: a R b and b R a simply implies a = b
Partial Order: Relation that is Reflexive, Antisymmetric and Transitive.
Total Relation: ∀ a,b ∈ A we have a R b or/both b R a (every pairing of elements of A is related by R)
Total Order/Linear Order: A partial Order that is also a total Relation
Total Preorder: A total relation that is transitive, but not necessarily reflexive and antisymmetric.
Functions:
They are the subset of relations. Not all relations are functions, but all functions are relations.
Hope this gives a brief info on the frequent terms in sets and relations. In the subsequent topics you will get to learn more about where they can be used specifically in programming and how they are helpful in forming Functions.
