[PDF] [PDF] CS 30: Discrete Math in CS (Winter 2019): Lecture 4 1 Functions

[PDF] Functions II

Definition: A function f is called a bijection if it is both one-to- one and onto Definition: Let f be a bijection from set A to set B The inverse function of f is the function that assigns to an element b from B the unique element a in A such that f(a) = b Hence, f-1 (b) = a, when f(a) = b

[PDF] Introduction Bijection and Cardinality

Discrete Mathematics - Cardinality 17-2 Previous Lecture Functions Describing functions Injective functions Surjective functions Bijective functions 

[PDF] Section 44 Functions

CS 130 – Discrete Structures 44 Properties of Functions: Surjective • Three properties: surjective (onto), injective, bijective • Let f: S → T be an arbitrary 

[PDF] ICS141: Discrete Mathematics for Computer Science I - University of

ICS 141: Discrete Mathematics I – Fall 2011 University of Hawaii Functions can be represented graphically in A function f : A → B is onto or surjective or a

[PDF] CS 30: Discrete Math in CS (Winter 2019): Lecture 4 1 Functions

9 jan 2019 · Exercise: If A and B are finite sets, and f : A → B is a surjective function, can you show B≤A? – injective, if there are no collisions That is, for 

[PDF] Chapter 10 Functions

“One of the most important concepts in all of mathematics is that of function one-to-one and onto (or injective and surjective), how to compose functions,

[PDF] CS 70 Discrete Mathematics and Probability Theory Spring 2016

Consider the “birthday function” f, which given a person's birth date, outputs the age of that person What are the domain A and range B of f? Intuitively, a bijection  

[PDF] Section 23 - Transparencies for Rosen, Discrete Mathematics & Its

Functions Definition: Let A and B be sets A function (mapping, map) f from A to B , denoted f:A→ B, is a Transparencies to accompany Rosen, Discrete Mathematics and Its Applications Definition: f is bijective if it is surjective and injective

[PDF] Lecture Notes on Discrete Mathematics

30 juil 2019 · A function f : X → Y is said to be bijective (also call a bijection) if f is both one-one and onto The set X is said to be equinumerous1 with the set 

[PDF] CS243: Discrete Structures Functions Functions Functions

Is f surjective? Isıl Dillig, CS243: Discrete Structures Functions 16/35 Bijective Functions ▷ Function that is both onto and one-to-one called bijection

[PDF] bike path san francisco sausalito

[PDF] bike paths presidio

[PDF] bike routes near me

[PDF] bilal in islam

[PDF] bilan coronavirus france 11 mai 2020

[PDF] bilan covid france 6 juin

[PDF] billet air france paris barcelone pas cher

[PDF] billet air france paris nantes

[PDF] billet air france paris noumea

[PDF] billet air france paris pointe noire

[PDF] billet avion air france ile maurice

[PDF] billet avion air france paris nice

[PDF] billet avion aller retour paris nice

[PDF] billet avion aller retour paris nice pas cher

[PDF] billet avion la rochelle paris orly

CS 30: Discrete Math in CS (Winter 2019): Lecture 4

Date: 9th January, 2019 (Wednesday)

Topic: Functions and Countable Sets

Disclaimer: These notes have not gone through scrutiny and in all probability contain errors. Please discuss in Piazza/email errors to deeparnab@dartmouth.edu1 Functions Definition.A function is amappingfrom one set to another. The first set is called thedomain of the function, and the second set is called theco-domain. Foreveryelement in the domain, a function assigns a unique element in the co-domain.

Notationally, this is represented as

f:A!B whereAis the set indicating the domain, andBis the set indicating the co-domain. For everya2A, the function maps the value ofa7!f(a)wheref(a)2B.

For example, suppose

A=f1;2;3g;andB=f5;6g;then the mapf(1) = 5;f(2) = 5;f(3) = 6is a valid function. Therangeof the function is the subset of the co-domain which areactually mapped to. That is, b2Bis in the range if and only if there is some elementa2Asuch thatf(a) =b.

More Examples.

-f(x) =x2is a function whose domain isR, the set of read numbers, and so is the co-domain. The range, however, is the set of non-negative real numbers (sometimes denoted asR+). -f(x) = sinxis a function whose domain isRand the range is the interval[1;1]. -A (deterministic) computer program/algorithm is also a function; its domain is the set

