Applied Discrete Structures

Subsection 1.1.1 The notion of a set

Informal Definition: A set is a collection of objects that are called elements (of the set).

• For a set \(A\text{,}\) if \(x\) is an element of \(A\text{,}\) we will write \(x \in A\text{.}\).
• If \(x\) is not an element of \(A\text{,}\) we write \(x \notin A\text{.}\)
• The most convenient way of describing the elements of a set will vary depending on the specific set.

• Enumeration. set elements enumerated (or listed) between braces. E.g. the set of binary digits \(\{0, 1\}\); the set of decimal digits is \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\text{.}\)

• Names of sets should be meaningful to ease understanding. “logical” to call them \(B\) and \(D\text{,}\) respectively.
• Large sets may enumerated without listing all the elements: e.g. alphabet letter set is \(A = \{a, b, c,\ldots , x, y, z\}\text{,}\) "..." is called ellipsis. We use them when it is clear what elements are included but not listed.
• An ellipsis is used in two other situations:
  1. Enumerate positive integers: \(\{1, 2, 3,\ldots \}\text{,}\) indicating that the list goes on infinitely.
  2. Enumerate integers between 1 and \(n\text{,}\) where \(n\) is some undetermined positive integer, we might write \(\{1,\ldots ,n\}\text{.}\)

Standard Symbols. Sets frequently encountered have reserved names (identifiers)

• \(\mathbb{P}\text{:}\) the positive integers, \(\{1, 2, 3, 4, \ldots \}\)

• \(\mathbb{N}\text{:}\) the natural numbers, \(\{0, 1, 2, 3, \ldots \}\)

• \(\mathbb{Z}\text{:}\) the integers, \(\{\ldots , -3, -2, -1, 0, 1, 2, 3,\ldots \}\)

• \(\mathbb{Q}\text{:}\) the rational numbers

• \(\mathbb{R}\text{:}\) the real numbers

• \(\mathbb{C}\text{:}\) the complex numbers

Set-Builder Notation. For example, we could define the rational numbers as

Note that in the set-builder description for the rational numbers:

• \(a/b\) indicates that a typical element of the set is a “fraction.”

• The vertical line, \(\mid\text{,}\) is read “such that” or “where,” and is used interchangeably with a colon.

• \(a, b\in \mathbb{Z}\) is an abbreviated way of saying \(a\) and \(b\) are integers.

• Commas in mathematics are read as “and.”

For example, \(\{x\in \mathbb{R} \mid x^{2}-5x+6 =0\}\) and \(\{x \mid x \in \mathbb{R}, x^{2}-5x+6=0\}\) both describe the solution set \(\{2, 3\}\text{.}\)

For this course, the set of real numbers is the set of points on a number line. The set of complex numbers can be defined as \(\mathbb{C} = \{a + b i:a, b \in \mathbb{R}\}\text{,}\) where \(i^2 = -1\text{.}\)

In the following definition we will leave the word “finite” undefined.

As we will see later, there are different infinite cardinalities. We can't make this distinction until Chapter 7, so we will restrict cardinality to finite sets for now.

Subsection 1.1.2 Subsets

Definitions:

• if and only if means “is equivalent to saying,” or more exactly, that the word (or concept) being defined can at any time be replaced by the defining expression. Conversely, the expression that defines the word (or concept) can be replaced by the word.

• The set that contains no elements is the empty set, \(\emptyset\), also called the null set.

• Given any set \(A\) \(A\subseteq A\) and \(\emptyset \subseteq A\text{.}\) If \(A\) is nonempty, then \(A\) is called an improper subset of \(A\text{.}\) All other subsets of \(A\text{,}\) including the empty set, are called proper subsets of \(A\text{.}\) The empty set is an improper subset of itself.