Unit 1 | unit 1 mathematical logic and set theory

DMGT

Unit - 1

Set theory, relations and functions

1.1 Sets: Review of propositions and logical operations

Introduction and significance of discrete mathematics

Computer science is all about the study of problems and solving problems by some process. The main goal is to develop an algorithm (a step by step list of some instructions in order to solve a certain problem).

According to K.H Rosen, discreet mathematics has more than one purpose but more importantly it equips computer science students with logical and mathematical skills.

By B.Miller and D. Ranum, A computing machine end is to develop an algorithm, a measure by step list of instructions in work outing a job. Algorithm are finite procedures that if followed will work out the job.

Discreet mathematics is the study of mathematics which deals on discreet structures like graphs, trees and networks.

It deals with discreet objects like integers and rational numbers which are separated from each other

Discreet mathematics is the language of computer science

The field of mathematics that are considered to be part of discrete mathematics include graph theory and the theory of computation. Topics in number theory such as congruence’s and recurrence relations are also considered part of discrete mathematics.

Theoretical computer science includes areas of Theoretical computer science includes areas of discrete mathematics relevant to computing. It draws heavily on graph theory and logic. Included within theoretical computer science is the study of algorithms for computing mathematical results.

Theoretical computer science also includes the study of various continuous computational topics.

We study about the following topics under discreet mathematics-

1. Information theory

2. Mathematical logic

3. Set theory

4. Graph theory

5. Discreet probability theory

6. Number theory

7. Trees

8. Topology

Statement-

When a declarative sentence which is true or false but not both is called statement.

The truth values “true” and “false” of a statement are denoted by T ad F respectively. We can denote them by 0 and 1 as well.

Examples of statements are-

1. 2 + 11 = 12

2. Jaipur is in India

Truth table-

The table showing the truth values of a statement formula is called ‘truth table’.

The truth table for a given statement form displays the truth values that correspond to all possible combinations of truth values for its component statement variables.

Laws of formal-

1. Law of contradiction- According to the law of contradiction the same predicate cannot be both affirmed and denied precisely of the same subject

For every preposition p is not the same that p is both true and false.

2. Law of excluded middle- If p is a statement, then either p is true or p is false and there cannot be middle ground.

Connectives-

Statements in mathematical logic are combinations of simpler statements joined by words and phrases like ‘and’. ‘or’, ‘if and only if’, etc. These words and phrases are called logical connectives.

Disjunction-

Definition: The disjunction of two propositions p and q is the compound statement 10 Elementary Logic p or q, denoted by p ∨ q.

For example, ‘Aman has a house or Amit has a house’ Is the disjunction of p and q, where-

p: Aman has a house, and

q: Amit has a house.

Example: Obtain the truth value of the disjunction of ‘The earth is flat’. And ‘3 + 5 = 2’.

Solution: Let p denote ‘The earth is flat,’ and q denote ‘3 + 5 = 2’. Then we know that the truth values of both p and q are F. Therefore, the truth value of p ∨ q is F.

Example-Let p: 5 + 2 = 7, q: 9 + 2 = 10 then p ∨q: 5 + 2 = 7 or 9 + 2 = 10

Truth table for disjunction-

Exclusive disjunction-

The exclusive disjunction of two propositions p and q is the statement ‘Either p is true or q is true, but both are not true. Either p is true or q is true, but both are not true’. We denote this by p ⊕q.

Conjunction-

Definition: We call the compound statement ‘p and q’ the conjunction of the

Statements p and q. We denote this by p ∧q.

Example- ‘3 + 1 ≠ 7 ∧ 2 > 0’ is the conjunction of ‘3 + 1 ≠ 7’ and ‘2 > 0’.

Example-

Obtain the truth value of the conjunction of ‘2 ÷5 = 1’ and ‘Ramesh is in Jaipur’.

Solution: Let p: 2 ÷5 = 1, and

q: Ramesh is in Jaipur.

Then the truth value of p is F. Therefore, from Table 3 you will find that the truth

Value of p ∧ q is F.

Negation-

The negation of a proposition p is ‘not p’, denoted by ~p.

Example-

If p is ‘Smriti is at the station.’, then ~ p is ‘Smriti is not at the station’.

Similarly, if p is ‘No person can live without food.’,~ p is ‘At least one person can live without food.’

Conditional connectives-

Given any two propositions p and q, we denote the statement ‘If p, then q’ by

