1
$\begingroup$

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?

$\endgroup$
2
  • 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 '20 at 14:43
  • $\begingroup$ @flinty Thank you very much for your explanations and solutions. $\endgroup$ – hxiao Oct 31 '20 at 8:06
1
$\begingroup$
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 *)
$\endgroup$

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.