Understanding Sets and Functions in ICS 6D
Sets are collections of items where order doesn't matter, and functions define relationships between sets. Learn about cardinality, famous sets, set operations, subsets, and the power set in this overview. Explore examples and notations to enhance your understanding of these fundamental concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Overview of Sets an Functions for ICS 6D Prof. Sandy Irani
Sets A set is an unordered collection of items. For example, S = {a, b, c, d} Curly braces {} denote that order does not matter: {a, b, c, d} = {b, a, d, c} Each item is called an element of the set. b is an element of S (b S) e is not an element of S (e S)
Cardinality of Sets An infinite set has an infinite number of elements. Example: the set of all integers. A finite set has a finite number of elements. Example: the set of students enrolled in ICS 6D Spr 2016. If S is a finite set, then the cardinality of S (denoted |S|) is the number of elements in S. Example: S = {a, b, c, d}. |S| =
Famous Sets = the set of all integers = the set of real numbers = the set of rational numbers (A number x is rational if x = c/d, where c and d are integers and d 0.) = natural numbers (positive integers) the empty set (sometimes denoted as {})
Specifying a Set Roster notation: List the elements with curly braces {1, 3, 5, 9} List elements with an inferred pattern in ellipses {1, 3, 5, ., 99} Set builder notation {x : x S and some additional conditions on x} {x S : additional conditions on x} S is a larger set that has already been defined : is read as such that
Subsets T is a subset of S (T S): If x T then x S To show T S, Find x T and x S. Example: S = {a, b, c, d} T = {a, b, c} V = {a, e}
Set Operations Union: x A B x A x B Intersection: x A B x A x B Complement: x A (all elements and sets contained in a Universe set, usually denoted by U) (x A)
Set Operations Example U = A = { x : x is odd } B = { x : 0 < x 20 } C = {4, 5, 6, 7} B A? A B 6 A C ? C A 26 A C ? C B?
Power Set Let A be a finite set. Power set of A (denoted P(A)) is the set of all subsets of A. Example: A = {a, b, c} P(A) = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } {a, b} P(A) ? {a, b} P(A) ? a P(A) ? {a} P(A) ? { {a} } P(A) ? P(A) ? P(A) ?
Pairs, Triplets and Tuples (a, b) is an ordered pair. Parens (as opposed to {}) indicate that order matters: (a, b) (b, a) {a, b} = {b, a} (a, b, c) is an ordered triplet b is the second entry of the triplet (a, b, c) (a, b, c, d) is an ordered 4-tuple (a1, a2 , , an) is an ordered n-tuple.
Cartesian Product Let S and T be sets Cartesian product of S and T is S x T = { (s, t) : s S and t T } Example: S = {a, b, c} T = {1, 2} S x T = { (a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2) }
Cartesian Product T = {1, 2} T x T = T2 = { (1, 1), (1, 2), (2, 1), (2, 2) } T T2 ? What is x ? x ?
Cartesian Product Example: Drink = {OJ, Coffee} Main = {Waffles, Eggs, Pancakes} Side = {Hash browns, Toast} Breakfast Selections = Drink x Main x Side (OJ, Eggs, Toast) Drink x Main x Side A1, , An sets: A1x x An = { (a1, , an) : ai in Aifor 1 i n }
Cartesian Product Let S be a set: Sn= S x S x x S = { (s1, .., sn) : each siin S, for 1 i n } Example: {0, 1}5 Example: 4
N-tuples and Strings If is a set of single characters, elements in n can be denoted without the punctuation, in which case they are called strings. Example: = {a, b} (a, b, a, b) 4 (denoted as an n-tuple) abab 4 (denoted as a string) {0, 1}3 = set of all binary strings with 3 bits: {0, 1}3 = { 000, 001, 010, 011, 100, 101, 110, 111 } n-tuple punctuation is important if the underlying set is not a set of single characters!
Strings Concatenation: x = abba y = bab Concatenation of x and y is xy = abbabab Concatenation of x and a is abbaa Empty string has no characters: x = x = x The length of a string x (denoted by |x|) is the number of characters in the string: Example: |abba| = 4.
Infinite sets of strings The set of all strings of any length over an alphabet : * = 0 1 2 .. Example: {0, 1}* = { , 0, 1, 00, 01, 10, 11, 000, .} The set of all strings of any length over an alphabet : + = 1 2 3 .. Example: {0, 1}+= {0, 1, 00, 01, 10, 11, 000, .}
Functions A function maps elements of one set onto another: f: A B A is the domain A = {a, b, c, d} B is the target B = {1, 2, 3, 4, 5} 1 a 2 b A function maps each element of the domain to a unique element in the target set. 3 c 4 d 5
Functions A function maps elements of one set onto another: f: A B A is the domain A = {a, b, c, d} B is the target B = {1, 2, 3, 4, 5} 1 a 2 b The range is the set of elements y in the target for which there is an element x in the domain such that f(x) = y. 3 c 4 d 5
Functions on specified by an explicit formula f: f(x) = x2 - 4x + 3 Examples of non-functions: f(x) = x f(x) = 2/x
Functions: one-to-one A function f: D T is one-to-one if no two elements in the domain map on to the same element in the target: x D, x D, (x x ) f(x) f(x ) 1 a 1 a 2 2 b b 3 3 c c 4 4 d d 5 5
One-to-one Examples f: f(x) = x2 f: f(x) = 2x + 3 f: {0, 1}3 {0, 1}3 replace the last bit with 0, f(111) = 110 f: {0, 1}3 {0, 1}4 add a 0 to the end f(101) = 1010 A = {a, b, c} f: P(A) . For X A, f(X) = |X|
One-to-one examples f: {0, 1}3 {0, 1}2 drop the last bit f(101) = 10 000 001 00 010 01 If f: D T is one-to-one, then |D| |T| 011 10 100 11 If f: D T and |D| > |T| The f can not be one-to-one. 101 110 111
Functions: onto A function f: D T is onto if every element in the target is mapped to by some element in the domain For every y T, there is an x D, such that f(x) = y a a 1 1 b b 2 2 c c 3 3 d d
Onto Examples f: f(x) = x2 f: f(x) = 2x + 3 f: f(x) = 2x + 3 f: {0, 1}3 {0, 1}3 replace the last bit with 0, f(111) = 110 f: {0, 1}3 {0, 1}2 drop the last bit f(101) = 10 f: {0, 1}3 {0, 1}3 remove the last bit and concatenate it at the beginning of the string: f(101) = 110 f(100) = 010
Onto Examples Example f: {0, 1}2 {0, 1}3 add a 0 to the end f(10) = 100 000 001 00 010 01 If f:D T is onto, then |T| |D| 011 10 100 11 101 If f:D T and |T| > |D| The f can not be onto. 110 111
Bijections Definition: A function f:D T is a bijection if it is one-to-one and onto a 1 b 2 c 3 d 4 If f:D T and f is a bijection, then |D| = |T|
Inverse of a function f: D T The inverse of f (if it exists) is a function f-1: T D For every x D and y T, f(x) = y f-1(y) = x a 1 1 a A function f is a bijection if and only if f has an inverse b 2 b 2 c 3 c 3 d 4 d 4 f-1 f
Inverse of a function example A string is a palindrome if it is the same after it is reversed. Let P6 be the set of all 6-bit strings that are also palindromes. Bijection between {0, 1}3 and P6 f: {0, 1}3 P6 f(x) = xxR (xR is the reverse of x)
