Question

To prove the closure with respect to the property. ofthe relation \(R = \{ (0,0),(0,1),(1,1),(2,2)\} \) on the set \(\{ 0,1,2\} \) does not exist if . is the property" has an odd number of elements."

Short answer

procedure reflexive closure of transitive closure \(\left( {{M_R}:} \right.\) zero-one \(n*n\) matrix )

\(W: = {M_R}\)

procedure reflexive closure of transitive closur

W: \( = {{\rm{M}}_{\rm{R}}}\)

fork: \( = 1\) to \({\rm{n}}\)

fori: \( = 1\) to \({\rm{n}}\)

forj: \( = 1\) to \({\rm{n}}\)

\({w_{{\rm{ij}}}}: = {w_{ij}} \vee \left( {{w_{ik}} \wedge {w_{kj}}} \right)\)

fork: \( = 1\) to \(n\)

fori: \( = 1\) to \(n\)

forj: \( = 1\) to \(n\)

\({w_{{\rm{ij}}}}: = {w_{ij}} \vee \left( {{w_{ik}} \wedge {w_{kj}}} \right)\).

Step-by-step solution

Given data

\(R = \{ (a,b)\mid a\)and \(b\) have at least one common class with \(a \ne b\} \)

\(A = \) Set of all students.

Concept used of algorithm

Algorithms are used as specifications for performingcalculations and data processing.

Find the reflexive closures

Suppose $S$ were the closure of $R$ with respect to this property. Since $R$ does not have an odd numberof elements, $S \neq R$, so $S$ must be a proper superset of R.

Clearly S cannot have more than 5 elements, for if it did, then any subset of $S$ consisting of $R$ and one element of $\mathrm{S}$ - $\mathrm{R}$ would be a proper subset of $\mathrm{S}$ with the property; this would violate the requirement that $\mathrm{S}$ be a subset of every superset of $R$ with theproperty.

Thus $\mathrm{S}$ must have exactly 5 elements.

Let Tbe another superset of $R$ with 5 elements (thereare $9-4=5$ such sets in all).

Thus Thas the property, but $S$ is not a subset of $T$.

This contradicts thedefinition.

Therefore our original assumption was faulty, and the closure does not exist.