p→ q. We also read this as ‘p implies q’. Or ‘p is sufficient for q’, or ‘p only if q’. We also call p the hypothesis and q the conclusion. Further, a statement of the form p → q is called a conditional statement.

Truth table for implication-

Definition for converse-

The converse of p → q is q → p. In this case we also say ‘p is necessary for q’, or ‘p if q’when we combine an implication and its converse, then-

Let p and q be two propositions. The compound statement

(p→ q) ∧(q → p) is the bi-conditional of p and q. We denote it by p ↔ q, and

(Read) as ‘p if and only q’.

We use ‘if and only ‘if’ as iff

We also say that ‘p implies and is implied by q’. Or ‘p is necessary and sufficient forq’.

Example- Pradeep will get good marks if and only if he studies regularly means that Pradeep will get good marks if he studies regularly and Pradeep studies regularly if he gets good marks.

Truth table for two-way implication-

Proposition-

A proposition (or statement) is a declarative statement which is true or false, but not both.

Example-

(i) Ice floats in water.

(ii) China is in Europe

(iii) 2 + 2 = 4

(iv) 2 + 2 = 5

Compound proposition-

Many propositions are composite, that is, composed of sub-propositions and various connectives discussed

Subsequently such composite propositions are called compound Propositions. A proposition is said to be primitive if it cannot be broken down into simpler propositions, that is, if it is not composite.

Following two propositions are composite:

“Roses are red and violets are blue.” and “John is smart or he studies every night.”

Logical Connectives

Basic logical operations-

1. Conjunction- p ⋀ q

Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions. Symbolically,

p∧q

Read “p and q,” denotes the conjunction of p and q. Since p ∧q is a proposition it has a truth value, and this truth

Value depends only on the truth values of p and q.

Note- If p and q are true, then p ∧q is true; otherwise p ∧q is false.

2. Disjunction, p ∨q

Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions. Symbolically,

p∨q

Read “p or q,” denotes the disjunction of p and q. The truth value of p ∨q depends only on the truth values of p

And q as follows-

If p and q are false, then p ∨q is false; otherwise p ∨q is true

Negation-

Given any proposition p, another proposition, called the negation of p, can be formed by writing “It is not true that . . .” or “It is false that . . .” before p or, if possible, by inserting in p the word “not.” Symbolically, the negation of p, read “not p,” is denoted by

￢p

The truth value of ￢p depends on the truth value of p as follows-

If p is true, then ￢p is false; and if p is false, then ￢p is true

Basic logical operations-

1. Conjunction- p ⋀ q

Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions. Symbolically,

p∧q

Read “p and q,” denotes the conjunction of p and q. Since p ∧q is a proposition it has a truth value, and this truth

Value depends only on the truth values of p and q.

Note- If p and q are true, then p ∧q is true; otherwise p ∧q is false.

2. Disjunction, p ∨q

Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions. Symbolically,

p∨q

Read “p or q,” denotes the disjunction of p and q. The truth value of p ∨q depends only on the truth values of p

And q as follows-

If p and q are false, then p ∨q is false; otherwise p ∨q is true

Key takeaways-

Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions.
Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions
Given any proposition p, another proposition, called the negation of p, can be formed by writing “It is not true that . . .” or “It is false that . . .” before p or, if possible, by inserting in p the word “not.” Symbolically, the negation of p, read “not p,” is denoted by￢p
If p and q are true, then p ∧q is true; otherwise p ∧q is false.
When a declarative sentence which is true or false but not both is called statement.
The table showing the truth values of a statement formula is called ‘truth table’.
Statements in mathematical logic are combinations of simpler statements joined by words and phrases like ‘and’. ‘or’, ‘if and only if’, etc. These words and phrases are called logical connectives.

Principle of Inclusion and Exclusion

There is a formula for n(A ∪ B) even when they are not disjoint, called the Inclusion–Exclusion Principle

The Inclusion-Exclusion principle can be stated as below-

Let A and B any two finite sets, then-

Meaning- Here if we have to find the number of elements in the union of A and B.

So then we add n(A) and n(B) which means we are including these two.

And then we exclude .

Note- For three sets-

If we have three finite sets A, B and C then-

Example: Find the number of students at a college choosing at least one of the subject from mathematics, physics and statistics.

The data is given as-

65 study maths, 45 study physics, 42 study statistics

20 study maths and physics, 25 study maths and statistics, 15 study physics and statistics and 8 study all the three subjects.

Sol.

Here we need to find

Now by using Inclusion-Exclusion principle-

Which gives-

