Equivalence relation and equivalence classes

[Sauraj]

Hello, how to find formula that will express a equivalence relation which has at most three equivalence classes?
For example here is a graph with 3 eq. classes:

I wrote 3 required property's for equivalence relation with this formula:
\(\displaystyle
\displaystyle
\varphi \,\colon = ( \forall x E(x,x)) \land \\
( \forall x \forall y(E(x,y) \to E(y,x))) \land \\
( \forall x \forall y \forall z((E(x,y) \land E(y,z)) \to E(x,z))) \land \\
...
\)

But I dont know how the last part looks like. For example the last part should express that in every 4 random nodes 2 are equivalent, but how to express this with formula or is there some other solution?
Thx.

 

[Dr.Peterson]

Hello, how to find formula that will express a equivalence relation which has at most three equivalence classes?
For example here is a graph with 3 eq. classes:

I wrote 3 required property's for equivalence relation with this formula:
\(\displaystyle
\displaystyle
\varphi \,\colon = ( \forall x E(x,x)) \land \\
( \forall x \forall y(E(x,y) \to E(y,x))) \land \\
( \forall x \forall y \forall z((E(x,y) \land E(y,z)) \to E(x,z))) \land \\
...
\)

But I dont know how the last part looks like. For example the last part should express that in every 4 random nodes 2 are equivalent, but how to express this with formula or is there some other solution?
Thx.

You are trying to write in a single statement the definition of an equivalence relation; but I'm not sure how that relates to the assignment, which seems to be asking for an example of a specific equivalence relation.

Can you show us the entire exercise as given to you? I want to see what you are actually told to so. Also, it may be helpful if you can show examples of how they "express an equivalence relation"; there are several ways to do so, which do not necessarily require a formula.

 

[Sauraj]

You are trying to write in a single statement the definition of an equivalence relation; but I'm not sure how that relates to the assignment, which seems to be asking for an example of a specific equivalence relation.

Can you show us the entire exercise as given to you? I want to see what you are actually told to so. Also, it may be helpful if you can show examples of how they "express an equivalence relation"; there are several ways to do so, which do not necessarily require a formula.

Right, maybe the definition is really unnecessary for the formula.
The exercise is not in English. More detailed translation maybe:
\(\displaystyle E\) is a relation symbol with arity of 2.
Find formula \(\displaystyle \varphi \in FO[\sigma]\) of \(\displaystyle \sigma\)-structure \(\displaystyle \mathcal{A}\) with no free variables for the following expression:
\(\displaystyle E^ \mathcal{A}\) is a equivalence relation with at most 3 equivalence classes.
\(\displaystyle \mathcal{A} \vDash \varphi \Leftrightarrow\) expression holds for \(\displaystyle \mathcal{A}\)

In the logic lecture we expressed the equivalence relation with the formula like I wrote, so it is reflexive, symmetric and transitive.

 

[pka]

Hello, how to find formula that will express a equivalence relation which has at most three equivalence classes?
For example here is a graph with 3 eq. classes:

I think that your question is far more problematic that a simple translation.
It appears the logical vocabulary is amiss as well. I for one have never see such diagrams.
If we say that integers \(a\equiv b\) if and only if \(a~\&~b\) have the same reminder when divided by three,
then defines an equivalence relation with exactly three equivalence classes.
How does that relate to your understanding?

 

[Sauraj]

I think that your question is far more problematic that a simple translation.
It appears the logical vocabulary is amiss as well. I for one have never see such diagrams.
If we say that integers \(a\equiv b\) if and only if \(a~\&~b\) have the same reminder when divided by three,
then defines an equivalence relation with exactly three equivalence classes.
How does that relate to your understanding?

Sorry, I made this image just for me, to understand that this are 3 equivalence classes of equivalence relation. It does not refer to the task.
What u mean is i mod 3 with \(\displaystyle i \in \mathbb{N}\), and here I should find something similar. \(\displaystyle \varphi \in FO[\sigma]\) which describes a equivalence relation E^A with no more than 3 classes.

 

[Sauraj]

\(\displaystyle E^\mathcal{A}\) could be in a structure which describes a graph \(\displaystyle \mathcal{A} = \{V, E^ \mathcal{A} \} \) V are vertices and E are edges.

 

[pka]

Well you posted AT MOST THREE. Which it? I don't think you have a grasp on what you are trying to ask.

 

[Sauraj]

Well you posted AT MOST THREE. Which it? I don't think you have a grasp on what you are trying to ask.

If I correctly understood I can give u example for it.
If I have only one node with reflexive edge in a graph then it has a equivalence relation with one equivalence class, then I add second isolated node with reflexive edge and I will have 2 equivalence classes then same for third and now if I add 4 or more nodes to the graph I will still only have 3 equivalence classes. This should be described somehow with FO formula. So E(x,x) is for example reflexive edge.