Mastering Proofs to Solving Complement, Subset, and Union Problems

[Emmiebird]

Hi!

I am having a lot of trouble with these problems:

A-(An complement B)= AnB

If A is a subset of B then AxC is a subset of BxC

Ax(BuC)=(AxB)u(AxC)

I don't get how to work them out. Can anyone help me please?

 

[Emmiebird]

I just don't know how to incorporate the (x,y) into the problem.

 

[bpet]

It often helps to draw coloured Venn diagrams. Cross products will look like rectangles.

 

[Emmiebird]

We didn't go over that stuff

 

[yossell]

One way of approaching the first and third questions is to break them into two steps:

(1) show that any x that is a member of the L(eft) H(and) S(ide) is a member of the R(ight) H(and) S(ide)

(2) Show that any x that is a member of the RHS is a member of the LHS.

(1) and (2) together show that the LHS and the RHS have the same members and, since two sets with the same members are in fact the same set, you can conclude identity.

The way the proofs typically proceed is to unpack the definitions of set-theoretic vocabulary, apply a bit of propositional logic to the definitions, and then repack what you get back up into set-theoretic vocabulary.

Here's an example that (all being well!) proves half of 3.

(3):
First suppose x is a member of A x (B U C).

Then x = <a d>, for some a in A and some d in B U C. (by definition of x)

(I assume your definition of A x B is the set of all ordered pairs whose first element is from a, and whose second element is from B - if it's something different you'll have to modify this accordingly...still, I hope it helps).

This implies that x = <a d> where a is in A and (d is in B or d is in C) (by definition of union)

This implies (by propositional logic) that x = <a d> with either (a in A and d in B) or (a in A and d in C)

This implies (By dfn of X) that x = <a d> with either <a d> in A X B or <a d> in A X C

This implies (by dfn of U) that x = <a d> with <a d> in (A X B) U (A X C)

So x is in (A X B) U (A X C)


This shows A x (B U C) is a subset of (A X B) U (A X C). To complete the proof, one then has to show the reverse direction.

 

[discrete*]

yossell gave a fantastic, detailed answer.

When I learned to do these set proofs I quickly learned that there was one particular style of proof that was invaluable: the mutual set inclusion method. This is exactly as the name suggests. Typically all you need to do is choose something to be in one set (the first one) and show that it is in the other. Than you do the same for the second set.

This sounds awfully easy, but can get pretty complicated. As yossell said, you will more often than not find yourself using the definitions and other handy things like De Morgan's laws to get you through these type of proofs.

I'm avoiding giving a proof directly suited to your problem, because I'm new here and I just saw the sticky post at the top of the forum "not for homework". I hope this helps in theory, at least.