Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Chapter 1

    Uploaded by

    jignasha.patel
    TOC NOTES

    Copyright:

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

    Chapter 1

    Uploaded by

    jignasha.patel
    4 views2 pages
    TOC NOTES

    Original Title

    Chapter-1

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    TOC NOTES

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    4 views2 pages

    Chapter 1

    Uploaded by

    jignasha.patel
    TOC NOTES

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 2

    Chapter: 1

    Review of Mathematical Theory


    Sets:
    A set is a collection of elements. To indicate that x is an element of the set S, we write x ∈ S.
    The statement that x is not in S is written as x ∈/ S. A set is specified by enclosing some
    description of its elements in curly braces; for example, the set of all natural numbers 0, 1, 2, · ·
    is denoted by

    N = {0, 1, 2, 3, · · ·}

    We use ellipses (i.e.,. . .) when the meaning is clear, thus Jn = {1, 2, 3, · · · , n} represents the set
    of all natural numbers from 1 to n.

    When the need arises, we use more explicit notation, in which we write

    S = {i|i ≥ 0, i is even}

    Functions and Relations:


    A function is a rule that assigns to elements of one set (the function domain) a unique element
    of another set (the range). We write

    f : S1 → S2

    to indicate that the domain of the function f is a subset of S1 and that the range of f is a subset
    of S2. If the domain of f is all of S1, we say that f is a total function on S1; otherwise f is said to
    be a partial function on S1.

    1. Domain f = {x ∈ S1 | (x, y) ∈ f, for some y ∈ S2} = Df

    2. Range f = {y ∈ S2 | (x, y) ∈ f, for some x ∈ S1} = Rf

    3. The restriction of f to A ⊆ S1, f|A = {(x, y) ∈ f | x ∈ A}

    4. The inverse f −1 : S2 → S1 is {(y, x) | (x, y) ∈ f}

    5. f : S1 → S1 is called a function on S1

    6. If x ∈ Df then f is defined at x; otherwise f is undefined at x;

    7. f is a total function if Df = S1.


    8. f is a partial function if Df ⊆ S1

    9. f is an onto function or surjection if Rf = S2. If Rf ⊆ S2 then f is a function from S1(Df ) into S2

    10. f is a one to one function or injection if (f(x) = z and f(y) = z) ⇒ x = y 11. A total function f is an
    injection if it is both an injection and a surjection.

    A function can be represented by a set of pairs {(x1, y1),(x2, y2), · · · }, where each xi is an element in the
    domain of the function, and yi is the corresponding value in its range. For such a set to define a function,
    each xi can occur at most once as the first element of a pair. If this is not satisfied, such a set is called a
    relation.

    A specific kind of relation is an equivalence relation. A relation denoted r on X is an equivalence relation


    if it satisfies three rules, the reflexivity rule: (x, x) ∈ r ∀x ∈X the symmetry rule: (x, y) ∈ r then (y, x) ∈ r
    ∀x, y ∈X and the transitivity rule: (x, y) ∈ r,(y, z) ∈ r then (x, z) ∈ r ∀x, y, z ∈X

    Example: The relation congruence mod m (modulo m) on the set of the integers Z. i = j mod m if i − j is
    divisible by m; Z is partitioned into m equivalence classes:

    {· · · , −2m, −m, 0, m, 2m, · · ·} {· · · , −2m + 1, −m + 1, 1, m + 1, 2m + 1, · · · }

    {· · · , −2m + 2, −m + 2, 2, m + 2, 2m + 2, · · · } · · · {· · · , −m − 1, −1, m − 1, 2m, 3m − 1, · · · }

    Proof Techniques:
    We will give examples of proof by induction, proof by contradiction, and proof by Cantor
    diagonalization.

    In proof by induction, we have a sequence of statements P1, P2, · · · , about which we want to make
    some claim. Suppose that we know that the claim holds for all statements P1, P2, · · · , up to Pn. We then
    try to argue that this implies that the claim also holds for Pn+1. If we can carry out this inductive step for
    all positive n, and if we have some starting point for the induction, we can say that the claim holds for all
    statements in the sequence.

    The starting point for an induction is called the basis. The assumption that the claim holds for
    statements P1, P2, · · · , Pn is the induction hypothesis, and the argument connecting the induction
    hypothesis to Pn+1 is the induction step. Inductive arguments become clearer if we explicitly show these
    three parts.

    You might also like