Let $f$ be a non-convex set function defined on a set $L$. Hence there are subsets $A,B\subseteq L$ such that $$f(A)+f(B)>f(A\cup B)+f(A\cap B).$$

I tried to use FindInstance function to find a non-convex instance of $x$ and $y$ as follows:


But I have the following errors:

Union::normal: Nonatomic expression expected at position 1 in x\[Union]y.
Intersection::normal: Nonatomic expression expected at position 1 in x\[Intersection]y.
FindInstance::ivar: {} is not a valid variable.

Does FindInstance work with set functions? How should I modify my code?

  • 2
    $\begingroup$ Does FindInstance work with set functions? No it doesn't. You could express your sets as fixed length binary vectors, then the union corresponds to a BitOr and the intersection corresponds to a BitAnd. You should provide the f you're using and an example set as this will help get an answer. $\endgroup$
    – flinty
    Oct 30, 2020 at 14:43
  • $\begingroup$ @flinty Thank you very much for your explanations and solutions. $\endgroup$
    – hxiao
    Oct 31, 2020 at 8:06

1 Answer 1

findit[L_, f_] :=
 (* select pairs of subsets in the powerset Subsets[L] that satisfy the criterion *)
  Subsets[L], {2}, 
  Total[f /@ #] > f[Union @@ #] + f[Intersection @@ #] &
findit[{1, 2, 3}, Median]
(* result: {{{1,2},{1,3}}} *)

(* check it works *)
Median[{1, 2}] + Median[{1, 3}] > 
 Median[Union[{1, 2}, {1, 3}]] + Median[Intersection[{1, 2}, {1, 3}]]
(* result: True *)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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