6

I don't understand the following problem: http://i.imgur.com/qrqAhDX.png What does it mean exactly that a number of pairs can "determine" an equivalence relation? Say if I have the following set: {1, 2, 3}, and a relation R that's true for (a, b) if a=b. Then would the pairs {1, 1}, {2, 2}, and {3, 3} "determine" this relation? How then, does the author arrive at n/2 for this solution?

This problem is from this problem set.

user886596
  • 263
  • I think the question is a little ambiguous. I can't see how all blocks of size $1$ can be excluded given that the solution includes a block of that size. If it is intended that pairs of distinct elements are meant, then zero pairs gives you all blocks of size $1$. – Mark Bennet Oct 22 '13 at 16:10
  • 1
    I understand the problem statement as follows: Given a relation $R\subseteq A\times A$, there exists a smallest equivalence relation $E$ containing $R$. The $E$ is also the intersection of all equivalence relations containing $R$ and can be called the equivalence relation determined by $R$. As such, even the empty set determines an equivalence relation, namely $=$. As a corollary, the problem statement (or at least the given solution) does not make sense to me. – Hagen von Eitzen Oct 22 '13 at 16:10
  • @Hagen: That was my first reaction too, but if you look at the whole linked problem set, it sets out its own (slightly idiosyncratic) definition of how a set of pairs “determines” an equivalence relation. Essentially, it recovers the domain of the relation just as the union of the pairs, and so requires that every element of the domain is in one of the pairs. – Peter LeFanu Lumsdaine Oct 22 '13 at 16:17

2 Answers2

1

The author seems to describe very carefully what it means for a collection of pairs to "determine" a relation. You start with a relation that you know is an equivalence relation, and then start throwing things out until you cannot throw out anymore.

For instance, if you begin with the relation $$ R = \{(1,1), (2,2), (3,3), (2,3), (3,2)\} $$ Then you can throw out $(2,2)$ and $(2,3)$ and only keep $(3,2)$ $$ R' = \{(1,1), (3,3), (3,2)\} $$ because once you know $(3,2) \in R$, you know that $(2,3) \in R$ by symmetry and you know $(2,2) \in R$ by transitivity.

The author seems to arrive at $n/2$ as follows : You need each element of $S = \{1,2,\ldots, n\}$ to be present in some pair. We can order the elements so that $$ R' = \{(1,2), (3,4), \ldots, (n-1,n)\} \text{ (assume $n$ even for now)} $$ Now, $|R'| = n/2$, and this is the bare minimum. If any element appears in two pairs, then the element that it "kicked out" would have to show up in another pair, thereby increasing the number of pairs.

One has to make this argument rigorous, but that is the gist of it.

Prahlad Vaidyanathan
  • 31,554
0

This is explained, although in a slightly roundabout way, at the beginning of Problem 4 on the problem set.

Rephrasing the definition, hopefully slightly more clearly: if $R$ is any set of pairs, then the equivalence relation it determines is a relation $E_R$ on the set $\bigcup R$ (i.e. the set of all elements that appear in any pair in $R$); $E_R$ is defined as the smallest equivalence relation on $\bigcup R$ containing $R$.

Exercise: for $(x,y) \in \bigcup R$, you have $(x,y) \in E_R$ if and only if there is some sequence $(x_0,x_1,\ldots,x_n)$ such that $x_0 = x$, $x_n = y$, and for each $0 \leq i < n$, either $(x_i,x_{i+1}) \in R$ or $(x_{i+1},x_i) \in R$.

The slightly nonstandard part of the definition is taking the domain of the equivalence relation to be also determined by $R$, rather than as given separately. A more common version of the definition is: suppose $X$ is a set, and $R \subseteq X \times X$; then the equivalence relation on $X$ generated by $R$ is the smallest equivalence relation on $X$ containing $R$. (And again, one can give an explicit definition of this by sequences of elements that are related in $R$.)

Peter LeFanu Lumsdaine
  • 9,434