How to prove these three properties about sets?

49 Views Asked by At

So, here is the exercise. enter image description here

Here are my thoughts.

enter image description here

I don't like my proof of a) because it doesn't seem formal enough. As for b), isn't what I wrote a counterexample? If not, how can one prove these three statements rigorously?

I will rewrite the question to make it searchable.

a) $(X\times Y = \emptyset) \iff (X=\emptyset) \lor (Y=\emptyset)$,

b) $X\times Y \neq \emptyset$, then $(A\times B\subset X\times Y)\iff (A\subset X)\land (B\subset Y)$.

I am mainly interested in a) and b).

1

There are 1 best solutions below

1
On BEST ANSWER

You are correct about (b), it is likely a typo and they meant A × B ≠ ∅, instead. ( try proving (b) under the assumption that A × B ≠ ∅)

As for (a) your proof if fine, it relies on the fact that (p ⟺q) ⟺ ($\neg$p ⟺ $\neg$q) but I will write out a more standard proof with the details filled in.

Claim: (×=∅)⟺(=∅) ∨ (=∅)

Proof:

First we show that (×=∅) $\rightarrow$ (=∅) ∨ (=∅)

Assume × = ∅

× = { (x,y): x$\in$X and y$\in$Y } = ∅

We continue by a proof by contradiction, Assume (x $\neq$ ∅) $\wedge$ (y $\neq$ ∅)

Then $\exists$x$(x\in$X) and $\exists$y$(y\in$Y)

Instantiate $x_0$,$y_0$ such that $x_0$$\in$X and $y_0$$\in$Y

Thus, by definition ($x_0$,$y_0$,)$\in$×

But this is an absurdity as × is empty by assumption. We have produced our desired contradiction.

And so our assumption that (x $\neq$ ∅) $\wedge$ (y $\neq$ ∅) must be false.

And so it's negation is true, we conclude that (=∅) ∨ (=∅)

It remains to be shown that (=∅) ∨ (=∅) $\rightarrow$ ×=∅

I'll leave this for you to show.

Hint: Consider two cases, and try proving the conclusion under each case.

Case 1: =∅ and Case 2: =∅