Elementary Set Theory - CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Introduction

Most, if not all, of pure mathematics is couched in the language of sets. You may notice that this section contains many definitions and only a few theorems. However, even a definition can contain a lot of mathematical wisdom. It took mathematicians centuries to formulate some fundamental definitions.

1. Set

A set is a collection of items considered as a whole.

If there are only a few items, the set can be defined by listing them in braces. The relationships among sets are often represented pictorially by a Venn diagram, in which sets are represented as the interiors of overlapping circles (or other plane figures).

Example: the set A is defined as A = {1, 5,6,7,8,9,10,12} and the set B is defined as B = {2,3,4,6,7,9,11,12,13}. The sets A and B are shown in the venn diagram in the image below.

• The items in a set are called elements or members of the set. They are also said to belong to the set or to be in the set, and the set is said to contain them. The symbol ∈ is used to express the relationship 'belongs to' that is,  a ∈ A means 'a belongs to A', and a∉ A means 'a does not belong to A.'
• Two sets are equal if they contain exactly the same elements. That is, set A is equal to set B if every element of A is also an element of B, and every element of B is also an element of A. The order in which the elements of a set are listed in its definition is irrelevant.
  Example: the sets {1,2,3} and {3,2,1} are equal.
• An element cannot belong to a set more than once. Therefore, when a set is defined by listing its elements, each element is listed only once.

Types of Sets 

(i) Empty Set: A set that contains no elements is called the Empty set, and is represented by the symbol ∅.

(ii) Subset: If every element of the set A is also an element of the set B, then A is said to be a Subset of B, represented symbolically by A⊆ B, or B is said to include A. Every set is a subset of itself, and the empty set is a subset of every set. For example, in the diagram given below set A = {1, 2, 3} and set B = {1, 2, 3, 4, 5}. Now set A consists of elements 1, 2, and 3 which are elements of set B, hence set A is the subset of set B.

In the image, A is the subset of B.

(iii) Proper Subset: If A⊆ B and there is at least one element of B that is not an element of A, then A is said to be a Proper subset of B, represented symbolically by A⊂ B.

A subset is often defined by some property of its elements.

Example: Let A = {1,2,3,4,5,6}, and let B = {2,4,6}. Here B is the proper subset of A. Then B could be defined as the set of all elements of A which are even, or in symbols:
B ={x∈ A | x is even}.
Here the symbol | means "such that". 

Question: Write the solution set of the equation x² – 4=0 in roster form.

Solution:  Find the solution of x² – 4.
x² – 4 = x² – 2² = (x-2) (x+2)

x=2,-2

Thus, A = {-2,2}

Question: Write the set A = {1, 4, 9, 16, 25, . . . } in set-builder form.

Solution: If we see the pattern here, the numbers are squares of natural numbers, such as:

1² = 1

2² = 4

3² = 9

4² = 16

And so on.

A = {x : x is the square of a natural number}

Or we can write;

A = {x : x = n² , where n ∈ N and n < 5}

Operations on Sets 

(a) Intersection

The intersection of any number of sets is the set of elements that they all have in common.

The image shows the intersection of two sets A and B.

The intersection operation has several properties:

• Commutativity: As per the commutative property of the intersection of sets, the order of the operating sets does not affect the resultant set and thus A∩B equals B∩A.  For example,for the sets P = {a, b, c, d, e},and Q = {a, e, i}, P∩Q = {a,e} and Q∩P = {a.e}. Thus, P∩Q = Q∩P. 
• Associativity: As per the associative property of the intersection of sets, the order of the three operating sets does not affect the resultant set and thus (A∩B)∩C equals A∩(B∩C).  For example,for the sets P = {a, b, c, d, e}, Q = {a, e, i} and R = {g,h, a}, (P∩Q)∩R = {a} and P∩(Q∩R) = {a}. Thus, (P∩Q)∩R = P∩(Q∩R).
• A∩B = A if, and only if, A⊆ B. For example, A = {4, 7, 8}, B = {3, 4, 5, 6, 7,8} and A∩B = {4, 7, 8}. As A⊆ B, that is why A∩B = A.

The union of any number of sets is the set of all of their elements

The image shows the union of two sets A and B.

The union of any number of sets is the set of all of their elements. For example the union of {1,2,3,4,5}, {2,3,4,5,6,7,8,9} and {3,5,7,9} is {1,2,3,4,5,6,7,8,9}. It is clear that every set in a union is a subset of their union. The union of two sets A and B is represented symbolically by A∪ B.

The union operation has several obvious properties:

