Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

1) If a set is partitioned into non-overlapping, non-empty subsets, then those subsets are equivalence classes. If each element in a set is unique, how can a set be partitioned into subsets with equivalent elements?

2) What is the criteria for something to be an equivalence class? If the set of natural numbers was partitioned into odds {O} and evens {E}, then if I say E_1 ~ E_2 etc, am I just saying that they are equivalent in terms of how they were partitioned (i.e. divisible by 2)? Does that mean I could partition the real numbers into subsets with equal numbers of decimal places? If that is a legitimate partition, how do I 'mathematically' formulate it? If it is not, why not?

3) If a set is partitioned into non-overlapping, non-empty subsets at random, how would there be equivalence on the partitioned subsets?

Thanks in advance.

share|improve this question
    
I am not sure whether I understand your question no.3, but did you perhaps want to ask something like here: Proof of a Proposition on Partitions and Equivalence Classes? –  Martin Sleziak Aug 14 '12 at 5:41

5 Answers 5

up vote 4 down vote accepted

The idea for the first one is the following: Given a partition $\Delta$ of $X$, that partition induces an equivalence relation on $X$. Namely, we say $x$ and $y$ stand in relation if they belong to the same set of the partition. You can check that this is indeed an equivalence relation. Because

$(1)$ $x$ is always in the same set as $x$.

$(2)$ If $x$ is in the same set as $y$, then $y$ is in the same set as $x$.

$(3)$ If $x$ is in the same set as $y$, and $y$ is in the asme set as $z$, then $x$ is in the asme set as $z$.

Given a relation $\sim $ on a set $X$, we say it is an equivalence relation if it has the following three properties:

$(1)$ Reflexivity $x\sim x$. That is, every element stands in relation with itself.

$(2)$ Symmetry If $x\sim y$, then $y\sim x$. That is, if $x$ stands in relation with $y$, then $y$ stands in relation to $x$.

$(3)$ Transitivity If $x\sim y$ and $y\sim z$, then $x\sim z$. That is if $x$ stands in relation with $y$ and $y$ stands in relation with $z$, then $x$ stands in relation with $z$.

You can check that the relation divisibility is transitive and reflexive. You an check the relation of inclusio is transitive and reflexive, too, but not symmetryc. You can check that congruence $\mod{}$ a number $n$ is a equivalence relation, and so is usual equality of numbers.

Given a relation $\sim$ on a set $X$, and an element of $X$, we define the equivalence class $[[x]]$ of $x$ as all elements in $X$ that stand in relation to $x$. That is

$$[[x]]=\{a\in X:a\sim x\}$$

You can check equivalence classes are:

$(1)$ Non-empty: For each $x$, $x\in [[x]]$.

$(2)$ Either disjoint or equal: If there is one element $p$ in $[[x]]\cap[[y]]$ then we have that $p\sim y$ and $p\sim x$. Reflexivity means $y\sim p$ and $p\sim x$ so transitivity means $y\sim x$. Reflexivity once more gives $y\sim x$. Thus whenever $a\in [[x]]$, $a\sim x$ and $x\sim y$, whence $a\sim y$. Similarily whenever $b\in [[y]]$, $b\sim y$ and $y\sim x$, whence $b\sim x$. This means $[[x]]=[[y]]$.

This means that they are a partition of $X$. So any partition induces an equivalence relation, and conversely.

As to the first thing you say: if by unique you mean $x\sim y\iff x=y$, then what you have is the equivalence relation of equality which simply induces the partition of $X$ into singletons of its elements.

On you last question you talk about an equivalence on the partitioned subsets. I presume you mean an equivalence relation , but what do you mean by "on the partitioned subsets"?

Regarding the part on the "partitioning the real numbers into subsets of equal number of decimal places." Recall there are some rational numbers with nonterminating decimal expansion, and any irrational number will have a nonterminating decimal expansion. Thus, maybe you will have to work with rationals whose decimal expansion has the same amount of decimal numbers, and say talk about "number of decimal places" with nonterminating rationals acording to the period of the expansion. For example, $3^{-1}=0.\hat 3$. Else, if the number is irrational, it goesto $\mathbb I$, the set of irrational numbers.

share|improve this answer

