Sequences, Relations,
The concepts of ordered pairs, Cartesian product, longer sequences, examples, and relations in sets. Learn how to represent points in the plane, fractions, and more using set theory. Dive into different types of relations on sets like siblings, ancestors, and instructors.
Uploaded on Mar 04, 2025 | 0 Views
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Sequences, Relations, Functions
Ordered Pairs Let a and b be two objects. Define the set Sab= {a, {a, b}}. We call this the ordered pair with a as the first element of the pair and b as the second element. We use the notation <a,b> = {a, {a, b}} (Note: <a,a> = {a, {a}})
Cartesian Product For two sets, S and T, the cartesian product of S and T, written SxT, is the set of all ordered pairs where the first element is in S and the second in T. SxT = {<s,t> | s S and t T} Example: {a, b, c} x {a, d, f, g} = { <a,a>, <a,d>, <a,f>, <a,g>, <b,a>, <b,d>, <b,f>, <b,g>, <c,a>, <c,d>, <c,f>, <c,g> }
Longer sequences How could we extend the idea of ordered pair to more objects? <<a,b>,c> or <a, <b,c>> For simplicity, just use <a,b,c> for a sequence of three objects
We can extend the idea of Cartesian product For sets S, T, U, W, let S x T x U x W be the set of sequences of 4: {<s,t,w,u> |s S, t T, u U and w W} We also write An= A x A x A x x A (n times)
Examples All points in the plane can be represented by R x R (all pairs of real numbers) All (unreduced) positive fractions can be represented by Z+x Z+ <1, 1> mean 1/1, <1,2> means 1/2 , <2,1> means 2/1, <3,6> means 3/6, etc. Other examples??
Relations A relation on sets S and T is a subset of S x T. Examples: Sib and Ancestor on P x P, where P is all people Sib = {<x,y> | x and y are siblings} Ancestor = {<x,y> | x is an ancestor of y} IsInstructor on Faculty x Students IsInstructor = {<f,s> | f is an instructor for s}
Relation examples LessThan on the set Z>=0x Z>=0 LessThan = {<a,b> | there exist set A and B, such that A B and a = |A|, b = |B|} If <a,b> LessThan, we write a < b
Inverse relation If R is a relation on SxT, the the inverse of R, written R-1is defined by R-1= {<t,s> | <s,t> R} Example: the inverse of ancestorOf is descendentOf
Functions For sets S and T, a function from S to T is a relation f on SxT such that If <s,t> f and <s,w> f, then t = w and for any s S, there is some t T such that <s,t> f Write f: S -> T In other words, every s S maps to exactly one t T. We write t = f(s).
Examples of functions motherOf on PxP any person has exactly one mother (where we assume the biological mother) f(x) = x2is a function, f:R -> R (or f:Z -> Z) But SquareRootOf is not because for example 4 has +2 and -2 as squareroots and -4 has no squareroot in Z (or R).
Function terms For a function f: S -> T The domain of f is S The codomain of f is T The range of f is the set {t T | there is an s S with t = f(s)} Example: f(x) = x2on Z x Z domain(f) = Z and codomain(f) = Z. range(f) = { x Z | there is a y such that x = y2} = {0, 1, 4, 9, }
Composition of functions If f anf g are functions: f: S->T and g: T->W, the g o f : S->W is defined by g o f(s) = g(f(s)) Example: f(x) = x2and g(y) = y + 5. What are gof(x) and fog(x)? g o f(x) = x2+ 5. f o g(x) = (x + 5)2
Onto functions A function f: A -> B is onto if for every b B, there is an a A such that f(a) = b. In other words, f: A->B is onto if B = range(f). Example: f: Z x Z+-> Q, where f(x,y) = x/y (in reduced form), since every rational number is the ratio of two integers (except for zero in the denominator). Note: several different pairs in Z x Z+can map to the same q Q. What is another example?
One-to-one functions A function f: A -> B is one-to-one if for every b B, there is at most one a A such that f(a) = b. Sometimes called an injection. Example: f: Z -> Z, f(x) = x -3 is one-to-one. The inverse, f--1(x) = x + 3. f: Z -> Z, f(x) = x2 is not one-to one, since f(2) = f(-2) = 4
Bijection Some functions are one-to-one and onto. If f: A->B is one-to-one and onto, this means that every a A matches to exactly one b B and every b B is matched by an a A. We call such a function a bijection. Example: f: Z -> Z, f(x) = x -3 is one-to-one and onto, a bijection. Example: two sets, A and B, have the same cardinality if there is a bijection from A to B.
Sequences again A finite sequence of n items in a set S is a function from a set of integers {1,2, ,n} to S. We denote the sequence s1, s2, s3, , sn (alternatively, we may make the function from {0, 1, 2 .., n-1} to S) We can also have subsequences using any set of integers: {1,3,4,6,7} to get s1, s3, s4, s6, s7 An infinite sequence on a set S is a function f: Z+-> S. We denote the sequence s1, s2, s3, .
