Set Theory–A Dummies Guide

“If its possible to express the world in a set, a mathematician would do that!! :) The power of sets are vast that its used in statistics and computing a lot!!. To understand algorithms clearly, you need to understand set theory!!”

Background

    I am assuming that, the reader already know a little bit about Sets. Sets is a collection of unique objects. There is natural(without negative) number set, real number(floating point) set, integer(with negative) set. You can also have sets with different symbols. But the major operations that can be done between two sets, A & B, are:

• Intersection: common items between A & B , $A\capB$
• Union: all unique items between A & B (common items appear only once)  $A\cupB$
• Difference: if its, A-B, then items in B if present in A are removed and you get remaining elements.
• Disjoint: both A & B don’t have any items in common

I assume you understand the above general and basic concepts to move on into More details

Point-By-Point

   Extra concepts which you might require in some problem solving & algorithms are,

• singleton set: a set with only 1 element in it.
• partition of a set: a set if gets partitioned into subsets of size>0.. its called a partition. [Check here: http://en.wikipedia.org/wiki/Partition_of_a_set]
• complement of a set: If you take a set A, complement of set A is the elements which are not present in A. $\bar{A}$
• universal set: $A\cup\bar{A}$ is a universal set which includes all the elements in the bigger set
• n-set: If you have “n” elements in a set, its called n-set,
• k-subset: If you have “k” element subset from a “n” element set, its called a k-subset of the bigger set.
• Cartesian product set: Its the product of two sets.. straight to straight!! A x B = {a,b} x {a,b} = {(a,a),(a,b),(b,a),(b,b)}
• binary relation set: subset of Cartesian product between sets. For example, if A & B are subsets in a Natural number set and a relation is defined between the elements in the sets, like, a<b, for a in A, b in B, then, it means, the two sets A & B has elements sorted in ascending order when combined!!
• equivalence relation between sets: is a type of binary relation set!! but the sets will contain elements which are disjoint and exhibit equivalence among each other!!.. i.e, two sets are equivalence sets only if they are part of a same set under a binary relation
• equivalence class: the condition of equivalence between two sets should hold in all the elements of the class set!!.. i.e, if you need a set of even numbers from a natural number set given an even number, define a relation such that, equivalence is hold, like a+b is even..
• functions: extension of Cartesian product. Instead of just Cartesian product, we place a function with a binary relation among elements in the set

Practical Applications

• The main application will be on Graphs!! :) We will study about it soon. We have all the set concepts in a graph!!
• As it can put in Graph, Tree is just a subset of Graph!!.. Tree concepts are all derived from the set theory!!
• Binary trees we studied are disjoint sets composed of: root node, left sub tree, right sub tree. Disjoint means, all these 3 sets should have completely different nodes!! It’s not necessary to have any nodes as well. This makes, Binary tree a special case of Trees.
• Partition of a set can be directly related to substring, subsets in an array etc.

Example: The set { 1, 2, 3 } has these five partitions:

• { {1}, {2}, {3} }, or 1/2/3.
• { {1, 2}, {3} }, or 12/3.
• { {1, 3}, {2} }, or 13/2.
• { {1}, {2, 3} }, or 1/23.
• { {1, 2, 3} }, or 123

This is clearly how python lists work!! :). Python and Perl both have splice, union, intersection of arrays/lists.

• Red-black tree’s & Graph colouring all uses the set theory principles to distinguish different coloured nodes
• Equivalence relations are used in extracting subsets which exhibit equivalence. The famous subset sum problem(http://www.codechef.com/problems/PAIRSUM/).
• Functions over a set can be used to extract elements matching a binary condition!! we use nested for loops & if conditions to do this actually :)