Chapter-i Set Theory

Chapter-I SET THEORY Contents: 1.1

Introduction to Set theory

1.2

Operation on Sets

1.3

Types of Sets 1.4

1.5

Venn Diagrams

Fundamental Laws of Set Operation

SET THEORY 1.1 Introduction to Set theory: Set theory lies at the foundation of all modern mathematics. It gives a very general framework in which almost every branch of mathematics can be discussed.A set is a collection of objects, numbers, ideas, etc. The different objects are called the elements or members of a set. Each element of a set can be listed, or they may be represented using builder notation. Give some examples of sets below. V = {a, e, i, o, u} A = {5, 10, 15, 20, ...} C = {x | x ∈N, 0 < x ≤ 1000} P is the set of all students in Math Studies. Numerical Sets :So what does this have to do with math? When we define a set, all we have to specify is a common characteristic. Who says we can't do so with numbers? Set of even numbers: {..., -4, -2, 0, 2, 4, ...} Set of odd numbers: {..., -3, -1, 1, 3, ...} Set of prime numbers: {2, 3, 5, 7, 11, 13, 17, ...} Positive multiples of 3 that are less than 10: {3, 6, 9} And the list goes on. We can come up with all different types of sets. There can also be sets of numbers that have no common trait, they are just defined that way. For example: {2, 3, 6, 828, 3839, 8827} {4, 5, 6, 10, 21} {2, 949, 48282, 42882959, 119484203} Are all sets that I just randomly banged on my keyboard to produce.

Basic symbols: , \in : belongs to , \not\in : does not belong to

, @ : empty set U,

: universal set , \subset : proper subset

, \not\subset : not a proper subset , \subseteq : subset , \not\subseteq : not a subset , \cup : set union Ai , \cup(i=1 to n) A_i : union of n sets , \cap : set intersection Ai , \cap(i=1 to n) A_i : intersection of n sets , \bar A : complement of set A (A) , P(A) : power set of set A

, X : Cartesian product Ai , X(i=1 to n) A_i : cartesian product of n sets 1.2 Operation On Sets: Union: The union of sets A and B, denoted by A U B , is the set defined as A

B={x|xєA

xєB}

Example 1: If A = {1, 2, 3} and B = {4, 5} , then A

B = {1, 2, 3, 4, 5} .

Example 2: If A = {1, 2, 3} and B = {1, 2, 4, 5} , then A

B = {1, 2, 3, 4, 5} .

Note that elements are not repeated in a set. Intersection: The intersection of sets A and B, denoted by A A

B={x|xєA

B , is the set defined as

xєB}

Example 3: If A = {1, 2, 3} and B = {1, 2, 4, 5} , then A Example 4: If A = {1, 2, 3} and B = {4, 5} , then A

B = {1, 2} .

B=Ø

Difference: The difference of sets A from B , denoted by A - B , is the set defined as A-B={x|xєA

x B}

Example 5: If A = {1, 2, 3} and B = {1, 2, 4, 5} , then A - B = {3} . Example 6: If A = {1, 2, 3} and B = {4, 5}, then A - B = {1, 2, 3}. Note that in general A - B ≠ B - A Complement: For a set A, the difference U - A, where U is the universe, is called the complement of A and it is denoted by . Thus is the set of everything that is not in A. Example 7: Suppose U = set of positive integers less than 10, And A = {1, 2, 5, 6, 7}

Then, = {3, 4, 8, 9,} The fourth set operation is the Cartesian product we first define an ordered pair and Cartesian product of two sets using it. Then the Cartesian product of multiple sets is defined using the concept of n-tuple. Ordered pair: An ordered pair is a pair of objects with an order associated with them. An ordered pair is defined in terms of sets as follows: = {{a}, {a, b}}. Similarly an ordered n-tuple can be defined as = { { a1 }, { a1, a2 }, ... , { a1, a2, ..., an } }. Two ordered pairs and are equal if and only if a = c and b = d. For example the ordered pair <1, 2> is not equal to the ordered pair <2, 1>. Cartesian product: The set of all ordered pairs , where a is an element of A and b is an element of B, is called the Cartesian product of A and B and is denoted by A×B .The concept of Cartesian product can be extended to that of more than two sets. First we are going to define the concept of ordered n-tuple. Ordered n-tuple: An ordered n-tuple is a set of n objects with an order associated with them (rigorous definition to be filled in). If n objects are represented by x1, x2, ..., xn, then we write the ordered n-tuple as <x1, x2, ..., xn> . Cartesian product: Let A1, ..., An be n sets. Then the set of all ordered n-tuples <x1, ..., xn> , where xi є Ai for all i, 1 ≤ i ≤ n , is called the Cartesian product of A1, ..., An, and is denoted by A1×...×. An . Equality of n-tuples: Two ordered n-tuples <x1, ..., xn> and are equal if and only if xi = yi for all i, 1 ≤ i ≤ n . For example the ordered 3-tuple <1, 2, 3> is not equal to the ordered n-tuple <2, 3, 1>. 1.3 Types Of Sets: 1.Finite Set –has a finite number of elements; you could list all elements in the set. Example: (a) A = {x:x is the river in India} (b) C = {2, 4, 6, 8, .... ,1000000} 2.Infinite Set – has infinitely many members; you could not list all elements in the set Example: (a) Z = {-1, -2, -3, -4, ... }

