Chapter 2 set theory relations and functions ppt

Post to:

Description
Chapter 2 set theory relations and functions

Type: ppt

Discussion
Presentation Transcript

PowerPoint Presentation : Sets : A set is a collection of objects. The three objects shown above constitute a set, there may be a purpose of building it or not. The objects may be similar or different. A carpenter’s tool box is a set. All presidents of India is a set. The objects in a particular set must be well defined . The set of tall boys in the class is not a set, the question ‘how tall’ would answer that. But the concept of ‘set’ is quite fundamental and commonly understood but undefined. Attempt to define the concept ‘set’ ends in ‘Russell's paradox’ explained next. Set theory, Relations, Functions A set of three objects : man, tortoise and asteroid.

PowerPoint Presentation : Russell’s Paradox : There was only one barber in a village , who shaved those who did not shave themselves and only those. Can you tell whether the barber shaved ‘himself’ or not ? Suppose he shaved himself. But he shaved those who did not shave themselves. So he won’t shave himself ! Suppose he did not shave himself. But he shaved those who did not shave themselves. So he would shave himself ! Either way we have reached a logical contradiction. The given statement is not sufficient to draw such conclusion. In short, there should have been no statement like this at all. Set theory, Relations, Functions Set of {B Russell, A. Einstein , G W Craver, G B Shaw, L W Churchill }

PowerPoint Presentation : Undefined concepts : The Russell’s paradox arises out of our attempt to define the concept of ‘set’. It is a well understood term , fundamental and undefined. Every discipline has some such undefined concepts; in terms of which we define other concepts to build a theory or a model. If you say your house is in front of mine and my house is in front of yours – does that make a valid reference? If we define a point as intersection of two straight lines and a straight line as the locus of a point in a fixed direction, that is lousy logic. One must ‘assume’ one of them and define the other in terms of that. Never-the-less, members of a set must be well defined. Set theory, Relations, Functions George Cantor Zermello Hilbert Dedikind Gödel Founders of set theory

PowerPoint Presentation : A child recognizes people and things before learning to speak and counting. So set theory is known to babies. Sets are not only numbers like the set of odd integers = {1,3,5,7,9,11,….} or the set of even integers = {0,2,4,6,8,10….}, it may contain a description like the closed interval[0,1] which contains every number between 0 and 1, including themselves. A set may not contain any member whatsoever. It is called a ‘ null set’ and is given a symbol φ = { }; containing no member at all. For example , the set of integers between 4 and 5 is a null set, a number more than 8 and less than 5 is a null. A null set is a ‘ subset ’ of every set. Does it contain the number 0? No. It serves as an identity in every set – It does not change any subset by union. Set theory, Relations, Functions Hadamard Hurwitz Borel Baire Lebesgue Riemann Venn Founders of set theory

Venn Diagrams, Operations on sets : Venn Diagrams, Operations on set s General operations on sets are shown above, irrespective of whether the sets have a structure or not. A = Set A, B = Set B, C = A  B,( union ) D = A  B ( intersection ), E = A – B ( difference) , F = B – A ( difference ), G = (A – B )  (B – A) = A ∆ B called symmetric difference of A and B. Venn Diagrams easily exhibit simple proofs of statement or its negation. Problem : Show that A ∆ B = (A  B) – (A  B ) Union and intersection operations are commutative, associative and distributive. A  B= B  A, A  (B  C)= (A  B)  C, A  (B  C)= (A  B )  (A  C) A  B= B  A, A  (B  C)= (A  B)  C, A  (B  C)= (A  B )  (A  C) Prove by making Venn diagrams.

