
# 8.1: How to Prove a∈A


We will begin with a review of set-builder notation, and then review how to show that a given object a is an element of some set A.

Generally, a set A will be expressed in set-builder notation $$A = \{x : \mathscr{P}(x)\}$$, where $$\mathscr{P}(x)$$ is some open sentence about x. The set A is understood to have as elements all those things x for which $$\mathscr{P}(x)$$ is true. For example,

$$\{x :$$ x is an odd integer $$\}$$ = $$\{\cdots, -5, -3, -1, 1, 3, 5, \cdots\}$$.

A common variation of this notation is to express a set as $$A= \{x \in S : \mathscr{P}(x)\}$$. Here it is understood that A consists of all elements x of the (predetermined) set S for which $$\mathscr{P}(x)$$ is true. Keep in mind that, depending on context, x could be any kind of object (integer, ordered pair, set, function, etc.). There is also nothing special about the particular variable x; any reasonable symbol x, y, k, etc., would do. Some examples follow.

$$\{n \in \mathbb{Z} :$$ n is odd $$\}$$ = $$\{\cdots , -5, -3, -1, 1, 3, 5, \cdots\}$$

$$\{x \in \mathbb{N} : 6|x\} = \{6, 12, 18, 24, 30, \cdots\}$$

$$\{(a,b) \in \mathbb{Z} \times \mathbb{Z} : b = a+5\} = \{\cdots, (-2,3), (-1,4), (0,5), (1,6), \cdots\}$$

$$X \in \mathscr{P}(\mathbb{Z}):|X|=1\} = \{\cdots, -1, 0, 1, 2, 3, 4, \cdots\}$$

Now it should be clear how to prove that an object a belongs to a set $$\{x : \mathscr{P}(x)\}$$. Since $$\{x : \mathscr{P}(x)\}$$ consists of all things x for which $$\mathscr{P}(x)$$ is true, to show that $$a \in \{x : \mathscr{P}(x)\}$$ we just need to show that $$\mathscr{P}(a)$$ is true. Likewise, to show $$a \in \{x \in S : \mathscr{P}(x)\}$$, we need to confirm that $$a \in S$$ and that $$\mathscr{P}(a)$$ is true. These ideas are summarized below. However, you should not memorize these methods, you should understand them. With contemplation and practice, using them becomes natural and intuitive.

How to show $$a \in \{x : \mathscr{P}(x)\}$$

Show that $$\mathscr{P}(a)$$ is true

How to show $$a \in \{x \in S : \mathscr{P}(x)\}$$

1. Verify that $$a \in S$$.

2. Show that $$\mathscr{P}(a)$$ is true.

Example 8.1

Let’s investigate elements of $$A = \{x : x \in \mathbb{N}$$ and $$7|x\}$$. This set has form $$A = \{x : \mathscr{P}(x)$$ where $$\mathscr{P}(x)$$ is the open sentence $$(x \in \mathbb{N}) \wedge (7|x)$$. Thus $$21 \in A$$ because $$\mathscr{P}(21)$$ is true. Similarly, 7, 14, 28, 35, etc., are all elements of A. But $$8 \notin A$$ (for example) because $$\mathscr{P}(8)$$ is false. Likewise $$-14 \notin A$$ because $$\mathscr{P}(-14)$$ is false.

Example 8.2

Consider the set $$A = \{X \in \mathscr{P}(\mathbb{N}) : |X| = 3\}$$. We know that $$\{4, 13, 45\} \in A$$ because $$\{4, 13, 45\} \in \mathscr{P}(\mathbb{N})$$ and $$|\{4, 13, 45\}| = 3$$. Also $$\{1,2,3\} \in A$$, $$\{10, 854, 3\} \in A$$, etc. However $$\{1, 2, 3, 4\} \notin A$$ because $$|\{1, 2, 3, 4\}| \ne 3$$. Further, $$\{-1,2,3\} \notin A$$ because $$\{-1,2,3\} \notin \mathscr{P}(\mathbb{N})$$.

Example 8.3

Consider the set $$B = \{(x,y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 5\}$$ . Notice $$(8, 23) \in B$$ because $$(8, 23) \in \mathbb{Z} \times \mathbb{Z}$$ and $$8 \equiv 23 \pmod 5$$. Likewise, $$(100, 75) \in B$$, $$(102, 77) \in B$$, etc., but $$(6, 10) \notin B$$.

Now suppose $$n \in \mathbb{Z}$$ and consider the ordered pair $$(4n+3, 9n-2)$$. Does this ordered pair belong to B? To answer this, we first observe that $$(4n+3, 9n-2) \in \mathbb{Z} \times \mathbb{Z}$$. Next, we observe that $$(4n+3)-(9n-2) = -5n+5 = 5(1-n)$$, so $$5|((4n+3)-(9n-2))$$, which means $$(4n+3) \equiv (9n−2) \pmod 5)$$. Therefore we have established that $$(4n+3, 9n-2)$$ meets the requirements for belonging to B, so $$(4n+3, 9n-2) \in B$$ for every $$n \in \mathbb{Z}$$.

Example 8.4

This illustrates another common way of defining a set. Consider the set $$C= \{3x^3+2 : x \in \mathbb{Z}\}$$. Elements of this set consist of all the values $$3x^3+2$$ where x is an integer. Thus $$-22 \in C$$ because $$-22 = 3(-2)^3+2$$. You can confirm $$-1 \in C$$ and $$5 \in C$$, etc. Also $$0 \notin C$$ and $$12 \notin C$$, etc.