[PDF] [PDF] Final Exam Solution Guide - Stony Brook Mathematics

[PDF] Bijective Proof Examples

8 fév 2017 · strings of length 13 that contain exactly three 1s Proof Because h is injective and surjective, it is bijective Because there exists a bijection between the number of ways to buy 10 donuts from four flavors and the number of 0/1 strings of length 13 that contain exactly three 1s, those numbers must be equal

[PDF] BIJECTIVE PROOF PROBLEMS

18 août 2009 · A combinatorial proof of the problem is not known In all cases are Problems 27 , 28, 59, 107, 143, 118, 123 (injection of the type described),

[PDF] 2 Properties of Functions 21 Injections, Surjections - FSU Math

The examples illustrate functions that are injective, surjective, and bijective Here Prove that the function f : N → N be defined by f(n) = n 2 is injective Proof

Bijective Proofs: You say you want an involution? - Penn Math

5 mar 2009 · Definition A bijection is a one-to-one and onto mapping Example A B The philosophy of combinatorial proof Bijective proof Example n ∑

[PDF] Bijective matrix algebra - CORE

bijective proof that BA = I (See Theorem 44 and Theorem 47 in §6 ) First, we must give a rigor- ous definition of what we mean by a bijective proof of a matrix 

[PDF] Proofs with Functions

23 fév 2009 · A function that is both one-to-one and onto is called a bijection or a one-to- Let's prove this using our definition of one-to-one Proof: We need 

[PDF] Section 44 Functions

CS 130 – Discrete Structures 45 Example of Surjective Functions • To prove a function to be surjective: need to show that an arbitrary member of the codomain  

[PDF] Functions

1 mai 2020 · The same proof works with minor changes if f′(x) < 0 for all x Example Define f : R − {0} → R − {1} by f(x) = x + 1 x Prove that f is surjective

[PDF] Introduction Bijection and Cardinality

A function f from A to B is called onto, or surjective, if and For example, {a,b,c} = {d,e,f} a b Exercise: Prove that a bijection from A to B exists if and only if

[PDF] Final Exam Solution Guide - Stony Brook Mathematics

Justify your answer with a proof or a counter-example Yes, f is necessarily a bijection Since we are told it is an injection, it suffices to show that it is a surjection

[PDF] bijoux victoria catalogue 2020 belgique

[PDF] bikini toulouse programmation 2019

[PDF] bilan covid 19 france 9 avril 2020

[PDF] bilan financier association modele

[PDF] bilan financier cours et exercices+pdf

[PDF] bilan financier d'une entreprise exemple

[PDF] bilan financier modèle

[PDF] bilingual education act

[PDF] bilingual university in canada

[PDF] bilingual university located in canada's capital

[PDF] billet avion paris toulon air france

[PDF] billet d'avion air france promotion

[PDF] billet d'avion easyjet paris nice

[PDF] billet d'avion japon air france

[PDF] billet d'avion paris congo brazzaville

Final ExamSolution Guide

MAT 200

There are ten questions.

Each question is worth 10 points.

1. Let (?) denote the following statement about integersn:

Ifnis divisible by 10, then it is divisible by 2 or divisible by 5. (a) Is (?) a true statement? (That is, is ituniversallytrue?)

Yes, (?) is a true statement.

(b) What is thecontrapositiveof (?)? Is it a true statement? Ifnis not divisible by 2andnot divisible by 5, it is not divisible by 10.

This is equivalent to (?), and thus also true.

(c) What is theconverseof (?)? Is it a true statement? Ifnis divisible by 2 or divisible by 5, it is divisible by 10. This is false. For example, 4 is divisible by 2, but not divisible by 10.

Remark.Consider the statement (y) given by

Ifnis divisible by 10, then it is divisible by 2anddivisible by 5.

Then (y) is also true, and (y) =)(?).

However, the distinction betweenandandoris important for part (c). Namely, the converse of (y) is true, while the converse of (?) is false! 1

2. Letf:X!Yandg:Y!Xbe functions, and suppose that

