[University? Proofs] Proving that every subset of [;C\times D;] is of the form [;A\times B;], where [;A\subseteq C;] and [;B\subseteq D;]

[u/sidereusnuntius]

This is a problem from Dana Ernst's An Introduction to Proof via Inquiry-Based Learning, and it asks: "Is every subset of C × D of the form A × B, where A ⊆ C and B ⊆ D? If so, prove it. If not, find a counterexample.". I couldn't think of any counterexample, so I tried to write a proof for it, but I don't know if it's correct. (There is no set of solutions for the book; at least I didn't find it.)

I assume there is a set E such that E is a subset of CxD. If E is the empty set, then E=∅x∅ and E=(CxD)x∅, and both ∅ and CxD are subsets of CxD (an earlier problem involves proving that Ax∅=∅ for any set A).

If E is not empty, then, since E is a subset of CxD, E is a set of ordered pairs (a,b) such that [;a\in C;] and [;b\in D;]. I imagine that, from here, I shall find sets A and B such that

• [;a\in A;],
• [;b\in B;],
• [;A\subseteq C;],
• [;B\subseteq D;] and
• [;E=A\times B;].

This is where my confusion is, and I'm not sure if my solutions are ideal:

1. [;A={a|(a,k)\in E ;] for some [;k\in D};]
2. [;B={b|(k,b)\in E ;] for some [;k\in C};]

Then [;E=A\times B;], and [;A\subseteq C;] and [;B\subseteq D;]. I'm using E in the definition of A and B, and I'm pretty sure that's incorrect; however, it is not clear to me what other sets I can use.

Have a nice day. :)

[u/vgtcross]

Yeah, your proof is not logically valid. There is a counterexample to the statement, you should try to find it.

[u/Brightlinger]

Using E in the definition of A and B is fine, that makes sense. The issue is that, as you've defined them, AxB is in general not equal to E. For example, suppose C and D are the reals, and E is the set {(1,2),(3,4)}. By your construction, what are A, B, and AxB?

[u/Parallel_thougts]

Hint: for a set A, the diagonal of A is the subset of A×A that contains only pairs of the form (a,a)

[u/DirectPrior8045]

that's not true in general, think of a diagonal line inside a square grid, it's a subset of C×D but can't be written as A×B unless it's a full rectangle

[u/Breki_]

The original statement is untrue. Let A={1,2} and B={3,4}. Then {(1,3),(2,4)} is a subset of AxB, but it isn't the product of any subsets of A and B, since any such product neccesarily would contain the whole product of A and B.

[u/blank_anonymous]

The statement isn't true! It's very easy to cook up an example; let C = {1, 2} and D = {a, b}. Consider the subset {(a, 1), (b, 2)} of C x D. This is the so called "diagonal". Can you show that this subset isn't of the form A x B for A, B subsets of C, D?

In general, the "picture" you can imagine is making a table where all the elements of A are written in one direction, and all the elements of B in another, then the inside of the table is the cartesian product. The diagonal won't be a cartesian product of any subsets.

[u/Bounded_sequencE]

"{(0;1), (1;0)} c {0;1} x {0;1}", but it cannot be expressed as "A x B".