Here’s my take on it. A bit more complicated than I’d want to but it appears to work for all cases.
I initially arrived at the same formula as @Ander, but as you @mr_motus observed it breaks for more than 1 category. This is because Contains is inherently an OR function.
The solution for this needs to make use of two nested FormulaMaps, but the problem is we only have access to the innermost CurrentValue.
So to be able to access both values we need to use columns across both tables.
So in the doc below, first Pre filter finds all items for each selected category. This will give duplicates.
Then Recipe Cat Count counts the occurrence of each Food item item in each recipe.
Effectively, a Food item will be filtered for all categories if and only if it appears in Pre filter a number of times equals to the number of selected categories. That is basically what Filtered Food does.