3
$\begingroup$

Many of the 16 binary set operations (corresponding to the 16 logical connectives) don’t seem to have common dedicated symbols. Instead, they are often simply expressed in terms of $\cup, \cap, \setminus$, etc.

My question is whether there is any known precedent of a symbol for the operation $A \cup B^\complement$. This would complete the following (where ? is a placeholder for the operation in question):

  • $A \setminus B = A \cap B^\complement$
  • $A \operatorname{?} B = A \cup B^\complement$

For more context (based on discussion in the comments below):

In everyday work, of course it makes sense to use just a few symbols (e.g. complement, $\cup, \cap, \setminus$) and express other operations in terms of these. This approach represents a practical tradeoff between two extremes:

  1. At one extreme, only one symbol is needed (just NAND or NOR, cf. functional completeness). The drawback is that most expressions will be quite large when written this way.
  2. At the other extreme, we would have a unique symbol for each of the 16 operations. Expressions may be written more compactly with these symbols, but then there is more to memorize.

(Why are the complement, $\cup, \cap, \setminus$ operations in particular given special status? My only guess is that they correspond with concepts in spoken language: NOT, OR, AND, WITHOUT, which, in turn, may correspond to which operations are most naturally computed by our brains, but I digress...)

A comment below suggests simply using $(B \setminus A)^\complement$ to represent $A \cup B^\complement$, but the same could be said of any operation, e.g. why do we need a symbol for set difference $A \setminus B$ when we can just write $A \cap B^\complement$? Or why do we need a special logical connective for implication (which actually corresponds to the set operation in question here)?

My point is that sometimes things can be written more concisely with dedicated symbols for the uncommon cases. It may be rare that these symbols are needed, but in those instances where one of the uncommon set operations is heavily utilized ($A \cup B^\complement$ in my case here), it would be nice to have some agreed-upon symbol. And here I simply want to know if there is any precedent in the literature for those weird cases.

The diagram below (originally found on Wikipedia here or here) shows that all 16 logical connectives have dedicated symbols. Why not extend this luxury to the corresponding set operations?

logical connectives diagram

$\endgroup$
13
  • 4
    $\begingroup$ $(B\setminus A)^c$ isn't satisfactory enough? $\endgroup$
    – JMoravitz
    Commented Feb 18, 2021 at 3:02
  • 9
    $\begingroup$ This diagram is pretty sweet. $\endgroup$ Commented Feb 18, 2021 at 3:18
  • 2
    $\begingroup$ This is an interesting question (to which I do not have an answer) but I think I might align with @JMoravitz in that I don't want to remember 16 symbols. I'd rather have fewer symbols perhaps at the cost of one or two basic set operations. There are tradeoffs here. If nobody has heard of the ? notation, for example, although they know the concept, it's not helping. $\endgroup$ Commented Feb 18, 2021 at 15:24
  • 1
    $\begingroup$ @TylerStreeter I kind of like the idea of just using the logical implication symbol, although I realize there might be visual static with the way a function from $A$ to $B$ is commonly written as a map $A \to B$. $\endgroup$ Commented Feb 18, 2021 at 15:49
  • 1
    $\begingroup$ I agree with @leslietownes. If I were assigned the task of simplifying $(A^c \cap (B \uparrow A) \vee (A \cup B^c \leftarrow A))\cup (A \oplus B^c \downarrow (A \wedge B))^c$ i would definitely write everything in terms of union, intersection and complement and use the few laws I know for these few symbols, instead of trying to memorize a lot of relations between all the other symbols. Which of those are associative? commutative? which distribute over which? which has an absorption law? what was the neutral element for this one? etc. $\endgroup$
    – jjagmath
    Commented Feb 18, 2021 at 15:49

2 Answers 2

3
$\begingroup$

In lattice theory, this is nothing but the Heyting arrow in the lattice $\mathcal P(S)$ of subsets of a set $S$:

$$(A\succ B) = A^c\cup B.$$

More generally, if $L$ is a meet-semilattice (meaning a partially ordered set with finite infima $\wedge$), and $a,b\in L$ are any two elements of $L$. An implication from $a$ to $b$ is an element $(a\succ b)\in L$ such that $$ (x\wedge a) \leq b \hspace{5mm} \text{if and only if} \hspace{5mm} x\leq(a\succ b)$$ for every $x\in L$. If the implication from $a$ to $b$ exists, then it is unique.

A distributive lattice where every pair of elements has an implication is called a Heyting algebra.

The set $\mathcal P(S)$ of subsets of a set $S$ has an order structure given by inclusion ($\leq=\subseteq$). With this order, $\mathcal P(S)$ is a meet-semilattice, since infima are given by intersection ($\wedge=\cap$). Moreover, $\mathcal P(S)$ is a Heyting algebra, and I claim that for every pair of subsets $A,B\subseteq S$, the implication $A\succ B$ is given by the formula $$(A\succ B) = A^c\cup B.$$

Proof: take any subset $X\in\cal P(S)$:

  • If $X\cap A\subseteq B$, then every $x\in X$ which is not in $B$ is in $A^c$. Hence $X\subseteq A^c\cup B$.

  • Conversely, if $X\subseteq A^c\cup B$, then $X\cap A \subseteq (A^c\cup B)\cap A=B\cap A\subseteq B$.

