Thread: [SOLVED] Prove that only the empty set is a subset of the cartesian product of itself

1. [SOLVED] Prove that only the empty set is a subset of the cartesian product of itself

The exercise: Use the axiom of regularity to prove that if $a$ is a set such that $a\subseteq a\times a$, then $a=\emptyset$.

The axiom of regularity: Every nonempty set $a$ contains an element $b$ such that $a\cap b=\emptyset$.

Definition of cartesian product: $a\times b=\{w\in\mathcal{P}(\mathcal{P}(a)):$ $(\exists x)(\exists y)(x\neq y\wedge x\in a\wedge y\in b\wedge (z)(z\in w\leftrightarrow z=\{x\}\vee z=\{x,y\}))$ $\vee (\exists x)(x\in a \wedge x\in b \wedge (z)(z\in w\leftrightarrow z=\{x\}))\}$.

More simply, we say $a\times b=\{(x,y):x\in a\wedge y\in b\}$, where ordered pairs are defined as $(x,y)=\{\{x\},\{x,y\}\}$.

I believe this exercise is supposed to be easy, but I'm having a lot of trouble with it. Assistance would be much appreciated!

2. The proof I know is fairly straightforward but does take a bit of manipulation.

I'll lead you through it by asking you questions, if you like.

Use proof by contradiction.

So there is a c such that c in a
and
a subset of axa.

So what's the next obvious inference? And what can you draw out further from that inference?

3. Originally Posted by MoeBlee
The proof I know is fairly straightforward but does take a bit of manipulation.

I'll lead you through it by asking you questions, if you like.

Use proof by contradiction.

So there is a c such that c in a
and
a subset of axa.

So what's the next obvious inference? And what can you draw out further from that inference?
Well, if $c\in a\subseteq a\times a$, then $c=\{\{x\},\{x,y\}\}$ for some $x,y\in a$, not necessarily distinct. It follows that $\{x\}\in a$ implies $\{x,y\}\notin a$, and $\{x,y\}\in a$ implies $\{x\}\notin a$.

This was the first approach I attempted, and I do not know how to make it work. In particular, I do not know how to show that $\{x\}\in a$ or $\{x,y\}\in a$. I seem to be missing something (obvious?), and it's really frustrating.

Thanks for the clues!

4. It follows that $\{x\}\in a$ implies $\{x,y\}\notin a$, and $\{x,y\}\in a$ implies $\{x\}\notin a$.
I don't see how you got that.

But nevertheless, let's keep going:

Let 'U' stand for the unary union operation.
Let 'u' stand for the binary union operation.
Let '^' stand for the binary intersection operation.

a u Ua is not empty. And no member of a u Ua is empty. (You can fill in the argument for those two assertions.)

So, by regularity, let c be a nonempty member of a u Ua such that c^(a u Ua) is empty.

Now see what contradiction you can find. (Remember, there are two cases now: where c in a and where c in Ua.)

5. Originally Posted by MoeBlee
I don't see how you got that.

But nevertheless, let's keep going:

Let 'U' stand for the unary union operation.
Let 'u' stand for the binary union operation.
Let '^' stand for the binary intersection operation.

a u Ua is not empty. And no member of a u Ua is empty. (You can fill in the argument for those two assertions.)

So, by regularity, let c be a nonempty member of a u Ua such that c^(a u Ua) is empty.

Now see what contradiction you can find. (Remember, there are two cases now: where c in a and where c in Ua.)
Thanks! That was less straightforward than I anticipated. I need to remember the unary union, which I do not often use.

Proof: Assume towards a contradiction that $a\neq\emptyset$. By regularity, there is $b\in a\cup\left(\bigcup a\right)$ with $b\cap \left(a\cup\left(\bigcup a\right)\right)=\emptyset$. Now, it cannot be the case that $b\in a$, because if it were, then $b=\{\{x\},\{x,y\}\}$ for some $x,y\in a$, which would mean $\{x\}\in\bigcup a$ and therefore $\{x\}\in b\cap\left(a\cup\left(\bigcup a\right)\right)$, a contradiction. So $b\notin a$, which means $b\in\bigcup a$. However, each member of $a$ has the form $\{\{x\},\{x,y\}\}$, where $x,y\in a$. So each member of $\bigcup a$ has either the form $\{x\}$ or $\{x,y\}$. So regardless of whether $b=\{x\}$ or $b=\{x,y\}$ for some $x,y\in a$, then $x\in b\cap\left(a\cup\left(\bigcup a\right)\right)$, a contradiction.

6. Right.

The strategy lesson learned is that for problems involving Cartesian products, we may need to "drill down" to the union of some set. More generally, when a set is built out of the power set operation, then when we prove stuff about the set we may need to "bring things back down" using the union operation.

Want another good exercise?

Show b = bXc -> b = 0

(This exercise is given as one of the first exercises in Suppes's 'Axiomatic Set Theory'. Almost all the exercises in that book are easy, except the only solution to this particular exercise that I've found is at least a bit tricky.)