Set theory for the Data Analysis and AI.pptx

Analysis Works

1. Fundamentals:   Set Theory

2. Use of the word set as a formal mathematical term was introduced in 1879 by Georg Cantor (1845–1918).

3. Sets: a collection of elements Why do we have to learn? Set theory is important for machine learning because  set theory may be used to represent logical rules and relationships . Logical relationships such as AND correspond to the intersection of two sets. Logical relationships such as OR correspond to the union of two sets Set  guarantees there is no duplicate object in it . Sets are well-determined collections that are completely characterized by their elements. Thus, two sets are equal if and only if they have exactly the same elements.   

4. Notations If S is a set, the notation x S means that x is an element of S. The notation x S means that x is not an element of S. set-roster notation: writing all of its elements between braces, eg . {1, 2, 3} A very large set, eg . {1, 2, 3, … , 100} An infinite set, as when we write {1, 2, 3, …} to refer to the set of all positive integers.    

5. Set-builder notation Let S denote a set and let P(x) be a property that elements of S may or may not satisfy. We may define a new set to be the set of all elements x in S such that P(x) is true. eg .    

6. Subsets If A and B are sets, then A is called a subset of B, written A B, if, and only if, every element of A is also an element of B. A B means that for every element x, if x A then x B.          

7. Which of the following are true statements? 1. 2. 3. 4.        

8. Cartesian products Given elements a and b, the symbol (a, b) denotes the ordered pair consisting of a and b together with the specification that a is the first element of the pair and b is the second element. Two ordered pairs (a, b) and (c, d) are equal if, and only if, a = c and b = d.

9. Ordered n - tuple Let be a positive integer and let be (not necessarily distinct) elements. The ordered n - tuple , ( ), consists of together with the ordering: first, then , and so forth up to .              

10. Cartesian product Given sets , the Cartesian product of , denoted , is the set of all ordered n- tuples where , ,…,              

11. Let and C = {a, b}. 1. Find 2. Find 3. Find 4. How many elements are in , and ? 5. Find 6. Find g. Let R denote the set of all real numbers. Describe .                  

12. String Let n be a positive integer. Given a finite set A, a string of length n over A is an ordered n - tuple of elements of A written without parentheses or commas. The elements of A are called the characters of the string. The null string over A is defined to be the “string” with no characters. It is often denoted and is said to have length 0. If A = {0, 1}, then a string over A is called a bit string.  

13. Let A = {a, b}. List all the strings of length 3 over A with at least two characters that are the same. aab , aba , baa, aaa , bba , bab , abb , bbb

14. Set equality Given sets A and B, A equals B, written A = B, if, and only if, every element of A is in B and every element of B is in A. Symbolically: A = B A B and B A. Define sets A and B as follows: A = {m Z| m = 2a for some integer a} B = {n Z| n = 2b-2 for some integer b}. Is A = B?        

15. Venn Diagrams A B  

16. Union union(X,Y): Union of the sets X and Y > X <- c(1,2,5) > Y <- c(5,1,8,9) > union (X,Y) #Compute the union of the set X and Y [1] 1 2 5 8 9  

17. Intersection Intersection of the sets X and Y consisting of all the elements common to X and Y > X <- c(1,2,5) > Y <- c(5,1,8,9) > intersect(X,Y ) #Compute the intersection of the set X and Y [1] 1 5  

18. Set difference setdiff (X,Y): Set difference between X and Y, consisting of all elements of X that are not in Y > X <- c(1,2,5) > Y <- c(5,1,8,9) > setdiff (X,Y) #Compute the set difference X -Y [1] 2 > setdiff (Y,X) [1] 8 9 #Compute the set difference Y -X  

19. Equality between sets setequal (X,Y): Test for equality between X and Y > X <- c(1,2,5) > Y <- c(5,1,8,9) > Z <- c(5,1,2) setequal (X,Y) [1] FALSE > setequal (X,Z) [1] TRUE

20. Membership c %in% Y: Membership, testing whether c is an element of the set Y > 2 %in% X [1] TRUE > 2 %in% Y [1] FALSE

21. Complement The complement of A, denoted , is the set of all elements in U that are not in A.   A    

22. Let the universal set be the set U = {a, b, c, d, e, f, g}, and let A = {a, c, e, g} and B = {d, e, f, g}. = {a, c, d, e, f, g} = {e, g} = {d, f} = {b, d, f }        

23. Interval notation Given real numbers a and b with a ≤ b: (a, b) = {x R | a < x < b } [a, b] = {x R | a ≤ x ≤ b } (a, b] = {x R |a < x ≤ b} [a, b) = {x R |a ≤ x < b}        

24. The symbols and are used to indicate intervals that are unbounded either on the right or on the left: (a, ) = {x R |x> a} [a, ) = {x R |x ≥a} ( ,b) = {x R |x <b} ( , b] = {x R | x ≤ b}.                    

25. Let the universal set be R, the set of all real numbers, and let A = (-1, 0] = {x R|-1< x≤ 0} and B= [0, 1) = {x [ R|0 ≤ x < 1}.     Find A B, A B, B - A, and A      

26. Disjoint sets Two sets are called disjoint if, and only if, they have no elements in common. A and B are disjoint A B=    

27. Partition of a set A finite or infinite collection of nonempty sets {A1, A2, A3, … } is a partition of a set A if, and only if, 1. A is the union of all the Ai ; 2. the sets A1, A2, A3, … are mutually disjoint.

28. Power set Given a set A, the power set of A, denoted P(A), is the set of all subsets of A.

29. Properties of Sets 1. Inclusion of Intersection: For all sets A and B, (a) A B A and (b) A B B . 2. Inclusion in Union: For all sets A and B, (a) A A B and (b) B A B. 3. Transitive Property of Subsets: For all sets A, B, and C, if A B and B C, then A C.                      

30. Set Identities Let all sets referred to below be subsets of a universal set U. 1. Commutative Laws: For all sets A and B, (a) A B =B A and (b) A B = B A. 2. Associative Laws: For all sets A, B, and C, (a) (A B) C = A (B C) and (b) (A B) C = A (B C).                      

31. 3. Distributive Laws: For all sets A, B, and C, (a) A (B C) = (A B) (A C) and (b) A (B C) = (A B) (A C). 4. Identity Laws: For every set A, (a) A =A and (b) A U = A. 5. Complement Laws: For every set A, (a) A A = U and (b) A A = .                                    

32. 6. Double Complement Law: For every set A, (A ) = A. 7. Idempotent Laws: For every set A, (a) A A = A and (b) A A = A. 8. Universal Bound Laws: For every set A, (a) A U = U and (b) A . 9. De Morgan’s Laws: For all sets A and B, (a) (A B) = A B and (b) (A B) = A B                                

33. 10. Absorption Laws: For all sets A and B, (a) A (A B) = A and (b) A (A B) = A. 11. Complements of U and : (a) U = and (b) = U. 12. Set Difference Law: For all sets A and B, A-B = A B