1
$\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

$\endgroup$
5
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 17:25

2 Answers 2

Reset to default
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]

$\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.

$\endgroup$
4
  • $\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, 2016 at 17:30
  • $\begingroup$ @Mainviel read about it $\endgroup$
    – rschwieb
    Oct 31, 2016 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, 2016 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, 2016 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.