Similarity relations on sets

Question

Good evening,

I am reading Hazel and Humberstone's "Similarity Relations and the Preservation of Solidity", a paper that has the aim of defining, starting from partitions and equivalence relations, what could a set resulting from a similarity relation on might look like.

There are two points not really clear to me regarding the very first section.

1. "Note that because a similarity relation need not be transitive, an element of U can belong to more than one similarity class, by contrast with the case of equivalence classes. Thus in solving our problem, the desired notion of an X will not require, as that of a partition does, that the sets it contains should be pairwise disjoint."

I don't really get why transitivity and not other properties in equivalence relations are directly responsibile of the fact that equivalence classes are pairwise disjoint and also why relations that are reflexive and symmetric, but not necessarily transitive, do not imply analogous similarity-classes that are pairwise disjoint. I think a good idea would be to find a counter-example, but i couldn't manage to do so

2)" As a first stab toward a solution, which will soon be seen to require further refinement, we introduce the notion of a decomposition of U , by which is meant a collection $\Delta$ of non-empty subsets of U such that

a) the union of all the elements of$\Delta = U$

b) for no x,y in $\Delta$ we have $X\subset Y$

Condition (i) is required if decompositions are to be sets of similarity classes for a similarity relation S, because of the reflexivity of S, and condition (ii), which replaces the condition of pairwise disjointness in the definition of partition, is needed because similarity classes are maximal amongst the S-solid subsets, so one cannot be properly included in another, for which reason the same should go for the components of a decomposition, as (ii) dictates."

Here i did not understand why refelxivity is responsibile for the fact that the union of the elements in the decomposition is equal to the origina set.

Thanks in advance.

source: https://www.researchgate.net/publication/225877517_Similarity_Relations_and_the_Preservation_of_Solidity

Answer 1

For your first question, let $R=\{\langle m,n\rangle\in\Bbb Z\times\Bbb Z:|m-n|\le 1\}$; then $R$ is reflexive, symmetric, and not transitive, and the similarity class of $n\in\Bbb Z$ is $[n]_R=\{n-1,n,n+1\}$. Thus, each $n\in\Bbb Z$ is in three similarity classes: $[n-1]_R=\{n-2,n-1,n\}$, $[n]_R=\{n-1,n,n+1\}$, and $[n+1]_R=\{n,n+1,n+2\}$.

For your second question, let $x\in U$. Reflexivity implies that $\langle x,x\rangle\in R$, so $x\in[x]_R$, and therefore $x$ is in the union of the similarity classes of $R$. Thus, $U=\bigcup_{x\in U}[x]_R$.

Added: Let $U=\{a,b,c,d,e,f\}$, and consider the decomposition

$$\Delta=\big\{\{a,b,c\},\{a,c,d,e\},\{d,e,f\},\{a,c,f\}\big\}\,;$$

we want to know whether $\Delta$ could be the set of similarity classes of some similarity $\sim$ on $U$. Suppose that they are. Each of them must be $\sim$-solid, so we know that

• $a\sim b$, $a\sim c$, and $b\sim c$;
• $a\sim c$, $a\sim d$, $a\sim e$, $c\sim d$, $c\sim e$, and $d\sim e$;
• $d\sim e$, $d\sim f$, and $e\sim f$; and
• $a\sim c$, $a\sim f$, and $c\sim f$.

Combining those results, we see that

• $a\sim c$, $a\sim d$, $a\sim e$, and $a\sim f$;
• $c\sim d$, $c\sim e$, and $c\sim f$;
• $d\sim e$ and $d\sim f$; and
• $e\sim f$.

That is, the set $\{a,c,d,e,f\}$ is also $\sim$-solid, and it is not a subset of any member of $\Delta$. In fact, it properly contains three of the members of $\Delta$, $\{a,c,d,e\}$, $\{d,e,f\}$, and $\{a,c,f\}$, which are therefore not maximal $\sim$-solid sets: each of them can be expanded to the set $\{a,c,d,e,f\}$. Since $\Delta$ has at least one component that is not a maximal $\sim$-solid set, $\Delta$ is not the set of similarity classes of any similarity relation.

We could have recognized this without listing all of the $\sim$-pairs implied by $\Delta$ by noticing that each two-element subset of $\{a,c,d,e,f\}$ is a subset of some component of $\Delta$: $\{a,c\}$ is a subset of $\{a,b,c\}$ (and of $\{a,c,d,e\}$ and $\{a,c,f\}$, for that matter); $\{a,d\}$ is a subset of $\{a,c,d,e\}$; and so on. Because each component of $\Delta$ is $\sim$-solid, every pair of elements of a component are $\sim$-related, so this tells us that every pair of elements of $\{a,c,d,e,f\}$ are $\sim$-related and hence that $\{a,c,d,e,f\}$ is also $\sim$-solid.

To rule out this kind of decomposition, the authors add the following condition: if $Y$ is a subset of $U$ such that each pair of element of $Y$ is contained in some member of $\Delta$, then $Y$ is a subset of some member of $\Delta$. That was not the case with this example: each pair of elements of $\{a,c,d,e,f\}$ is a subset of some member of $\Delta$, but $Y$ is not a subset of any member of $\Delta$. Then in their Proposition $2.2$ they show that this restriction is exactly what is needed to ensure that a decomposition really is the set of similarity classes of some similarity relation.