Produced by Charles Wells.  Home.   Website Contents     Website Index 

Back to Sets beginning  

Posted 28 October 2008

SETS: RULES OF INFERENCE

Contents

The method of comprehension. 1

Set equality. 1

Set inclusion. 2

The method of comprehension

Method: Let P(x) be an assertion and let A be the set . Then:

¨  If you know that , it is correct to conclude that the statement P(a) is true.

¨  If P(a) is a true statement then you know that .

This method is called The Method of Comprehension. (Why?)  It means that the elements of  are exactly all those x that make P(x) true. If , then every x for which P(x) is true is an element of A, and nothing else is.

This method is the main tool for proving statements involving setbuilder notation.

Restatement 1

The Method of Comprehension implies that the assertion “  ” and the assertion “P(a)” is an equivalence, in other words all four of these statements are true:

¨  If  then P is true of a.

¨  If P is true of a then .

¨  If  then P is not true of A.

¨  If P is not true of A then .

Restatement 2

Another way of writing the Method is

If you have trouble using the method of comprehension,  that may be because you have forgotten this fact.

Example

The only correct answer to the question

“What is  in list notation?”

is “{2,3,4,5}”.  {2,4,5} would be an incorrect answer, even though 2, 4 and 5 are all elements of the set.

The proof of the powerset theorem is a great exercise for helping you understand the method of comprehension.

Warning

The definite article “the” has a special role when defining a set.  For example “the set of even integers” automatically means the set of all even integers.  More about this.

Set equality  add references and rewrite

If  and  then . 

Given two sets A and B, how does one show that ?  As I said here,  A = B means that every element of A is an element of B and every element of B is an element of A. So by a DeMorgan Law, to prove  you must show that one of those two statements is false: either there is an element of A that is not an element of B or that there is an element of B that is not an element of A.

You needn't show both, and indeed you often can't show both. For example,  yet every element of the first one is an element of the second one.

Set inclusion      

Method:  To prove that  you must prove that if x is any element of A, then x is also an element of B.

Example

, because every integer is a real number.

Theorem

If A is any set then . 

Proof: 

a)   To show that  you must show that if , then .   (Rewrite according to definition.)

b)   The statement “  ” is false for every x.   (By definition, the empty set has no elements.)

c)   This means the statement “if , then  ” is vacuously true. 

End of proof.

Answers to questions

Why does the Method of Comprehension have that name?  Back.

Answer:  A somewhat old-fashioned meaning of the word “comprehend” is to include all of some things, as in “This book comprehends all aspects of the art of tatting.”  The metaphor is that the set  gathers together everything for which the assertion P is true.