Instead of passing a single multi-dimensional array, pass a set of 1-dimensional arrays - or really any dimensions, as dimensions are just noise in this case. This works:
SELECT ARRAY[1,3] && ALL ((SELECT ARRAY[1] UNION ALL SELECT ARRAY[2]));  -- false
Which is more useful when applied to a table column:
SELECT ARRAY[1,3] && ALL ((SELECT array_column FROM some_tbl));
The ALL or ANY constructs either expect a set or an array to the right. Your example only works with a set. I can see how one might conclude to pass a multi-dimensional array (an array of arrays). Unfortunately, that's not how it works. The manual:
The left-hand expression is evaluated and compared to each element of the array [...],
Bold emphasis mine. Element. Not sub-array or array-slice. So the attempt:
SELECT ARRAY[1,3] && ALL (ARRAY[ARRAY[1], ARRAY[2]]);  -- error
-- identical, more explicit:
SELECT '{1,3}'::int[] && ALL ('{{1},{2}}'::int[]);  -- error
... results in this error message accordingly:
ERROR:  operator does not exist: integer[] && integer
You tried something in between:
SELECT ARRAY[1,3] && ALL(SELECT ARRAY[ARRAY[1], ARRAY[2]]);  -- true
-- identical, more explicit:
SELECT '{1,3}'::int[] && ALL (SELECT '{{1},{2}}'::int[]);  -- true
Effectively a set containing single multi-dimensional array. It boils down to:
SELECT '{1,3}'::int[] && '{{1},{2}}'::int[];  -- true
... which yields true like you observed because, again, "overlap" is tested on the level of elements, ignoring dimensions. Effectively the same as:
SELECT '{1,3}'::int[] && '{1,2}'::int[];  -- true
Or, to prove my point:
SELECT '{{{1}},{{3}}}'::int[] && '{{1},{2}}'::int[];  -- true
Related: