Splitting set into subsets by criterion
I believe there are two interpretations of your criterion.  One interpretation is easily solvable, and the other is NP-Complete.

First, a greedy algorithm for what you describe:
Let $A_1$, $A_2$, ..., $A_N$ all start as the empty set.
Loop through each $a_i \in A$.
Put $a_i$ in the first $A_k$ such that for each $a_j$ already in $A_k$,
$crit(a_i, a_j) = false$.
After looping through all the elements of $A$, disregard any $A_i$ which is still empty.

This greedy algorithm holds in the three examples you give.

A second interpretation is: "Let the set $A_i$ be as large as possible but not including any elements from $A_1$ to $A_{i-1}$".  Let $A&#39;$ be an $N \times N$ matrix where $A_{i, j}&#39;$ is 1 if $crit(a_i, a_j) = false$ and 0 otherwise.  Then finding $A_1$ is exactly finding the maximum clique of a digraph with adjacency matrix $A&#39;$.  This, of course, makes the problem NP-Hard.

Let's hope you only need the first.