of possible inputs and its range is the set of possible outputs.bExercise:Given a setA=f1;2;3gandB=f4;5;6g, describe a functionfwhose range is

f5g, and describe a functiongwhose range isf4;6g. Just to get a feel, how many functions can you describe of the first form (whose range isf5g), and how many functions can you describe of the second form? Sur-, In-, Bi- jective functions.A functionf:A!Bis -surjective, if the range is the same as the co-domain. That is, for every elementb2B there exists somea2Asuch thatf(a) =b. Such functions are also calledontofunctions. For example, ifA=f1;2;3gandB=f5;6g, and consider the functionf:A!Bwith f(1) = 5;f(2) = 5, andf(3) = 6. Then,fis surjective. This is because for52Bthere is

12Asuch thatf(1) = 5and for62Bthere is a32Asuch thatf(3) = 6.b

1 Exercise:IfAandBarefinite sets, andf:A!Bis a surjective function, can you show jBj jAj? -injective, if there are no collisions. That is, for any two elementsa6=a02A, we have f(a)6=f(a0). Such functions are also calledone-to-onefunctions. For an injective func- tion, one can definef1(b)for allbin the range off. For example, ifA=f1;2;3gandB=f5;6;7;8g, and consider the functionf:A! Bwithf(1) = 5;f(2) = 6, andf(3) = 8. Then,fis injective. This is because

f(1);f(2);f(3)are all distinct numbers.bExercise:IfAandBarefinite sets, andf:A!Bis an injective function, can you show

jAj jBj? Injective functions haveinverses. Formally, given any injective functionf:A!B, we can define a functionf1:B!A[ f?gas follows f(b) =( aifais theuniquea2Awithf(a) =b. ?otherwise, that isf(a)6=bfor alla2A. Sometimes people define a different inverse function where instead of adding the?to the co-domain, they only consider therangeoffas the domain. That is, the following is a valid functiong:range(f)!Awheregmapsb2range(f)7!awhereais the unique element inAwithf(a) =b. In particular, whenfis bijective (to be defined below), this is the definition of the inverse and the?is not used. -bijective, if the function is both surjective and injective. For example, ifA=f1;2;3;4gandB=f2;4;6;8g, then the functionf(x) = 2xdefined

over the domainAand co-domainBis a bijective function. Can you see why?bExercise:IfAandBarefinite sets, andf:A!Bis a bijective function, can you show

jBj=jAj?

2 Countable Sets

Definition.A setSiscountableif there exists an injective functionf:S!N. It is called so because the elements ofScan be ordered and counted one at a time (although the counting may never finish). More precisely, usingfwe can devise an ordering of the elements anSand an algorithm which for any natural numberkgives thekth number in the ordering. Note that sincefis injective, for everyn2N, eitherf1(n)doesn"t exist, or f

1(n)is a well-defined element inS. The following code prints this sequence.1:forn= 1;2;3;:::do:.n2N

2:ifThere exists somea2Ssuch thatf(a) =nthen:.i.e.f1(n)2S

3:Printa

2

Examples

-Finite setsare almost trivially countable. If a setSis finite andjSj=k, then the elements ofScan be renamed asfe1;e2;:::;ekg. The injective functionf(ei) =iimpliesSis countable. Infinite sets can also be countable.Nis countable by definition. But there are many more interesting examples. -Set of Integers.The setZis countable. To see this, consider the following function f:Z!N. Ifx >0, thenf(x) = 2x. Ifx0, thenf(x) = 2(x) + 1. Note that the co-domain of this function is indeed the natural numbers.

For instance,f(2) = 4,f(2) = 5, andf(0) = 1.

Claim 1.The functionf:Z!Ndefined above is injective. Proof.To see this is injective, we need to showf(x)6=f(y)for two integersx6=y. We may assume, without loss of generality,x < y. If bothxandyare positive, then f(x) = 2x <2y=f(y). Similarly, if both are non-negative, then we getf(x) =2x+

1>2y+ 1 =f(y). The only other case isxis non-negative andyis positive. In this

case,f(x)is odd whilef(y)is even.If we use the above algorithm to figure out the ordering ofZ, we get:

(0;1;1;2;2;3;3;4;4;) 3quotesdbs_dbs20.pdfusesText_26