EDIT: You can find the Heyting arrow denoted by $A\succ B$ in the works of Harold Simmons. Books like that of Picado and Pultr use $A\to B$, while some sources also use $A\Rightarrow B$ or $A\multimap B$. At some point, Birkhoff's (in his book on lattice theory) uses the symbol $(A:B)$ to denote what he calls the "relative complement of $A$ in $B$", which coincides with what I write as $B\succ A$ (notice the change of order).

Another common Heyting algebra is a topology: i.e. the family of open subsets of a topological space. In this case you have $A\succ B = \text{Int}(A^c\cup B)$.

The intention of this last paragraph is to remind you that $A\succ B=A^c\cup B$ only in the context of the power set $\mathcal P(S)$ of a set $S$ (or, more generally, in the context of a Boolean algebra). If you are working with a different lattice, then the implication may be given by something different, as in the case $A\succ B = \text{Int}(A^c\cup B)$ of the family of open subsets of a topological space.

Then my answer to your last comment is no, $B\succ A$ is not commonly used to denote the set operation $B^c\cup A$, because there may be contexts where the set $B^c\cup A$ has no special importance.

$\endgroup$
4
  • $\begingroup$ Thanks, this helps show the general importance of this particular operation in a wider context. I’m mainly interested in the notation aspect... Can you say whether the $\succ$ symbol is commonly used to represent the set operation $A \cup B^\complement$? $\endgroup$ Commented Feb 21, 2021 at 0:06
  • $\begingroup$ @TylerStreeter I edited my answer. In short: no, or at least, no in my experience. $\endgroup$ Commented Feb 21, 2021 at 8:27
  • $\begingroup$ Those references you added are helpful. Looks like no strong consensus on notation, but still nice to see the underlying notion discussed in different contexts. $\endgroup$ Commented Feb 21, 2021 at 18:55
  • $\begingroup$ ...and at least it looks like there is some precedent in terms of notation in the sources you mentioned, so I'm accepted this answer. $\endgroup$ Commented Feb 21, 2021 at 20:15
2
$\begingroup$

Update: This answer lists sources which use various symbols for this set operation. (No strong consensus, but at least there is some precedent in the literature.)


I have not been able to find any literature containing a symbol for $A \cup B^\complement$, so I'm tentatively saying the answer here is: no, there is no precedent for such a symbol.

Here are some ideas for possible symbols (some inspired by comments on the question above):

  • Some set operations are visually similar to their corresponding logical connectives ($\cup$ and $\vee$, $\cap$ and $\wedge$). Logical implication corresponds to the set operation in question here, so we could just use the arrow: $A \leftarrow B = A \cup B^\complement$.

  • We could use a more "rounded" version of an arrow to distinguish it from the implication connective, e.g. the "lollipop" symbol (used for linear implication in linear logic): $B \multimap A = A \cup B^\complement$. (That's \multimap in LaTeX. \multimapinv is the opposite direction, but that appears not to work on stackexchange.)

  • We could just use a forward slash, mirroring the set difference backslash, so: $A \big{/} B = A \cup B^\complement$. This feels like the obvious solution when you look at the visual symmetries here ($\cup, \cap, \setminus, /$). My only hesitation is that having both forward and back slashes might be a bit hard to parse visually (in the same way that left/right are generally harder to learn and process than up/down).

  • As the operation in question here is just the complement of the set difference operation, maybe just add an overbar to the set difference symbol: $B \overline{\setminus} A = (B \setminus A)^\complement = A \cup B^\complement$. (This might not look great in LaTeX without a lot of tweaking. Alternatively, imagine a single symbol, like a number 7 mirrored left-to-right; but then one big drawback is that this is not a standard symbol in LaTeX or Unicode.)

$\endgroup$
4
  • 1
    $\begingroup$ It might be worthwhile to note that $B \multimap A$ appears naturally in the description of the power set of a universe set $U$ as a Heyting algebra. i.e. $B\multimap A$ is the maximum set such that $(B\multimap A) \cap B \subseteq A$, i.e. for any set $C$, $C \subseteq (B \multimap A)$ if and only if $C\cap B \subseteq A$. $\endgroup$ Commented Feb 19, 2021 at 21:07
  • 1
    $\begingroup$ And that characterization, in turn, can naturally lead to identities involving this $\multimap$ definition such as: $A \multimap (B \cap C) = (A \multimap B) \cap (A \multimap C)$; $(A \cup B) \multimap C = (A \multimap C) \cap (B \multimap C)$; and $A \multimap (B \multimap C) = (A \cap B) \multimap C$. Granted, those are also easy to prove directly from the definition. $\endgroup$ Commented Feb 19, 2021 at 21:10
  • 1
    $\begingroup$ @DanielSchepler Thanks for this extra info. I'm assuming that your $B \multimap A$ here means $A \cup B^\complement$ (i.e. the non-standard notation suggested above). Is that correct, or is there some other mean I'm not aware of (e.g. does $\multimap$ mean something specific in Heyting algebras?)? $\endgroup$ Commented Feb 20, 2021 at 17:05
  • $\begingroup$ I'd say the answer by Jackozee Hakkiuz pretty well summarizes the more general situation. $\endgroup$ Commented Feb 20, 2021 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .