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).foo(3,4).
foo(4,3).
?- setof(X,foo(X,Y),Set).
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:
?- setof(firstbit(X),Y^foo(X,Y),Set).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.