|
Seems like a lot of people are trying to understand the proposed solution in:
http://www.teamliquid.net/blogs/viewblog.php?topic_id=93007
And one of the big problem is that they do not understand these terms and what they mean:
equivalent class
equivalent relation
This blog is aimed to help people understand these terms, so that they might be able to understand the solution a bit better.
In particular, equivalent class is a powerful tool in mathematics that is NOT really difficult to grasp and very intuitive and easy to use, so for your own good, you should try to comprehend it.
If any math major reading this thread has some suggestions feel free to post them, the added information will surely help others understand these things better.
++++++++++++++++++++++++++++
Let us begin!
Grab a pen and some paper, it should be fun
Equivalent class is a way that you can use to partition a set. It is useful because it let us look at a big, maybe confusing set, in smaller pieces.
That's probably a lot of stuff so we start small:
First we'd have to understand what is a partition
What is a partition?
Say your set is a pizza, we can cut it into 4 slices, and that makes a "partition".
In a more precise term, a partition is an action, or a result of that action, on a set such that you divide the set into subsets, and when you concatenate all the subsets, you get the whole set back, and yet no subsets intersects each other.
Example:
Set A = {1 2 3 4 5 6}
A partition for set A can be:
{1 2 3} {4} {5 6}
{1 2 3 4 5 6}
A partition for set A cannot be:
{1 2 3} {4 6} (because concatenation does not reproduce the whole set back)
{1 2 3} {3 4 5 6} (because 3 is shared among 2 subsets)
More example:
A partition on all natural numbers N can be:
{1, 2, 3, 4, 5} {everything else}
{1 3 5 7 ... odd numbers} {2 4 6 8 ... even numbers}
A circle being partitioned into different subsets:
Now let's move on to [/b]equivalence relation[/b].
Remember in partition we're trying to divide a set into subsets? An equivalence relation helps us do that by saying:
element x and y are both in subset A if and only if x ~ y. The subset A is called an Equivalent Class.
"~" means "equivalent relation", and "x~y" reads "x is equivalent of y"
Let's understand it.
The definition for ~ include 3 of the following properties:
reflexive: x~x is true
symmetric: if x~y, then y~x is true
transitive: if x~y, y~z, then x~z is true
Examples of equivalent relations:
1) x~y if they have the same age.
To check that 1) describe an equivalent relation, we'll check it against our 3 criterias:
-reflexive, is x~x true?
yes, x has the same age as x.
-symmetric, is x~y implies y~x?
yes, x has same age as y, then y has same age as x.
-transitive, is x~y, y~z implies x~z?
yes, x has same age as y, y has same age as z, then x has same age as z.
Therefore 1) describes a valid equivalent relation.
How do we use equivalent relation to form partitions?
By construction. This is how:
Say our set is A, and we wish to form a partition on A.
We first pick an element a in A.
Now we find all elements x such that a~x
Think of it as finding all the x that are related to a.
Put the a and all the x into a set, call it H_a
We then pick an element b in A, but not in H_a
Now we find all elements x such that b~x
Put everything in H_b
repeat the process until A becomes empty.
Now I claim that H_a, H_b, .... H_n is a partition of A. Do you trust me?
Probably not, so let's prove it:
To satisfy the partition requirement, we must show 2 things, that concatenating all the subsets reproduce A, and no 2 subsets have intersections.
Since we repeat the process until A becomes empty, then our H_a, H_b... must contains ALL the elements from A, therefore concactenating them back will give us all of A.
To show that no 2 subsets have intersections though, that might take some work. Let's prove that by contradiction:
Suppose some 2 subsets have an intersection, then pick an element x from that intersection. Now x is in both H_j and H_k (that's what it means by living in the intersection).
By our definition, x is related to everything in H_j since x in H_j by our construction means x is related to j, and j related to everything.
Then similarly, x is related to everything in H_k.
It follows that everything in H_k is related to everything in H_j, meaning that H_k and H_j would've been in the same subset to begin with, forming a contradiction.
So if you read through all that... let's try an example of forming such partitions by using equivalent classes:
Let the room be full of people {a, b, c, d, e, f, g, h}
Let a = 10 by age, and b = 11, c = 10, d = 11, e = 12, f = 10, g = 12, h = 11;
We let our equivalent relation be x~y if x y same age.
We pick an element from these people, let's say we picked b.
We now find everybody that are related to b, namely all people of age 11, so b, d, h.
We put all that into a subset H_b, and H_b = {b, d, h}
Now we find an element that's not in H_b, but still in our set, we settled with a.
Then find everybody related to a, {a, c, f}
Name our set H_a = {a, c, f}
Then find element e, and H_e = {e, g}
So we've exhausted set A, and now we formed a partition:
H_a, H_b, H_e
or
{a, c, f}, {b, d, h}, {e, g}
Where H_a is an equivalent class, H_b is an equivalent class, H_e is an equivalent class.
You should varify that this does indeed forms a valid partition.
If you followed everything in this post you should get some idea what is a partition and what is an equivalent relation, and what is an equivalent class, and how they are used to construct each other.
|
exercise problems:
1) Form a partition on the real numbers, anything would work, and verify that it is a valid partition.
2) Let us consider the real numbers, we define an equivalent relation: x~y if x-y=0. Is this a valid equivalent relation? Show works.
3) Let us consider a group of humans, we define an equivalent relation: x~y if x and y are in a family. Is this a valid equivalent relation? Show works.
4) Suggest a way to partition the natural numbers into equivalent classes, how many subsets are there in your partition? What is the equivalent relations you used?
|
Wow this is awesome. I've tried to learn math on wikipedia a couple times and the writing style just isn't for that.
Thanks!
|
On May 10 2009 16:03 seppolevne wrote:
Wow this is awesome. I've tried to learn math on wikipedia a couple times and the writing style just isn't for that.
Thanks!
thx for the thanks! this is quite a long post and I was worried it won't be appreciated 
|
I believe the canonical terms are "equivalence class" and "equivalence relation."
Additional comment:
Equivalence classes are useful when you have a bunch of things that you don't wan't to distinguish from each other.
Some uses of equivalence classes:
1. The rational numbers need to be sorted out into equivalence classes or you won't have unique additive inverses (1/2, 2/4, 3/6 etc)
2. In constructing decimal expansions of real numbers you want to clump together numbers like .9999--- and 1. (Equivalence classes of cauchy sequences) (Actually that's how you make any metric space complete)
3. If you want to talk about an inner product space (lebesgue integrable functions on an interval for example) you need to be able put together measurable functions that are the same almost everywhere (everywhere except for a set of measure zero) or else we don't have positive definiteness
4. You can construct weird things like non measurable sets
(Good thread - there should be more math threads)
|
Yeah it is usually equivalence, very nice read though. Seems to cover everything pretty well
|
you need to come teach at my old school. i swear you are overqualified. xD
|
Teacher! teacher! i learned then what is an equivalence relation. However, I think you missed to tell what is a relation in first place (: . Well just a small point. Good work Evan.
|
On May 10 2009 17:35 Malongo wrote:
what is a relation
It is what they get when a guy asks a woman out and she says yes.
Equivalent relation is just another word for a polyamoric relationship, with the normal 2 element relation being a special case.
|
On May 10 2009 16:14 UnitarySpace wrote:
I believe the canonical terms are "equivalence class" and "equivalence relation."
Additional comment:
Equivalence classes are useful when you have a bunch of things that you don't wan't to distinguish from each other.
Some uses of equivalence classes:
1. The rational numbers need to be sorted out into equivalence classes or you won't have unique additive inverses (1/2, 2/4, 3/6 etc)
2. In constructing decimal expansions of real numbers you want to clump together numbers like .9999--- and 1. (Equivalence classes of cauchy sequences) (Actually that's how you make any metric space complete)
3. If you want to talk about an inner product space (lebesgue integrable functions on an interval for example) you need to be able put together measurable functions that are the same almost everywhere (everywhere except for a set of measure zero) or else we don't have positive definiteness
4. You can construct weird things like non measurable sets
(Good thread - there should be more math threads)
OoOO! equivalent class of cauchy sequences!
Do you go let x, y be cauchy sequences, x~y if x, y converge to the same element?
That's so cool!
|
Ah it would be nice if this forum had some sort of latex input, but this is clear enough anyway.
The first time I heard of equivalence relations I was very confused, partly due to the fact that I didn't even know what a set was. If I had an explanation like the one you've given I'm sure I would've understood instantly.
Also I just noticed the spelling of concatenate, I've heard people say it like "con-cak-ta-nate" so I assumed there was another c there. Strange that I've never actually written that word.
|
In conclusion:
A set is a sequence of stuff:
{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z} is the set of lowercase letters in the alphabet.
{..., -3, -2, -1, 0, 1, 2, 3, ...} is the set of integers.
{a, x, p, L, 2, 0, F, s, 5} is just a set (no a particular one, obviously)
A subset is a little piece of a bigger set:
{e, f, g, h, i} is a subset of the alphabet
A partition of a set is when you take all of its subsets and concatenate (sort of like add) them together, you get back the whole set again:
{a, b, c, d, e}{f, g, h, i, j, k, l, m, n}{o, p, q, r, s, t u, v, w, x, y}{z}
No overlapping allowed: {a, b, c}{c, d, e, ...}
+ Show Spoiler +
|
On May 10 2009 20:35 evanthebouncy! wrote:Show nested quote +On May 10 2009 16:14 UnitarySpace wrote:
I believe the canonical terms are "equivalence class" and "equivalence relation."
Additional comment:
Equivalence classes are useful when you have a bunch of things that you don't wan't to distinguish from each other.
Some uses of equivalence classes:
1. The rational numbers need to be sorted out into equivalence classes or you won't have unique additive inverses (1/2, 2/4, 3/6 etc)
2. In constructing decimal expansions of real numbers you want to clump together numbers like .9999--- and 1. (Equivalence classes of cauchy sequences) (Actually that's how you make any metric space complete)
3. If you want to talk about an inner product space (lebesgue integrable functions on an interval for example) you need to be able put together measurable functions that are the same almost everywhere (everywhere except for a set of measure zero) or else we don't have positive definiteness
4. You can construct weird things like non measurable sets
(Good thread - there should be more math threads) OoOO! equivalent class of cauchy sequences! Do you go let x, y be cauchy sequences, x~y if x, y converge to the same element? That's so cool!
That would totally defeat the purpose (the purpose is for example defining the real numbers). They are equivalent if they get infinetely close to each other (I wont bother with the exact epsilon definition but it's not hard).
The point is that you can't express all limits of cauchy sequences with rational numbers and thus define the limits(=real numbers) over the sequences.
[EDIT]: Damn it's hard to write about math in english, I'll try to clarify: you can't say a_n -> a if you do not have this a, so we try to define the real number a over the equivalence class of all rational sequences a_n that get infinetly close to our unknown a and thus infinetly close to each other.
|
On May 10 2009 23:15 silynxer wrote:Show nested quote +On May 10 2009 20:35 evanthebouncy! wrote:On May 10 2009 16:14 UnitarySpace wrote:
I believe the canonical terms are "equivalence class" and "equivalence relation."
Additional comment:
Equivalence classes are useful when you have a bunch of things that you don't wan't to distinguish from each other.
Some uses of equivalence classes:
1. The rational numbers need to be sorted out into equivalence classes or you won't have unique additive inverses (1/2, 2/4, 3/6 etc)
2. In constructing decimal expansions of real numbers you want to clump together numbers like .9999--- and 1. (Equivalence classes of cauchy sequences) (Actually that's how you make any metric space complete)
3. If you want to talk about an inner product space (lebesgue integrable functions on an interval for example) you need to be able put together measurable functions that are the same almost everywhere (everywhere except for a set of measure zero) or else we don't have positive definiteness
4. You can construct weird things like non measurable sets
(Good thread - there should be more math threads) OoOO! equivalent class of cauchy sequences! Do you go let x, y be cauchy sequences, x~y if x, y converge to the same element? That's so cool! [EDIT]: Damn it's hard to write about math in english, I'll try to clarify: you can't say a_n -> a if you do not have this a, so we try to define the real number a over the equivalence class of all rational sequences a_n that get infinetly close to our unknown a and thus infinetly close to each other.
It's funny you say that, the lecturer for Analysis always said "...and in German..." before giving a definition using epsilons, exists, for-alls etc.
|
On May 10 2009 20:35 evanthebouncy! wrote:Show nested quote +On May 10 2009 16:14 UnitarySpace wrote:
I believe the canonical terms are "equivalence class" and "equivalence relation."
Additional comment:
Equivalence classes are useful when you have a bunch of things that you don't wan't to distinguish from each other.
Some uses of equivalence classes:
1. The rational numbers need to be sorted out into equivalence classes or you won't have unique additive inverses (1/2, 2/4, 3/6 etc)
2. In constructing decimal expansions of real numbers you want to clump together numbers like .9999--- and 1. (Equivalence classes of cauchy sequences) (Actually that's how you make any metric space complete)
3. If you want to talk about an inner product space (lebesgue integrable functions on an interval for example) you need to be able put together measurable functions that are the same almost everywhere (everywhere except for a set of measure zero) or else we don't have positive definiteness
4. You can construct weird things like non measurable sets
(Good thread - there should be more math threads) OoOO! equivalent class of cauchy sequences! Do you go let x, y be cauchy sequences, x~y if x, y converge to the same element? That's so cool!
Just to clarify Not all cauchy sequences converge to an element. IF the space is complete then Cauchy sequences converge. This depends as much as the space sample as the metric used.
And still no "Relation" definition /:
|
On May 11 2009 00:48 Malongo wrote:Show nested quote +On May 10 2009 20:35 evanthebouncy! wrote:On May 10 2009 16:14 UnitarySpace wrote:
I believe the canonical terms are "equivalence class" and "equivalence relation."
Additional comment:
Equivalence classes are useful when you have a bunch of things that you don't wan't to distinguish from each other.
Some uses of equivalence classes:
1. The rational numbers need to be sorted out into equivalence classes or you won't have unique additive inverses (1/2, 2/4, 3/6 etc)
2. In constructing decimal expansions of real numbers you want to clump together numbers like .9999--- and 1. (Equivalence classes of cauchy sequences) (Actually that's how you make any metric space complete)
3. If you want to talk about an inner product space (lebesgue integrable functions on an interval for example) you need to be able put together measurable functions that are the same almost everywhere (everywhere except for a set of measure zero) or else we don't have positive definiteness
4. You can construct weird things like non measurable sets
(Good thread - there should be more math threads) OoOO! equivalent class of cauchy sequences! Do you go let x, y be cauchy sequences, x~y if x, y converge to the same element? That's so cool! Just to clarify Not all cauchy sequences converge to an element. IF the space is complete then Cauchy sequences converge. This depends as much as the space sample as the metric used. And still no "Relation" definition /:
a=b+2 is an example of a relation.
a=x+2n were n is any whole number is an example of a relation which have two equivalence classes, the odd and the even numbers. Of course a and x are whole numbers too, otherwise you would have an infinite amount of equivalence classes.
|
On May 10 2009 23:06 EsX_Raptor wrote:In conclusion: A set is a sequence of stuff: {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z } is the set of lowercase letters in the alphabet. {..., -3, -2, -1, 0, 1, 2, 3, ... } is the set of integers. {a, x, p, L, 2, 0, F, s, 5 } is just a set (no a particular one, obviously) A subset is a little piece of a bigger set: {e, f, g, h, i } is a subset of the alphabet A partition of a set is when you take all of its subsets and concatenate (sort of like add) them together, you get back the whole set again: {a, b, c, d, e }{f, g, h, i, j, k, l, m, n }{o, p, q, r, s, t u, v, w, x, y }{z }No overlapping allowed: {a, b, c}{c, d, e, ... }+ Show Spoiler +
yeah u got it
Keep in mind that no 2 subsets have overlaps, that is, take ANY 2 subset, there'd be no overlaps.
Basically think of disc partition and use your intuitions.
|
On May 11 2009 00:48 Malongo wrote:Show nested quote +On May 10 2009 20:35 evanthebouncy! wrote:On May 10 2009 16:14 UnitarySpace wrote:
I believe the canonical terms are "equivalence class" and "equivalence relation."
Additional comment:
Equivalence classes are useful when you have a bunch of things that you don't wan't to distinguish from each other.
Some uses of equivalence classes:
1. The rational numbers need to be sorted out into equivalence classes or you won't have unique additive inverses (1/2, 2/4, 3/6 etc)
2. In constructing decimal expansions of real numbers you want to clump together numbers like .9999--- and 1. (Equivalence classes of cauchy sequences) (Actually that's how you make any metric space complete)
3. If you want to talk about an inner product space (lebesgue integrable functions on an interval for example) you need to be able put together measurable functions that are the same almost everywhere (everywhere except for a set of measure zero) or else we don't have positive definiteness
4. You can construct weird things like non measurable sets
(Good thread - there should be more math threads) OoOO! equivalent class of cauchy sequences! Do you go let x, y be cauchy sequences, x~y if x, y converge to the same element? That's so cool! Just to clarify Not all cauchy sequences converge to an element. IF the space is complete then Cauchy sequences converge. This depends as much as the space sample as the metric used. And still no "Relation" definition /:
I know that already, I'm in an analysis class so don't worry.
I'm trying to understand what kind of fun equivalence class can be drawn on the real numbers.
I was proposing let's have a space of all cauchy sequence that converges, maybe we can break that space into equivalent classes with Xn~Yn iff Xn->k, Yn->k. or something fun
I don't want to define relation here because a relation is more of a "noun" than a "verb" so I think it'll be very confusing for alot of people.
Rigorously speaking
a relation between set X and set Y is a SET(call it R), of pairs with the form (x, y) where x lives in X and y lives in Y.
We say x and y are related(lets denote this by xRy) if and only if the pair (x, y) exists in R.
Example:
set X = {a, b, c}
set Y = {1, 2, 3, 4}
A relation can be
R = {(a, 3), (c, 1), (b, 1)}
Is aR3?
Yes, because (a, 3) exists in R
Is aR1?
No, because (a, 1) does not exist in R
|
|
|
On May 11 2009 04:59 evanthebouncy! wrote:
I was proposing let's have a space of all cauchy sequence that converges, maybe we can break that space into equivalent classes with Xn~Yn iff Xn->k, Yn->k. or something fun
Let X be a set. You can have some fun in trying to define an equivalence
relations on sequences with value on X.
Let F be a subset of P(N). That means that every element of F is a subset
of N. Now if you have two sequences (u_n) and (v_n), you can define the
relation
(u_n) ~ (v_n) iff {n | u_n = v_n} is in F.
(that is you look for which intergers the have the same values, and you say
there are "equivalent" if this set is in F).
Now how can we choose F such that ~ is an equivalence relation?
1) We must have (u_n) ~ (u_n), so that N is in F.
2) If (u_n) ~ (v_n) and (v_n) ~ (w_n), we must have (u_n) ~ (w_n).
Let A={n | u_n=v_n}, B={n| v_n=w_n} and C={n| u_n=w_n}. A and B are in F,
and me must have that C is in F.
Or A cap B is a subset of C.
By detailling further we have: ~ is an equivalence relation iff
- N is in F.
- for every A in F, if B contains A, then B is in F.
- for every A,B in F, A cap B is in F.
Furthermore, if you don't want the relation to be trivial, you have:
- the empty set is not in F.
If F satisfy these relations, it is called a filter. Filters were invented
by Cartan, and there is a book by Bourbaki (Topologie générale) explaining
how to use them in topology.
Some examples:
the equivalence relation used to solve the problem you speak about in the
op is the one defined by the filter of complements of finite sets. That is
A is in F iff N\A is finite.
When you look at converging sequence, you will use the filter
F={ {n,n+1,n+2,...}: n \in N}. If X is a topological space, then (u_n)->x
is the same as saying that for every neighbourhoud V_x of x, {n | u_n \in
V_x} is in F.
|
On May 10 2009 23:15 silynxer wrote:
Damn it's hard to write about math in english, I'll try to clarify: you can't say a_n -> a if you do not have this a, so we try to define the real number a over the equivalence class of all rational sequences a_n that get infinetly close to our unknown a and thus infinetly close to each other.
Yup, but you can still say that a_n -> 0, because 0 is a rationnal number.
So you can define two cauchy sequences (u_n) and (v_n) to be equivalent iff (u_n-v_n)->0.
(as you remark, this is just another way of saying that they will be infinitely close to each other).
(By the way, there is another fun way to construct the real, by using Dedekink's cut).
|
Wow, I can't believe so many here are into advanced math (advanced like university level), it's awesome! I'll try to keep track on the math threads, being able to have a forum for both math and sc, I'm in heaven .
|
|
|
|
|
|
EPT![[image loading]](http://www.bearfruit.org/files/asymetric-cut.png)
