0
$\begingroup$

While going through some discrete mathematics exercises I stumbled over the following statement:

there's a bijection between equivalence relations on a set S and the number of partitions on that set.

I KNOW

  • the definition of "set, subset, equivalence relation, partition, equivalence class".

  • further do I know what a bijection is.

  • I was checking out on similar questions but I have not found any satisfying answers.

MY QUESTION

So every equivalence relation forms a disjoint partition of set S.

How do I find a bijection from any equivalence relation to the number of partitions on a set?

Furthermore I am puzzled with "the number of partitions". is the number of partitions the sum of all equivalence classes to every equivalence relation that exists on S?

And if my thoughts were correct, how do I create such an bijection?

I find it very confusing since one equivalence relation always produces I or more equivalence classes so I do not see how to create such an bijection.

WHY

I am solving an exercise and it is about this topic in fact its about finding out whether the number of all equivalence relations over set $\mathbb{N}$ is countable or not and prove that.

I do not want an answer to my question I just want to give you information for what I need help.

I would be very thankful for any helpful piece of advice and explanation which then would make it able for me to solve my exercise

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ I have edited your title to remove the all-caps phrase "HELP." When some people see that on this site, they tend to ignore it. $\endgroup$ – Sean Roberson Oct 31 '16 at 17:15
  • 1
    $\begingroup$ If we have an equivalence relation on a set $X$, then the equivalence classes form a partition of $X$. This gives a mapping from the equivalence relations on $X$ to the partitions of $X$. This mapping is injective, because two different equivalence relations cannot yield the same partition. Now, we show that the mapping is surjective. If we have a partition of $X$, we define an equivalence relation by saying that two elements of $X$ are equivalent if they belong to the same subset in the partition. $\endgroup$ – user8960 Oct 31 '16 at 17:15
  • 1
    $\begingroup$ The theorem is kind of poorly stated - "there's a bijection between equivalence relations on S(set) and the number of partitions on that set." might be better phrased as "there's a bijection between equivalence relations on S(set) and the number of partitions on that set." $\endgroup$ – Dustan Levenstein Oct 31 '16 at 17:16
  • $\begingroup$ This just crossed my mind: so if there exists a partition of a set that means there must be some equivalence relation forming this set of subsets(=equivalence classes). so this basically means all kind of possibilities how to arrange a set is the number of equivalence relations on that set? is that correct? $\endgroup$ – Mainviel Oct 31 '16 at 17:17
  • $\begingroup$ yes i just realized how this statement was meant, after i released the question. thank you anyways for your very fast response! $\endgroup$ – Mainviel Oct 31 '16 at 17:25
1
$\begingroup$

I think you are mis-reading the statement. What it says is, there is a bijection from the set of equivalence relations to the set of partitions, which implies that the number of each is the same. Another way of saying the same thing, which is more consistent with the statement as given, is: Collect all partitions and assign a distinct number to each (partition #1, #2, ...); then there is a bijection between the set of equivalence relations and this set of numbers.

[So yeah, I think the statement is poorly phrased]

|cite|improve this answer
$\endgroup$
1
$\begingroup$

how do i create such an bijection?

Given an equivalence relation, you can make a partition into "mutually equivalent elements." Given a partition, you can declare two elements to be equivalent if they reside in the same piece of the partition.

furthermore i am puzzled with "the number of partitions".

An example: the partitions of $\{1,2,3\}$ are $\{\{1,2,3\}\}$, $\{\{1\},\{2,3\}\}$, $\{\{2\},\{1,3\}\}$, $\{\{3\},\{2,1\}\}$, and $\{\{1\},\{2\},\{3\}\}$. Five partitions.

is the number of partitions the sum of all equivalence classes to every equivalence relation that exists on S ?

You can't add equivalence classes in general, so no. You simply have to count how many ways the set can be split into disjoint subsets.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ so if i would have a bigger set how would i then determine the number of disjoint subsets? i thought that should be n! $\endgroup$ – Mainviel Oct 31 '16 at 17:30
  • $\begingroup$ @Mainviel read about it $\endgroup$ – rschwieb Oct 31 '16 at 17:35
  • $\begingroup$ so the number of equivalence relations on $\mathbb{N}$ there for is the bell number of infinte many elements and therefore countable? $\endgroup$ – Mainviel Nov 1 '16 at 12:15
  • $\begingroup$ @Mainviel There is no such thing as "the bell number of infinite many elements". I am not sure the partitions of a countable set are countable either. $\endgroup$ – rschwieb Nov 1 '16 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.