Introduction to Relations

Correct answer: C. ((2,3)) and ((5,6))

Step 1: (\gcd(2,3)=1), so ((2,3)) belongs to the relation. Step 2: (\gcd(2,4)=2), so ((2,4)) does not belong. Step 3: (\gcd(5,6)=1), so ((5,6)) also belongs.

Correct answer: B. (24)

Step 1: An upper bound must be divisible by both (6) and (8). Step 2: In (A), (24) works, while (12) is not divisible by (8). Step 3: Therefore the least upper bound is (24).

Correct answer: C. (4)

Step 1: A lower bound must divide both (8) and (12). Step 2: The elements (1,2,4) satisfy this. Step 3: Under divisibility, the greatest among them is (4).

Correct answer: B. (2)

Step 1: A maximal element has no distinct element above it in the set. Step 2: Neither (12) nor (18) divides another distinct element of (A). Step 3: Elements (2,4,6) have elements above them, so the maximal elements are (12) and (18).

Correct answer: A. (1)

Step 1: A minimal element has no distinct element below it. Step 2: There is no distinct element of (A) below (2). Step 3: Each of (4,6,12,18) has (2) or another element below it, so there is only (1) minimal element.

Correct answer: B. (5)

Step 1: Two elements are comparable if one divides the other. Step 2: The comparable pairs are ({1,2},{1,3},{1,6},{2,6},{3,6}). Step 3: ({2,3}) is not comparable, so the count is (5).

Correct answer: B. (3)

Step 1: In a chain, every two elements must be comparable. Step 2: (1\mid2\mid6) and (1\mid3\mid6) are chains of three elements. Step 3: Since (2) and (3) are not comparable, a four-element chain is impossible.

Correct answer: C. (8)

Step 1: An upper bound must be divisible by both (2) and (8). Step 2: (8) and (16) are upper bounds. Step 3: Under divisibility, the least among them is (8).

Correct answer: C. (4)

Step 1: A lower bound must divide both (4) and (16). Step 2: (1,2,4) are lower bounds. Step 3: Under divisibility, the greatest among them is (4).

Correct answer: A. (R\circ R=R)

Step 1: Reflexivity gives (R\subseteq R\circ R). Step 2: Transitivity gives (R\circ R\subseteq R). Step 3: Combining both inclusions gives (R\circ R=R).

Correct answer: A. ({(1,3),(2,4)})

Step 1: ((1,2)) and ((2,3)) give ((1,3)). Step 2: ((2,3)) and ((3,4)) give ((2,4)). Step 3: There is no other two-step chain, so this is (R\circ R).

Correct answer: B. ({(1,4)})

Step 1: A triple composition represents a three-step chain. Step 2: Here (1\to2\to3\to4) is the only three-step chain. Step 3: Therefore (R\circ R\circ R={(1,4)}).

Correct answer: D. ((1,2))

Step 1: (1\to2\to1) gives ((1,1)), and (1\to2\to3) gives ((1,3)). Step 2: (3\to2\to1) gives ((3,1)). Step 3: There is no two-step chain from (1) to (2), so ((1,2)) is not in (R\circ R).

Correct answer: A. it will be equal to (R\circ R)

Step 1: For a symmetric relation, (R^{-1}=R). Step 2: So in (R\circ R^{-1}), we may replace (R^{-1}) by (R). Step 3: Hence (R\circ R^{-1}=R\circ R).

Correct answer: A. (R)

Step 1: Taking the inverse reverses every ordered pair. Step 2: Reversing twice brings each pair back to its original direction. Step 3: Therefore ((R^{-1})^{-1}=R).

Correct answer: A. (R^{-1}\cup S^{-1})

Step 1: A pair in the union comes from (R) or from (S). Step 2: Its reverse will then lie in (R^{-1}) or in (S^{-1}). Step 3: Hence ((R\cup S)^{-1}=R^{-1}\cup S^{-1}).

Correct answer: B. (R^{-1}\cap S^{-1})

Step 1: A pair is in the intersection only when it belongs to both (R) and (S). Step 2: Its reverse then belongs to both (R^{-1}) and (S^{-1}). Step 3: Therefore ((R\cap S)^{-1}=R^{-1}\cap S^{-1}).

Correct answer: A. (R^{-1}\subseteq S^{-1})

Step 1: If ((a,b)\in R^{-1}), then ((b,a)\in R). Step 2: Since (R\subseteq S), ((b,a)\in S). Step 3: Therefore ((a,b)\in S^{-1}), so (R^{-1}\subseteq S^{-1}).

Correct answer: A. it is always true

Step 1: Transitivity gives (R\circ R\subseteq R). Step 2: (R^3=R\circ R\circ R). Step 3: Combining the first two factors into (R) shows (R^3\subseteq R).

Correct answer: A. ((1,1))

Step 1: ((1,2)) and ((2,1)) are in the relation. Step 2: Transitivity requires ((1,1)) from these two pairs. Step 3: Therefore ((1,1)) is a compulsory pair to add.

Correct answer: A. ((1,4))

Step 1: There is a chain (1\to2), (2\to3), and (3\to4). Step 2: The transitive closure adds all reachable pairs. Step 3: Since (4) is reachable from (1), ((1,4)) will be included.

Correct answer: C. (13)

Step 1: Elements (1,2,3) are connected into one class. Step 2: Elements (4,5) form another class. Step 3: The first class gives (3^2=9) pairs and the second gives (2^2=4), so the total is (13).

Correct answer: A. (4)

Step 1: In this set, (a-b) being divisible by (4) occurs only for equal elements. Step 2: So (S) acts like the identity relation, and all its (4) self-pairs also lie in (R). Step 3: Hence (R\cap S) contains (4) pairs.

Correct answer: A. Reflexive

Step 1: Put (Y=X) on the diagonal. Step 2: Then (X\cap X=X), which is true for every set. Step 3: Therefore every ((X,X)) belongs to the relation, so (R) is reflexive.

Correct answer: A. Yes

Step 1: For reflexivity, put (Y=X). Step 2: Then (X\cup X=X), which is the same as (Y). Step 3: Hence every diagonal pair satisfies the condition.