Difference between revisions of "SP18:Lecture 5 Functions"

From CS2800 wiki
m (<math>'"1 {{GENDER:Sy536|moved}} page </math>'"3 to SP18:Lecture 5 Functions)
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
<noinclude>[[Category:SP18]]</noinclude>
+
 
  
 
We finished our list of proof techniques, adding [[implication]] (<math>[[\Rightarrow]]</math>) and [[existential]]s (<math>[[\exists]]</math>).  We then defined functions and discussed some examples.
 
We finished our list of proof techniques, adding [[implication]] (<math>[[\Rightarrow]]</math>) and [[existential]]s (<math>[[\exists]]</math>).  We then defined functions and discussed some examples.
Line 28: Line 28:
  
 
{{:Function}}
 
{{:Function}}
 +
 +
 +
{{:Image definition}}
  
 
== Function examples ==
 
== Function examples ==

Latest revision as of 13:04, 10 September 2018


We finished our list of proof techniques, adding implication ([math]\href{/cs2800/wiki/index.php?title=%5CRightarrow&action=edit&redlink=1}{\Rightarrow} [/math]) and existentials ([math]\href{/cs2800/wiki/index.php/%5Cexists}{\exists} [/math]). We then defined functions and discussed some examples.

Proof techniques continued

There exists x such that P

If [math]P [/math] is a predicate depending only on [math]x [/math], then "there exists [math]x [/math] such that P" (written [math]\exists x, P [/math] or [math]\exists x~\href{/cs2800/wiki/index.php?title=S.t.&action=edit&redlink=1}{s.t.}~P [/math]) is a proposition. It is true if there is some value [math]x [/math] that makes [math]P [/math] evaluate to true.

[math]\href{/cs2800/wiki/index.php/%5Cexists}{\exists} [/math] is sometimes called the existential quantifier.

  • To prove that there exists an [math]x [/math] such that [math]P(x) [/math] holds, it suffices to give a specific [math]x [/math] and then prove that [math]P [/math] is true for that [math]x [/math]. Such a proof usually starts "let [math]x:= \cdots [/math]", and then goes on to prove that [math]P(x) [/math] holds for the given [math]x [/math]. [math]x [/math] is sometimes referred to as a witness for [math]P(x) [/math].
  • If you know there exists some [math]x [/math] satisfying [math]P [/math], you can use it in a proof by treating [math]x [/math] as an arbitrary value. [math]x [/math] is arbitrary because the only thing you know about [math]x [/math] is that it exists, not what its value is.
  • To disprove that there exists an [math]x [/math] satisfying [math]P [/math], you must disprove [math]P [/math] for an arbitrary [math]x [/math]. Put another way, the logical negation of "there exists an [math]x [/math] such that [math]P [/math]" is "for all x, not P".


When trying to prove an existential statement [math]\href{/cs2800/wiki/index.php/%E2%88%83}{∃x}, \href{/cs2800/wiki/index.php/Predicate}{P}(x) [/math], you need to give a specific value of [math]x [/math] (a witness).

Often, in a proof, it is not immediately obvious what the witness should be. Finding one often involves solving some equations or combining some known values.

One nice technique for finding a witness is to simply leave a blank space for the value of [math]x [/math] and continue on with your proof of [math]P(x) [/math]. As you go, you may need [math]x [/math] to satisfy certain properties (for example, maybe you need [math]x \gt 17 [/math] at one point, and later you need [math]x \lt 85 [/math]). You can make a "wishlist" on the side of your proof, reminding you of all the properties you want [math]x [/math] to satisfy. Once you've completed your proof, you can go back and find a specific value of [math]x [/math] (say, [math]50 [/math]) that satisfies all of your wishes.

If P then Q

If [math]P [/math] and [math]Q [/math] are propositions, then "if [math]P [/math] then [math]Q [/math]" (written [math]P \href{/cs2800/wiki/index.php?title=%5Cimplies&action=edit&redlink=1}{\implies} Q [/math] or "[math]P [/math] implies [math]Q [/math]") is a proposition. It is true if either [math]P [/math] is false, or if [math]Q [/math] is true.

  • To prove "if [math]P [/math] then [math]Q [/math]", assume [math]P [/math] and then prove [math]Q [/math].
  • If you know "if [math]P [/math] then [math]Q [/math]", and you also know [math]P [/math], you can conclude [math]Q [/math]. This technique is sometimes referred to as "modus ponens".
  • To disprove "if [math]P [/math] then [math]Q [/math]", you must show that [math]P [/math] is true and that [math]Q [/math] is false ("[math]P [/math] implies [math]Q [/math]" only makes a claim about the world where [math]P [/math] is true; an example where [math]P [/math] is false doesn't contradict the claim).

Logical negation

If [math]P [/math] is a proposition, the logical negation of [math]P [/math] is the proposition that is equivalent to "not [math]P [/math]".

For example, to disprove "[math]P [/math] and [math]Q [/math]", it suffices to either disprove [math]P [/math] or to disprove [math]Q [/math]. This is the same thing as proving "not [math]P [/math] or not [math]Q [/math]," so the logical negation of "[math]P [/math] and [math]Q [/math]" is "not [math]P [/math] or not [math]Q [/math]."

For further examples, see the table of proof techniques.

Table of proof techniques

Here is a table of proof techniques summarizing proof techniques for the basic logical connectives. These techniques will get you most of the way through most of the proofs in this course. There is also a convenient one-page pdf

Proposition Symbol To prove it To use it Logical negation
P and Q (P Q) prove both P and Q you may use either P or Q (¬P) (¬Q)
P or Q (P Q) You may either prove P or prove Q case analysis (¬P) (¬Q)
P is false (or "not P") ¬ P disprove P contradiction P
if P then Q (or "P implies Q") P Q assume P, then prove Q if you know P, conclude Q P ¬ Q
for all x, P ∀x, P choose an arbitrary value x apply to a specific x x, ¬ P
there exists x such that [math]P [/math] ∃x, P give a specific x use an arbitrary x satisfying P x, ¬ P

You can think of these as the valid outlines of a valid proof. When writing a 5-paragraph essay, the structure consists of an introductory paragraph, three supporting paragraphs, and a conclusion. Supporting paragraphs have their own structure (made up of sentences, which themselves have a structure...).

Similarly, a proof of a statement like "for all x, P" has an introduction of an arbitrary variable, followed by another proof (this time of P(x)). This proof in turn will have one of the structures in the table above, and so on.

Note that this process is recursive: most of these techniques say "to prove ..., do ... and then prove ...". In most cases, you must repeatedly apply these techniques to build a complete proof.

Functions


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.

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, [math]f : \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] 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 [math]f(x) : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] be given by [math]f(x) := x^2 [/math]. The domain and codomain of [math]f [/math] are both [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]; the image is [math]\{y ∈ \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} y ≥ 0\} [/math].