Therefore, we find that 100 students study at least one of the three subjects.

Example:

Suppose a list A contains the 30 students in a mathematics class, and a list B contains the 35 students in an English class, and suppose there are 20 names on both lists. Find the number of students: (a) only on list A, (b) only on list B, (c) on list A or B (or both), (d) on exactly one list.

Sol:

(a) List A has 30 names and 20 are on list B; hence 30 − 20 = 10 names are only on list A.

(b) Similarly, 35 − 20 = 15 are only on list B.

n(A ∪ B) = n(A) + n(B) − n(A ∩ B) = 30 + 35 − 20 = 45.

In other words, we combine the two lists and then cross out the 20 names which appear twice.

(d) By (a) and (b), 10 + 15 = 25 names are only on one list; that is, n(A ⊕ B) = 25.

1.2 Principal of mathematical induction

Mathematical induction is a mathematical technique is used to prove a statement, a theorem or a formula is true for every natural number.

An essential property of the set N = {1, 2, 3, …} of positive integers follows:

Principle of Mathematical Induction I: Let P be a proposition defined on the positive integers N; that is, P(n) is either true or false for each n ∈ N. Suppose P has the following two properties:

(i) P(1) is true.

(ii) P(k + 1) is true whenever P(k) is true.

Then P is true for every positive integer n ∈ N.

We shall not prove this principle. In fact, this principle is usually given as one of the axioms when N is developed axiomatically.

Principle of Mathematical Induction II: Let P be a proposition defined on the positive integers N such that:

(i) P(1) is true.

(ii) P(k) is true whenever P(j) is true for all 1 ≤ j < k.

Then P is true for every positive integer n ∈ N.

Note: Sometimes one wants to prove that a proposition P is true for the set of integers {a, a + 1, a + 2, a + 3, . . .} where a is any integer, possibly zero. This can be done by simply replacing 1 by a in either of the above Principles of Mathematical Induction.

The technique has two steps to prove any statement-

1. Base step (it proves that a statement is true for the initial value)