PowerPoint Presentation : Set theory, Relations, Functions Set U A set B is a subset of A which is subset of universal set U. In the left figure, A  B. If A  B and B  A then A = B. This is a standard technique of proving equality of two sets, differently described. A set U is called universal set all other sets in consideration are its subsets. The green portion on the right side figure is complement of set A in the universal set U , denoted as A’ = U – A . Thus (A’)’ = A. De Morgan’s laws : (A  B)’ = A ‘  B’ , (A  B)’ = A ‘  B’ .(Replace A by A’ and B by B’. The set of all subsets of A is called power set of A, P(A). If A has n members, then P(A) has 2 n members . Apply binomial expansion (1+1) n = n C 0 + n C 1 + n C 2 …..+ n C n . Set B Set A set A Augustus De Morgan George Boole

Relations : Relations one to one mapping 1 many to one mapping 1 one to many mapping 1 many to many mapping 1 Sets are building blocks of symbolic logic and Mathematics, in turn. Sets are merely collection of objects; some may have some purpose or other. Some may have some structure built into them or no structures. For example , the set of aces or spades are ordered sets. A family of elephants have a definite social hierarchical structure. We would study the structured sets in advanced courses, such as groups, rings, fields, vector spaces , topologies etc. Modern mathematics such as algebra, analysis, differential equations, topology and functional analysis etc. study the structured sets for problem solving in different environments and apply the knowledge to other fields such as physics, economics, biology and medicine etc. Before studying structures in sets, we have to relate members of one set to members of a reference set, say for example, listing, labeling, indexing or simply counting a set with the help of a reference set. Not only there are infinite sets, that there are uncountable sets too. Correlating members of a set with members of another is called a relation, or mapping. Between two sets, there may be one-to-one, one-to-many, many-to-one or many-to-many relations (mappings). (see figures above).

Relations : Relations one to one mapping 1 many to one mapping 1 one to many mapping 1 many to many mapping 1 A Cartesian product of a set A = {1, 2, 3} and B = {a, b, c, d} is given by all ordered pairs (x, y) : x ϵ A and y ϵ B ( ϵ stands for belongs to) and is denoted by A X B = { (1, a),(1, b), 1, c),(1, a),(1, d),(1, a),(2, a),(2, b),(2, c),(2, d),(3, a),(3, b),(3, c), (3, d)} Any subset of the Cartesian product is a relation e.g. A R B ={(1, d), (1, a), (2, a), (2, b), (2, c), (2, d), (3, a)}, members are 1Rd, 2Rc etc. Only listing or exhibiting the ordered pairs defines the relation, stating ‘relationship’ between the members of the ordered pair is not necessary. This is the difference between ‘relation ‘and relationship. If B is exhausted in mapping the relation, the relation is called onto otherwise it is an into relation. Every relation R has an inverse relation R -1 : B →A such that bR -1 a ⇔ aRb . Binary relation is a special type of relation from A X A into A, or from A X A onto A. Binary relations are building blocks of symbolic logic. Another important relation is equivalence relation. The two sets under this relation are structurally same and can be replaced by each other in many circumstances. For example, the set of natural numbers are equivalent to the set of even positive integers . Consider the mapping 1 →2, 2→4, 3→6, 4→8, 5→10, 6→12, 7→14, ……….etc. is an equivalence relation.

PowerPoint Presentation : Equivalence Relations: An equivalence relation must be “ relexive ” e.g. if aRb means a is a factor of b, then a is also a factor of a, i.e. aRa is true. An equivalence relation must be “symmetric” e.g. if aRb means a is a similar to b, then b is also similar to a, i.e. bRa is true. An equivalence relation must be “transitive” e.g. if aRb means a > b, and also if b > c , then this would imply a > c . Find out a3 relations which do not satisfy the above criteria one by one. Let us call aRb if a and b both leave the same remainder when divided by 7. So 0R7, 0R14, 0R21, etc, 1R8, 1R15, 1R 22 etc, 2 R 9, 9R16,16R 23, etc. verify that this is an equivalence relation by showing that all the above conditions are satisfied. Verify that it satisfies each of the 3 criteria as above , thus an equivalence relation. Call [0] ={0, 7, 14, 21….}, [1] = {1, 8, 15, 22….}, [2] = {2, 9, 16, 23….} and [3] = {3, 10, 17, 24……} .The entire set of integers are partitioned into equivalence classes [1], [2], [3], [4], [5], [6], [0] . Does every equivalence relation partitions the set into equivalence classes? Yes. Partition and equivalence relation are not two but one single concept seen from two different points of views or built out of two different approaches. The sets of natural numbers and integers are equivalent. Any set equivalent to the set of natural numbers is said to be countable.

PowerPoint Presentation : A O B C D P Q For each in the st line AB there is one and only one point in CD and vice versa. Equivalence Relations: P Q Q ’ R R ’ The Euler’s circle For each point on the st line, there is one and only one point on the circle and vice versa. A set, which is equivalent to a proper subset of it, must be infinite!

Relations : Relations one to one mapping 1 many to one mapping 1 one to many mapping 1 many to many mapping 1 A one- toone or many-to-one mapping or a relation between two sets 9not necessarily diferent ) is called a function. One-to-many or many-to-many relations are excluded from the perview of functions of real numbers, A real valued function is one whose range ( the second set) must be a subset of real numbers. Such functions must be “ single valued’ i.e. must be either one-to-one or many-to-one relations. For example y = f(x)= mx +c can be a real valued function putting y = f(x). The domain , i.e., the first set is freely chosen to be anything. The function y in x 2 + y 2 = 25 is an implicit real valued function of x (f(x)) if the domain is restricted to the set of positive numbers. ( implicit because y is not expressed explicitly in terms of x. ( you can see that for a given value of x, the y ,the image of x can take two values as well, x is called inverse image of y).. Single valued- ness is required for analysis of real valued functions. But multiple valued functions are of course allowed in cases the range is a set of complex number. A function of natural numbers is called a sequence, e.g. the sequence 3, 6, 9, 12, 15,18,…… can be written as f(1)= 3, f(2)= 6, f(3)= 9, f(4)= 12, f(5)= 15, etc.