Sets

Introduction: A set is a collection of well-defined objects. Usually the elements of a set have common properties. For example, all the students who enroll for a course ‘Computability’ make up a set. Formally,a set is an unordered collection of objects. The definition of a set is intuitive in nature and was stated by the German mathematician Cantor in 1895. The objects in a set are called the elements or members of the set.

Example 1: The set E of even positive integers less than 20 can be expressed by:

E = {2, 4, 6, 8, 10, 12, 14, 16, 18}, or

E = {x|x is even and 0 < x < 20}

A set is finite if it contains a finite number of elements and is infinite otherwise. The empty set has no elements and is denoted by φ. Cardinality of a set A is the number of elements in A and is denoted by #A or |A|. For example, if A = {2, 4, 6, 8}, then #A = 4. Note that #φ = 0. If a set is infinite, one cannot list all its elements. This set can be specified by providing a property that all members of the set must satisfy.

For example, A = {x|x is a positive integer divisible by 3}. The general format of such specification is A = {x|P(x) is a property that x must satisfy}.

Sets can be represented by either set builder form or by explicitly listing its elements. Sets can be defined using an inductive definition also. An inductive definition of a set has three components. They are:

The basis or basis clause that lists some elements in the set (which are basic building blocks).
The induction or inductive clause which states how to produce new elements from the existing elements of the set.
The extremal clause which asserts that no object is a member of the set unless its being so follows from a finite number of applications of the basis and inductive clauses.

Example 2: Let W denote the set of well-formed parentheses. It can be defined inductively as follows:

Basis clause: [ ] ∊W

Inductive clause: if x, y ∊W, xy∊ W and [x] ∊W

External clause: No object is a member of W unless it’s being so follows from a finite number of applications of the basis and the inductive clauses.

A set A is a subset of a set B if each element of A is also an element of B and is denoted by A⊆ B. We also say that A is included in B. If A is a subset of B and A is not same as B, then we say that A is a proper subset B and is denoted by A⊂ B. φ is a subset of every set. Two sets A and B are equal if every element of A is also an element of B and vice versa. We denote equal sets by A = B.

Two sets can be combined to form a third set by various set operations. They are union, intersection, and difference. The union of two sets has as elements, the elements of one of the two sets and possibly both. Union is denoted by the symbol ∪ so that A ∪ B = {x|x∊ A or x ∊ B}.

The intersection of two sets is the collection of all elements of the two sets which are common and is denoted by ∩. For two sets A, B, A ∩ B = {x|x∊ A and x ∊ B}.

The difference of two sets A and B denoted by A − B is the set of all elements that are in the set A but not in the set B. For the sets A and B, A − B = {x|x∊ A and x ∉ B}.

Let U be the universal set and A ⊆ U. The complement of A with respect to U is defined as Ā = U − A.

The power set of set S is the set of all subsets of S and is denoted by. If S = {a, b, c} then,

= {φ, {a}, {b}, {c},{a, b},{b, c}, {a, c}, {a, b, c}}.

Finite and Infinite Set:A finite set contains finite number of elements. The size of the set is its basic property. The set which is not finite is said to be infinite. Two sets A and B have equal number of elements, or is said to be equinumerous if there is a one-to-one, onto function f: A → B. In general, a set is finite if it is equinumerous with the set {1, 2, 3, ..., n} for some natural number n. A set is said to be countably infinite if it is equinumerous with N, the set of natural numbers. A set which is not countable is said to be uncountable.