Q about Lisp union

As I thought I understood it, Lisp union implements set union. So, I thought that

  (union '(a a) '(a b))

would return

  (a b)

And, in fact, it does. This led me to think that

  (union '(a a) '(b))

would also return

  (A B)

However, it returns:

  (A A B)

Why does the fact that there is one less 'a in the second argument in the second call mean that there is one more 'a in the result? This is definitely not set-theoretic union. Why is the behavior of Lisp union defined this way?

Here is the sequence of calls again:

  [1]> (union '(a a) '(a b))
  (A B)
  [2]> (union '(a a) '(b))
  (A A B)