Scribd Logo
Upload

Welcome to Scribd!

  • 62 views

    w06 Cits2211lectures Functions

    Uploaded by

    Fred
    The document defines and describes functions from a set-theoretical perspective. It defines a function as a special type of relation where every element in the domain has exactly one corresponding element in the range. It discusses how functions can be viewed as either relations or rules that map each domain element to a unique range element. The document also defines injection, surjection, and bijection functions and provides the formal definitions for each.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    w06 Cits2211lectures Functions

    Uploaded by

    Fred
    62 views16 pages
    The document defines and describes functions from a set-theoretical perspective. It defines a function as a special type of relation where every element in the domain has exactly one corresponding element in the range. It discusses how functions can be viewed as either relations or rules that map each domain element to a unique range element. The document also defines injection, surjection, and bijection functions and provides the formal definitions for each.

    Original Description:

    w06 Cits2211lectures Functions

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document defines and describes functions from a set-theoretical perspective. It defines a function as a special type of relation where every element in the domain has exactly one corresponding element in the range. It discusses how functions can be viewed as either relations or rules that map each domain element to a unique range element. The document also defines injection, surjection, and bijection functions and provides the formal definitions for each.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    62 views16 pages

    w06 Cits2211lectures Functions

    Uploaded by

    Fred
    The document defines and describes functions from a set-theoretical perspective. It defines a function as a special type of relation where every element in the domain has exactly one corresponding element in the range. It discusses how functions can be viewed as either relations or rules that map each domain element to a unique range element. The document also defines injection, surjection, and bijection functions and provides the formal definitions for each.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 16

    Functions

    CITS2211 Discrete Structures


    Functions

    September 1, 2017
    Functions

    Highlights

    What functions are (from a set-theoretical perspective)


    Types of functions
    Functions

    Reading

    Section 4.3
    of
    Mathematics for Computer Scientists
    Functions

    Why

    Functions are particularly important to computer science,


    since calculating functions is what algorithms do.
    The proofs we will look at later (covering things such what
    its possible for a computer program to do) rely on a good
    understanding of functions.
    Functions, like sets, are ubiquitous!
    Functions

    What is a function?

    Weve all heard the word function, but what does it actually
    mean?
    Functions

    What is a function?

    Weve all heard the word function, but what does it actually
    mean?
    Is a function just something given by a formula like f (x) = x 2
    or f (x) = sin x?
    Is a function like a machine that transforms an input to an
    output?

    x The f -machine f (x)

    Or is it something else entirely?


    Functions

    Function

    Formally, a function is just a special kind of relation, as follows:


    Definition
    A function with domain A and codomain B is a relation f A B
    with the property that every element of A lies in exactly one tuple
    of f .
    In other words, in the bipartite graph of the relation, there is
    exactly one arrow leading from every element of A.
    Functions

    Reconciliation

    Given a relation satisfying the function condition, such as

    5 5
    4 4
    3 3
    2 2
    1 1

    we can declare that

    f (1) = 5, f (2) = 5, f (3) = 2, f (4) = 2, f (5) = 3

    and recover the notation that we usually use for functions.


    Functions

    Functions
    Let A, B be two sets. A function f : A B with domain A and
    codomain B can be viewed in two different ways
    A special kind of relation with the property that every element
    of A appears in exactly one pair, or
    A rule or mapping that associates exactly one element of
    B with every element of A.

    A B
    Functions

    Functions
    Let A, B be two sets. A function f : A B with domain A and
    codomain B can be viewed in two different ways
    A special kind of relation with the property that every element
    of A appears in exactly one pair, or
    A rule or mapping that associates exactly one element of
    B with every element of A.

    f (a)
    a

    A B
    Functions

    Functions
    Let A, B be two sets. A function f : A B with domain A and
    codomain B can be viewed in two different ways
    A special kind of relation with the property that every element
    of A appears in exactly one pair, or
    A rule or mapping that associates exactly one element of
    B with every element of A.

    f (a)
    a

    A B
    Functions

    Injection
    Definition
    A function is called injective (or an injection) or simply one-to-one
    if no two elements of A map to the same element of B.

    A B A B Is
    Not injective injective
    Functions

    Injection
    Definition
    A function is called injective (or an injection) or simply one-to-one
    if no two elements of A map to the same element of B.

    A B A B Is
    Not injective injective
    Formal proposition that expresses f : A B being an injection:
    x, y A. f (x) = f (y ) x = y
    Functions

    Surjection
    Definition
    A function is called surjective (or a surjection) or simply onto if
    every element of B is the image of some element of A.

    A B A B Is
    Not surjective surjective
    Functions

    Surjection
    Definition
    A function is called surjective (or a surjection) or simply onto if
    every element of B is the image of some element of A.

    A B A B Is
    Not surjective surjective
    Formal proposition that expresses f : A B being a surjection:
    b B. a A. f (a) = b
    Functions

    Bijections

    Definition
    A function is called bijective (or a bijection) or simply one-to-one
    and onto if it is both injective and surjective.

    A B

    You might also like