# Find a non-convex instance for a non-convex set function with FindInstance

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:

Powerset=Subsets[L];
FindInstance[f[x]+f[y]>f[Union[x,y]]+f[Intersection[x,y]],Powerset]


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?

• 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. – flinty Oct 30 '20 at 14:43
• @flinty Thank you very much for your explanations and solutions. – hxiao Oct 31 '20 at 8:06

## 1 Answer

findit[L_, f_] :=
(* select pairs of subsets in the powerset Subsets[L] that satisfy the criterion *)
ResourceFunction["SelectSubsets"][
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 *)