2. Inductive step (it proves that is the statement is true for n’th iteration then it is also true for iteration.

Example-1:

Sol. Here for n = 1, 1 = 1²

Now let us assume that the statement is true for n = k

Hence we assume that is true.

Now we need to prove that

So that which satisfies the second step.

Hence-

Example-2: Prove 1+2+...+n=n(n+1)/2 using a proof by induction

Sol.

Let n=1: 1 = 1(1+1)/2 = 1(2)/2 = 1 is true,

Step-1: Assume n=k holds: 1+2+...+k=k(k+1)/2

Show n=k+1 holds: 1+2+...+k+(k+1)=(k+1)((k+1)+1)/2

Substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.

Step-2: Now start with the left side of the equation

1+2+...+(k+1)=1+2+...+k+(k+1)

=k(k+1)/2 + (k+1)

=(k(k+1) + 2(k+1))/2 by 2/2=1 and distribution of division over addition

=(k+2)(k+1)/2 by distribution of multiplication over addition

=(k+1)(k+2)/2 by commutativity of multiplication.

Example-3: Prove the following by using the principle of mathematical induction for all n ∈ N-

Sol. Here, n = 1, , which is true

Step-1: Assume n = k holds-

Now show n = k + 1 also holds-

Consider-

Which is also true for n = k + 1

Hence proved.

Strong inductions-

It is another form of mathematical induction. By using this we can prove that a propositional function, P(n) is true for all positive integers n.

Working steps-

1. Base step- this proves that the initial proposition P(1) is true.

2. It proves that the conditional statement[P(1)∧P(2)∧P(3)∧⋯∧P(k)]→P(k+1) is true for positive integers k.

Key takeaways-

Mathematical induction is a mathematical technique is used to prove a statement, a theorem or a formula is true for every natural number.

1.3 Review of sets, types and operations on sets

Sets- A set is a collection of well-defined objects which are called the elements or members of the set.

We generally use capital letters to denote sets and lowercase letters for elements.

If any element which exists in the set is to be denoted as-

Suppose an element ‘a’ is from a set X, then it is represented as- aX

Which means the element ‘a’ belongs to the set X.

If the element is not form the group then we use ‘not belongs to’.

Representation of sets-

There are two ways to represent sets.

1. In first way, the elements of the set are separated by comma and contained in the bracket-{ }.

2. The second way is that we define the characteristic of the element.

For example-

Suppose we have a set ‘A’ of all odd integers which are greater than 3.

Then we can represent it two ways-

1. A = {5, 7, 9…….}

2. A = {x | x is an odd integer, x>3 }

Subsets-

Let every element of set X is also an element of a set Y, then X is said to be the subset of Y.

Symbolically it is written as-

Which is read as- X is the subset of Y.

Note- If X = Y then

Proper sub-set-

A set X is called proper subset the set Y is-

1. X is subset of Y

2. Y is not subset of X

Note- every set is a subset to itself.

Equal sets-

If X and Y are two sets such that every element of X is an element of Y and every element of Y is an element of X, the set and set Y will be equal always.

We write it as X = Y and read as X and Y are identical.

Super set-

If X is a subset of Y, then Y is called a super set of X.

Null set-

A set which does not contain any element is known as null set.

We denote a null set by ∅

The null set is a subset of every set.

Singleton-

A set which has only one element is called singleton.

Example- A = {10} and B = {∅}

Theorem- if ∅ and ∅’ are empty sets then ∅=∅’

Proof: Let ∅≠ ∅’ then the following conditions must be true-

1. There is element x∈∅ such that x∉∅’

2. There is element x∈∅’ such that x∉∅.

But both these conditions are false since ∅’ and ∅’ has any elements if follows that ∅=∅’.

Operations on sets-

1. Union and intersection-

Union-We denote union of two sets as- A∪B, which is the set of all elements which belongs to A or to B.

That is-

A∪B = {x |x∈∅A or x∈∅B}

Intersection- We denote intersection of two sets as- A∩B, which is the set of all elements which belongs to A and to B.

That is-

A∩B = {x |x∈∅A and x∈∅B }

Note- Two sets are said to be disjoint if they have no common elements in common.

Example: If A = {1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8, 9} and C = {5, 6, 7, 8, 9, 10}

Then-

A∪B = {1, 2, 3, 4, 5, 6,7, 8, 9}

A∪C = {1, 2, 3, 4, 5, 6,7, 8, 9,10}

B∪C = {4, 5, 6,7, 8, 9, 10}

A∩B = {4, 5, 6}

A∩C = {5, 6}

B∩C = {5, 6, 7, 8, 9}

Property-1-

An element x belongs to the union A∪B if x belongs to A or x belongs to B; hence every element

In A belongs to A ∪B, and every element in B belongs to A ∪B. That is,

A ⊆A ∪B and B ⊆A ∪B

Property-2-

An element x belongs to the union A∪B if x belongs to A or x belongs to B; hence every element

In A belongs to A ∪B, and every element in B belongs to A ∪B. That is,

A ⊆A ∪B and B ⊆A ∪B

Complements, differences and symmetric differences-

Complement-

The complement of a set A, denoted by , is the set of elements which belong to U(universal set)but which do not belong to A. That is

= {x | x ∈U, x /∈A}

Difference-

The difference of A and B, denoted by A\B or A-B, is the set of elements which belong to A but which do not belong to B that is-

A-B = {x | x ∈A, x / ∈B}

The set A\B or A-Bis read “A minus B”.

Symmetric difference-

The symmetric difference of sets A and B, denoted by A⊕B, consists of those elements which belong to A or B but not to both. That is

A ⊕B = (A ∪B)-(A ∩B) or A ⊕B = (A-B) ∪(B-A)

Cardinality of sets-

If A is finite set with n distinct elements, then n is called the cardinality of A. The cardinality of A is denoted by |A| [or by n (A)].

Example: Let A = {a, b, c, d}, then A is a finite set and |A| = 4

Cardinality of union of two sets-

Number of elements in A ∪B: (Cardinality of union) If A and B are any two finite sets then, the numbers of elements in A ∪B, denoted by | A ∪B | is given by | A ∪B | = | A | + | B | −| A ∩B |

Principal of inclusion and Exclusion-

Let we have A andB are finite sets. Then A ∪B and A ∩B are

Finite and

n(A ∪B) = n(A) + n(B) −n(A ∩B)

That is, we find the number of elements in A or B (or both) by first adding n(A) and n(B) (inclusion) and then

Subtracting n(A ∩B) (exclusion) since its elements were counted twice

For three sets-

n(A ∪B ∪C) = n(A) + n(B) + n(C) −n(A ∩B) −n(A ∩C) −n(B ∩C) + n(A ∩B ∩C)

Finite set-

If a set has finite number of elements then the set said to be a finite set.

Examples:

1. {2, 5, 9, 8, 11, 15, 19, 85}

2. The set of all vowels in English alphabets

3. The set of students in of high school in a particular school.

Infinite set-

If a set has infinite number of elements then the set said to be a infinite set.

Examples:

1. The set of all natural numbers.

2. The set of total points on a line.

Countable and uncountable sets-

A set S is said to be countable if it is either a finite set or countably infinite set.

A set is said to be uncountable otherwise.

Example-

Suppose we have a set of even natural numbers N = {2n: n∈N }. We can find a Bijection with the formula . So we can say that the set is Countably infinite and also countable.

The set of odd natural numbers is also countably infinite.

Countably infinite and uncountably infinite sets-

Any set which can be put in a one-to-one correspondence with integers so that the prescription can be given for identifying its members one at a time is called a countably infinite set.

Any set which cannot be put in a one-to-one correspondence with integers is said to be uncountably infinite set.

Multi-set-

A multi-set is a generalization of a set where repetition of elements matters.

Like {4, 5, 6} and {5, 4, 6} are the same multi-set but the set {5, 5, 4, 6} is the different multi-set as there is repetition of the elements.

So that, “A multi-set is a set-like, unordered collection where multiplicity(repetition) of the elements matters.

Here multiplicity means how many times an element occurs in the set.

Notation-

If an element ‘a’ occurs ‘n’ times in a multi-set A then it can be represented as - .

For example-

, ,

Ordered pair-

An ordered pair of element a and b, where a is designated as the first element and b as the second element, it is denoted by (a, b).

In particular

If and only if a = c and b = d. Thus

Unless a = b.

n-tuple-

A finite sequence over a set A is a function from {1, 2,….,n} into A, and it is usually denoted by

Such a sequence which is finite is called an n-tuple.

Here ‘n’ is a non-negative integer.

Tuples are written by listing the elements with parentheses ().

Cartesian product

Suppose we have two sets A and B, then we can form the set-

To be the set of all ordered pairs (x,y) where x is an element of A and y is an element of B.

Here we call the Cartesian product of A and B.

Example: If A = {1, 2} and B = {3, 4, 5} then find .

Sol.

Example: Let A = {1, 2} and B = {a, b, c}, then-

And

Note-

3. The Cartesian product of two sets of real numbers can be represented by tree diagrams.

Theorems-

If A, B, C are sets then-

Proof-

Theorem-

If A, B, and C are non-empty sets then A ⊆B ⇒A × C ⊆B × C

Proof: Let (a, b) be any element A × C, then

⇒a∈B and b ∈C (becauseA ⊆B)

⇒ (a, b)∈B × C

Hence A × C ⊆B × C

Cartesian product of n-sets-

Let denote n sets where n ≥2 , then the Cartesian product is the set ofall n-tuples of the form where

From the definition we have

Application of sets and propositions

Set theory is a branch of mathematics that deals with the properties of well-defined collections of objects such as numbers and functions.

German mathematician George Cantor introduced a theory of abstract sets of entities.

Set theory is used in the following areas of computer science-

1. Data structure

2. Object-oriented systems

3. Databases

4. Machine learning

Many mathematical concepts can be defined precisely using set theory concepts.

Graphs, manifolds, rings and vector spaces can all be defined as sets.

Fuzzy set theory is a sweeping statement of set theory. Fuzzy sets deals with a particular kind of uncertainty.

In axiomatic set theory, axioms are set to be describe sets.

Propositions have many applications in computer science like designing of computing machines, AI, definition of data structures for programming languages etc.

Propositional logic concerned with statements to which the truth values “true” and “false” can be assigned.

A proposition is a collection of declarative statements that has either a truth value “true” or a truth value “false”

Applications of propositional logics are-

1. System specification

2. Boolean searching

3. Logic puzzles

4. Logic circuits

1.4 Relations: Ordered pairs and n-tuples, types of relations, composite relation

We define a relation in terms of ordered pairs-

An ordered pair of elements of x and y, where x is the first element and y is the second element, it is denoted by (x, y),

If and only if x = p and y = q

Thus (x, y) unless x = y

Product sets-

Suppose we have two sets X and Y. The set of all ordered pairs (x, y) where is called the Cartesian product of X and Y.

It is represented as follows-

And it is read as X cross Y.

Relation-

Let X and Y are two sets, A relation from X to Y is a subset of .

Now suppose R is a relation form X to Y, then R is a set of ordered pairs where each first element comes from X and each second element comes from Y.

For each pair , one the following rule is true-

The domain of a relation R is the set of all first elements of the ordered pairs which belongs to R, and range is the second element.

Pictorial representation of relations-

Let A = {1, 2, 3}, B = {a, b, c} and R ={(1, a), (1, b), (2, c)}

Then this relation can be represented as in picture format-

Inverse relation-

Let R be any relation from set X to set Y. The inverse of R is the relation form Y o X which consists of those ordered pairs which, when reversed, belong to R, such that-

Example- If R = {(1, x),(1, y),(2, z)} then {(x, 1),(y, 1),(z, 2)}

Composition of relations-

Let X, Y and Z are three sets and R be a relation from X to Y and S is a relation from Y to Z.

So that R is a subset of and S is a subset of .

Then R and S give a relation form X to Z which is denoted by RoS,

And can be defined as follows-

The relation RoS is called the composition of R and S.

Note- If R is a relation on a set A, that is, R is a relation from a set A to itself. Then the composition of R is RoR. Denoted by .

Types of relations-

1. Reflexive relations

A relation R on a set X is reflexive if xRx for every xX. That is is (x, x) for every xX. Thus R is not reflexive if there exists x such that (x, x) does not belongs to R.

2. Symmetric and anti-symmetric relations-

A relation R on a set X is said to be symmetric if whenever xRy then yRx, that is if whenever (x, y)∈R then (y, x)∈R

R is said to be anti-symmetric if (x, y)∈X such that (x, y)∈R but (y, x)R

3. Transitive relation-

A relation R on a set X is said to be transitive if whenever xRy and yRzthen xRz, that is, if whenever (x, y), (y, z)∈R then (x, z)∈R

Equivalence relation-

A relation in a set R is said to be an equivalence relation in A, If R is reflexive, symmetric and transitive.

Irreflexive relation

A relation R on a set A is irreflexive if aRafor every a ∈A

Example-

Let A = {1, 2, 3} and

R = {(1, 2), (2, 3), (3, 1), (2, 1)}

Then the relation R is irreflexive on A.

Asymmetric relation-

A relation R defined on a set A is asymmetric if whenever aRb, then .

Example:

Let A = {a, b, c} and R = {(a, b), (b, c)} be a relation on A. Then R is a symmetric.

Compatible relation-

A relation R in A is said to be a compatible relation if it is reflexive and symmetric.

If R is an equivalence relation on A, then R is compatible relation on A.

Universal relation-

A relation R in a set A is said to be universal relation if

R = A × A

Example:

Let A = {1, 2, 3}, then

R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}

