SP20:Lecture 5 prep

From CS2800 wiki

We'll introduce functions and partial functions and start proving things about them.

Some of this material was covered last semester in lecture 2, other material was covered in lecture 5

Bring your proof techniques handout.

Please come to lecture with the following definitions:


Definition: Function
If [math]A [/math] and [math]B [/math] are sets, then a function from [math]A [/math] to [math]B [/math] (written [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]) is an unambiguous rule giving, for every input [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], an output [math]f(x) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math]. [math]A [/math] is called the domain of [math]f [/math]; [math]B [/math] is called the codomain.

A partial function is like a function, except that it does not need to give an output for every input. However, the outputs it does give must be unambiguous. One way to formalize this is by defining a partial function as a function from a restricted domain:

Definition: Partial function
A partial function [math]f : A \href{/cs2800/wiki/index.php/%E2%86%9B}{↛} B [/math] is a subset [math]S⊆A [/math] (called the support of [math]f [/math]), along with a function [math]\tilde{f}:S \href{/cs2800/wiki/index.php/%E2%86%92}{→}B [/math] We say that [math]f(x)=y [/math] if [math]\tilde{f}(x) = y [/math] and [math]f(x) [/math] is undefined if [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} S [/math].