FA19:Lecture 2 Set and function definitions

From CS2800 wiki

We discussed the definitions for sets and functions.

Sets

Definition: Set
A set is a collection of things. If [math]A [/math] is a set and [math]x [/math] is a thing, then [math]x [/math] is either in [math]A [/math] (written [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math]) or not in [math]A [/math] (written [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} A [/math]).

If [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] we say that [math]x [/math] is an element of [math]A [/math].

Two sets are equal if they contain the same set of things (see the definition of set equality for more details).

examples

Here are some useful sets:

  • The set [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{0,1,2,\dots\}} [/math] of natural numbers.
  • The set [math]\href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{\dots,-2,-1,0,1,2,\dots\}} [/math] of integers.


Sets can contain things other than numbers:

  • Let [math]A [/math] be the set of people in the room


The defining feature of a set [math]A [/math] is that every object is unambiguously either in [math]A [/math] or not in [math]A [/math]. You don't need an algorithm for determining which is true. For example:

  • Let [math]B [/math] be the set of Java programs that never crash


This is a perfectly good set (assuming you define "Java program" and "crash"), even though there is no algorithm to determine whether a given program crashes or not. It either does or it doesn't, we don't have to know which.

  • The empty set (written [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] or [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{\}} [/math]) is a set; [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] for all [math]x [/math].


This is an example of a degenerate object. An informal definition of a set would be something that has things in it; the empty set has no things in it, so perhaps we should rule it out. But most proofs work just as well with special cases as they do for the general case, so by default we include the special cases. We do the same thing when we define subset below.


We can list (or enumerate) the elements of a set:

You can think of this as shorthand for the set comprehension [math]\{n \href{/cs2800/wiki/index.php/%5Cmid}{\mid} n = 1\href{/cs2800/wiki/index.php/Or}{\text{ or }n} = 2\href{/cs2800/wiki/index.php/Or}{\text{ or }n}=3\} [/math].

Sometimes we include a $\dots$ in an enumerated set if its meaning is clear (such as in the definition of [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]). This can be formalized more carefully as an inductively defined set.

Sets can contain other sets:

  • [math]\{\{1,2\}, \{3,4\}\} [/math] is a set containing two elements: the first is the set [math]\{1,2\} [/math]; the second is the set containing [math]\{3,4\} [/math].
  • Note that [math]\{\href{/cs2800/wiki/index.php/%E2%88%85}{∅}\} \href{/cs2800/wiki/index.php?title=Set_equality&action=edit&redlink=1}{\neq} ∅ [/math]; the former contains one thing (the empty set), while the latter contains no things. This is analogous to the difference in python between [] and [[]]:
>>> len([])
0
>>> len([[]])
1

One easy way to construct a set is to draw a picture of it. A common way of doing so is a Venn diagram such as this one:

Venn-diag.svg

This diagram indicates that the set [math]A [/math] consists of all of the points in the left-hand circle, while set [math]B [/math] consists of the points in the right hand circle.

Be careful: although Venn diagrams are a great way to create examples, they do not provide proofs that work for arbitrary sets. For example, an argument made using the diagram above does not describe the cases where [math]A \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} B [/math] or when [math]A \href{/cs2800/wiki/index.php/%5Ccap}{\cap} B \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math]. Moreover, it doesn't consider finite sets or sets that are larger than any set of points in the plane. Venn diagrams give intuition (and examples) but not proofs.

Set comprehensions

The notation [math]\{x \mid \text{property of } x\} [/math] denotes the set of all [math]x [/math] that satisfy the property. You should read [math]\href{/cs2800/wiki/index.php/%5Cmid}{\mid} [/math] as "such that". For example,

[math]A \href{/cs2800/wiki/index.php/Definition}{:=} \{x \mid x\href{/cs2800/wiki/index.php/Even}{\text{ is even}}\} [/math]

indicates the set of all even numbers. [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] because [math]2 [/math] is even, while [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} A [/math] because [math]1 [/math] is not even.

We may want to specify that we're only interested in natural numbers; we often use notation like [math]\{x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \mid x\href{/cs2800/wiki/index.php/Even}{\text{ is even}}\} [/math]. This should be read as "the set of natural numbers which are even".

We can also have more complicated expressions to the left of the vertical bar, for example [math]B \href{/cs2800/wiki/index.php/Definition}{:=} \{2y \mid y \in \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\} [/math] also denotes the set of even natural numbers: [math]8 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math] because [math]8 = 2\href{/cs2800/wiki/index.php?title=%5Ccdot&action=edit&redlink=1}{\cdot}4 [/math] and [math]4 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], while [math]7 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} B [/math] because there is no natural number that when multiplied by 2 gives 7.

Set equality

The defining feature of a set is the collections of elements that are in or not in it. This suggests that we should consider two sets to be the same if they contain the same elements. This motivates the definition of equality:

Definition: Equality (sets)
Two sets $A$ and $B$ are equal if [math]A \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} B [/math] and [math]B \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} A [/math].

This is equivalent to the following definition:

Definition: Equality (sets)
Two sets $A$ and $B$ are equal if, for all [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math], [math]x [/math] is also in [math]B [/math] and if for all [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math], [math]x [/math] is also in [math]A [/math].

Here is a third variant:

Definition: Equality (sets)
Two sets [math]A [/math] and [math]B [/math] are equal if, for all [math]x [/math], [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] if and only if [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math].

These three definitions are equivalent (proof left as an exercise), so you can use them interchangeably.

This definition tells us that sets "ignore" duplicates and order. For example, [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,1,2,3\}} \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]; we can prove this using the definition. First, we check every [math]x [/math] in the left hand side (LHS) is in the right hand side (RHS); by inspection, we see that [math]1 \in \href{/cs2800/wiki/index.php/RHS}{RHS}, 1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS}, 2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], and [math]3 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. Then, we check that every [math]x [/math] in the RHS is in the LHS; which they are, again by inspection.

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].

Partial functions

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].
Definition: Total
A partial function [math]f [/math] is total if the support is equal to the domain, i.e. if [math]f [/math] is a function.

Note that, somewhat confusingly, not all partial functions are functions. However, we do consider a (total) function to be a partial function. We use this terminology because it is standard in mathematics and because it simplifies proofs (so that we don't have to say "a partial or total function" in places where the same argument works for both).

To summarize,

Parfun-nosupp.svg

is a partial function, but not a function (because it is not total), while

Fun-a2b1c3.svg

is a partial function, a function and a total function (also an injection, a surjection, a bijection, and a relation).