Is a universal relation on A.

Complementary relation-

Let R be a relation from A to B, then the complement of R denoted by R′and is

Expressed in terms of R as follows;

ARb if

The inverse of a relation-

Let R be a relation from A to B. Then the relation from B to A is called the inverse of R.

Example-1: A = {2, 3}, B = {3, 4, 5, 6} and R is a relation from A to B defined as follows-

(a, b) ∈R if “a divides b” write the solution set of R.

Sol: 2 divides 4 and 2 divides 6

⇒(2, 4) ∈R and (2, 6) ∈R

3 divides 3, 3 divides 6

⇒(3, 3) ∈R and (3, 6) ∈R

4 divides 4 ⇒(4, 4) ∈R

Thus R = {(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)}

Example-2: Let Z denote the set of integers and the relation R in Z be defined by “aRb” iffa – b is an even integer”. Then show that R is an equivalence relation.

Sol.

1. R is reflexive; since

∅ = a −a is even, hence aRa for every a∈Z.

2. R is symmetric:

If a – b is even then b – a = – (a – b) is also even hence aRb⇒bRa

3. R is transitive: for if aRb and bRc then both a – b and b – c are even.

Consequently, a – c = (a – b) + (b – c) is also even.

∴aRb and bRc⇒aR c

Thus, R is an equivalence relation.

