# 8.1: How to Prove a∈A

- Page ID
- 24842

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.