Unit 3: Counting Principles and Relations - Subjective Questions

MTH401 — Discrete Mathematics • Practice Questions with Detailed Answers

20 questions

State and derive the Principle of Inclusion-Exclusion for three finite sets $A$ , $B$ , and $C$ .

Using the Principle of Inclusion-Exclusion, find how many integers from $1$ to $500$ are divisible by at least one of $3$ , $5$ , or $7$ .

State the Pigeonhole Principle and use it to prove that among any $13$ people, at least two were born in the same month.

State and prove the Generalized Pigeonhole Principle. Hence, determine the minimum number of students who must share a birth month in a group of $100$ students.

Define a binary relation and explain the reflexive, symmetric, antisymmetric, and transitive properties of a relation.

Let $R$ be the divisibility relation on the set of positive integers, defined by $aRb$ if and only if $a\mid b$ . Determine whether $R$ is reflexive, symmetric, antisymmetric, and transitive.

Explain how relations can be combined using union, intersection, difference, complement, and inverse. State an important property of the inverse operation.

Define the composition of two relations. For $R=\{(1,2),(2,3),(3,1)\}$ and $S=\{(1,1),(2,1),(3,2)\}$ on $A=\{1,2,3\}$ , find $S\circ R$ and $R\circ S$ .

Explain how a finite relation is represented using a zero-one matrix. How can the matrix of a composition of relations be obtained?

Describe the directed-graph representation of a relation. Explain how reflexivity, symmetry, and transitivity can be recognized from its directed graph.

Define an equivalence relation. Prove that the relation $R$ on $\mathbb{Z}$ defined by $aRb$ if and only if $a\equiv b\pmod{5}$ is an equivalence relation.

Explain equivalence classes and prove that the equivalence classes of an equivalence relation form a partition of the underlying set.

Distinguish between partial ordering and total ordering relations, with suitable examples.

Construct and describe the Hasse diagram of the poset $(\mathcal{P}(\{a,b,c\}),\subseteq)$ . Identify its levels, least element, greatest element, and number of covering edges.

Explain the components of a Hasse diagram: covering relation, minimal and maximal elements, least and greatest elements, upper and lower bounds, supremum, and infimum.

Define a lattice. Show that the set of positive divisors of $12$ , ordered by divisibility, forms a lattice.

Define a sublattice. Determine whether $S_1=\{1,2,4,12\}$ and $S_2=\{1,2,3,12\}$ are sublattices of the divisor lattice of $12$ .

State the fundamental algebraic laws satisfied by meet and join in a lattice. Illustrate the absorption laws.

Draw conceptually the Hasse diagram for the positive divisors of $30$ ordered by divisibility. List all covering pairs and show that the poset is a lattice.

Let $R=\{(1,2),(2,3),(3,4)\}$ be a relation on $A=\{1,2,3,4\}$ . Find $R^2$ , $R^3$ , and the transitive closure of $R$ using composition.

Question 1

State and derive the Principle of Inclusion-Exclusion for three finite sets $A$ , $B$ , and $C$ .

Tap card to reveal answer

Answer 1

Principle of Inclusion-Exclusion: It determines the number of elements in the union of overlapping finite sets.

For two sets,

$|A \cup B|=|A|+|B|-|A \cap B|.$

For three sets, first add the sizes of all three sets. Elements in pairwise intersections are then counted twice, so subtract each pairwise intersection. However, elements in $A \cap B \cap C$ were initially counted three times and subsequently subtracted three times, so they must be added once.

Therefore,

$|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C|.$

More generally, for finite sets $A_1,A_2,\ldots,A_n$ ,

$\left|\bigcup_{i=1}^{n}A_i\right|=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|.$

The signs alternate because each element must finally be counted exactly once.

Tap card to flip back

Question 3

State the Pigeonhole Principle and use it to prove that among any $13$ people, at least two were born in the same month.

Tap card to reveal answer

Answer 3

Pigeonhole Principle: If more than $n$ objects are placed into $n$ boxes, then at least one box contains at least two objects.

In this problem:

The objects are the $13$ people.
The boxes are the $12$ months of the year.

Suppose, for contradiction, that no two people were born in the same month. Then each month could contain the birthday of at most one person, so at most $12$ people could be assigned to the $12$ months.

However, there are $13$ people. Since

$13>12,$

the Pigeonhole Principle guarantees that at least one month contains the birthdays of at least two people.

