# What Does the Logical Equivalence Symbol Mean Between Two Sets?

I was reading the paper Computing Small Search Numbers in Linear Time by Bodlaender et. al. and I noticed a notation that I had never seen before. On page three it says:

$X$ is nice if $|X_1| = 1$ and $\forall_{2 \leq i \leq |X|} |(X_i \Leftrightarrow X_{i-1}) \cup (X_{i-1} \Leftrightarrow X_i)| = 1$

What does the logical equivalence symbol mean when it is used between sets? Does this indicate a bijection?

• A it before that the paper uses $\max_{1\le i\le |X|}\{|X_i|\Leftrightarrow 1\}$, which makes little sense as well (logical equivalebde of numbers? Maximum over singleton sets contaiing a truth value? – Hagen von Eitzen Jul 14 '17 at 18:17

## 1 Answer

Seeing the other uses of that symbol in that particular paper, it looks like something went wrong with the font in that paper. I guess many occurrences of $\iff$ should be $-$, and in your particular case it then means set-difference.

A compelling hint that this is the error, is the definition of linear width: in the abstract it uses a $-$, but in the body a $\iff$ at the same place.

• ... and so $(X_i\Leftrightarrow X_{i-1}\cup(X_{i-1}\Leftrightarrow X_{i})$ turns out to be the symmetric set difference $X_i\mathop\Delta X_{i-1}$ ... – Hagen von Eitzen Jul 14 '17 at 18:22
• This would make sense since pathwidth is $max\{|X_i|\} - 1$ by the traditional definitions. That also makes sense with niceness, as then the definition simply becomes a symmetric difference. – Jabbath Jul 14 '17 at 18:22