fg=IY; whereIYis the identity function onY. Prove thatfis a surjection. Proof.Letybe any element ofY. If we setx=g(y), then f(x) =f(g(y)) = (fg)(y) =IY(y) =y: Thus, for everyy2Y, there exists anx2Xsuch thatf(x) =y. But this precisely says thatfis surjective. QED 2

3. Recall thatZdenotes the set of integers,Z+the set of positive integers,

andQthe set of rational numbers. Dene a functionf:ZZ+!Qby f(p;q) =pq (a) Isfan injection? Why? No. There are many dierent choices of (p;q)2ZZ+which are assigned the same value byf. For example,f(1;1) = 1 =f(2;2). (b) Isfa surjection? Why? Yes. Every rational number is, by denition, a quotient of integers, and we can always arrange for the denominator to be positive. (c) Isfa bijection? Why? No. To be a bijection, a function must be both an injection and a surjection. Sincefis not an injection by part (a), it is not a bijection, either. 3

4. LetXbe aniteset, and suppose thatf:X!Xis an injection.

Does it follow thatfis a bijection? Justify your answer with a proof or a counter-example. Yes,fis necessarily a bijection. Since we are told it is an injection, it suces to show that it is a surjection. This is proved as follows:

Proof.We proceed via proof by contradiction.