Therefore, among any $13$ people, at least two must have been born in the same month.

Tap card to flip back

Question 4

State and prove the Generalized Pigeonhole Principle. Hence, determine the minimum number of students who must share a birth month in a group of $100$ students.

Tap card to reveal answer

Answer 4

Generalized Pigeonhole Principle: If $N$ objects are distributed among $k$ boxes, then at least one box contains at least

$\left\lceil\frac{N}{k}\right\rceil$

objects.

Proof: Assume every box contains fewer than $\left\lceil N/k\right\rceil$ objects. Then every box contains at most

$\left\lceil\frac{N}{k}\right\rceil-1$

objects. Hence, the total number of objects would be at most

$k\left(\left\lceil\frac{N}{k}\right\rceil-1\right)<N,$

which contradicts the fact that there are $N$ objects. Therefore, at least one box must contain at least $\left\lceil N/k\right\rceil$ objects.

For $100$ students and $12$ birth months,

$\left\lceil\frac{100}{12}\right\rceil=\left\lceil 8.33\ldots\right\rceil=9.$

Thus, at least 9 students must have been born in the same month.

Tap card to flip back

Question 5

Define a binary relation and explain the reflexive, symmetric, antisymmetric, and transitive properties of a relation.

Tap card to reveal answer

Answer 5

A binary relation $R$ from a set $A$ to a set $B$ is any subset of the Cartesian product $A\times B$ :

$R\subseteq A\times B.$

If $A=B$ , then $R$ is called a relation on $A$ . The notation $aRb$ means $(a,b)\in R$ .

For a relation $R$ on $A$ :

Reflexive: $R$ is reflexive if every element is related to itself:
$\forall a\in A,\ (a,a)\in R.$
Symmetric: $R$ is symmetric if reversing every related pair produces another related pair:
$\forall a,b\in A,\ aRb\Rightarrow bRa.$
Antisymmetric: $R$ is antisymmetric if two distinct elements cannot be related in both directions:
$\forall a,b\in A,\ (aRb\land bRa)\Rightarrow a=b.$
Transitive: $R$ is transitive if a relation from $a$ to $b$ and from $b$ to $c$ implies a relation from $a$ to $c$ :
$\forall a,b,c\in A,\ (aRb\land bRc)\Rightarrow aRc.$

A relation may satisfy several of these properties simultaneously. Symmetry and antisymmetry are not logical opposites; for example, the equality relation is both symmetric and antisymmetric.

Tap card to flip back

Question 6

Let $R$ be the divisibility relation on the set of positive integers, defined by $aRb$ if and only if $a\mid b$ . Determine whether $R$ is reflexive, symmetric, antisymmetric, and transitive.

Tap card to reveal answer

Answer 6

The relation is defined by

$aRb\iff a\mid b.$

Reflexive: For every positive integer $a$ , $a=a\cdot1$ , so $a\mid a$ . Therefore, $R$ is reflexive.
Symmetric: The relation is not symmetric. For example, $2\mid4$ , but $4\nmid2$ .
Antisymmetric: Suppose $a\mid b$ and $b\mid a$ . Then there exist positive integers $m$ and $n$ such that
$b=am\quad\text{and}\quad a=bn.$
Substitution gives $a=amn$ . Since $a>0$ , $mn=1$ , which implies $m=n=1$ . Hence, $a=b$ . Therefore, $R$ is antisymmetric.
Transitive: If $a\mid b$ and $b\mid c$ , then $b=ak$ and $c=bm$ for some positive integers $k,m$ . Thus,
$c=(ak)m=a(km),$
so $a\mid c$ . Therefore, $R$ is transitive.

Hence, divisibility is reflexive, antisymmetric, and transitive, but not symmetric. It is consequently a partial ordering relation on the positive integers.

Tap card to flip back

Question 10

Describe the directed-graph representation of a relation. Explain how reflexivity, symmetry, and transitivity can be recognized from its directed graph.

Tap card to reveal answer

Answer 10

For a relation $R$ on a finite set $A$ , its directed graph, or digraph, consists of:

A vertex for each element of $A$ .
A directed edge from $a$ to $b$ whenever $(a,b)\in R$ .
A loop at $a$ whenever $(a,a)\in R$ .

The main relation properties can be recognized as follows:

