I want to know how you can represent this dependency using the operations of

  • intersection
  • union
  • complement
  • cartesian product
  • symmetric difference
  • etc

$$X1 \: ??? \: X2 = Y$$

| X1 | X2 | Y |
| Ø  | A  | Ø |
| B  | A  | A |

A, B - nonempty sets

  • $\begingroup$ So this table should be, so to say, representative of the predicate of three variables $P(x_1,x_2,y)$ which is true if and only if either $x_1=\emptyset$ and $x_2\ne\emptyset$ and $y=\emptyset$, or $x_1\ne\emptyset$ and $x_2=y$? And you want to know if this can be represented as what, exactly? $\endgroup$
    – user239203
    Dec 1 '20 at 11:42
  • $\begingroup$ What do you want to happen if $A$ is empty (with $B$ empty or not)? $\endgroup$ Dec 1 '20 at 12:03
  • $\begingroup$ I'm a little confused by how you are defining this. I think you mean you want a function, $f(X_1, X_2)$, where $f(X_1, X_2)=\emptyset$ if $X_1=\emptyset$, $f(X_1,X_2)=X_2$ if neither are empty. Is this right? If so, as other have stated, what happens when $X_2$ is empty? $\endgroup$ Dec 1 '20 at 15:47

Using only unions, intersections and complements, this cannot be done.

Namely, each formula using only those operations can be converted to its "disjunctive normal form", which will be a disjunction of zero to four of the following terms $X_1\cap X_2$, $X_1\cap X_2^c$, $X_1^c\cap X_2$, $X_1^c\cap X_2^c$. On the universal set $\{0,1,2,3\}$ and the $2$-element sets $X_1=\{1,2\}, X_2=\{1,3\}$ you verify that the formula providing $Y=X_2$ as a result must be $(X_1\cap X_2)\cup(X_1^c\cap X_2)$, which is (by the way) equivalent to "$X_2$" standing alone.

But then this formula does not work for $X_1=\emptyset$ and nonempty $X_2$, as it will still return a nonempty set ($X_2$).

However, if "etc." means that we can use *Cartesian product" ($\times$) and "projection" ($\pi_1$ and $\pi_2$), then you can have the formula doing what you want, and it is going to be $Y=\pi_2(X_1\times X_2)$, i.e. $Y=\{y\in X_2\mid (\exists x\in X_1)((x,y)\in X_1\times X_2)\}$.

Update You removed "etc." and added that you allow for Cartesian product but not for projections. This makes it a different question. I will keep this answer and see if you will additionally allow for projections later on. Next time, please don't change the essence of your question once you've posted it.

  • $\begingroup$ The way I was reading it, there can be no class-function (let there be whatever you want) $F:\text{Set}\times\text{Set}\to\text{Set}$ such that $P(x_1,x_2,y)$ is true if and only if $y=F(x_1,x_2)$, because the quantification on $A$ and $B$ ("A, B - nonempty sets") doesn't define $Y$ for $x_1=x_2=\emptyset$. $\endgroup$
    – user239203
    Dec 1 '20 at 12:00
  • $\begingroup$ @Gae.S. I think the OP may have just forgotten to define what happens if both sets are empty, rather than assuming that the formula should be undefined in that situation. They have also not defined what happens if $B$ is nonempty and only $A$ is empty. However, they definitely seem to want a function of $X_1$ and $X_2$, not merely a relation between $X_1, X_2$ and $Y$, because their relation looks like "$\text{some formula}(X_1, X_2)=Y$", so $Y$ can always be picked to be equal to the calculation on the LHS. $\endgroup$ Dec 1 '20 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.