Search code examples
discrete-mathematics

Necessary and Sufficient conditions on sets

I'm having difficulty solving this problem -

State and prove a necessary and sufficient condition on sets A and B such that A×B=B×A (cartesian product). While it is sufficient that A=B, it is not necessary.

My understanding of necessary conditions is that A does not guarantee B while in a sufficient condition A does guarantee B, but I'm unsure how it applies to this question or what the last sentence is saying. I'm also unsure how to approach this type of proof in general.

Solution

  • Your confusion comes from the fact that you use A and B for sets and statements.

    Let's use A and B for sets and S and N for statements.

    Statements

    A good explanation for necessity and sufficiency is here. Those are all equivalent :

    • S is sufficient condition for N
    • S implies N
    • if S then N
    • N is implied by S
    • S only if N
    • N is a necessary condition for S

    "A necessary and sufficient condition" is an "equivalent condition". See Simultaneous necessity and sufficiency.

    For the original question, what's asked is to find a mathematical statement that is true if, and only if A×B=B×A.

    Sets

    As for your original question, you're looking at the conditions for commutativity of the cartesian product.

    • if A=B then A×B=B×A
    • if A or B is empty then A×B=B×A
    • there are no other cases for which A×B=B×A

    So A×B=B×A if and only if ( A=B, A is empty or B is empty ).