0

Perhaps I'm missing something from just the definition of an equivalence relation but wouldn't a matrix representing an equivalence relation on any set be only ones and anything less than that is just an equivalence class? If someone can clarify this for me that'd be great.

herpaherm
  • 1
  • Can you give a formal definition of the "matrix representing an equivalence relation"? (presumably on a finite set) – Greg Martin Apr 17 '19 at 22:04
  • @GregMartin I'm sorry to answer your question with another but my question really stems from this question that has me put off. Say you have a set of { a, b, c } where { a, c } and { c, b } are required to be contained in the equivalence relation on that set. Wouldn't it suffice to say you have the reflexive pairs and the symmetric pairs for those that are missing? How wouldn't these pairs be transitive? Do you need to use every element in the set? – herpaherm Apr 17 '19 at 22:09
  • It is a true fact (and a good exercise to work through) that any equivalence relation on ${a,b,c}$ that contains both $(a,c)$ and $(c,b)$ must in fact contain all $9$ ordered pairs. I strongly encourage you to work on this exercise and your original question from the standpoint of starting with the formal definitions. Building intuition is absolutely great in mathematics, but ultimately definitions, axioms, and rigorous deduction are the tools of the trade. – Greg Martin Apr 17 '19 at 22:14
  • 2
    @GregMartin You're right I went back and read. My definitions were off. I was missing that I need to look at every element in the set that I'm working on. Thank you! – herpaherm Apr 17 '19 at 22:20
  • The diagram of the 52 equivalence relations on a 5-element set found on https://en.m.wikipedia.org/wiki/Equivalence_relation might be illuminating. – amd Apr 17 '19 at 23:07

1 Answers1

0

For $n\gt1$, there is more than one possible equivalence relation on a set with $n$ elements. Obviously they can’t all be represented by the same matrix. In particular, the “minimal” equivalence relation on $S$ is $R=\{(x,x) \mid x\in S\}$. This relation is represented by the $n\times n$ identity matrix.

It’s a worthwhile exercise to work out what properties the representative matrix must have. The reflexive and symmetric properties are pretty easy to translate into statements about the matrix, but transitivity might be a bit tricky.

amd
  • 53,693