After posting my puzzles, I realized that I was also assuming that A and B were totally ordered in my own solution. I haven't yet thought about the existence of a solution in the more general case of posets.

I think Reuben's solutions can be generalized to posets by replacing min and max with meet and join respectively, using his same reasoning.