Collaborative filtering aims to make use of users' feedbacks to improve the recommendation performance, which has been deployed in various industry recommender systems. Some recent works have switched from exploiting explicit feedbacks of numerical ratings to implicit feedbacks like browsing and shopping records, since such data are more abundant and easier to collect. One fundamental challenge of leveraging implicit feedbacks is the lack of negative feedbacks, because there are only some observed relatively "positive" feedbacks, making it difficult to learn a prediction model. Previous works address this challenge via proposing some pointwise or pairwise preference assumptions on items. However, such assumptions with respect to items may not always hold, for example, a user may dislike a bought item or like an item not bought yet. In this paper, we propose a new and relaxed assumption of pairwise preferences over item-sets, which defines a user's preference on a set of items (item-set) instead of on a single item. The relaxed assumption can give us more accurate pairwise preference relationships. With this assumption, we further develop a general algorithm called CoFiSet (collaborative filtering via learning pairwise preferences over item-sets). Experimental results show that CoFiSet performs better than several state-of-the-art methods on various ranking-oriented evaluation metrics on two real-world data sets. Furthermore, CoFiSet is very efficient as shown by both the time complexity and CPU time.