Reflexive: Every vertex has a loop.
Irreflexive: No vertex has a loop.
Symmetric: Whenever there is an edge from $a$ to $b$ , there is also an edge from $b$ to $a$ .
Antisymmetric: For distinct vertices $a$ and $b$ , edges cannot occur in both directions.
Transitive: Whenever there are edges $a\to b$ and $b\to c$ , there must also be an edge $a\to c$ .

For example, if

$R=\{(1,1),(2,2),(1,2),(2,1)\},$

then the graph has loops at $1$ and $2$ and directed edges in both directions between them. Thus, the relation is reflexive and symmetric. It is not antisymmetric because $1R2$ and $2R1$ while $1\neq2$ .

Tap card to flip back

Question 12

Explain equivalence classes and prove that the equivalence classes of an equivalence relation form a partition of the underlying set.

Tap card to reveal answer

Answer 12

Let $R$ be an equivalence relation on a set $A$ . The equivalence class of $a\in A$ is

$[a]=\{x\in A:xRa\}.$

To show that the equivalence classes form a partition, the following conditions must hold:

Every class is nonempty: Since $R$ is reflexive, $aRa$ . Hence, $a\in[a]$ , so $[a]\neq\varnothing$ .
The classes cover $A$ : Every $a\in A$ belongs to its own class $[a]$ . Therefore,
$\bigcup_{a\in A}[a]=A.$
Two classes are either identical or disjoint: Suppose
$[a]\cap[b]\neq\varnothing.$
Then some $x$ satisfies $xRa$ and $xRb$ . By symmetry, $aRx$ , and by transitivity, $aRb$ . If $y\in[a]$ , then $yRa$ . Since $aRb$ , transitivity gives $yRb$ , so $y\in[b]$ . Thus, $[a]\subseteq[b]$ . Similarly, $[b]\subseteq[a]$ , so $[a]=[b]$ .

Hence, distinct equivalence classes are disjoint and together cover $A`; therefore, they form a partition of $A$.

Conversely, every partition of a set defines an equivalence relation by declaring two elements equivalent when they belong to the same block.

Tap card to flip back

Question 13

Distinguish between partial ordering and total ordering relations, with suitable examples.

Tap card to reveal answer

Answer 13

A relation $R$ on a set $A$ is a partial ordering relation if it is:

Reflexive,
Antisymmetric,
Transitive.

The pair $(A,R)$ is then called a partially ordered set, or poset.

A partial order does not require every pair of elements to be comparable. Elements $a$ and $b$ are comparable if

$aRb\quad\text{or}\quad bRa.$

A total ordering relation is a partial order in which every pair of elements is comparable:

$\forall a,b\in A,\quad aRb\text{ or }bRa.$

Examples:

The subset relation $\subseteq$ on $\mathcal{P}(S)$ is a partial order. For $S=\{1,2\}$ , the sets $\{1\}$ and $\{2\}$ are incomparable.
The usual relation $\leq$ on $\mathbb{Z}$ is a total order because for any integers $a$ and $b$ , either $a\leq b$ or $b\leq a$ .
Divisibility on positive integers is a partial order but not a total order; for example, neither $2\mid3$ nor $3\mid2$ .

Thus, every total order is a partial order, but every partial order need not be a total order.

Tap card to flip back

Question 14

Construct and describe the Hasse diagram of the poset $(\mathcal{P}(\{a,b,c\}),\subseteq)$ . Identify its levels, least element, greatest element, and number of covering edges.

Tap card to reveal answer

Answer 14

The power set is

$\mathcal{P}(\{a,b,c\})=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}.$

In a Hasse diagram, reflexive loops and transitive edges are omitted. An element $Y$ covers $X$ when

$X\subset Y$

and no set lies strictly between them. For the subset relation, $Y$ covers $X$ exactly when $Y$ is obtained by adding one element to $X$ .

The levels are:

Level 0: $\varnothing$
Level 1: $\{a\},\{b\},\{c\}$
Level 2: $\{a,b\},\{a,c\},\{b,c\}$
Level 3: $\{a,b,c\}$

The covering edges connect sets on consecutive levels that differ by one element.

From level $0$ to level $1$ : $3$ edges.
From level $1$ to level $2$ : $6$ edges.
From level $2$ to level $3$ : $3$ edges.

Thus, the total number of covering edges is

$3+6+3=12.$

The least element is $\varnothing$ , and the greatest element is $\{a,b,c\}$ . The diagram is the three-dimensional Boolean lattice $B_3$ .

Tap card to flip back

Question 15

Explain the components of a Hasse diagram: covering relation, minimal and maximal elements, least and greatest elements, upper and lower bounds, supremum, and infimum.

Tap card to reveal answer

Answer 15

A Hasse diagram is a simplified graphical representation of a finite poset. Larger elements are placed above smaller elements, while loops, arrowheads, and edges implied by transitivity are omitted.

Covering relation: An element $y$ covers $x$ if $x<y$ and there is no $z$ such that $x<z<y$ . A line is drawn between $x$ and $y$ .
Minimal element: An element with no strictly smaller element in the poset. A poset may have several minimal elements.
Maximal element: An element with no strictly greater element. A poset may have several maximal elements.
Least element: An element $l$ satisfying $l\leq x$ for every $x$ . If it exists, it is unique.
Greatest element: An element $g$ satisfying $x\leq g$ for every $x$ . If it exists, it is unique.
Upper bound of $S$ : An element $u$ such that $s\leq u$ for every $s\in S$ .
Lower bound of $S$ : An element $l$ such that $l\leq s$ for every $s\in S$ .
Supremum or least upper bound: The smallest of all upper bounds, denoted $\sup S$ or $\bigvee S$ .
Infimum or greatest lower bound: The greatest of all lower bounds, denoted $\inf S$ or $\bigwedge S$ .

A least element is necessarily the unique minimal element, but a unique minimal element in an infinite poset need not always be least. Similar terminology applies to greatest and maximal elements.

Tap card to flip back

Question 16

Define a lattice. Show that the set of positive divisors of $12$ , ordered by divisibility, forms a lattice.

Tap card to reveal answer

Answer 16

A lattice is a poset $(L,\leq)$ in which every pair of elements $a,b\in L$ has:

A unique greatest lower bound, called the meet and denoted $a\wedge b$ .
A unique least upper bound, called the join and denoted $a\vee b$ .

The positive divisors of $12$ are

$D_{12}=\{1,2,3,4,6,12\}.$

The ordering relation is divisibility. For any $a,b\in D_{12}$ :

Their greatest lower bound is their greatest common divisor:
$a\wedge b=\gcd(a,b).$
Their least upper bound is their least common multiple:
$a\vee b=\operatorname{lcm}(a,b).$

Since $a$ and $b$ both divide $12$ , their greatest common divisor and least common multiple also divide $12`. Thus, both belong to $D_{12}$.

