Skip to main content
Logo image

Applied Combinatorics

Section B.1 Introduction

Set theory is concerned with elements, certain collections of elements called sets and a concept of membership. For each element \(x\) and each set \(X\text{,}\) exactly one of the following two statements holds:
  1. \(x\) is a member of \(X\text{.}\)
  2. \(x\) is not a member of \(X\text{.}\)
It is important to note that membership cannot be ambiguous.
When \(x\) is an element and \(X\) is a set, we write \(x\in X\) when \(x\) is a member of \(X\text{.}\) Also, the statement \(x\) belongs to \(X\) means exactly the same thing as \(x\) is a member of \(X\text{.}\) Similarly, when \(x\) is not a member of \(X\text{,}\) we write \(x\notin X\) and say \(x\) does not belong to \(X\text{.}\)
Certain sets will be defined explicitly by listing the elements. For example, let \(X=\{a,b,d,g,m\}\text{.}\) Then \(b\in X\) and \(h\notin X\text{.}\) The order of elements in such a listing is irrelevant, so we could also write \(X=\{g,d,b,m,a\}\text{.}\) In other situations, sets will be defined by giving a rule for membership. As examples, let \(\posints\) denote the set of positive integers. Then let \(X=\{n\in\posints:5\le n\le 9\}\text{.}\) Note that \(6,8\in X\) while \(4,10,238\notin X\text{.}\)
Given an element \(x\) and a set \(X\text{,}\) it may at times be tedious and perhaps very difficult to determine which of the statements \(x\in X\) and \(x\notin X\) holds. But if we are discussing sets, it must be the case that exactly one is true.

Example B.1.

Let \(X\) be the set consisting of the following \(12\) positive integers:
\begin{align*} \amp 13232112332\\ \amp 13332112332\\ \amp 13231112132\\ \amp 13331112132\\ \amp 13232112112\\ \amp 13231112212\\ \amp 13331112212\\ \amp 13232112331\\ \amp 13231112131\\ \amp 13331112131\\ \amp 13331112132\\ \amp 13332112111\\ \amp 13231112131 \end{align*}
Note that one number is listed twice. Which one is it? Also, does \(13232112132\) belong to \(X\text{?}\) Note that the apparent difficulty of answering these questions stems from (1) the size of the set \(X\) and (2) the size of the integers that belong to \(X\text{.}\) Can you think of circumstances in which it is difficult to answer whether \(x\) is a member of \(X\) even when it is known that \(X\) contains exactly one element?

Example B.2.

Let \(P\) denote the set of primes. Then \(35\notin P\) since \(35= 5\times 7\text{.}\) Also, \(19\in P\text{.}\) Now consider the number
\begin{equation*} n = 77788467064627123923601532364763319082817131766346039653933 \end{equation*}
Does \(n\) belong to \(P\text{?}\) Alice says yes while Bob says no. How could Alice justify her affirmative answer? How could Bob justify his negative stance? In this specific case, I know that Alice is right. Can you explain why?