We finished our list of proof techniques, adding implication () and existentials (). We then defined functions and discussed some examples.

Reading: MCS 4.3 — 4.5
This material was covered in lectures 2 (modeling problems) and 4 (functions) in 2017sp.
File:Lec05-board.pdf

Proof techniques continued

There exists x such that P

If P then Q

Logical negation

Table of proof techniques

Functions

Definition: Function

If and are sets, then a function from to (written ) is an unambiguous rule giving, for every input , an output . is called the domain of ; is called the codomain.

When giving a function, you must indicate the domain, the codomain, and an unambiguous rule giving an output for every input.

The output of a function is unambiguous if there is only one output for any input. It is especially important to check this when the input of the function can be written in different ways. For example, given by [math]f(1) := 2 [/math], [math]f(2) := 2 [/math], and [math]f(1+1):=4 [/math] is not unambiguous, because [math]2 = 1 + 1 [/math] so it is not clear if [math]f(2) = 2 [/math] or [math]f(2) = 4 [/math].

Specifying functions

When giving a function, you must indicate the domain, the codomain, and an unambiguous rule giving an output for every input. There are many, many ways to do this, as long as the output is clear. We gave a few examples during lecture:

direct specification

We can define the output of the function directly:

let be given by [math]f(x) := x^2 [/math]. The domain and codomain of [math]f [/math] are both ; the image is .

drawings

We can draw a function:

The domain of [math]f [/math] is , and the codomain of [math]f [/math] is .

We might also write this as is given by [math]f(a):=2 [/math], [math]f(b):=1 [/math], and [math]f(c):=3 [/math].

tables

Another way to draw a function is with a table:

x	[math]f(x) [/math]
a	1
b	1
c	1

This almost describes a function; the domain is clearly [math]\{a,b,c\} [/math] (because if there were any other domain elements, [math]f [/math] would not be a function); and the rule is clear. However, the codomain is not clear: is it ? Or ? Or , or ? When describing a function with a table, the codomain should be specified somewhere.

function description

A function need not have an algorithm for constructing the output; a description of the output is also fine. For example, let give, on input [math]d [/math], the closing Dow-Jones Industrial average on day [math]d [/math].

Function examples

You can write a function in many different ways; the important thing is that the domain is clear, the codomain is clear, and the output is clear (and unambiguous).

direct specifications

We can define the output of the function directly:

let be given by [math]f(x) := x^2 [/math]. The domain and codomain of [math]f [/math] are both ; the image is .

drawings

We can draw a function:

The domain of [math]f [/math] is , and the codomain of [math]f [/math] is .

We might also write this as is given by [math]f(a):=2 [/math], [math]f(b):=1 [/math], and [math]f(c):=3 [/math].

tables

Another way to draw a function is with a table:

x	[math]f(x) [/math]
a	1
b	1
c	1

This almost describes a function; the domain is clearly [math]\{a,b,c\} [/math] (because if there were any other domain elements, [math]f [/math] would not be a function); and the rule is clear. However, the codomain is not clear: is it ? Or ? Or , or ? When describing a function with a table, the codomain should be specified somewhere.

SP18:Lecture 5 Functions

Contents

Proof techniques continued

There exists x such that P

If P then Q

Logical negation

Table of proof techniques

Functions

Specifying functions

direct specification

drawings

tables

function description

Function examples

direct specifications

drawings

tables