Functions

Question 1

Partial function

Answer 1

R : A -|-> B is functional, and a partial function iff
- For all a in domain,
- For all b1, b2 in codomain:
: (a R b1 && a R b2) => b1 = b2

Analogy : an array indexed by elements of the codomain, may store null or a unique element.

Question 2

How to disprove that a relation has the property of being functional.

Answer 2

R : A -|-> B is NOT functional if exists an a in domain A, and b1 != b2 in B, such that both:
[(a, b1) in R & (a, b2) in R]

Analogy: Chaining to resolve hash collisions. A particular key may correspond to multiple values under a hash collision - hence exist distinct values which are associated with the same key. So the hash function in this sense is not a partial function.

Question 3

Give 3 examples of relations that are also functional.

Answer 3

1. {(x, y) | y = x^2} : Z -|-> N
   every integer has a unique square in N.
2. ADD
3. ADD

Question 4

Give 3 examples of relations that are NOT functional

Answer 4

1. { (m,n) | m = n^2} : N -|-> Z.
   because some integers have more than one square root in the integers. (e.g. both (1, 1) and (1, -1) are in this relation.
2. ADD
3. ADD

Question 5

A -` B

Answer 5

partial function with domain A and codomain B.

Question 6

(A =`` B)

Answer 6

the set of all partial functions from A to B.

Question 7

In/out degrees-type definition of a partial function f : A -‘ B

Answer 7

for each element a in A, (exists at most one) b in B $ b = f ( a ) iff b is the value of f at a iff (a f b) iff (a,b) in f.

Array indexing defines a partial function from integers to Strings (etc…) with each element of domain (subscript position) being associated to at most one element of codomain (= a reference to a string, or NULL).

Question 8

Semantics of f(a) in context of partial functions

Answer 8

f(a) denotes ‘the value of’ f at a, whenever this exists, and is considered undefined otherwise.

Analogy: A[i] denotes the value of the array at index position i, or throws an NPE (imagine…) or throws other exceptions if A[i] is not defined.

Question 9

Prove that the composition of partial functions is a partial function

Answer 9

(answer p359 notes … relevant qn in exercises)
- Suppose f : A - B and g: B - C are partial functions.
- The expression g(f(a)) is defined iff f(a) is defined (call it b) and so an element of b …
&& if g(b) is defined where b= f(a),

Analogy: if our array holds yet other array positions, if A[i] is defined and A is defined on A[i] then A[A[i]] defined and is a partial function from indices to type of value stored by array.

Question 10

Functional composition

Answer 10

Case of relational composition

g(f(x)) = (g o f) (x)

Question 11

How is functional equality defined?

Answer 11

f = g : A -` B
 if
- have same codomain and domain 
&&
- For all elements of domain, f is defined on x iff g is defined on x in A. 
- And, f(a) = g(a). 

Analogy: Two arrays are value-equal if they are of the same size and type, and all index positions agree on value mapped to in codomain.

Question 12

State how to define a partial function f : A -` B

Answer 12

1. Specify a domain of definition Df subset of A.
2. Specify a mapping

f : a |-> b_a

rule that assigns a unique element b_a in codomain B to each element a in the domain of definition,

such that f(a) = b_a.

Question 13

State how to prove that a partial function is well defined.

Answer 13

1. Show definition of partial function holds (for every a in Df, the b_a as described by your mapping rule is (i) unique, and (ii) is in B)
   - which hows that f(a) has a well defined value.
2. Show domain of definition is a subset of domain A.

Question 14

Give an example of a partial function from ZZ -` ZN based on quo(m,n) and rem(m,n) given these take non-negative arguments. State its domain of definition

Answer 14

see 363 of notes

Df = integer tuples where second tuple element is nonzero.

Question 15

Definition of a total function / map

Answer 15

f : A -> B is a total function whenever:

domain of definition = source

Question 16

Meaning of f : A -> B

Answer 16

f is a total function from A to B.

Question 17

notation: A => B

Answer 17

the set of functions from A to B

Question 18

State a theorem relating functions to relations

Answer 18

A relation is a function from A to B iff

for all a in A, there exists a unique b in B such that (a f b)

Question 19

Count the number of partial functions from A to B (i.e. what is #(A =`` B) ?

Answer 19

For each element of A there are (#B + 1) choices to map to (either one of the #B elements of B, or ‘null’, leave undefined). This choice is repeated for #A elements, hence #(A =`` B) = (#B + 1) ^ (#A).

Question 20

How many functions are there from a set A to a set B?

Answer 20

For each of the #A elements of A, there are #B choices (since undefined is no longer an option), so there are (#B) ^ (#A) such total functions from finite sets A to B.

Question 21

Compare definition of function with definition of partial function (operationally)

Answer 21

1. Total function - a mapping rule f : a |-> b_a suffices, w/o needing a domain of definition.
2. Mapping should be defined for every element in A specifying a unique element of B.

Question 22

Thm 126 : The identity partial function is a function

Answer 22

1. id(x) = x

Defined for every element of source, mapping to a unique element of codomain.

assume id (x) = id (y) 
implies x = y (as required - uniqueness)

Question 23

Thm 126 ii: Composition of functions is a function

Answer 23

Let f : A -> B and g : B -> C be functions. Let a be an arbitrary member of A, then f(a) is defined and a member of B, say ‘b’ since f is a function. Since g is a function, g(b) will be defined and equal to a unique c in C. Hence g(f(a)) is defined for all ‘a’ and equal to a unique c in C, so g(f(a)) is a function from A -> C, such that

(g o f) : a |-> g(f(a))

Question 24

What is a bijection? Or, given a function f : A -> B, when is it bijective?

Answer 24

A fn f:A ->B is bijective if:
   exists a (necessarily unique) function g : B -> A (g is the inverse of f) such that g is both a retraction and a section for f.

Question 25

What is a section?

Answer 25

s is a section (or right inverse) for f iff: s : B -> A f o s = id_b i.e. f(s(b)) = b for all b in B.

Question 26

What is a retraction?

Answer 26

g : B -> A is a retraction / left inverse for f iff : (g o f) = id_A i.e. g(f(x)) = x for all x in A.

Question 27

Prove that the two sided inverse of a function, if it exists, is necessarily unique

Answer 27

1. Let f : A -> B be a function and assume that the function g : B -> A is a two sided inverse for f, such that (g o f) = idA and (f o g) = idB 2. Suppose we had another two sided inverse g' : B -> A. 3. Then g' o (f o g) = g' (g' o f) o g = g' idA o g = g' g = g' hence g is unique.

Question 28

Prove that for finite sets A and B, the cardinality of all bijections between A and B is...

Answer 28

0 if cardinalities differ as then no one-to-one correspondence is possible (for finite sets) n! if cardinalities both equal n (only for finite sets). Proof idea : want to associate each element of A with one and only one element of B under the bijection. Possible ways of doing this = possible number of permutations of B (equally A) = n! where n = #A = #B

Question 29

Def 131 : Two sets A and B (possibly infinite) are said to be isomorphic whenever...

Answer 29

there exists a bijection between the two sets | if finite sets, their cardinalities are the same

Question 30

Def 132: A relation E on a set A is an equivalence relation whenever it is:

Answer 30

1. Reflexive (For all x in A, xEx) 2. Symmetric (For all x, y in A. xEy => yEx) 3. Transitive (For all x,y,z in A. xEy & yEz => xEz)

Question 31

Notation : EqRel(A)

Answer 31

set of ALL EQUIVALENCE relations on A.

Question 32

Def 133: A partition P of a set A

Answer 32

A partition P of a set A is: - a set of non-empty subsets of A, (1. so P subset of Pow(A) and 2. emptyset not in P) whose elements consist of connected components, such that 1. The union of all blocks yields A. 2. All distinct blocks are pairwise disjoint (for all b1,b2 in P, b1 != b2 => (intersection of b1 and b2 = empty set)

Question 33

Notation : Part(A)

Answer 33

set of all partitions of A

Question 34

Thm 134: For every set A, EqRel(A) ~= Part(A)

Answer 34

Proof outline: 1. Prove mapping E to its quotient set is a function from EqRel(A) -> Part(A) 2. Prove that the mapping P |-> ==p .... yields a function Part(A) -> EqRel(A) 3. Prove that the above two functions are inverses of each other.

Question 35

Thm 134: For every set A, EqRel(A) ~= Part(A)

Answer 35

p379 notes Proof outline: 1. Prove mapping E to its quotient set is a function from EqRel(A) -> Part(A) 2. Prove that the mapping P |-> ==p .... yields a function Part(A) -> EqRel(A) 3. Prove that the above two functions are inverses of each other.

Question 36

Thm 134: For every set A, EqRel(A) ~= Part(A) !!!!!!!!!!!!!!

Answer 36

p379 notes Proof outline: 1. Prove mapping E to its quotient set is a function from EqRel(A) -> Part(A) 2. Prove that the mapping P |-> ==p .... yields a function Part(A) -> EqRel(A) 3. Prove that the above two functions are inverses of each other.

Question 37

Define the quotient set mapping

Answer 37

The quotient set mapping maps an equivalence relation E, to the set written A/E which is the quotient set := ``` the set of all b (subsets of A) such that there exists an a in A, such that b is the equivalence class of a under E. [a]E = {x in A | x E a} ``` IE A/E is the set of all equivalence classes of E in A.

Question 38

Define the mapping P |-> ==p from Part(A) -> EqRel(A)

Answer 38

This mapping takes a partition P and maps it to an equivalence relation ==p, where x ==p y iff exists block in partition $ x in block && y in block. iff x and y belong to the same block within the partition P.

Question 39

Proving bijection between P(A) and (A => [2])

Answer 39

...

Question 40

Def 139 : Surjection

Answer 40

A function f : A -> B is said to be surjective whenever For all b in B there exists an a in A $ f(a) = b IE if f is a surjection we can always solve the equation f(x) = b by finding an x in A such that f(a) = b. This is an onto mapping, every element of the codomain has an inverse image.

Question 41

f : A ->> B

Answer 41

" f is a surjection from A to B"

Question 42

Give five examples of surjections

Answer 42

1. Every bijection is a surjection 2. The unique function A -> [1] is surjective iff A is nonempty. 3. The quotient function A -> A/E : a |-> [a]E associated to an equivalence relation E on a set A is surjective. 4. The projection function AxB -> A : (a, b) |-> a is surjective iff B is nonempty OR A is empty. 5. For natural numbers m and n, with m

Question 43

Thm 140: The identity function is a surjection and the composition of surjections yields a surjection.

Answer 43

....

Question 44

Def 145 : Injection

Answer 44

A function f : A -> B is injective, f : A >-> B whenever for all a1 and a2 in A if [f(a1) = f(a2)] then (a1=a2) i.e. like a cancellation law for f's. So every element of B has a only a singleton inverse image / gets hit at most once by the injection.