If you leave off the existential quantification the semantics of setof/3 becomes conditional on the status of Y at the time the predicate is called.
foo(2,3).In this case, Set is the set of all X for which there is a specific (but somewhat arbitrary) Y such that foo(X,Y).
Set = [2,4] [-5pt]
Note that the first argument is really a variable pattern which specifies which variables get put into the list of solutions and how they are to appear. For example:
Set = [firstbit(2),firstbit(3),firstbit(4)] [-5pt]
Note also that any repeated solutions are removed and all the solutions are placed in a standard ordering.