requirement on proposition

Question

I want to draw a conclusion from an equivalent description of a relation.

Let $R$ be a relation on a set $M$ with $R \subseteq M \times M$.

First I have 2 examples of what I mean:

1. $x \sim_R y \Longleftrightarrow 1 = 1$, which obviously means $R = M \times M$

2. Let $M = \mathbb{N}$ and $F(x) = 1$ for all even $x \in \mathbb{N}$ and $0$ else.

   $x \sim_R y \Longleftrightarrow F(x) = F(y)$

   In this case it's easy to see, that $\sim_R$ is an equivalence relation, hence we were able to show the equivalence of $\sim_R$ to an equality.

But actually I want to be more abstract. I want to examine cases of the following:

$R$ is still a relation on a set $M$ with $R \subseteq M \times M$. It holds that:

$x \sim_R y \Longleftrightarrow F(x) = F(y)$ where $F(x), F(y)$ are 'missing word'.

What can $F(x), F(y)$ be? Sure, they are propositions, but they can't be any proposition, since you have to be able to compare $F(x)$ and $F(y)$ in terms of equality. How do I describe this circumstance mathematically correct?

Answer 1

It seems you're wondering about two different though related things, and are coming close to confusing them:

1. How general a definition can one give for a function $F$?, and
2. Given any function, can one define an equivalence relation on the domain of $F$ by $$x \sim_F y \iff F(x) = F(y)\ ?$$

The answer to 2. is, absolutely yes. Regarding 1., however, I'm not sure what you mean, and your example about '$F(x)$ and $F(y)$ are "missing word"' is a bit confusing. This $F$ is supposed to have string values, in the alphabet $\{a,b,c,...,z\}$? What's its domain (what are $x,y$)?

Answer 2

I think I was able to solve my problem. It was wrong to try anything with 'propositions'. I needed functions. I was able to prepare two lemmata.

Lemma 1: Be $Z$ a set and be $\sim_R$ an equivalence relation on a set $M$. Be $f$ a function with $f\colon\, M\to Z$ and $g$ a function with $g\colon\, M\to M$, with: \begin{align} &\forall x,y \in M: f(x) = f(y) \implies g(x) = g(y)\\ &\forall x \in M: x \sim_R g(x) \end{align} Now it follows: $$\forall x,y \in M: f(x) = f(y) \implies x \sim_R y$$

Lemma 2: Be $Z$ a set and be $\sim_R$ a relation on a set $M$. Be also $f$ a (surjective) function with $f\colon\, M\to Z$. Also be $X \subseteq M$, with $f|_X$ bijective, with: \begin{align}\forall x,y \in M: x \sim_R y \Longleftrightarrow f(x) = f(y)\end{align} (This is enough to prove that $\sim_R$ is an equivalence relation.) Now it follows: $$M/{\sim_R} = \{[a]_{\sim_R} \mid a \in X\} $$ It also holds: $$\forall x,y \in X: x \sim_R y \implies x = y$$