drawings

We can draw a function:

Fun-a2b1c3.svg

The domain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} [/math], and the codomain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math].

We might also write this as [math]f : \{a,b,c\} \href{/cs2800/wiki/index.php/%5Cto}{\to} \{1,2,3\} [/math] 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 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], or [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]? 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 [math]dji : Days \href{/cs2800/wiki/index.php/%E2%86%92}{→} ℝ [/math] give, on input [math]d [/math], the closing Dow-Jones Industrial average on day [math]d [/math].

Definition: Image
If [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], then the image of [math]f [/math] (written [math]\href{/cs2800/wiki/index.php?title=Im&action=edit&redlink=1}{im}(f) [/math]) is the set of values that are output by [math]f [/math]. Formally, [math]\href{/cs2800/wiki/index.php?title=Im&action=edit&redlink=1}{im}(f) \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Set_comprehension}{\{y ∈ B \mid} \href{/cs2800/wiki/index.php/%E2%88%83}{∃x} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A\text{ such that }y=f(x)\} [/math] or more succinctly, [math]\href{/cs2800/wiki/index.php?title=Im&action=edit&redlink=1}{im}(f) := \href{/cs2800/wiki/index.php/Set_comprehension}{\{f(x) \mid x ∈ A\}} [/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 [math]f(x) : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] be given by [math]f(x) := x^2 [/math]. The domain and codomain of [math]f [/math] are both [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]; the image is [math]\{y ∈ \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} y ≥ 0\} [/math].

drawings

We can draw a function:

Fun-a2b1c3.svg

The domain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} [/math], and the codomain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math].

We might also write this as [math]f : \{a,b,c\} \href{/cs2800/wiki/index.php/%5Cto}{\to} \{1,2,3\} [/math] 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 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], or [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]? When describing a function with a table, the codomain should be specified somewhere.