Introduction to Relations

Correct answer: A. (2^9)

Step 1: (A\times A) has (3\times 3=9) ordered pairs. Step 2: A relation is any subset of (A\times A), so the number of relations is (2^9). Step 3: In exams, count the ordered pairs first and then use the subset count.

Correct answer: B. (2^{12})

Step 1: (A\times A) contains (16) pairs. Step 2: A reflexive relation must contain the (4) diagonal pairs, so the remaining (12) pairs are optional. Step 3: For reflexive relation counts, subtract the compulsory diagonal pairs.

Correct answer: C. (2^6)

Step 1: The three diagonal pairs are independently optional. Step 2: The (6) off-diagonal pairs form (3) reverse-pair groups, and each group is chosen together or not chosen. Step 3: Thus there are (3+3=6) independent choices, giving (2^6).

Correct answer: D. (2^3)

Step 1: Reflexivity forces all three diagonal pairs to be present. Step 2: Outside the diagonal, only the three reverse-pair groups are independent. Step 3: Therefore the total number is (2^3); do not count the diagonal choices again.

Correct answer: A. equivalence relation

Step 1: (a-a=0) is divisible by (5), so the relation is reflexive. Step 2: If (a-b) is divisible by (5), then (b-a) is also divisible by (5), and adding two such differences gives transitivity. Step 3: Remainder-based relations often form equivalence relations.

Correct answer: B. reflexive and transitive but not symmetric

Step 1: For every (a), (a\le a), so it is reflexive. Step 2: If (a\le b) and (b\le c), then (a\le c), so it is transitive. Step 3: Since (2\le 3) is true but (3\le 2) is false, it is not symmetric.

Correct answer: C. reflexive and transitive but not symmetric

Step 1: Every number divides itself, so the relation is reflexive. Step 2: If (a\mid b) and (b\mid c), then (a\mid c), so it is transitive. Step 3: Since (1\mid 2) is true but (2\mid 1) is false, it is not symmetric.

Correct answer: D. equivalence relation

Step 1: All three diagonal pairs are present, so the relation is reflexive. Step 2: ((1,2)) is accompanied by ((2,1)), so symmetry holds. Step 3: From ((1,2)) and ((2,1)), ((1,1)) is required and present; hence transitivity also holds.

Correct answer: A. transitivity

Step 1: All diagonal pairs are present, so reflexivity holds. Step 2: Since ((1,2)) and ((2,3)) are present, transitivity requires ((1,3)). Step 3: ((1,3)) is absent, so transitivity fails.

Correct answer: B. no reverse pair can occur off the diagonal

Step 1: Symmetry says that if ((a,b)) is present, then ((b,a)) must also be present. Step 2: Antisymmetry says that for (a\ne b), both cannot be present together. Step 3: Therefore, for distinct elements, no two-way off-diagonal pair can occur.

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

Step 1: A reflexive relation must contain each element paired with itself. Step 2: The smallest such relation contains only the required diagonal pairs. Step 3: Adding extra pairs keeps it reflexive but no longer smallest.

Correct answer: D. it is reflexive, symmetric and transitive

Step 1: The universal relation contains every pair in (A\times A). Step 2: Therefore all diagonal, reverse, and transitivity-required pairs are present. Step 3: When all pairs are present, the relation automatically satisfies these three properties.

Correct answer: A. only on the empty set

Step 1: Reflexivity requires ((a,a)) for every (a\in A). Step 2: The empty set has no element that can violate this condition. Step 3: On a non-empty set, at least one diagonal pair is required, so the empty relation is not reflexive.

Correct answer: B. they partition (A) into disjoint parts

Step 1: An equivalence relation is reflexive, symmetric, and transitive. Step 2: These properties make every element belong to exactly one class, and distinct classes do not overlap. Step 3: The classes need not have equal size, so remember the partition idea.

Correct answer: C. ({..., -8,-4,0,4,8,...})

Step 1: The class of (0) contains integers that leave remainder (0) on division by (4). Step 2: These are exactly the multiples of (4). Step 3: When writing remainder classes, include both negative and positive multiples.

Correct answer: D. equivalence relation

Step 1: (a+a=2a) is always even, so the relation is reflexive. Step 2: If (a+b) is even, then (b+a) is even, so it is symmetric. Step 3: If two numbers have the same parity as a middle number, they have the same parity with each other, so it is transitive.

Correct answer: A. equivalence relation

Step 1: (a-a=0) is rational, so the relation is reflexive. Step 2: If (a-b) is rational, then (b-a) is rational. Step 3: The sum of two rational differences is rational, so transitivity also holds.

Correct answer: B. equivalence relation

Step 1: For every (a), (a^2=a^2), so it is reflexive. Step 2: If (a^2=b^2), then (b^2=a^2), so it is symmetric. Step 3: If (a^2=b^2) and (b^2=c^2), then (a^2=c^2), so it is transitive.

Correct answer: C. neither reflexive nor symmetric but transitive

Step 1: (a<a) is never true, so it is not reflexive. Step 2: (2<3) is true but (3<2) is false, so it is not symmetric. Step 3: If (a<b) and (b<c), then (a<c), so it is transitive.

Correct answer: D. symmetric

Step 1: ((1,2)) appears with ((2,1)), and ((2,3)) appears with ((3,2)). Step 2: Every present pair has its reverse present, so the relation is symmetric. Step 3: Since diagonal pairs are missing, do not call it reflexive or equivalence.

Correct answer: A. (2^{n^2})

Step 1: (A\times A) has (n^2) ordered pairs. Step 2: Every relation can be any subset of these (n^2) pairs. Step 3: Therefore, the total number of relations is (2^{n^2}).

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

Step 1: (A\times A) has (n^2) pairs. Step 2: A reflexive relation must contain the (n) diagonal pairs. Step 3: The remaining (n^2-n) pairs are optional, so the count is (2^{n^2-n}).

Correct answer: C. (2^{\frac{n(n+1)}{2}})

Step 1: The (n) diagonal pairs can be chosen independently. Step 2: The off-diagonal pairs form (\frac{n(n-1)}{2}) reverse-pair groups. Step 3: Total independent choices are (n+\frac{n(n-1)}{2}=\frac{n(n+1)}{2}), giving (2^{\frac{n(n+1)}{2}}).

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

Step 1: Reflexivity makes all (n) diagonal pairs compulsory. Step 2: For symmetry, only the off-diagonal reverse-pair groups are independent. Step 3: There are (\frac{n(n-1)}{2}) such groups, so the count is (2^{\frac{n(n-1)}{2}}).

Correct answer: A. transitive

Step 1: From ((1,2)) and ((2,3)), transitivity requires ((1,3)), which is present. Step 2: Other possible chains either have the required pair or do not form a chain. Step 3: Since ((3,3)) is missing, do not call it reflexive.