Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

8.1: How to Prove a∈A

  • Page ID
    24842
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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.