• Commutativity: As per the commutative property of the union of sets, the order of the operating sets does not affect the resultant set and thus A∪B equals B∪A.  For example,for the sets P = {a, b, c, d, e},and Q = {a, e, i}, A∪B = {a, b, c, d, e, i} and B∪A = {a, b, c, d, e, i}. Thus, A∪B = B∪A. 
• Associativity:  As per the associative property of the union of sets, the order of the three operating sets does not affect the resultant set and thus (A∪B)∪C equals A∪(B∪C).  For example,for the sets P = {a, b, c, d, e}, Q = {a, e, i} and R = {g,h, a}, (P∩Q)∩R = {a} and P∩(Q∩R) = {a}. Thus, (P∩Q)∩R = P∩(Q∩R).
• A∪B = B if, and only if, A⊆ B. For example, A = {4, 7, 8}, B = {3, 4, 5, 6, 7, 8} and A∪B = {3, 4, 5, 6, 7, 8}. As A⊆ B, that is why A∪B = A.

Question: If A = { 2, 4, 6, 8} and B = { 6, 8, 10, 12}. Find A ∪ B.

Solution: A ∪ B = { 2, 4, 6, 8, 10, 12}

Question: If A = { 2, 4, 6, 8} and B = { 6, 8, 10, 12}. Find A ∩ B.

Solution: A ∩ B = { 6, 8 }

(c) Disjoint

Two sets are said to be disjoint if they have no elements in common; i.e., A and B are disjoint if A∩B = ∅.

• Three or more sets are said to be disjoint if every two of them are disjoint. 
• The notation A-B is used to indicate the set of all elements of A that are not elements of B.

(d) Complement

The complement of a set is the set that includes all the elements of the universal set that are not present in the given set.

• The complement of any set is represented as A', B', C' etc. In other words, we can say, if the universal set is (U) and the subset of the universal set (A) is given then the difference of universal set (U) and the subset of the universal set (A) is the complement of the subset, that is A' = U - A. 
• Example: If the universal set is all prime numbers up to 25 and set A = {2, 3, 5} then the complement of set A is other than the elements of A. Now, U = {2, 3, 5, 7, 11, 13, 17, 19, 23} and A = {2, 3, 5}. Then compliment of A' = (U - A). Therefore, A' = {2, 3, 5, 7, 11, 13, 17, 19, 23} - {2, 3, 5} = {7, 11, 13, 17, 19, 23}

Venn diagrams of operations are shown below in the diagram:

Questions: If U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and A = {1, 3, 5, 7, 9}. Find A′.

Solution: A′ = { 2, 4, 6, 8,10 }

2. Ordered Pairs

• An ordered pair is a set of two elements in a specified order. An ordered pair is usually written (a,b) where a is the first element and b is the second element. Two ordered pairs (a,b) and (c,d) are equal if a=c and b=d. Reversing the elements of an ordered pair produces a different ordered pair if the elements are not the same.
  Example: The ordered pair (1,2) is not equal to the ordered pair (2,1).
• For two sets A and B, the cross product A⨯ B is the set of all ordered pairs whose first and second elements are elements of A and B, respectively. That is, A⨯B = {(a,b) ∣ a∈ A and b∈ B}. For example, if A = {1, 2} and B = {3, 4, 5}, then the Cartesian Product of A and B is {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}.  
• Ordered triples, quadruples, etc. could be defined, but they are seldom needed.
  
  Question for Elementary Set Theory - CSIR-NET Mathematical Sciences

  Try yourself:The shaded area of figure is best described by?
  

  • A.

    A‘ (Complement of A)
  • B.

    A U B - B
  • C.

    A ∩ B
  • D.

    B

  Explanation

  The shaded region is B compliment which is equal to the option B.

  Report a problem

  Cancel Report

  View Solution

3. Relations

A relation from a set A to a set B is a subset of A×B. Hence, a relation R consists of ordered pairs (a,b), where a∈A and b∈B. If (a,b)∈R, we say that is related to , and we also write aRb.

This image shows the mapping of a relation from set A into set B. A relation from A to B is a subset of A x B. The ordered pairs are (1,c),(2,n),(5,a),(7,n) 

• A relation R on a set A is simply a set of ordered pairs of elements of A, i.e., R ⊆ A⨯ A. Two elements a and b are said to obey the relation if (a,b) is in R. 
• However, for most relations, the set notation is not used. Instead, a symbol such as ~ placed between the elements to indicate that they obey the relation; for example a~b means that (a,b) is in R.
• Other symbols often used for relations are: = > < ≥ ≤ ∣ ≠ ⊃ ⊂ ⊇ ⊆ ≡
• Most useful relations have some additional properties. A relation ~ on the set A is an equivalence if the following hold for every a, b and c in A:
  1. It is reflexive: a~a.
  2. It is symmetric: a~b implies that b~a.
  3. It is transitive: a~b and b~c imply that a~c.

