MHB Show that ~ is an equivalence relation

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Let $M:=\{1, 2, \ldots, 10\}$ and $\mathcal{P}:=\{\{1,3,4\}, \{2,8\}, \{7\}, \{5, 6, 9, 10\}\}$.

For $x \in M$ let $[x]$ be the unique set of $\mathcal{P}$ that contains $x$.

We define the relation on $M$ as $x\sim y:\iff [x]=[y]$.

Show that $\sim$ is an equivalence relation.
For that we have to show that the relation is reflexive, symmetric and transitive.
  • Reflexivity:

    Let $x \in M$. Then it holds, trivially, that $[x]=[x]$. Therefore $x\sim x$. So $\sim$ is reflexive.
  • Symmetry:

    Let $x,y \in M$ and $x\sim y$. Then $[x]=[y]$. Equivalently it holds that $[y]=[x]$ and therefore $y \sim x$. So $\sim$ is symmetric.
  • Transitivity:

    Let $x,y,z\in M$ and $x\sim y$ and $y\sim z$. Then it holds that $[x]=[y]$ and $[y]=[z]$. So we have that $[x]=[y]=[z]$, so $[x]=[z]$ and therefore $x\sim z$. So $\sim$ is transitive.

Is everything correct and complete? Or do we have to justify each property with more details, i.e. using the definition of $[x]$ ? (Wondering)
 
Last edited by a moderator:
Physics news on Phys.org
Well, how obvious to you consider each of your claims?

It might be useful to specify that [1]= [3]= [4]= {1, 3, 4}, that [2]= [8]= {2, 8}, that [7]= {7}, and that [5]= [6]= [9]= [10]= {5, 6, 9, 10}.

 
More generally, for all sets $A$ and $B$ and functions $f:A\to B$ the relation $x\sim y\iff f(x)=f(y)$ is an equivalence relation on $A$.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

Replies
1
Views
2K
Replies
5
Views
535
Replies
3
Views
1K
Replies
9
Views
2K
Replies
2
Views
1K
Replies
1
Views
2K
Replies
2
Views
2K
Back
Top