Results 1 to 6 of 6

Math Help - [SOLVED] Prove that only the empty set is a subset of the cartesian product of itself

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    410

    [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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by MoeBlee View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    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.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by MoeBlee View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. prove subset of R has empty interior
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: December 11th 2011, 11:20 PM
  2. Empty Cartesian product implies...?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 5th 2010, 07:12 AM
  3. How to prove using cartesian product
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 15th 2009, 01:47 PM
  4. Replies: 1
    Last Post: February 10th 2009, 08:42 AM
  5. [SOLVED] Empty Set subset of every set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 28th 2005, 08:32 AM

Search Tags


/mathhelpforum @mathhelpforum