Equivalence relations

Definition-

A relation R in a set A is said to be an equivalence relation in A, if R is reflexive, symmetric and transitive.

Example- Let A = {a, b, c}, and R = {(a, a), (a, b), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)} then R is an equivalence relation in A.

Example: Let Z denote the set of integers and the relation R in Z be defined by “aRb” iffa – b is an even integer”. Then show that R is an equivalence relation.

Sol.

1. R is reflexive; since

∅ = a −a is even, hence aRa for every a∈Z.

2. R is symmetric:

If a – b is even then b – a = – (a – b) is also even hence aRb⇒bRa

3. R is transitive: for if aRb and bRc then both a – b and b – c are even.

Consequently, a – c = (a – b) + (b – c) is also even.

∴aRb and bRc⇒aR c

Thus, R is an equivalence relation.

Key takeaways-

Suppose we have two sets X and Y. The set of all ordered pairs (x, y) where is called the Cartesian product of X and Y.
Let R be any relation from set X to set Y. The inverse of R is the relation form Y o X which consists of those ordered pairs which, when reversed, belong to R, such that-

3. A relation R on a set X is reflexive if xRx for every xX. That is is (x, x) for every xX. Thus R is not reflexive if there exists x such that (x, x) does not belongs to R.

4. A relation R on a set X is said to be transitive if whenever xRy and yRzthen xRz, that is, if whenever (x, y), (y, z)∈R then (x, z)∈R