A set of nonempty subsets of a set A is called a partition of A if each element of A belongs to one and only one of the subsets; i.e., if the subsets are disjoint and their union is A. The following theorem establishes a connection between an equivalence relation and a partition.

Theorem 3.1. If ~ is an equivalence relation on the set A, then there is partition of the set A such that a~b if, and only if, a and b belong to the same set in the partition. Conversely, if P is a partition of A, then "a and b belong to the same set in P" is an equivalence relation.

Proof. Consider the set P of subsets T_a = {x ∈ A | x~a}. Clearly every a in A belongs to at least one subset in P, namely T_a. Hence the sets in P are nonempty and their union is A.

Now let T_a and T_b be two subsets in P. If they have an element c in common, then c~a, c~b and x~b for every x ∈ T_b. By transitivity x~a and x ∈ T_a, too. Similar arguments show that every element of T_a is also an element of T_b. Hence T_a and T_b are equal. If two subsets in P have no element in common, they are disjoint. Hence P is the desired partition.

The converse is trivial.

The sets in the partition associated in this way with an equivalence relation are called its equivalence classes. They are often used to define mathematical systems.

Equivalence relations on two sets A and B can be used to define an equivalence relation on A⨯ B in the obvious way: (a,b) is equivalent to (c,d) if a is equivalent to c and b is equivalent to d.

4. Order

A partial order on a set A is a relation ≤ with the following properties for every a, b and c in A:

• It is reflexive: a ≤ a.
• It is antisymmetric: a ≤ b and b ≤ a imply that a = b.
• It is transitive: a ≤ b and b ≤ c imply that a ≤ c.

A partial order ≤ on the set A is called a linear order (or a total order) if, for every two elements a and b of A, a ≤ b or b ≤ a (or both, if a = b).

The set of all subsets of a set is partially ordered by inclusion: S ≤ T means S⊆ T. This partial order is usually not a total order because we can find two subsets, such as {1,2,3} and {2,3,4}, such that neither is a subset of the other.

The familiar relation ≤ in arithmetic is a total order.

In working with a partial or total order, it is common to define some associated relations:

• a ≥ b means b ≤ a,
• a < b means a ≤ b and a ≠ b,
• a > b means b ≤ a and b ≠ a.

There is an alternative way to define partial and total orders. A relation < is a partial order if obeys the following two conditions:

• It is transitive: a < b and b < c imply that a < c.
• a < a is always false.

A partial order is a total order if it is also trichotomous. For any two elements a and b, one and only one of the following holds:

• a < b,
• a = b,
• b < a.

The other relations are then defined in terms of <:

• a ≤ b means a < b or a = b.
• a ≥ b means b < a or a = b.
• a > b means b < a.

It can be shown that the two ways of defining partial and total orders are equivalent.

Generally, the names "partial order" and "total order" are applied to the entire set of relations ≤, <, > and ≥ without specifying which is the order relation and which are associated with it.

5. Functions

A function f from the set A to the set B is a rule which, given any element x of A, produces exactly one corresponding element of B represented by f(x). This concept is often expressed symbolically as f: A⟶B.

• Mapping: A function is also called a mapping. Both names are commonly used in mathematics, but from this point forth we will use the name function.
• A second, and more abstract, way to define a function f:A⟶B is as subset of A ⨯ B such that for every element x of A there is one and only one ordered pair in the subset whose first element is x. The second element of the pair is then defined to be f(x).
• Image: The element f(x) is called the image of x under the function. The function f is also said to map or carry the element x to the element f(x).
• Domain: If f:A⟶B then A is called the domain of f, and the set of all elements of B which are images of elements in A is called the range of f. The sets A and B need not be different; in fact, they are the same in many applications.

Types of Functions based on Set Elements

• Surjection: If the function f: A⟶B, is such that each element in B (co-domain) is the image of at least one element in A, then we say that f is a function of A ‘onto’ B. Thus, f: A⟶B such that f(A) = B i.e., Range = Co-domain. The function is sometimes also said to be "onto", but the use of a preposition as an adjective sounds so stilted that good writers tend to avoid it. 
• Into Function: Into function is exactly opposite in properties to an onto function. Here there are certain elements in the co-domain that do not have any pre-image. The elements in set B are excess and are not connected to any elements in set A.
• Injective Function or One-to-One Function: A one-to-one function is defined by f: A → B such that every element of set A is connected to a distinct element in set B. The one-to-one function is also called an injective function. Here every element of the domain has a distinct image or co-domain element for the given function.
• Many to One Function: A many to one function is defined by the function f: A → B, such that more than one element of the set A are connected to the same element in the set B. In a many to one function, more than one element has the same co-domain or image. If a many to one function, in the codomain, is a single value or the domain element are all connected to a single element, then it is called a constant function. 
• Bijection: A function that is both a one and onto function is called a bijective function. Here every element of the domain is connected to a distinct element in the codomain and every element of the codomain has a pre-image. Also in other words every element of set A is connected to a distinct element in set B, and there is not a single element in set B which has been left out.
  
