Re: Empty set is and is not a subset of empty set

[Andrew Makhorin]

Thank you for your bug report.



On Thu, 2025-03-13 at 18:45 +0000, Piotr Kocia wrote:
> Hello,
> 
> I have been writing a model that evaluates an expression when a
> relevant arithmetic set is not a subset of another arithmetic set. I
> was getting incorrect results, so I spent some time narrowing down the
> issue and eventually I arrived at the following snippet:
> 
> ---
> display 1..2 inter 3..4;
> display (100..120 inter 130..150);
> display (100..120 inter 130..150) within (1..2 inter 3..4);
> display (100..120 inter 130..150) not within (1..2 inter 3..4);
> ---
> 
> The output of the above with GLPK 5.0 is:
> 
> ---
> Display statement at line 108
> set is empty
> Display statement at line 109
> set is empty
> Display statement at line 110
> true
> Display statement at line 111
> true
> ---
> 
> The empty set is indeed a subset of itself, but can it also be not a
> subset of itself at the same time? I suppose it depends on the
> definition of the subset operation, but the most common one I have
> come across is 'A is a subset of B if every element in A is in B'. The
> negation of this would be 'A is not a subset of B if there exists an
> element in A that is not in B'. There are no such elements in the
> empty set, which implies that '{} not within {}' should be false.

You are perfectly correct: '{} not within {}' should be false, because
empty set is a subset of any set including empty set itself.

The bug is seen from the following fragment (file glpk/src/mpl/mpl3.c,
lines 4225-4255):

         case O_WITHIN:
            /* test on 'X within Y' */
            {  ELEMSET *set;
               MEMBER *memb;
               set = eval_elemset(mpl, code->arg.arg.x);
               value = 1;
               for (memb = set->head; memb != NULL; memb = memb->next)
               {  if (!is_member(mpl, code->arg.arg.y, memb->tuple))
                  {  value = 0;
                     break;
                  }
               }
               delete_elemset(mpl, set);
            }
            break;
         case O_NOTWITHIN:
            /* test on 'X not within Y' */
            {  ELEMSET *set;
               MEMBER *memb;
               set = eval_elemset(mpl, code->arg.arg.x);
               value = 1;
               for (memb = set->head; memb != NULL; memb = memb->next)
               {  if (is_member(mpl, code->arg.arg.y, memb->tuple))
                  {  value = 0;
                     break;
                  }
               }
               delete_elemset(mpl, set);
            }
            break;

The operation X not within Y returns false (value = 0) if there exists
an element e in X such that e in Y, otherwise true (value = 1).  This
evaluation is completely wrong; I think this bug hasn't been reported,
because 'not within' is practically not used in practice.

The obvious way to fix the bug is to evaluate 'not within' as negation
of 'within':

         case O_WITHIN:
         case O_NOTWITHIN:
            ...
            if (code->op == O_NOTWITHIN)
               value = ! value;
            ...

Hope this will be fixed in a next relase of the package.


Andrew Makhorin


> 
> Best regards
> Piotr Kocia
>