5. A relation R defined on a set A is asymmetric if whenever aRb, then .

1.5 Transitive closure of a relation, partially ordered set, Hasse diagram

Transitive closure of relations

Let R be a relation on the set A. denote the transitive extension of R, denote the transitive extension of and in general denote the transitive extension of then the transitive closure of R is defined as the set union of R, ,, It is denoted by

Thus

Example: Let A = {1, 2, 3, 4} and B = {a, b, c, d, e, f} consider the relation

R = {(1, a), (1, c), (1, e), (2, b), (2, d), (2, f), (3, c), (3, d), (4, a), (4, f)}

Let then

And

Clearly-

Thus,

Partial ordering relations

Partial orderings-

A relation R on a set Sis called a partial order relation in Sif R is, Reflexive Anti-symmetric and transitive.

A set S together with a partial ordering R is called a partially ordered set.

We denote a partial order relation by the symbol ≤.

Comparability-

Suppose R be a partial order on Sand a, b ∈S whenever aRb or bRa, we say that a A a and b are comparable otherwise a And b are non-comparable.

Dual order-

If ≤is a partial order on a set S, then the converse of R is also a partial order on S. That means if ≤is a partial ordering on S, then ≥is also a partial ordering on S. (S, ≥) is called the dual of (S, ≤).

Partitions-

Let S be a set which is non-empty. Then the collection of subset of S is said to be a partition of S if-

2. For any

Either

Cross partition-

If and both are partition of set S which is non-empty, then forms a partition of S

is called a cross partition of S.

Ordered partition-

A partition a non-empty set is called an ordered partition of S if there is a specified order on the subsets of S.

An ordered t-tuple of sets is called a t-part ordered partition if the sets form a partition of S.

Theorem-

