18.5k views
3 votes
A) How many reflexive relations are there on a set with n elements?

b) How many symmetric relations are there on a set with n elements?
c) How many antisymmetric relations are there on a set with n elements?

1 Answer

1 vote

Final answer:

The number of reflexive, symmetric, and antisymmetric relations on a set with n elements can be determined using combinatorics. The total number of reflexive relations is 2^n, the total number of symmetric relations is 2^(n*(n+1)/2), and the total number of antisymmetric relations is 3^(n*(n+1)/2).

Step-by-step explanation:

a) To determine the number of reflexive relations on a set with n elements, we need to consider each element in the set. Each element can either be related to itself or not. So, there are 2 choices for each element. Since there are n elements in the set, the total number of reflexive relations is 2^n.

b) To determine the number of symmetric relations on a set with n elements, we need to consider each pair of elements in the set. Each pair can either be related or not. So, there are 2 choices for each pair. Since there are n*(n+1)/2 pairs of elements in the set, the total number of symmetric relations is 2^(n*(n+1)/2).

c) To determine the number of antisymmetric relations on a set with n elements, we need to consider each pair of elements in the set. Each pair can be related, or if the first element is related to the second element, the second element cannot be related to the first element. So, there are 3 choices for each pair. Since there are n*(n+1)/2 pairs of elements in the set, the total number of antisymmetric relations is 3^(n*(n+1)/2).

User DavidWayne
by
8.1k points