Welcome to Edukum.com

Set, Relation, Function, Proof techniques

Set
A group or collection of "things", i.e., objects or numbers is defined as a set. Each member of the set is called an element of the set. Its examples include set of all books in a library, set of all prime numbers between 1 to 10, etc. It can also be symbolically represented as: S = {a, b} where a and b are elements of set S. In set, the repetition of elements doesn’t change the set. So, the sets {1, 2, 4}, {2, 4, 1} and {4, 1, 2} are same. This shows that any two sets are equal only if they contain same elements. Also, the set containing another set as its element is called set of sets.
A different method to detail a set is by finding and referring to other sets which has the same properties of elements as the original set. For example, if A = {1, 5, 8} and B = {5, 8}, we can define B as the set of elements of A that are greater than 1. We write this detail as:
B = {x: x ∈ A and x >1}.
The number of elements contained by a set is known as cardinality of set. For example, let us consider a set S= {a, v, f}. Here, the cardinality of set is 3 as there are 3 elements in the set.

Sets are of different types. They are as follows:

  1. Singleton Set
    A set is said to be singleton if it contains only one element. For example, S = {a}, S = {5}, etc.
  2. Empty Set
    A set which contains no element at all due to which it is empty is called empty/null set. It is represented by { } or \(\phi\). But, the set {\(\phi\)} is not a null set.
  3. Non-empty Set
    Any set other than empty set is known as non-empty set. For example, S = {a, b, f}, S = {1, 9}, etc.
  4. Finite Set
    A set which contains finite number of elements is called finite set. For example, S = {3, 4} which contains finite number of elements, i.e., 2.
  5. Infinite Set
    A set which is not finite and contains infinite number of elements is called an infinite set. For example, set of all real numbers, set of all integers, etc.
  6. Equal Set
    Two sets are equal if they contain same elements regardless of their order. For example, two sets A = {3, 7} and B = {7, 3} are equal sets as they contain the same elements, i.e., 3 and 7.
  7. Equinumerous Set
    The sets having the same cardinality are said to be equinumerous sets. For example, A = {a, b, c} and B = {d, f, g} are equinumerous sets as they have the same number of elements, i.e., 3.
  8. Universal Set
    Set of all the elements under consideration is known as universal set. It is denoted by capital letter U.
  9. Subset
    Any set D is a subset of set E, denoted by D ⊂ E, if every element of D is also an element of E. For example, if D = {a, b} and E = {a, b, c} then, D ⊂ E but D ⊆ E. Here as D is subset of E but D ≠ E, D is called proper subset of E and E is called superset of E. If D ⊆ E and also E ⊆ D, then we can say that D and E are equal sets.
  10. Power Set
    Let us consider a set, S = {a, b, c}. Then, power set of set S is defined as the set formed by the subsets of set S. It is denoted by 2S or P(S). So, the power set of S is,
    P(S) = {{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, { }}

Operation of Sets
With the help of various set operations, we can combine two sets to form a third set. These set operations are as follows:

  1. Union
    The union of any two sets is defined as the set which contains elements that belongs to at least one of the two sets, and possibly of both. The symbol ‘∪’ is used to denote union of two sets. It can also be defined as, for any two sets D and E,
    D ∪ E = {x: x ∈ D or x ∈ E}
    For example, if D = {a, b, c} and E= {f, g, h} then
    D ∪ E = {a, b, c, f, g, h}
  2. Intersection
    The intersection of any two sets is defined as the set which contains all the elements that the two sets have in common. The symbol ‘∩’ is used to denote union of two sets. It can also be defined as, for any two sets D and E,
    D ∩ E = {x: x ∈ D and x ∈ E}
    For example, if D= {a, b, c, d} and E = {c, f, t, y} then
    D ∩ E = {c}
    If two sets do not contain a common element between them, i.e., their intersection is empty, then the sets are called disjoint.
  3. Difference
    The difference of any two sets D and E is the set of all the elements of D that are not contained by E. It is denoted by D – E. It is defined by,
    D – E = {x: x ∈ D and x ∉ E}
    For example, if D= {a, b, c, d} and E = {c, f, t, y} then
    D – E = {a, b, d}
  4. Complement
    Let us consider a set S such that it is a subset of universal set U. Then, the complement of set S contains all the elements of the universal set that are not in the set S. Every set has a complement. It is denoted by SC or S' and is defined by,
    SC = {x: x ∈ U and x ∉ S}
    For example, if U= {a, b, c, d} and S = {a, b} then
    SC = {c, d}
    Now, we can clearly say that S ∪ SC = U and S ∩ SC = { }.

Partition of Sets
A partition of any set Sis a grouping of the all the elements of S into non-empty subsets, so that each element is included in one and only one of the subsets. For example, if S = {5, 6, 8, 9} then {{5, 6}, {8}, {9}} is a partition of S but {{5, 6}, {8, 9}} is not a partition of S. If N is a set of all the natural numbers, then the sets of odd and even natural numbers form a partition of N.

Properties of Sets
If A, B and C are sets, then the following laws hold for them:

  • Idempotent Law
    A ∪ A = A
    A ∩ A = A
  • Commutative Law
    A ∪ B = B ∪ A
    A ∩ B = B ∩ A
  • Associative Law
    (A ∪ B) ∪ C = A ∪ (B ∪ C)
    (A ∩ B) ∩ C = A ∩ (B ∩ C)
  • Distributive Law
    (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
    (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
  • Absorption Law
    (A ∪ B) ∩ A = A
    (A ∩ B) ∪ A = A
  • DeMorgan’s Law
    A - (B ∪ C) = (A - B) ∩ (A - C)
    A - (B ∩ C) = (A - B) ∪ (A - C)

Important proofs of the above laws

  1. Prove A - (B ∪ C) = (A - B) ∩ (A - C).
    Solution:
    Here, we have to show that A - (B ∪ C) ⊆ (A - B) ∩ (A - C).
    For this, we show LHS ⊆ RHS and RHS ⊆ LHS.
    First for L.H.S.,
    x ∈ A – (B ∪ C) → x ∈ A & x ∉ (B ∪ C)
    → x ∈ A & (x ∉ B & x ∉ C)
    → x ∈ A & x ∉ B and x ∈ A & x ∉ C
    → x ∈ A - B and x ∈ A – C
    → x ∈ ((A – B) ∩ (A – C))
    Thus, A - (B ∪ C) ⊆ (A - B) ∩ (A - C).
    Conversely,
    x ∈ ((A – B) ∩ (A – C)) → x ∈ A - B and x ∈ A – C
    → x ∈ A & x ∉ B and x ∈ A & x ∉ C
    → x ∈ A & (x ∉ B & x ∉ C)
    → x ∈ A & x ∉ (B ∪ C)
    → x ∈ A – (B ∪ C)
    Thus, (A - B) ∩ (A - C) ⊆ A - (B ∪ C).
    This proves A - (B ∪ C) = (A - B) ∩ (A - C).
  2. Prove (A ∩ B) ∩ C = A ∩ (B ∩ C).
    Solution:
    Here, we have to show that (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C).
    For this, we show LHS ⊆ RHS and RHS ⊆ LHS.
    First for L.H.S.,
    x ∈ (A ∩ B) ∩ C → x ∈ (A ∩ B) & x ∈ C
    → x ∈ A & x ∈ B & x ∈ C
    → x ∈ A & x ∈ (B ∩ C)
    → x ∈ A ∩ (B ∩ C)
    Thus, (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C).
    Conversely,
    x ∈ A ∩ (B ∩ C) → x ∈ A & x ∈ (B ∩ C)
    → x ∈ A & x ∈ B & x ∈ C
    → x ∈ (A ∩ B) & x ∈ C
    → x ∈ (A ∩ B) ∩ C
    Thus, A ∩ (B ∩ C) ⊆ (A ∩ B) ∩ C.
    This proves (A ∩ B) ∩ C = A ∩ (B ∩ C).

To understand set relations, first, we have to understand the concept of ordered pair and Cartesian product.

Ordered Pair
An ordered pair is defined as the pair of objects which has a specific order associated with them. An ordered pair (a, b) is built from two objects, i.e., a and b which are also called the components of the ordered pair. As the name suggests, the order matters, i.e., (a, b) and (b, a) are two different ordered pairs unless a = b. Also the two components of the ordered pair need not to be different, i.e., (a, a) is a legitimate ordered pair.
For any two ordered pairs (a, b) and (f, g), they are equal if and only if a = f and f = g, i.e., (3, 5) and (5, 3) are not equal as their respective first and second elements are not equal to each other.

Cartesian Product
The Cartesian product of any two sets A and B (also called the product set or cross product), denoted by A×B, is defined to be the set of all ordered pairs(a, b) where a ∈ A and b ∈ B. For example,
Let us suppose A = {a, b, c} and B = {3, 6, 9}, then the Cartesian product of A and B is,
A × B = {(a, 3), (a, 6), (a, 9), (b, 3), (b, 6), (b, 9), (c, 3), (c, 6), (c, 9)}
The Cartesian product can also be expressed as,
A × B = {(a, b): a ∈ A, b ∈ B}

Relation
The relation is simply defined as a set of ordered pairs. A binary relation R on any two sets A and B, i.e., R (A, B), is simply a subset of the Cartesian product of A and B. Its notation is written as R ⊆ A×B.
If A = {4, 5, 6} and B = {7, 8, 9}, then R is given by,
R = {(4, 7), (4, 8), (5, 8)}.

A relation R (A, B) can be represented pictorially. For the above given two sets A and B,

Fig. Pictorial representation of a relation
Fig. Pictorial Representation of a Relation

The above mapping shows the relation between A and B.
An n-ary relation R (A1, A2, … , An) is a subset of (A1 × A2 ×···× An). Here, 1-ary, 2-ary, and 3-ary relations are called unary, binary and ternary relations respectively.

Types of Relation

  1. Reflexive Relation
    A relation R is said to be a reflexive relation if R is a relation in A and for every a∈A, (a, a)∈ R, i.e., ∀x ∈ A, (x, x) ∈ R. A relation is reflexive if each element possesses an edge looping around on it.
    Its simple example is,
    We know that every real number is equal to itself. Therefore "is equal to" is a reflexive relation on the set of real numbers.
  2. Symmetric Relation
    A relation R is said to be a symmetric relation if R is a relation in A and (a, b)∈R implies (b, c)∈ R, i.e., for ∀x, y ∈ A if (x, y) ∈ R then (y, x) ∈ R. The graph of a symmetric relation will show for every arrow from a to b an opposite arrow from b to a.
    Its simple example is,
    In the set of all real numbers, "is equal to" relation is symmetric.
  3. Anti-Symmetric Relation
    A relation R which itself is a relation in A is said to be an anti-symmetric relation if (a, b)∈R and (b, a)∈R implies a = b. It can also be defined as for anti-symmetric relation R whenever (a, b) ∈ R and a, b are distinct, then (b, a) ∉ R.
    Its simple example is,
    In a set of all natural numbers the relation R defined by "x divides y if and only if (x, y)∈R" is anti-symmetric. For x|y and y|x then x = y.
  4. Transitive Relation 
    A relation R which itself is a relation in A is said to be a transitive relation if (a, b)∈R and (b, c)∈R implies (a, c)∈R.
    Its simple example is,
    In the set of all real numbers the relation "is equal to" is a transitive relation. For a = b, b = c implies a = c.
  5. Equivalence Relation
    A relation R which itself is a relation in A is said to be an equivalence relation if it is reflexive, symmetric and transitive. The classes of an equivalence relation are called equivalence classes.
    Its simple example is,
    In the set of all real numbers the relation "is equal to" is an equivalence relation for a∈R, a = a, b = a implies b = a and a = b, b = c implies a = c.
    Also, let Z = {…., -10, -9, …., 0, …., 9, 10, …..}
    Then, the equivalence relation R is given by,
    R = {(x, y): x, y ∈Z, (x-y) is divisible by 5}
    And the equivalence classes,
    [0] = {….., -5, 0, 5, 10, …..}
    [1] = {….., -4, 1, 6, 11, …..}
    [2] = {….., -3, 2, 7, 12, …..}
    [3] = {….., -2, 3, 8, 13, …..}
    [4] = {….., -1, 4, 9, 14, …..}
    Π = {[0], [1], [2], [3], [4]}
    = {[-12], [-11], [-10], [-9], [-8]}

Partial Order
A relation R which itself is a relation in A is said to be a partial order relation if it is reflexive, anti-symmetric and transitive.
Its simple example is,
Let A = {a, d, h}
Then, R = {(a, a), (d, d), (h, h), (a, d), (d, h), (a, h)} is a partial order relation.
A partial order relation is called total order relation if ∀x, y ∈A then (a, b) ∈R or (b, a) ∈R.
Its simple example is,
Let S = {a, d, h}
Then, R = {(a, a), (d, d), (h, h), (d, a), (d, h), (a, h)} is a total order relation.
Also, a set on which there is a partial ordering defined is called a partial order set.
For example, A = {{a}, {d}, {h}, {a, d}, {b, d, c}, {a, b, c, d, e}}
Now, for a given set A = {{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} the relation T = {{a}, {c}, {b, c}} is called subset relation for T ⊆ S.

Functions
In set theory, a function from set A to set B is defined as a relation which symbolically associates each element of set A with a unique element of set B. In other words, a function is defined as a set of ordered pairs in which each x-element has only one y-element associated with it, where x and y are distinct elements. A function from set A to B is denoted by f : A→B, written as f(a) = b and is said f maps and into b. Here, A is called domain of the function and B is called co-domain/range of the function. Also, a is called the image of b and b is called pre-image of b under the function f.

Fig. Function f : A→B
Fig. Function f : A→B

Every function is a relation but not every relation is a function. For example, the relation in the figure below is not a function since p maps with two elements, i.e., 1 and 5, instead of just one distinct element.

Fig. Function f : A→B
Fig. Function f : A→B

Types of Functions
There are mainly three types of functions. They are:

  1. Injective Function
    Let f be a function from A to B, then f is injective if a distinct element of the domain of the function is mapped to a distinct element of the range of the function f. So, A function f : A→B is injective if:
    f (a) = f (b) ⇒ a = b.
    An injective function is also called one to one function.
    Fig. Injective function f : A→B
    Fig. Injective function f : A→B
    For example, let us consider the function f : R→R with f (x) = x2. Then f (2) = f (−2) = 4 and so this function is not one to one (injective).
  2. Surjective Function
    Let f be a function from A to B, then f is surjective if every distinct element of a range of the function appears as an image of at least one element of the domain of the function f. So, a function f : A→B is surjective if given any b ∈ B, there exists an a ∈A such that f (a) = b. Consider the function f : R→R with f (x) = x +1. Clearly, given any r ∈ R then f (r − 1) = r and so f is the surjective function.
    A surjective function is also called onto function.
    Fig. Surjective function f : A→B
    Fig. Surjective function f : A→B
  3. Bijective Function:
    Let f be a function from A to B, then f is bijective if it is both one to one and onto. In other words, if a function is both injective and surjective, it is said to be bijective.
    Fig. Bijective function by A→B
    Fig. Bijective function by A→B

Other types of functions are as follows:

    1. Inverse Function
      Let f be a bijective function from A to B, then we define f—1 : B→A by f—1(b)=a, where a is the unique pre-image of b. The function f—1 is called the inverse of function f.
    2. Composite Function
      Let f be a function from a setAto a setBand letgbe a function from set B to a set C.Then the composition of functions f and g, denoted b ygofis the function from set A to set C that satisfies
      gf(x) = g(f(x)) for all x in A.
    3. Identity Function
      The identity function 1A:A→A is a function such that 1A(a) = a for all a ∈A. Clearly, when the inverse of the function exists then we have that f—1 o f = 1A and f o f—1 = 1B.
    4. Dovetailing
      The method of linking the details of various sets is defined as dovetailing. It interweaves different computations and executes them at once. To explain this technique, we prove,
      “The union of any finite number of the countably infinite set is countably infinite.”
      Proof
      Let us consider 3 pair wise disjoint countably infinite sets A, B and C such that
      A = {a0, a1, a2 …}
      B = {b0, b1, b2 …}
      C = {c0, c1, c2 …}
      The union of the three sets A, B and C is listed as:
      A ∪ B ∪ C = {a0, b0, c0, a1, b1, c1 …}
      Fig. Dovetailing of A ∪ B ∪ C
      Fig. Dovetailing of A ∪ B ∪ C
      The listing amounts to a way of visiting all the elements in A ∪ B ∪ C by alternating between different sets as shown in the figure above. We first visit the first element of the first set, a first element of the second set, and a first element of the third set and so on.

Principle of Mathematical Induction
Let A be a set of natural numbers such that

      • 0 ∈ A and
      • For each natural number n, if {0, 1, ..., n} ∈ A, then (n + 1) ∈ A. Then A = N.

This is the principle of mathematical induction.
In simple term, the principle of mathematical induction states that any set of natural numbers which contains element 0 and with the property that it contains (n+1) whenever it contains all the numbers up to and including n, must in fact be the set of all natural numbers.
This principle is used to prove statements in the form; “For all natural numbers n, P is true.”

There are three steps we have to follow to prove a statement using the principle of mathematical induction. They are as follows

  • Basic Step
    In this step, we show that 0 ∈ A, i.e., P is true of 0.
  • Induction Hypothesis
    This hypothesis is simply an assumption that for some fixed but arbitrary n≥ 0, the property P holds for each and every natural number up to and including n, i.e., 0, 1, 2, ..., n.
  • Induction Step
    In this step, using the induction hypothesis, we show that P holds true for n+1. Thus, by this principle, we prove that A is equal to N, i.e., P is true for every natural number.

Important Examples

  1. Prove by induction 1 + 2 + 3 + … + n = \(\frac{(n^2 + n)}{2}\)
    Solution:
    1. Basic step:
      To show that 0 ∈ A,
      For n = 0,
      0 = (0+ 0)/2 = 0(True).
      For n = 1,
      1 = (1+ 1)/2 = 1(True).
    2. Induction Hypothesis:
      Here, let m≤ n such that,
      ∑ m = \(\frac{(m^2 + m)}{2}\)
    3. Induction step:
      Here, we have to show ∑ m+ 1 = \(\frac{((m + 1)^2 + (m + 1))}{2}\)
      We have,
      ∑ (m + 1) = (m + 1) + ∑ m
      = (m + 1) + \(\frac{(m^2 + m)}{2}\)
      = \(\frac{{2(m + 1) + m (m+ 1)}}{2}\)
      = \(\frac{(m + 1) (2+ m)}{2}
      Thus, ∑ (m + 1) = \(\frac{((m+ 1)^2 + (m+ 1))}{2}\)
      Hence, proved.
  2. Prove by induction for every integer n > 0, the number 42n+1 + 3n+2 is multiple of 13.
    Solution
    1. Basic step:
      For n = 0,
      42*0+1 + 30+2 = 41 + 32 = 13.
      For n = 1,
      42*1+1 + 31+2 = 43 + 33 = 91 = 13*7.
    2. Induction Hypothesis:
      Here, let m≤ n such that,
      42m+1 + 3m+2 = 13(r), where r is any integer.
    3. Induction step:
      Here, we have to show 42(m+1) + 1 + 3 (m+1)+2 is a multiple of 13.
      We have,
      42(m+1) + 1 + 3 (m+1)+2 = 42m+1 42 + 3m+2 3
      = 42 42m+1 + 42 (3m+2 - 3m+2) + 3* 3m+2
      = 42 (42m+1 + 3m+2) + 3m+2 (-42 + 3)
      = 42 (13(r)) + 3m+2 (-13)
      = 13(16r + 3m+2)
      Hence, the number 42n+1 + 3n+2 is a multiple of 13.
      Proved.

The Pigeonhole Principle
The pigeonhole principle states that if A and B are two finite sets and |A| > |B|, then there exists no one to one function from A to B. It means that if we try to pair off elements of A known as “pigeons” with elements of B known as “pigeonholes”, sooner or later we will have to put more than one pigeon in a pigeonhole so that one to one function doesn’t exist between them.
The pigeonhole principle can be used to show that results must be true because they are “too big to fail.” This principle matters because given a large enough number of objects with a restricted number of properties, eventually at least two of them will share a property.

The following steps are necessary for using this principle to prove a statement.

  1. First find the m objects to distribute.
  2. Then find the n < m labels into which to distribute them.
  3. Finally, we finish off by the pigeonhole principle that there must be two objects in some label.
  4. The details of how to proceed from there are specific to the particular proof that we do.

Example

  • In an office of 93 staffs, prove by pigeonhole principle that there will be at least 1 month where 7 or more staffs have their birthday.
    Solution:
    First of all label each staff with their birth month. There will be possible m labels. As the number of staffs is 93 and the possible labels are 12, so \(\frac{93}{12}\) = 7.5, i.e. more than 7 staffs have the common birth month.
    Hence, proved.

Proof Techniques
Since every proof is designed to give a different result, every proof is different. Here, we have to learn about four fundamental proof techniques, i.e., diagonalization principle, mathematical induction, contradiction and the pigeonhole principle.

Diagonalization Principle
Let R be a binary relation on a set A, and let D (the ‘diagonal’ set for relation R) be {a: a ∈ A and (a, a) ∉ R}. For each, a ∈ A let Ra = (b: b ∈ A and (a, b) ∈ R}. Then D is distinct from each Ra. This is the diagonalization principle. It is a dominant and useful proof technique. This principle can also be rephrased as The complement of the diagonal is different from each and every row.

For example, let us consider a set A given by A = {a, b, c, d}, and a relation given by R = {(a, b), (a, c), (b, b), (b, d), (c, b), (c, d), (d, a)}. Now, R can be shown in a table as:

  a b c d
a 0 1 1 0
b 0 1 0 1
c 0 1 0 1
d 1 0 0 0

Here, we can see that the diagonal is D = {0, 1, 0, 0}.
Now, according to the diagonalization principle, we know that the complement of the diagonal (replacing 1’s with 0’s and vice versa) is different from each row.
The reversed diagonal in the example is D = {1, 0, 1, 1} and we can see that it is different from each and every row of the array.
The reversed diagonal differs from the first row in the first element (we have taken the complement in the diagonal), it differs from the second row in the second element, etc.
This principle is mainly used to prove uncountability of sets.
Example

  • Show that set of real numbers in the interval [0, 1) is uncountable.
    Solution:
    Real numbers in [0, 1) that are not rational, have infinite decimal expansions. We can assume that rational numbers also have infinite expansions consisting of zeros after the rightmost non-zero digit. Decimal digits have binary representations, so we can represent the numbers by binary sequences.
    Let us assume that the numbers can be ordered. The ordering will give an infinite table consisting of 0 and 1. The complement of the diagonal of this table is an infinite sequence of 0 and 1, and as such, it represents a real number that has to be somewhere in the ordering. However, this cannot be the first number, since the complement of the diagonal differs from the first row in the first position. Similarly, it cannot be the second number; it cannot be the third number, etc.
    Thus, the number represented by the complement of the diagonal does not occur in the ordering.
    This contradicts the assumption that the numbers can be ordered.
    Therefore the set of all real numbers in [0, 1) is uncountable.
    Alternative way,
    Given that we have to show the set of real numbers in [0, 1) is uncountable. For this, let us assume the contrary, i.e., that [0, 1) is countable.
    Then the elements can be listed in decimal expansion as follows:
    x1 = 0. a11 a12 a13...
    x2 = 0. a21 a22 a23...
    x3 = 0. a31 a32 a33..., etc.
    Here each xi is the decimal expansion of a number between 0 and 1.
    Now, let us define a number ‘x’ such that its ith digit is
    0 if aii ≠ 0 and
    1 if aii = 0.
    This gives us x ≠ xi for all i. But as x is a real number in the given interval, it must be equal to any xi. Hence, there occurs a contradiction which shows that our initial assumption was wrong.
    Thus, the set of real numbers in the interval [0, 1) is uncountable.

Proof by Contradiction
A proof by contradiction institutes the certainty of a given suggestion by the theory that it is false and the successive illustration of a conclusion that is conflicting with something that is proven to be true.The method of proof by contradiction is to suppose that a statement is not true and then to show that that hypothesis leads to a contradiction. Since the contradiction is always false, our original assumption becomes true so the original statement is proved.

Example

  • Prove the following statement by contradiction: For all integers n, if nis odd, then n is odd.
    Proof:
    Here, we take the negation of the given statement and suppose it to be true. So, let us assume, to the contrary, that there exists an integer n such thatn2is odd and n is even. By definition of even number, we have
    n = 2p for some integer p.
    So, by substitution, we have
    2.n = (2p). (2p) = 2 (2.p2)
    Now (2.p2) is an integer because products of integers are the integer, and also 2 and p are integers. Hence, we can write,
    2.n = 2. (some integer) or n= 2. (some integer)
    and so by definition of neven, n is even.
    Since n is even, n2, which is the product of n with itself, is also even. This contradicts our supposition that nis odd. Hence, the supposition is false and the proposition is true.
    Proved.

Reference

  • H.R. Lewis, C. H. (1998). Elements of Theory of Computation. Pearson Education.
  • Shadrach, R. (n.d.). Introduction to sets. Retrieved from https://www.mathsisfun.com: https://www.mathsisfun.com/sets/sets-introduction.html
  • Sipser, M. (1996). Introduction to Theory of Computation. Thomson Course Technology.
  • Definition of a Relation and Function. (n.d.). Retrieved from http://www.regentsprep.org: http://www.regentsprep.org/regents/math/algtrig/atp5/lfunction.htm
  • H.R. Lewis, C. H. (1998). Elements of Theory of Computation. Pearson Education.
  • Types of relations. (n.d.). Retrieved from http://www.kwiznet.com: http://www.kwiznet.com/p/takeQuiz.php?ChapterID=10907&CurriculumID=48&Num=8.8
  • Definition of a Relation and Function. (n.d.). Retrieved from http://www.regentsprep.org: http://www.regentsprep.org/regents/math/algtrig/atp5/lfunction.htm
  • H.R. Lewis, C. H. (1998). Elements of Theory of Computation. Pearson Education.
  • H.R. Lewis, C. H. (1998). Elements of Theory of Computation. Pearson Education.
  • Lecture. (n.d.). Retrieved from http://dept.cs.williams.edu: http://dept.cs.williams.edu/~andrea/cs361/Lectures/lect3.pdf
  • H.R. Lewis, C. H. (1998). Elements of Theory of Computation. Pearson Education.
  • Lecture. (n.d.). Retrieved from http://dept.cs.williams.edu: http://dept.cs.williams.edu/~andrea/cs361/Lectures/lect3.pdf

© 2019 EDUKUM.COM ALL RIGHTS RESERVED


#Things To Remember



1040 Views