Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete Mathematics > Functions > Flashcards

Functions Flashcards

1
Q

Partial function

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Give 3 examples of relations that are also functional.

A
  1. {(x, y) | y = x^2} : Z -|-> N
    every integer has a unique square in N.
  2. ADD
  3. ADD
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Give 3 examples of relations that are NOT functional

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

A -` B

A

partial function with domain A and codomain B.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

(A =`` B)

A

the set of all partial functions from A to B.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Semantics of f(a) in context of partial functions

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Prove that the composition of partial functions is a partial function

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Functional composition

A

Case of relational composition

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How is functional equality defined?

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A
  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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

see 363 of notes

Df = integer tuples where second tuple element is nonzero.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Definition of a total function / map

A

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

domain of definition = source

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Meaning of f : A -> B

A

f is a total function from A to B.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

notation: A => B

A

the set of functions from A to B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

State a theorem relating functions to relations

A

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)

19
Q

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

A

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

20
Q

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

A

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.

21
Q

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

A
  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.
22
Q

Thm 126 : The identity partial function is a function

A
  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)
23
Q

Thm 126 ii: Composition of functions is a function

A

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))

24
Q

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

A 
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.
25
Q

What is a section?

A

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.

26
Q

What is a retraction?

A

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.

27
Q

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

A
  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.
28
Q

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

A

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

29
Q

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

A

there exists a bijection between the two sets

if finite sets, their cardinalities are the same

30
Q

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

A
  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)
31
Q

Notation : EqRel(A)

A

set of ALL EQUIVALENCE relations on A.

32
Q

Def 133: A partition P of a set A

A

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)

33
Q

Notation : Part(A)

A

set of all partitions of A

34
Q

Thm 134: For every set A,

EqRel(A) ~= Part(A)

A

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.
35
Q

Thm 134: For every set A,

EqRel(A) ~= Part(A)

A

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.
36
Q

Thm 134: For every set A,

EqRel(A) ~= Part(A)

!!!!!!!!!!!!!!

A

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.
37
Q

Define the quotient set mapping

A

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.

38
Q

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

A

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.

39
Q

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

A

…

40
Q

Def 139 : Surjection

A

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.

41
Q

f : A -» B

A

” f is a surjection from A to B”

42
Q

Give five examples of surjections

A
  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
43
Q

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

A

….

44
Q

Def 145 : Injection

A

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.

Discrete Mathematics (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions