SP20:Lecture 6 prep

From CS2800 wiki

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.

Last semester, parts of the material for this lecture were covered in lecture 5 and lecture 6.

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.