abstractmath.org 2.0
help with abstract math

Produced by Charles Wells     Revised 2017-03-03
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.

Warning

• The name "method of comprehension" can cause semantic contamination.
• "Comprehension" to most people means understanding. Ignore that meaning. In the olden days, "comprehend" meant "contain".
• If I were dictator of the math language, I would call it the "Method of whatsinit".

Method of proof for setbuilder notation:

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

• (ES) If you know that $a\in A$, then you can conclude that the statement $P(a)$ is true.
• (SE) If $P(a)$ is a true statement then you can conclude that $a\in A$.
• (ES) and (SE) together mean that if $A=\{x\,|\,P(x)\}$, then every $x$ for which $P(x)$ is true is an element of $A$, and nothing else is.

The elements of $\{x\,|\,P(x)\}$ are exactly all those $x$ that make $P(x)$ true.

Example

For an integer $n$, the assertion \[\{n\,|\,1\lt n\lt6\}=\{2,3,4,5\}\] is correct.

• The method of comprehension allow you to state
  • Since $3\in\{2,3,4,5\}$, ES says $1\lt3\lt6$.
  • Since $1\lt3\lt6$, SE says $3\in\{2,3,4,5\}$.
• It would be wrong to say that \[\{n\,|\,1\lt n\lt6\}=\{2,3,4,6\}\] because $1\lt6\lt5$ is false, violating ES.
• It would be wrong to say that \[\{n\,|\,1\lt n\lt6\}=\{2,3,4\}\] because $1\lt5\lt6$ but $5\notin\{2,3,4\}$, violating SE.

Other examples

• $\{n\,|\,1\lt n\text{ and }1\gt n\}=\emptyset$.
• $\{n\,|\,2\gt n\text{ or }0\lt n\}=\mathbb{N}$.

The method of comprehension and equivalence

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 not even.
• 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 of proof for inclusion

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.