This is from Algebraic Graph theory, by Godsil.

Let $r$ be a function on the subsets of a finite set $\Omega$ and define

$r^*(A)=|A| +r(\Omega \setminus A) - r(\Omega)$

It follows that if $r(\emptyset)=0$ then $(r^*)^*=r$.

I don't see how this follows. $r$ is a function from the subsets of $\Omega$ to nonnegative integers. If I apply $^*$ to a subset of $\Omega$ I get a positive integer and I don't see how I can apply $^*$ to that.

I don't think I understand correctly how the dual function is defined.


When you apply $*$ you don't get an integer, you can a new function which happens to be a function plus an integer.

Let $$f(A)=r^*(A)=\vert A\vert + r(\Omega\setminus A) - r(\Omega)$$

Then $(r^*)^*(A)=f^*(A)$ so that

\begin{align*} (r^*)^*(A)&=\vert A\vert + f(\Omega\setminus A) - f(\Omega)\\ &=\vert A\vert + \vert \Omega\setminus A\vert + r(A) - r(\Omega) - \vert \Omega\vert - r(\emptyset) + r(\Omega)\\ &= r(A)-r(\emptyset) \end{align*} So that if $r(\emptyset)=0$, then $(r^*)^*=r$

  • 1
    $\begingroup$ Thanks. I failed to realize that integers are not in the domain of $^*$ and so they get “ignored” by $^*$. $\endgroup$ – ak87 Mar 20 at 16:29

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.