SP20:Lecture 6 prep

From CS2800 wiki
Revision as of 16:09, 31 January 2020 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)

Before next lecture, think about the difference between [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} x, \href{/cs2800/wiki/index.php/%5Cexists}{\exists} y, x \lt y [/math] and [math]\href{/cs2800/wiki/index.php/%5Cexists}{\exists} y, \href{/cs2800/wiki/index.php/%5Cforall}{\forall} x, x \lt y [/math]. One of these is true, one is false. See if you can figure out which is which. You might think about the intuitive meaning of these statements, or you might look at the proof techniques you'd use to prove/disprove them.

Please also come to lecture with the following definitions:

Definition: Injective
A function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math] is injective if, for all [math]x_1 [/math] and [math]x_2 \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math], whenever [math]f(x_1) = f(x_2) [/math], we have [math]x_1 = x_2 [/math].
Definition: Surjective
A function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math] is surjective if for every output [math]y \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math], there exists an input [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] such that [math]f(x)=y [/math].
Definition: Bijective
A function [math]f:A\href{/cs2800/wiki/index.php/%5Cto}{\to}B [/math] is bijective if it is both injective and surjective.