Suppose thatfis not a surjection. Then there is somex02Xwhich is not in the image off. SettingY=X fx0g, we can therefore viewfas dening a functiong:X!Y. (This change of pont-of-view is an exam- ple of \restriction of codomain".) Sincefis injective, and sincegis really justfby another name,gis injective, too. However, ifjXj=m, then jYj=m1. In particular,jYj5. Now letXinstead be adenumerableset, and suppose thatf:X!X is an injection. Does it follow thatfis a bijection? Justify your answer with a proof or a counter-example.

No,fis not necessarily a bijection.

Here is a counter-example: letX=Z+be the set of positive integers, and to letf:Z+!Z+be the functionf(n) =n+ 1. Thenfis injective, but not surjective. 5

6. LetPbe the Euclidean plane. Recall thatPis a set, and that its elements

are calledpoints. Show that the axioms for Euclidean geometry, as given in the geometry notes, imply thatPis an uncountable set.

Hint:How many points are there on a line?

Proof.The incidence axiom implies thatPcontains a line`. Theruler axiomthen tells us that there is a bijective \coordinate system" f:`!R and sincefis a bijection, it has an inversef1:R!`, which is also a bijection. Ifj:`!Pis the inclusion function, arising from the fact that` is a subset ofP, the composition jf1:R!P is therefore necessarily injective, since it is the composition of two injections. IfPwere countable, there would be an injectiong:P!Z+, and the composition gjf1:R!Z+ would be injective. Since any subset ofZ+is either nite or denumerable, this gives rise, via restriction of codomain, to a bijection betweenRand a countable set | namely, the image ofgjf1. It follows thatRis countable. But Cantor's Theorem says thatRisuncountable, so this is a contradiction. It follows thatPmust be uncountable, as claimed. QED 6

7. Prove by induction that, for any positive integerk, 10kis congruent to

(1)kmodulo 11. Then use this to show that any positive integer is congruent mod 11 to the alternating sum of its digits.

LetP(k) be the statement

10 k(1)kmod 11: Base case.10 = 111 1 = (1)1mod 11, soP(1) is true.

Inductive step.We will show thatP(m) =)P(m+ 1).

Suppose thatP(m) is true. Then

10 m(1)mmod 11:

However, we also know that

10

1(1)1mod 11;

since we have just checked that the bases case is true. Furthermore, we know that multiplying two valid congruences with the same modulus yields another valid congruence with that modulus. Multiplying the last two congruences above thus yields (10 m)101(1)m(1)1mod 11; and on simplication this gives us 10 m+1(1)m+1mod 11; which is the statementP(m+ 1). ThusP(m) =)P(m+ 1), as claimed. Since both the base case and the inductive step are valid, the principle of

induction therefore tells us thatP(k) is true for every positive integerk.In decimal notation,nmnm1n1n0represents the positive integerPm

j=0nj10j.

Since 10

0and (1)0are both just fancy notations for 1, the above inductive

argument tells us 10 j(1)jmod 11 for every integerj0. Hence mX j=0n j10jmX j=0n j(1)jmod 11 and the right-hand expression is exactly the alternating sum n

0n1+n2n3+ nm

of the digits of the number in question. 7

8. (a) Carefully state the denition of congruence of triangles, according to

our geometry notes. By denition,4ABC=4A0B0C0means the following statements are true: jABj=jA0B0jm\A=m\A0 jACj=jA0C0jm\B=m\B0 jBCj=jB0C0jm\C=m\C0 (b) LetTbe the set of all triangles4ABCin the plane, where our denition of a triangle is understood to include a listing of its three vertices in a denite order. Show that congruence of triangles is an equivalence relation onT. Re exive:For any triangle4ABC2T, we have4ABC=4ABCbecause jABj=jABjm\A=m\A jACj=jACjm\B=m\B jBCj=jBCjm\C=m\C

Symmetric:4ABC=4A0B0C0=) 4A0B0C0=4ABCbecause

0 @jABj=jA0B0jm\A=m\A0 jACj=jA0C0jm\B=m\B0 jBCj=jB0C0jm\C=m\C01 A =)0 @jA0B0j=jABjm\A0=m\A jA0C0j=jACjm\B0=m\B jB0C0j=jBCjm\C0=m\C1 A

Transitive:For three triangles2T, we have

4ABC=4A0B0C0and4A0B0C0=4A00B00C00=) 4ABC=4A00B00C00

because jABj=jA0B0jandjA0B0j=jA00B00j=) jABj=jA00B00j jACj=jA0C0jandjA0C0j=jA00C00j=) jACj=jA00C00j jBCj=jB0C0jandjB0C0j=jB00C00j=) jBCj=jB00C00j m\A=m\A0andm\A0=m\A00=)m\A=m\A00 m\B=m\B0andm\B0=m\B00=)m\B=m\B00 m\C=m\C0andm\C0=m\C00=)m\C=m\C00 Since =is therefore re exive, symmetric, and transitive, it is therefore an equivalence relation onT. 8

9. Recall thatRdenotes the set of real numbers, whileZdenotes the set of

integers. Dene a relationonRby xy()xy2Z for anyx;y2R. Prove thatis an equivalence relation. Re exive:For anyx2R,xx= 02Z, and hencexx. Thereforeis re exive. Symmetric:Suppose thatx;y2R, and thatxy. Thenxy=nfor some integern2Z. Henceyx=(xy) =n2Z, so thatyx. This shows thatxy=)yx. Thereforeis symmetric. Transitive:Suppose thatx;y;z2R, thatxy, and thatyz. Then xy=mfor some integern, andyz=nfor some integern. Hence xz= (xy) + (yz) =m+n2Z so thatxz. This shows thatxyandyz=)xz. Thereforeis transitive.

We have now shown thatis re

exive, symmetric, and transitive. Therefore is an equivalence relation. 9

10. LetXandYbe nite sets, withjYj= 2 andjXj=n2. Compute the

cardinality of

Surj(X;Y) =ffunctionsf:X!Yjfis a surjectiong:

Hint:What is the cardinality of its complement in Fun(X;Y)? Letaandbbe the two elements ofY. Iff:X!Yisnotsurjective, then eitherais not in the image off, or elsebis not in the image off. Ifais not in the image, we must havef(x) =bfor allx2X, since a function must assign a value to every element of its domain, andbis the only possible value that hasn't been excluded; so in this case,fmust therefore be the constant function with valueb. On the other hand, ifbis not in the image, then, by the same reasoning,f(x) =afor allx2X, andfis therefore the constant function with valuea. Thus, there are exactly 2 functionsX!Ywhich aren'tsurjections.

SincejFun(X;Y)j=jYjjXj= 2n, it follows that

jSurj(X;Y)j= 2n2: 10quotesdbs_dbs21.pdfusesText_27