• Inverse: If f: A⟶B is a one-to-one correspondence then it has an Inverse function called f ^-1:B⟶ A defined by f ^-1(x) = the element w of A such that f(w) = x. Of course, the converse is also true. If a function has an inverse, then it is a one-to-one correspondence.
• Two functions f:A⟶ B and g:A⟶ B are equal if f(x) = g(x) for every x in A.
  
  Question for Elementary Set Theory - CSIR-NET Mathematical Sciences

  Try yourself: A function is said to be ______________ if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f.

  • A.

    One-to-many
  • B.

    One-to-one
  • C.

    Many-to-many
  • D.

    Many-to-one

  Explanation

   A function is one-to-one if and only if f(a)≠f(b) whenever a≠b.

  Report a problem

  Cancel Report

  View Solution

Composite Function

If the range of one function is a subset of the domain of another, then a composite function is defined by applying the functions successively.

That is,
If f:A⟶B and g:B⟶C then the composite function (f◌g):A⟶C is defined by

• (f ◌g)(x) = f(g(x)) for every x in A.

If the functions have appropriate domains and ranges, composition is associative

• (f ◌g) ◌h = f ◌(g ◌h).

Isomorphism and Automorphism

Isomorphism: A one-to-one function f:A⟶B of two sets with some structure is called an isomorphism if it preserves the structure.

• We have seen one example of a set with structure: the partially ordered set. If the sets A and B are partially ordered, then f:A⟶B is an isomorphism if it is one-to-one, surjective, and f(x) < f(y) if, and only if, x < y.

Automorphism: An isomorphism of a structured set with itself is called an automorphism. Clearly, the identity function (f(x) = x for all x) is an automorphism of any structured set. 

• A good example of a nontrivial automorphism is the function which carries a complex number into its conjugate (i.e,. f(x+iy) = x-iy for all real x and y). It is one-to-one, surjective, and preserves addition and multiplication of complex numbers.

6. Operations

• A unary operation on a set is a function whose domain is that set. What distinguishes a unary operation from an ordinary function is the notation used, and often its relationships with other functions or operations.
  Example: The function that carries any real number x to the number -x is a unary operation called negation. The range of the function is often the same set, but this is not required.
• A binary operation is a function whose domain is the cross product of two sets (or the cross product of a set with itself).
  Example: Addition and multiplication are two binary operations on the set R⨯ R, where R is the set of real numbers. 
• The image of an ordered pair (x,y) is usually written as x+y for addition and xy for multiplication. Here x and y are called the operands. The former notation is usually used only for addition, or operations very much like addition. The latter notation is used for more general operations.
• Unary and binary operations are very common in mathematics; operations with three or more operands are rare, except for extensions of binary operations as noted below. Binary operations on a single set are more common than binary operations on pairs of sets, but both are encountered frequently.
• A binary operation is said to be associative if it can be used on three operands without regard to their grouping, i.e., if
  (xy)z = x(yz)
   (x + y) + z = x + (y + z)
• If a binary operation is associative, we can write the result for three operands without parentheses, making it a well-defined operation with three operands:
  xyz = (xy)z = x(yz)
   x + y + z = (x + y) + z = x + (y + z)
• Ordinary addition and multiplication are associative; so are many other binary operations. The composition of functions is an associative binary operation (provided the functions have suitable domains and ranges). In fact, most binary operations are associative.
• If a binary operation is associative, it is easy to extend the property to operations on four or more operands:
  wxyz = (wxy)z = (w(xy))z = w((xy)z) = w(xyz).
• A binary operation is commutative if the order of the operands does not affect the result; i.e., if
  xy = yx
   x + y = y + x
• If a commutative operation is also associative, commutativity can easily be extended to operations on three or more operands:
  xyz = (xy)z = (yx)z = yxz = y(xz) = (yx)z = yxz, etc.
• Binary operations which are commutative but not associative are very rare. Binary operations which are associative but not commutative are fairly common. Composition of functions is one example; a demonstration of that fact will be given later.
• Now consider a binary operation on A⨯ B with its range in C (which need not be different sets). Suppose there are equivalence operations on these sets (which also need not be different), and the binary operation preserves equivalence, i.e., the operation when applied to equivalent operands gives equivalent results, or a ~ b and c ~ d imply that ac ~ bd. Then, just as a function of one variable was extended to a function on equivalence classes, an operation on two variables can be extended similarly. If a and b are any elements of the equivalence classes P and Q, respectively, then PQ is defined to be the equivalence class containing ab. The new operation inherits many properties of the old one, including associativity and commutativity.