The number of non-empty equivalence relations on the set $\{1, 2, 3\}$ is:

Step 1: Understand Equivalence Relations and Partitions

An equivalence relation on a set partitions the set into disjoint non-empty subsets, called equivalence classes. Each element of the set belongs to exactly one equivalence class. Therefore, counting the number of equivalence relations is equivalent to counting the number of ways to partition the set.

Step 2: Identify the Set

The given set is $S = \{1, 2, 3\}$, which has 3 elements. We need to find all possible partitions of this set.

Step 3: List Partitions with One Equivalence Class

The first type of partition is when all elements are in a single equivalence class. This means the entire set forms one partition.

Step 4: List Partitions with Two Equivalence Classes

Next, we consider partitions where the set is divided into two equivalence classes. This can be done by grouping two elements together and leaving the third as a singleton. There are $\binom{3}{2}$ ways to choose two elements, which is 3 ways.

Step 5: List Partitions with Three Equivalence Classes

Finally, we consider partitions where each element forms its own equivalence class. This means each element is a singleton set.

Step 6: Count Total Partitions

Summing up the number of partitions from each case: 1 partition with one class, 3 partitions with two classes, and 1 partition with three classes. The total number of partitions is $1 + 3 + 1 = 5$. This is also known as the Bell number $B_3$.

More from this chapter

• Show that an onto function f:1,2,3 →1,2,3 is always one-one.
• Let A=-2,-1,0,1,2,3. Define a relation R on A by xRy if and only if y=max(x,1). If l is the number of elements in R, and m and n are the minimum numbers of orde
• 32. Show that f: R -> R defined as f(x) = x / sqrt(1 + x²) is one-one but not onto. (function, one-one, onto, real numbers, domain, codomain, range)
• Let A be the set of all students of a boys school. Show that the relation R in A given by R=(a, b): a is sister of b is the empty relation and R^()=(a, b): the
• Consider the identity function I_N: N → N defined as I_N(x)=x x N. Show that although I_N is onto but I_N+I_N: N → N defined as (I_N+I_N)(x)=I_N(x)+I_N(x)=x+x=2
• Prove that the relation R in the set A = 1, 2, 3, 4, 5 given by R = (a, b): |a - b| is even is an equivalence relation.
• Let f(x) = log_e x and g(x) = (x^4 - 2x³ + 3x² - 2x + 2)/(2x² - 2x + 1). Then the domain of f ° g is
• Let the domain of the function f(x) = cos^(-1) ( (4x + 5)/(3x - 7)) be [α, β] and the domain of g(x) = log_2(2 - 6log_7(2x + 5)) be [, ]. Then |7(α + β) + 4( +)

All Relations and Functions solutions →