If and is a multiple of or , where is the set of positive integers, then the total number of symmetric relations on is
The set is defined as all positive integers that are multiples of or .
Multiples of below : .
Multiples of below : .
Taking the union and removing repetition we get
, so .
A relation on is a subset of . For the relation to be symmetric, whenever is present, must also be present.
Counting choices for a symmetric relation on an -element set:
• Diagonal (reflexive) ordered pairs : there are of them. Each can be either included or not, giving choices.
• Off-diagonal ordered pairs: group them into unordered pairs with . Each unordered pair corresponds to the two ordered pairs and which must be chosen together (both in or both out). The number of such unordered pairs is , giving choices.
Therefore, the total number of symmetric relations is
.
For , this exponent equals
.
Hence the number of symmetric relations on is .
Option B which is:
Tagged Reflexive, symmetric and transitive relations. Machine-assigned, so read it as a strong shortlist rather than a verdict.