abstractmath.org 2.0
help with abstract math

Produced by Charles Wells     Revised 2016-01-31
Introduction to this website    website TOC
website index   blog
Back to head of Sets chapter

SETS: RULES OF INFERENCE

The method of comprehension

The method of comprehension is the main tool for proving statements involving setbuilder notation. The name "method comprehension" can cause semantic contamination. "Comprehension" to most people means understanding. Ignore that meaning. Think of "comprehension" as just a technical word. If I were dictator of the math language, I would call it the "Method of whatsinit".

In the olden days, "comprehend" meant "contain". Now you know.

Method:

Let $P(x)$ be an assertion and let $A$ be the set $\{x\,|\,P(x)\}$. Then the following two statements are true:

• If you know that $a\in A$, then it is correct to conclude that the statement $P(a)$ is true.
• If $P(a)$ is a true statement then you know that $a\in A$.

This means that the elements of $\{x\,|\,P(x)\}$ are exactly all those $x$ that make $P(x)$ true. If $A=\{x\,|\,P(x)\}$, then every $x$ for which $P(x)$ is true is an element of $A$, and nothing else is.

Examples

• If we are talking about integers $n$, then \[\{n\,|\,1\lt n\lt6\}=\{2,3,4,5\}\] It would be wrong to say that \[\{n\,|\,1\lt n\lt6\}=\{2,3,4\}\] because of the word "exactly" in the preceding paragraph.
• $\{n\,|\,1\lt n\text{ and }1\gt n\}=\emptyset$.
• $\{n\,|\,2\gt n\text{ or }0\lt n\}=\mathbb{N}$.

Another way of stating the method of comprehension is that the statements "$a\in A$" and "$P(a)$" are equivalent. This means:

The method of comprehension works both ways.

Example

Let $E$ be the set of even integers. Then:

• $E=\{n\,|\,n\text{ is even.}\}$
• $42\in E$ because $42$ is even.
• $43\notin E$ because $43$ is odd.
• Suppose you know that the integer $m$ is even. Then $m\in E$.
• Suppose you know that $k$ is odd. Then $k\notin E$.

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. There is more about this in the Glossary.

Set inclusion

Inclusion is discussed in detail in the article Subsets and Inclusion. There is a rule of inference for inclusion:

Method

To prove that $A\subseteq B$, you must prove that any element of $A$ is an element of $B$.

Examples

• Let $A=\{1,2,3\}$ and $B=\{1,2,3,4\}$. Then $A\subseteq B$ because, going through the elements of $A$, $1\in B$, $2\in B$ and $3\in B$.
• $A\subseteq \mathbb{R}$ because $1$, $2$ and $3$ are all real numbers.
• It is not true that $\{1,2,3,\pi\}\subseteq\mathbb{Z}$, because $\pi$ is not an integer.
• For any set $A$, $\emptyset\subseteq A$ because it is vacuously true that if $x\in\emptyset$ then $x\in A$.

Thus the empty set is included in every set. But the empty set is not an element of every set. For example, it is not an element of $\{1,2,3\}$, as you can see by looking at the list of elements in $\{1,2,3\}$ -- you don't see "$\emptyset$" in that list, do you?

The notion that the empty set is an element of every set is a myth widely believed by undergraduate math students. Get over it.

Set equality

This is a basic fact about sets:

$A\subseteq B$ and $B\subseteq A$ if and only if $A$ and $B$ are the same set.

In other words, For "$A=B$" to be true, $A$ and $B$ have to have exactly the same elements.

Inequality

So how do you show that two sets are not equal? Answer: You have to show that at least one of the following statements is true:

1. There is an element $x\in A$ for which $x\notin B$.
2. There is an element $x\in B$ for which $x\notin A$.

Think through the three examples below. Altogether, they show you that it can happen that one of the statements above can be true and the other false, and also that both statements can be true.

• $A=\{1,2,3\}$, $B=\{1,2\}$.
• $A=\{1,2,3\}$, $B=\{1,2,3,4\}$.
• $A=\{1,2,3\}$, $B=\{1,2,4\}$.

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.