(b) B = {all real numbers between 2 and 5} Hint: Infinite sets are those which include all R, Q, or Q’ between two values or end with ... 3.Null or Empty Set – the set with no elements; { } or ∅ Example: D = {x:x 2 = 5 and x is an integer} = ∅ , since there is no integer whose square is 5 The null set is a subset of every set, including the null set itself. 4.Equality of Set – Two sets are equal if they have precisely the same members. Now, at first glance they may not seem equal, you may have to examine them closely! And the equals sign (=) is used to show equality, so we would write: A=B More formally, for any sets A and B, A = B if and only if

x[xєA

xєB].

Thus for example {1, 2, 3} = {3, 2, 1}, that is the order of elements does not matter, and {1, 2, 3} = {3, 2, 1, 1}, that is duplications do not make any difference for sets. 5. Equivalent Sets–Two sets are equivalent if it is possible to pair off members of the first set with members of the second, with no leftover members on either side. To capture this idea in settheoretic terms, the set A is defined as equivalent to the set B (symbolized by A ≡ B) if and only if there exists a third set the members of which are ordered pairs such that: (1) the first member of each pair is an element of A and the second is an element of B, and (2) each member of A occurs as a first member and each member of B occurs as a second member of exactly one pair. Thus, if A and B are finite and A ≡ B, then the third set that establishes this fact provides a pairing, or matching, of the elements of A with those of B. Conversely, if it is possible to match the elements of A with those of B, then A ≡ B, because a set of pairs meeting requirements (1) and (2) can be formed Example: Let A= {a, b, c, d} and B= {1, 2, 3, 4} be two sets. Clearly A is not equal to b. However, the elements of A can be put into one-to-one correspondence with those of B, therefore we write A ≡ B.

6.Subset –If every member of set A is also a member of set B, then A is said to be a subset of B, written A ⊆ B (also pronounced A is contained in B). Equivalently, we can read as B is a superset of A, B includes A, or B contains A. The relationship between sets established by ⊆ is called inclusion or containment.

If all the members of a set M are also members of a set P, then M is a subset of P: M ⊆ P . *Note: M could be exactly the same as P. Example (a) If A = 1,2 and B = −2,−1,0,1,2 and C = −2,−1,0,1,2 then. A⊆ B A⊆ C C⊆B A⊆ A

{ }

{

}

{

}

(b) Every set has at least two subsets, itself and the null set. List all the subsets of a, b, c . Use proper notation

{

}

7.Proper Subsets– If all the members of a set M are also members of a set P and M is a smaller set than P, then M is a proper subset of P: M ⊂ P . Example: {1, 2, 3} is a subset of {1, 2, 3}, but is not a proper subset of {1, 2, 3}.On the contrary, {1, 2, 3} is a proper subset of {1, 2, 3, 4} because the element 4 is not in the first set. 8. Power set– The set of all subsets of a set A is called the power set of A and denoted by 2A or (A). Example: (a) A = {1, 2}, (A) = {Ø, {1}, {2}, {1, 2} } . (b) B = {{1, 2}, {{1}, 2}, Ø } , (B) = { Ø, {{1, 2}}, {{{1}, 2}}, { Ø }, { {1, 2}, {{1}, 2 }}, { {1, 2}, Ø }, { {{1}, 2}, Ø }, {{1, 2}, {{1}, 2}, Ø } } . 9.Universal Set–The set which contains all the available elements for a particular problem. The complement of a set A is defined to be the set of all elements of the universal set which are not in A. Note that A U Ac is always the universal set, while A

Ac = Ø

The set U is the superset of every set 10. Family of Sets– a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets.

Example: If A = {1, 2} then the set {Ø, {1}, {2}, {1, 2}} is the family of sets whose elements are subsets of the set A. 1.4 Venn Diagrams: Venn diagrams are used to represent sets. Here, the set A{1, 2, 4, 8} is shown using a circle. In Venn diagrams, sets are usually represented using circles. The universal set is the rectangle. The set A is a subset of the universal set and so it is within the rectangle.

The complement of A, written Ac, contains all events in the sample space which are not members of A. A and Ac together cover every possible eventuality.

A ∪B means the union of sets A and B and contains all of the elements of both A and B. This can be represented on a Venn Diagram as follows:

A∩B means the intersection of sets A and B. This contains all of the elements which are in both A and B. A∩B is shown on the Venn Diagram below:

An important result connecting the number of members in sets and their unions and intersections is: •

n(A) + n(B) - n(A∩ B) = n(A∪B)

1.5 Fundamental Laws of Set Operation : i.

Identity Laws AUØ= A A

ii.

U= A

Domination Laws AUU= U A

iii.

Ø= Ø

Idempotent Laws AUA= A A

iv.

A= A

Commutative Laws AUB=BUA A

v.

B=B

A

Associative Laws (A U B) U C = A U (B U C) (A

B)

C= A

(B

C)

vi.

Distributive Laws A U (B A

C) = (A U B)

(B U C) = (A

(A U C)

B) U (A

C)

Proof: x ε A U (B ∩ C) x ε A or x ε (B ∩ C) x ε A or (x ε B and x ε C) (x ε A or x ε B) and (x ε A or x ε C) x ε (A U B) and x ε (A U C) x ε (A U B) ∩ (A U C) Hence: A U (B ∩ C) = (A U B) ∩ (A U C) Similarly, the second distributive law can also be proved. vii.

De Morgan's Laws a. Complement of the intersection of two sets is the union of their complements, i.e.

Proof:

or or

Therefore b. Complement of the unions of two sets is the intersection of their complements, i.e.

Proof: same as above