The number ‘m’ of ordered partitions of a set S with ‘n’ elements into r cells , where for each ‘i’, n( – follows-

Example:

Find the number of ways to partition of 10 peoples into four groups

So that two teams contain 3 persons and two teams contain 2 persons.

Sol.

By using above theorem, we get-

ordered partitions

Here the group form an unordered partition so that we divide m’ by Because of the two cells with three elements each and Because of the two cells with two elements each.

So that-

Example: There are 12 employees in a company. Find the number of ways that the 12 employees do three different tasks if four employees are to take each task.

Sol.

Here we find the number of ordered partitions of twelve employees into cells containing 4 employees each.

There are total - partitions

Hence the required number of ways, the employees can do the task is 34,650.

Hasse Diagram-

The elements in Hasse diagram are represented as vertices and it is pictorial representation of a finite order on a set.

Two related vertices of a partial order are connected by line if they are related.

Example-1: If A = {1, 2, 3} and ≤ be a relation on A. The theHasse diagram will be-

Example-2: Draw the Hasse diagram of positive division of 36.

Sol.

We have

Suppose R is the partial order relation on

The Hasse diagram will be-

Example-3: Let B = {a, b, c, d, e} then the Hasse diagram defines a partial order on B in the natural way. That is, d ≤ b, d ≤ a, e ≤ c and so on.

Key takeaways-

A relation R on a set Sis called a partial order relation in Sif R is, Reflexive Anti-symmetric and transitive.
If ≤is a partial order on a set S, then the converse of R is also a partial order on S. That means if ≤is a partial ordering on S, then ≥is also a partial ordering on S. (S, ≥) is called the dual of (S, ≤).
An ordered t-tuple of sets is called a t-part ordered partition if the sets form a partition of S.

1.6 Functions: Definition, composition of functions, types of functions

Let X and Y are two sets. A relation f from X to Y is said to be a function if for every x ∈ X there is a unique element y ∈ Y, such that (x, y) ∈ X

We denote it as f: X → Y, which means f is a function from X to Y.

We represent the function as-

Example: Let and

And

Hence the function can be represented as-

Here A is called the domain of f and B is called the co-domain of f

Surjective function (Onto-Mapping)-

A mapping is said to be onto-mapping if the range set

If is onto then each element of B if f-image of at least one element of X.

That means.

A mapping is said to be into if it is not onto.

Injective function (One-To-One Mapping)-

A mapping is said to be one-to-one mapping if distinct elements of X are mapped into distinct elements of Y.

That means if f is a one-to-one mapping, then-

Bijective functions (One-To-One, Onto)-

A mapping is said to be bijective mapping if it is both one-to-one and onto.

Identity function (Identity Mapping)-

If is a function such that every element of X is mapped onto itself then f is said to be an identity mapping.

We denote identity mapping by .

If is an identity mapping.

Partial functions-

Let X and Y be sets and A be a subset of X. A function f from A to Y is called a partial function from X to Y. The set A is a called the domain of f.

Constant function-

Let then f is said to be a constant function if every element of X is mapped onto the same element of Y.

Inverse functions-

Let is a one-one and onto mapping, then is called the inverse mapping of f.

Inverse mapping can be defined as-

Example-1: Prove that is both one-one and onto then is both one-one and onto.

Sol.

Let f: X→Y be both one-one and onto.

Then there exist elements ∈X, and elements∈Y

Such that

f() = , and f () =

= () and = ()

Now,

Let () = (), then

() = ()

⇒ =

⇒f() = f ()

⇒ =

Thus is one-one

Since f is onto, for y∈Y, there is some element x∈X, such that f (x) = y.

Now

f(x) = y

⇒x=

So that is onto.

Hence is both one-one and onto.

Composition of Functions

Let and are two mappings, then the composition of these two mappings f and g is denoted by gof is the mapping from X into Z.

It is defined as-

That means is a mapping defined as below-

Example-1: Show that the inverse of an invertible mapping is unique.

Sol

Let

By any invertible mapping,

Let,

g: Y→X

h: Y→X

Are two different inverse mapping of f.

Let y ∈ Y and

Now-

And

So that-

and

Now-

Which shows that g(y) = h(y)∀ y ∈ Y

So that the inverse of f is unique.

Example-2: Prove that is both one-one and onto then is both one-one and onto.

Sol.

Let f: X→Y be both one-one and onto.

Then there exist elements ∈X, and elements∈Y

Such that

f() = , and f () =

= () and = ()

Now,

Let () = (), then

() = ()

⇒ =

⇒f() = f ()

⇒ =

Thus is one-one

Since f is onto, for y∈Y, there is some element x∈X, such that f (x) = y.

Now

f(x) = y

⇒x=

So that is onto.

Hence is both one-one and onto.

Invertible function-

A function f from a set X to a set Y is said to be a invertible function if there exists a function g from Y to X, such that-

f(g(y)) = y

And

g(f(x)) = x

For every x ∈ X and y∈ Y

Example-1: Show that the inverse of an invertible mapping is unique.

Sol

Let

By any invertible mapping,

Let,

g: Y→X

h: Y→X

Are two different inverse mapping of f.

Let y ∈ Y and

Now-

And

So that-

and

Now-

Which shows that g(y) = h(y)∀ y ∈ Y

So that the inverse of f is unique.

Recursive Functions

Definition-

A function f is said to be Primitive recursive if it can be obtained from the initial functions by a finite number of operations of composition and recursion.

Example: Show that addition is primitive recursive.

Sol.

Addition is defined by a + 0 = a, a + (b + 1) = (a + b) + 1 for all natural numbers a a, b.

We define f (a, b) = a + b such that

f (a, b + 1) = a + b + 1 = (a + b) + 1

= f (a, b) + 1

= S (f (a, b))

Also f (a, 0) = a

We define f (a, b) as

If follows that f comes from primitive recursion from and so that f is primitive recursive.

Key takeaways

Let X and Y are two sets. A relation f from X to Y is said to be a function if for every x ∈ X there is a unique element y ∈ Y, such that (x, y) ∈ X
A mapping is said to be onto-mapping if the range set
A mapping is said to be one-to-one mapping if distinct elements of X are mapped into distinct elements of Y.
Let X and Y be sets and A be a subset of X. A function f from A to Y is called a partial function from X to Y. The set A is a called the domain of f.