Proving Basic Set Theory: Trichotomy, Union, Intersection, and Multiplication

[SpY]]

At first glance these things seem so intuitive and familiar from other maths (like distribution) that I don't see how/where to start in proving them; while I know its probably quite simple. I understand what union and intersection are, but I'm unsure if multiplying two sets means a new set with elements being every permutation between the two sets.

Trichotomy - [tex]A \subseteq B , B \subseteq C then A \subseteq C[/tex]
For non empty sets, [tex]A \times (B \cap C) = (A \times B) \cap (A \times C)[/tex]
[tex](A \times B) \cap (A\timesB) = (A \cap B) \times (A \cap B)[/tex]

 

[Fredrik]

Two sets are equal if and only if they have the same members. So X=Y if and only if every member of X is a member of Y and every member of Y is a member of X. To prove equality, you should start out saying "let x be an arbitrary member of X", and then prove that this x must also be a member of Y. Then say "let y be an arbitrary member of Y" and prove that it's also a member of X.

The proof of the first step will consist of a small number of implications. You can usually prove the second step just by staring at those implications until you see that they all hold in the opposite direction too.

Your first problem is much easier than that. Just use the assumptions to fill in the part I left out here:

[tex]x\in A\Rightarrow\ \underline{\hspace{2cm}}\ \Rightarrow x\in C[/tex].

A×B is the cartesian product of A and B. It's the set of all ordered pairs (a,b) such that a is in A and b is in B. "Ordered pairs" can be defined using sets. (Sets can't be ordered, since two sets are equal if and only if they have the same members. That axiom implies that {a,b}={b,a}). The standard definition is (a,b)={a,{a,b}} (but you probably don't need to know that).

 

[yossell]

OP, are you sure about that third equation?

 

[Gib Z]

A×B is the cartesian product of A and B. It's the set of all ordered pairs (a,b) such that a is in A and b is in B. "Ordered pairs" can be defined using sets. (Sets can't be ordered, since two sets are equal if and only if they have the same members. That axiom implies that {a,b}={b,a}). The standard definition is (a,b)={a,{a,b}} (but you probably don't need to know that).

It's more commonly defined as (a,b) = {{a},{a,b}} as we can prove the characteristic property of ordered pairs ( (a,b) = (c,d) iff a=c, b=d ) without invoking the Axiom of Foundation, and to avoid ambiguities such as 2 = {0, 1} = {0, {0}} = (0,0).

 

[Fredrik]

Good catch Gib Z, I got a little sloppy there.

Spy, yossell is right about the third problem. The left-hand side is actually empty. (Do you see why?) Did you mean something different than what you wrote?

 

[Edgardo]

Start with the definitions. For example,
[tex]A \subseteq C[/tex] means [tex]\forall x( x \in A \Rightarrow x \in C)[/tex]

What does [tex]\forall x( x \in A \Rightarrow x \in C)[/tex] mean?

As Fredrik pointed out, you start with [tex]x \in A[/tex] and derive [tex]x \in C[/tex], that is you show [tex]( x \in A \Rightarrow x \in C)[/tex]

See also:
Basics of Set
Mathematical Reasoning