If you partition a set, you have an equivalence relation on the partitions where x ~ y if x and y belong to the same partition. Since an equivalence relation on a set is also a partition of the set where each part of the partition corresponds to an equivalence class. So every partition of a set corresponds to an equivalence relation on the set and vice versa.

I would also suggest you take a look at http://en.wikipedia.org/wiki/Equivalence_class, specifically under the Properties section.

share|improve this answer

1.It is not a single element that you partition but rather the set, for example take the integers and devide them into Odds end Evens as in your question. you do not partion the number $1$ or $2$ etc'.

2." What is the criteria for something to be an equivalence class" - your statement in the quesion is correct "If a set is partitioned into non-overlapping, non-empty subsets, then those subsets are equivalence classes".

Normally we define when two elements are called equivalent: $xRy$ iff ... For $R$ to be an equivalence relation it must satisfy some conditions. see Wikipedia.

Regarding "Does that mean I could partition the real numbers into subsets with equal numbers of decimal places?" - the answer is no, since irrational numbers e.g. $\pi$ does not have a finite number of decimal places. if you change this a bit to have a class for the irrational numbers then yes.

3.The relation is simple $xRy$ is $x$ and $y$ are in the same set in the partition

share|improve this answer

1/ 2 and 4 are distinct and unique natural numbers, but they share the property of evenness. Insofar as they are both even, they are equivalent. So, the equivalence would regroup all the even numbers in one class and all the others in another.

2/ See 1. For real numbers, yeah that would be a valid way of partitioning the real numbers. You can just formulate it as $r_1 \sim r_2 \Leftrightarrow r_1$ has the same number of digits as $r_2$in its decimal expansion.

3/ What do you mean by "at random". In any case, you can always define the equivalence by $r_1 \sim r_2 \Leftrightarrow r_1$ and $r_2$ belong to the same subset of the partition.

share|improve this answer
    
Thanks for your answer. By 3/, I meant that the partitions were not whether a number was even or odd or some other way of categorizing them, but that there was just no pattern into how the set was partitioned. I see now that equivalence can be defined as just being in the same set. –  achacttn Aug 14 '12 at 5:43

This is less of an answer, and more of an attempt to address what I think is your misunderstanding.

1) I think you might be confusing equivalent with equal, and confusing elements with subsets (which are elements of another set!).

Perhaps a few examples will help clarify?

Each partition of a given set defines a different equivalence relation. For example, take the set $S=\{1,...,10\}$. One partition could be $\Pi_1 =\{\{1,3,5,7,9\}, \{2,4,6,8,10\} \}$, another could be $\Pi_2 = \{ \{1,...,10\}\}$, and yet another could be $\Pi_3 = \{ \{1\},...,\{10\} \}$. There are many more, of course.

The partition $\Pi_1$ has 2 elements, one element consists of the odd numbers of $S$, the other contains the even numbers. With this partition, the numbers 1 and 3 are considered equivalent, but are clearly not equal. Each element of $\Pi_1$ contains many elements of $S$.

Partition $\Pi_2$ is trivial, all elements of $S$ are considered equivalent.

Partition $\Pi_3$ is the other extreme, no pair of distinct elements are considered equivalent. However, note that $\{1\}$ is an element of $\Pi_3$, but is a (single element) subset of $S$.

2) A partition of a set $S$ is a collection of non empty subsets of $S$, say $\{P_\alpha \}$ (with each $P_\alpha \subset S$), such that every element of $S$ belongs to exactly one of the $P_\alpha$. Then each subset $P_\alpha$ is an equivalence class for the relation $\sim$ defined by $x \sim y $ iff $\exists \alpha$ such that both $x,y \in P_\alpha$.

Or, if you prefer, you could start with an equivalence relation $\sim$ (ie, a relation that is symmetric, transitive and reflexive), and define the partitions as $\{ [x] \}$, where $[x] = \{ y | x \sim y \}$. Each element of the partition is an equivalence class.

3) Each random partition defines a different notion of equivalence. For example, I could define $\Pi_4 = \{ \{1\}, \{2,...,10\} \}$ (which, perhaps, encapsulates the notion of one or many). This is obviously different from the partition $\Pi_5 = \{\{1,...9\}, \{10\} \}$ (which defines an equivalence based on the number of digits in the number).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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