Discrete Mathematics

The Computer Representation Of Sets

THE COMPUTER REPRESENTATION OF SETS:

There are various ways to represent sets using a computer. Modern programming languages, such as JAVA, have predefined collection class to represent the set. In such class, we need to insert the set elements and there are various class operations defined for the algebraic operations on the set.

In this section, we shall present a method for storing elements using the arbitrary ordering of the elements of a universal set.

Assume that the universal set U is finite (and of reasonable size so that the number of elements in U are not larger than the memory size).

First, specify the arbitrary ordering of elements of U, such as a1, a2, ..., ..., an. Represent a subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A and is 0 otherwise.

E.g. Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and A be subset of U containing elements that are multiples of 3 or 5. Thus,

A = {3, 5, 6, 9, 10}. We shall represent elements of U as per the order given in the above set. Then, A represents a bit string 0010110011.

With this, we have completed basic discussion on set theory and now is the time to check the understanding for the same.