1

This question is from pg 171 of this book. http://users.metu.edu.tr/serge/courses/111-2011/textbook-math111.pdf

For any sets A, B, C, and D, if A × B ⊆ C × D then A ⊆ C and B ⊆ D. Is the following proof correct? If so, what proof strategies does it use? If not, can it be fixed? Is the theorem correct?

Proof. Suppose A × B ⊆ C × D. Let a be an arbitrary element of A and let b be an arbitrary element of B. Then (a, b) ∈ A × B, so since A × B ⊆ C × D, (a, b) ∈ C × D. Therefore a ∈ C and b ∈ D. Since a and b were arbitrary elements of A and B, respectively, this shows that A ⊆ C and B ⊆ D.

I know A or B being empty screws up the theorem but I need someone to explain to me the flaw in the proof.

I also noticed in the same book this statement: "Because p ∈ A × (B ∩ C) means ∃x∃y(x ∈ A ∧ y ∈ B ∩ C ∧ p = (x, y))" I'm also a bit confused why the existential quantifiers were introduced when p is suppose to be arbitrary. When we suppose (a, b) ∈ A × B are we then assuming that there exists a∈A and b∈B? On top of letting a and b are arbitrary?

I feel there is something different going on with supposing arbitrary elements in cartesian products compared to just plain sets. I need someone to clarify what is going on.

helios123
  • 63

3 Answers3

2

Let $a$ be an arbitrary element of $A$ and let $b$ be an arbitrary element of $B$.

If one of the sets is empty, you can't do that.

In particular, if for example $A$ is empty but $B$ is not, then you will never reach the conclusion $b\in D$.

hmakholm left over Monica
  • 286,031
  • When we say that the ordered pair (a,b) is an arbitrary element of AxB are we then always assuming that A and B are non empty? Then for any proof we do we have to check the case where either A or B is empty? This is precisely what is confusing me about this issue. – helios123 Apr 14 '17 at 09:33
  • @helios123: Not exactly -- but if $A\times B$ is empty then "all elements of $A\times B$" does not necessarily lead you to consider "all elements of $A$" and "all elements of $B$". – hmakholm left over Monica Apr 14 '17 at 09:38
  • In other words, you need to prove "for every $b\in B$ we have $b\in D$", but this proof only proves "for every $b\in B$ and $a\in A$ we have $b\in D$", which is weaker in this case because once you have chosen a $b$ there may not be an $a\in A$ to complete the rest of the argument with. – hmakholm left over Monica Apr 14 '17 at 09:40
  • Is your approach actually different from DHMO above? He identifies the error being in the implication rather than letting a and b being arbitrary elements. Can you also give you response to this question: https://math.stackexchange.com/questions/2233383/spot-error-in-proof-axb-bxa-only-if-a-b – helios123 Apr 14 '17 at 10:44
  • @helios123: No, we're saying the same thing. The error is in the combination of starting with "let $a\in A$ and $b\in B$ and concluding "therefore $B\subseteq D$". Formally the problem is that the assumption $a\in A$ did never get properly discharged on the way to $B\subseteq D$ -- and discussing exactly which step to point to for saying "there's a step missing here" is not much enlightening. I'm pointing to where you make the assumption that doesn't get dischaged; DHMO is pointing to where you conclude the proof without discharging it -- both really refer to the same failing. – hmakholm left over Monica Apr 14 '17 at 11:08
2

No, we are not assuming that $\exists a \in A$ or $\exists b \in B$.

Contrary to what Henning Makholm said in another answer, you can still let $a$ be an arbitrary element of $A$ even if $A$ is empty, just that you would be doing vacuous truths.

"Let $a$ be arbitrary" means no more than "$\forall a:$".

In fact, what the "proof" proved is: $$\forall a,b[(a \in A \land b \in B) \implies (a \in C \land b \in D)]$$

And then tried to extrapolate it into: $$(\forall a[a \in A \implies a \in C]) \land (\forall b[b \in B \implies b \in D])$$

This is the real incorrect step.

(Note: the definition of $A \subseteq C$ is $\forall a[a \in A \implies a \in C]$.)

DHMO
  • 3,014
  • 12
  • 20
  • How about AxB=BxA only if A=B? This is false unless we exclude A or (exclusive) B are empty. If we suppose (a,b) is in AxB iff BxA then we might come to the conclusion that A=B. What would be the error here? – helios123 Apr 14 '17 at 04:29
  • @helios123 Ask a new question in a new question. – DHMO Apr 14 '17 at 04:30
  • ok done. https://math.stackexchange.com/questions/2233383/spot-error-in-proof-axb-bxa-only-if-a-b – helios123 Apr 14 '17 at 04:36
0

I think the easiest way to see why $A$ empty "screws up the theorem" is to start from the fact that if $A$ is empty then $A \times B$ is empty, whatever $B$ is. Then you won't be able to show that $B$ is a subset of $D$. So, for a simple example $$ \phi\times \mathbb{R} = \phi \subset \{1\} \times \{1\} $$ but $\mathbb{R}$ is not a subset of $\{1\} $.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199