Can I define a predicate over a set and use it in the definition of another one?

Question

Let's say I have two sets $A$ and $B$, and a relation $R \subseteq A \times B$. $R' \subset R$.

Can I define a predicate $P(R) = \forall a \in A, \exists b \in B, (a,b) \not\in R$

And then define another set $X = \{ (a,b) | (a,b) \in R, P(R')\}$ ?

If yes, did I miss anything in the notation? If no, how can I achieve what I want to define? In fact, the predicate $P$ is just a global constraint that should be satisfied.

Answer 1

The "set-forming" symbol $X = \{ x \mid \varphi(x) \}$ is used to define a set using a formula $\varphi(x)$ with a free variable $x$.

The formula expresses a "condition" that must hold or not for the objects in the domain : the condition $\varphi(x)$ will "select" those $a$ such that $\varphi(a)$ holds, and they will be "put" in $X$, from those $a$ such that $\varphi(a)$ does not hold, and they will be "left out" from $X$.

Of course, the formula expressing the condition can have other variables (used as "parameters").

In your example, the formula $P(R′):= ∀a∃b(a,b) \notin R′$ has no free variables, except for the "parameter" $R′$; thus, for a specified $R'$, the formula is either true or false.

This implies that the set $X = \{ (a,b) \mid (a,b) \in R \ \text {and} \ P(R') \}$ can be the emptyset or simply $X= \{ (a,b) \mid (a,b) \in R \}$.

Considering your example with $R' \subset R$, what we can do, for example, is :

$X = \{ x \mid \exists y [(x,y) \in R \ \text {and} \ (x,y) \notin R'] \}$.

Here the formula $\varphi$ is $\exists y [(x,y) \in R \ \text {and} \ (x,y) \notin R']$, i.e. we have : $\varphi(x,R,R')$.

---

If you need is to "separate" the "complement" of $R'$ in $R$, this will be :

$X = \{ x \mid x=(a,b) \land a \in A \land b \in B \land (a,b) \in R \land (a,b) \notin R' \}$

or, more simply :

$X = \{ x \mid x \in R \land x \notin R' \}$.