Introduction to Relations

Correct answer: C. ((1,3)) is missing, so transitivity fails

Step 1: The union contains all diagonal pairs and the needed reverse pairs. Step 2: It also contains ((1,2)) and ((2,3)). Step 3: Transitivity requires ((1,3)), which is missing, so it is not an equivalence relation.

Correct answer: A. if and only if (R) is symmetric

Step 1: The inverse relation reverses the direction of every pair. Step 2: Symmetry means the relation behaves the same after reversing pairs. Step 3: Hence (R^{-1}) is symmetric exactly when (R) is symmetric.

Correct answer: A. it will be reflexive

Step 1: A reflexive (R) contains every ((a,a)). Step 2: The inverse of ((a,a)) is again ((a,a)). Step 3: Therefore all diagonal pairs remain in (R^{-1}).

Correct answer: A. it is also an equivalence relation

Step 1: Since (R) is reflexive, its inverse is also reflexive. Step 2: Since (R) is symmetric, (R^{-1}=R). Step 3: Because (R) is transitive, the same property remains in its inverse.

Correct answer: A. it is always transitive

Step 1: If ((a,b)) and ((b,c)) are in (R^{-1}), then ((b,a)) and ((c,b)) are in (R). Step 2: Transitivity of (R) gives ((c,a)). Step 3: Reversing it gives ((a,c)) in (R^{-1}), so (R^{-1}) is transitive.

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

Step 1: In an inverse relation, every ordered pair is reversed. Step 2: ((1,2),(2,3),(1,3)) become ((2,1),(3,2),(3,1)). Step 3: Do not add any new diagonal pair automatically while finding the inverse.

Correct answer: A. because it is reflexive, antisymmetric and transitive

Step 1: Every number divides itself, so it is reflexive. Step 2: If (a\mid b) and (b\mid a), then for positive numbers (a=b), so it is antisymmetric. Step 3: Divisibility passes through a middle element, so it is transitive.

Correct answer: A. (1)

Step 1: A least element is related to every element of the set. Step 2: (1\le 1,2,3,4) is true for all elements. Step 3: Hence (1) is the least element.

Correct answer: D. (12)

Step 1: A greatest element is one that is divisible by every element of the set. Step 2: (2,3,6,12) all divide (12). Step 3: Therefore (12) is the greatest element in this divisibility order.

Correct answer: C. (6)

Step 1: An upper bound must be divisible by both (2) and (3). Step 2: In (A), both (6) and (12) satisfy this. Step 3: Under divisibility, the least such upper bound is (6).

Correct answer: D. (6)

Step 1: A lower bound must divide both (6) and (12). Step 2: (1,2,3,6) are lower bounds. Step 3: The greatest among them under divisibility is (6).

Correct answer: C. (3)

Step 1: A minimal element has no distinct element below it in the relation. Step 2: (2,3,5) are not divided by any other distinct element of (A). Step 3: (30) is not minimal because (2,3,5) divide it.

Correct answer: A. (1)

Step 1: A maximal element has no distinct element above it. Step 2: (2,3,5) all divide (30), so they are not maximal. Step 3: No distinct element of (A) lies above (30), so there is exactly one maximal element.

Correct answer: A. (2^6(2^3-2))

Step 1: Not reflexive means not all diagonal pairs are present. Step 2: Not irreflexive means at least one diagonal pair is present. Step 3: Diagonal choices are (2^3-2), and the (6) off-diagonal pairs give (2^6) choices.

Correct answer: B. (2^{n^2-n})

Step 1: An irreflexive relation contains no diagonal pair. Step 2: Out of (n^2) pairs, the (n) diagonal pairs are forbidden. Step 3: The remaining (n^2-n) pairs are optional, so the count is (2^{n^2-n}).

Correct answer: A. (2^{\frac{n(n-1)}{2}})

Step 1: Irreflexivity forbids all diagonal pairs. Step 2: Symmetry makes each off-diagonal reverse-pair group chosen together or not chosen. Step 3: There are (\frac{n(n-1)}{2}) such groups, so the count is (2^{\frac{n(n-1)}{2}}).

Correct answer: A. (3^6)

Step 1: Irreflexivity forces all diagonal pairs to be absent. Step 2: For each pair of distinct elements, antisymmetry gives three choices. Step 3: With (4) elements, there are (6) such pairs, so the count is (3^6).

Correct answer: A. (3\cdot 2^6)

Step 1: Choose exactly two of the three diagonal pairs in (\binom{3}{2}=3) ways. Step 2: The remaining (6) off-diagonal pairs are independently optional. Step 3: Therefore the count is (3\cdot 2^6).

Correct answer: A. (6\cdot 2^6)

Step 1: Choose exactly (2) diagonal pairs from (4) in (\binom{4}{2}=6) ways. Step 2: In a symmetric relation, the (6) off-diagonal reverse-pair groups are independently optional. Step 3: Hence the total number is (6\cdot 2^6).

Correct answer: A. (2^6-2^3)

Step 1: Reflexive relations force the three diagonal pairs and leave (6) off-diagonal pairs free, giving (2^6). Step 2: Reflexive symmetric relations have (3) independent off-diagonal reverse-pair groups, giving (2^3). Step 3: Therefore the reflexive but not symmetric relations are (2^6-2^3).

Correct answer: A. (2^6-2^3)

Step 1: On (3) elements, the total number of symmetric relations is (2^6). Step 2: Among these, reflexive symmetric relations are (2^3). Step 3: Hence symmetric but not reflexive relations are (2^6-2^3).

Correct answer: A. (2^3-1)

Step 1: Being both symmetric and antisymmetric allows only diagonal pairs. Step 2: With (3) diagonal pairs, there are (2^3) such relations. Step 3: One of them is the full identity relation, which is reflexive; removing it gives (2^3-1).

Correct answer: C. (10)

Step 1: For (a=1), (b=1,2,3,4) work. Step 2: For (a=2), (3) values work; for (a=3), (2); and for (a=4), (1). Step 3: The total number of pairs is (4+3+2+1=10).

Correct answer: B. (8)

Step 1: In (A), remainder (0) has (3), remainder (1) has (1,4), and remainder (2) has (2,5). Step 2: A sum divisible by (3) needs remainder pairs ((0,0),(1,2),(2,1)). Step 3: The count is (1\cdot1+2\cdot2+2\cdot2=9), so the correct count is (9).

Correct answer: A. symmetric but not reflexive

Step 1: (\gcd(a,b)=\gcd(b,a)), so the relation is symmetric. Step 2: (\gcd(2,2)=2), so not all diagonal pairs are present and it is not reflexive. Step 3: (2R3) and (3R4) hold, but (2R4) fails, so it is not transitive.