For example, for $4$ and $6$ ,

$4\wedge6=\gcd(4,6)=2,$

$4\vee6=\operatorname{lcm}(4,6)=12.$

Therefore, every pair has a meet and a join, so $(D_{12},\mid)$ is a lattice. Its least element is $1$ , and its greatest element is $12$ .

Tap card to flip back

Question 19

Draw conceptually the Hasse diagram for the positive divisors of $30$ ordered by divisibility. List all covering pairs and show that the poset is a lattice.

Tap card to reveal answer

Answer 19

The positive divisors of $30$ are

$D_{30}=\{1,2,3,5,6,10,15,30\}.$

Since

$30=2\cdot3\cdot5,$

each divisor corresponds to a subset of the prime factors ${2,3,5}`. The Hasse diagram has four levels:

Level 0: $1$
Level 1: $2,3,5$
Level 2: $6,10,15$
Level 3: $30$

The covering pairs are

$1\prec2,\quad1\prec3,\quad1\prec5,$

$2\prec6,\quad2\prec10,$

$3\prec6,\quad3\prec15,$

$5\prec10,\quad5\prec15,$

$6\prec30,\quad10\prec30,\quad15\prec30.$

For any $a,b\in D_{30}$ , the meet and join are

$a\wedge b=\gcd(a,b),$

$a\vee b=\operatorname{lcm}(a,b).$

Both values are divisors of $30`. For example,

$6\wedge10=2,\qquad6\vee10=30,$

and

$6\wedge15=3,\qquad6\vee15=30.$

Thus, every pair has a unique greatest lower bound and least upper bound. Therefore, $(D_{30},\mid)$ is a lattice. It is structurally equivalent to the Boolean lattice $B_3$ .

Tap card to flip back

1 / 20

Unit2 Unit4

Unit 3: Counting Principles and Relations - Subjective Questions

Did this save you a night before the exam?