Re: Testing for the equivalence relation

"Dan Guntermann" <gunterm...@xxxxxxxxxxx> wrote in message

news:f3Oxe.6649$Fy4.5701@xxxxxxxxxxx

> "VC" <boston...@xxxxxxxxxxx> wrote in message
[...]
>> There are just two equivalence classes. What's a 'distinct' equivalence
>> class ? Is it some kind of 'computer'-math speak ?

> Erratum

> Change the words "4 equivalence classes" to "four elements with
> equivalence classes, denoted [a], [b], [c], [d]."

: The words "four elements with equivalence classes, denoted [a], [b],
[c],
: [d]." just does not make sense because, say, [a] is not 'an element
with an
: equivalence class.

Hmmm. I don't claim to be a math expert, and my skills and
understanding are admittedly modest. I'll try to explain my
understanding with the caveat that there are probably more qualified
individuals to explain and/or correct. I don't think I am technically
incorrect here, but I can see that perhaps sloppiness was at play here,
if for no other reason than my difficulty in articulating my
understanding of concepts in basic math textbooks.

If we were to accept that [a] is 'not an element with an equivalence
class,' then we are not talking about equivalence relations or
equivalence classes, by definition. Every element is an element
assigned to an equivalence class.

And by definition, an element 'a' is always a member of [a] in an
equivalence relation. Think of [a] as a shorthand for "some set of
which a is a member of." If each element of a domain is assigned some
set for which it is a member of in terms of equivalence, and the number
of elements is N, then there are N sets (associated with N elements)
which we must evaluate and compare, either explicitly or in our
imagination.

Depending on the nature of the equivalence relation, [a] might assigned
the set {a}, meaning it is not equivalent (not related) to any other
symbol but itself (this is called an identity relation), or it might be
assigned the set consisting of all elements in the domain, meaning that
all symbols in the domain are equivalent to each other, or something in
between.

In the first case, there will be the same number of "distinct"
equivalence classes as there are elements. In the latter case, there
will be one common equivalence class assigned to all elements of the
domain.

: It's just an equivalence class, that's all. You might
: say let's introduce a pair (a, [a]) but I fail to see what the use of
this
: construction would be.

Well, I think your example works. If you recall my original example,
we would have the following pairings using your suggestion of a
pairing:
{(a,[a]), (b,[b]), (c,[c]), (d, [d])}

Upon evaluation, we can make the following substitutions:
{(a,{a,b}), (b,{a,b}), (c, {c,d}), (d, {c, d})}

Suppose, however, that the binary relation was updated to give the
following over domain s = {a, b, c d}:
R := { (a,a), (a,b), (a,c), (a,d), (b, b), (b,a),
(b,c), (b,d), (c,c), (c,a), (c, b), (c, d),
(d, d), (d, a), (d, b), (d, c) }

Again, using your pairing:
{(a,[a]), (b,[b]), (c,[c]), (d, [d])}

But this time evaluation and substition yields:
{(a,{a,b,c,d}), (b,{a,b,c,d}), (c, {a,b,c,d}), (d, {a,b,c,d})}

Make sense? So perhaps we can say that the basic algorithm for finding
distinct equivalence classes in an equivalence relations involves 1)
constructing an equivalence class (a set) for each element; and 2)
eetermining which element classes are the same.

By axiom of extension, you are right. Each equivalence class is
determined soley by the element membership of the set.

>>

>> Saw your later comment. Since an equivalence class is a subset of the
>> original set over which the equivalence relation is defined, how the
>> {a,b} subset is different from the {a, b} subset ?

> Yes, it is a partition and the sets are the same. Perhaps if one applies
> a name to both sets, we now have a basis for distinguishing the first from
> the second, even if they were to be proven equal?

: See above.

>[...] when we ask whether set A is equal to set B. They might be exactly
>the same, but we still distinguish them because they might not be the same.

: ??? How is it possible to be exactly the same and not the same at
once ?

I never meant to imply that they are the same and not the same at once.
I said they might or might not be the same and I meant to imply that
equality must be determined by examining and comparing the contents of
each element's set. By the axiom of extension, we have to evaluate
each element's equivalence class to determine equality.

Depending on the partition, the set denoted by [a] might not equal the
set denoted by [c] because {a, b} <> {c, d} (such as in my original
example), but in another equivalence relation over the same domain,
[a] = [c] because {a, b, c, d} = {a, b, c, d}.

Let me ask this:
For a question concerning sets A, B, C, if I were to ask whether A = B
= C, could you tell me how many sets I am talking about? If so, how?

Regards,

Dan

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... each component of the graph should be considered as a second ... equivalence class over the vertices and be intersected with the first. ... vector of size N containing equivalence classes for the corresponding ...
    (sci.crypt)
  • Re: An uncountable countable set
    ... equivalence class and the equivalence class itself. ... This is the principle used in NBG using the von Neumann naturals as ... subjectivity, but the fact that any normal theory only addresses certain ...
    (sci.math)
  • Re: (.999999... == 1) = 1 <--No, if it does 0 =1
    ... is naturally associated with the Cauchy sequence ... we can define an equivalence relation on ... meaning that x and y belong to the same equivalence class. ...
    (sci.math)
  • Re: equivalence classes
    ... > equivalence classes. ... > equivalence classes for any set, X, such that they ... > cases where there are infinite equivalence classes? ... Although an equivalence relation in a non empty class ...
    (sci.math)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Ben Livengood wrote: ... graphs" variant never falsely declare graphs non-isomorphic. ... Let N be the number of equivalence classes over ... class i to vertices in equivalence class j. ...
    (sci.crypt)