Змінити мову

English

Увійдіть до Mathigon

або

Новий акаунт     Скинути пароль     

Sets and functions
by Samuel S. Watson
Introduction
Subsets
Set Builder Notation
Set Operations
Lists
Functions
Function Properties
Function Operations

Поділіться

Скинути прогрес

Це видалить ваші дані про хід і чат для всіх розділів цього курсу, і їх не можна скасувати!

Глосарій

Виберіть одне з ключових слів ліворуч ...

Sets and functionsSet Operations

Час читання: ~50 min

Complement

Given a set S describing a grocery list and a subset A \subset S describing the set of items we've already purchased, the set we might be most interested in constructing from S and A is the set of items which are in S but not in A. This is called the complement of A with respect to S.

The complement of the set of groceries in the cart with respect to the set of groceries on the list is a meaningful set because those are the items .

Definition (Complement)
If A and S are sets and A \subset S, then the complement of A with respect to S, denoted S \setminus A or A^{\mathsf{c}}, is the set of all elements in S that are not in A. That is,

\begin{align*}A^{\mathsf{c}} = \{s \in S : s \notin A\}.\end{align*}

With the blob-and-point visualization:

Since S is not part of the notation A^\mathsf{c}, we will usually only use that notation when the intended containing set S is clear from context.

Sometimes you grab some items at the grocery store which were not on your list. Likewise, the notation S \setminus A may be used regardless of whether A is a subset of S. In this case, we use a different term: the set difference S \setminus A is defined to be the set of elements which are in S which are not in A.

Exercise
Suppose S = \{1,2,3,4,5\} and A = \{4,2\}. Find the complement A^{\mathsf{c}} of A with respect to S. It has elements.

Solution. The complement is A^{\mathsf{c}} = \{1,3,5\}, since 1, 3, and 5 are the elements of S which are not in A.

Exercise
Suppose A\subset S, |S| = 55, and |A| = 13. Then |S \setminus A| = .

Is the assumption that A \subset S necessary for the problem to be well-specified?

Solution. Since S has 55 elements and A has 13, then there are \boxed{42} elements in S which are not in A.

The assumption is necessary, since if some of the elements of A were not in S, |S \setminus A| would be larger.

Union

If two members of your household supplied you with grocery lists as you were about to go to the store, then the first thing you might want to do is produce a combined grocery list. This set operation is called taking the union.

Definition (Union)
The union of two sets S and T, denoted S \cup T, is the set containing all the elements of S and all the elements of T and no other elements. In other words, s \in S \cup T if and only if either s\in S or s \in T.

Exercise
Let S = \{1,2,4,5\} and T = \{1,5,6,7,8\}. Find S \cup T. It has elements.

Solution. Listing all the elements of S and all elements of T and eliminating duplicates, we get

\begin{align*}S \cup T = \{1,2,4,5,6,7,8\}.\end{align*}

Intersection

You realize that you and your partner inadvertently both made grocery lists and went grocery shopping the same afternoon. You want to know the items on both lists, because .

The set of items which are in both sets is called the intersection of the two sets.

Definition (Intersection)
The intersection of two sets S and T, denoted S \cap T, is the set consisting of elements that are in both S and T. In other words, s \in S \cap T if and only if s\in S and s \in T.

Exercise Let S = \{1,2,3,4,5\} and T = \{1,5,6,7,8\}. Then S \cap T has elements.

Set operations with more sets

The union and intersection operations may be applied to any number of sets. Suppose S_1, S_2, \ldots, S_n are sets—the union of these sets can be expressed as S_1 \cup S_2 \cup \cdots \cup S_n.

More compactly,

\begin{align*}\bigcup_{i=1}^n S_i = S_1 \cup S_2 \cdots \cup S_n = \{s : s \in S_i\text{ for some }1 \leq i \leq n\}.\end{align*}

Similarly, we can take the intersection of an arbitrary number of sets:

\begin{align*}\bigcap_{i=1}^n S_i = S_1 \cap S_2 \cap \cdots \cap S_n = \{s : s \in S_i\text{ for all }1 \leq i \leq n\}.\end{align*}

Disjoint sets

Often we will want to specify whether two sets have any elements in common. For example, if S is the set of vegetables you are interested in, and T is the set of vegetables that your partner is interested in, then whether S and T have any overlap determines whether you will need to prepare separate vegetable dishes.

Definition (Disjoint)
Two sets S and T are disjoint if they do not have any elements in common.

In other words, S and T are disjoint if S \cap T = \emptyset.

This definition extends to an arbitrary number of sets. We say that the sets S_1, S_2, \ldots, S_n are pairwise disjoint if any pair is disjoint (in other words, if S_i \cap S_j = \emptyset whenever i \neq j).

Exercise
Find three sets A, B, and C which have A \cap B \cap C = \emptyset, but for which all of the intersections A \cap B, B\cap C, and A \cap C are nonempty.

Solution. We can take A = \{1,2\}, B = \{1,3\}, and C = \{2,3\}. These sets are pairwise non-disjoint, but there are no elements common to all three sets.

Partitions

Suppose you're part of a group of n shoppers working together to purchase the items on a single grocery list. A good idea is to partition the set of items you want to purchase into n smaller sets so that each person can purchase only the items on their own set.

Definition (Partition)
A partition of a set S is a collection of non-empty sets S_1, S_2, \ldots, S_n such that

\begin{align*}S = \bigcup_{i=1}^n S_i\end{align*}

and S_1, S_2, \ldots, S_n are disjoint.

Exercise
Find a partition of \{1,2,3,4,5\} into three sets. Is there a partition of \{1,2,3,4,5\} into six sets?

Solution. There are many partitions of \{1,2,3,4,5\} into three sets. For example,

\begin{align*}\{\{1,2\},\{3,4\},\{5\}\} \text{ or } \{\{1,2,5\},\{3\},\{4\}\}.\end{align*}

It is not possible to partition \{1,2,3,4,5\} into six sets, because each set must have at least one element, and no pair of the sets can have any element in common.

Cartesian Products

Suppose we perform an experiment which consists of flipping a coin and rolling a standard six-sided die. The outcome of the coin flip is an element of the set S_1 = \{H, T\}, and the outcome of the die roll is an element of the set S_2 = \{1,2,3,4,5,6\}. The set of all possible outcomes of the experiment is the set with the following elements.

(H,1)
(H,2)
(H,3)
(H,4)
(H,5)
(H,6)
(T,1)
(T,2)
(T,3)
(T,4)
(T,5)
(T,6)

We call this 12-element set the Cartesian product of S_1 and S_2.

Definition (Cartesian Product)
If S_1 and S_2 are sets, then the Cartesian product of S_1 and S_2 is defined by

\begin{align*}S_1 \times S_2 &= \{(s_1, s_2) : s_1 \in S_1 \text{ and } s_2 \in S_2\}.\end{align*}

Likewise, if S_1,S_2, \ldots, S_n are sets, then

\begin{align*}S_1 &\times S_2 \times \cdots \times S_n \\\ &= \{(s_1, s_2, \ldots, s_n) : s_1 \in S_1 \text{ and } s_2 \in S_2 \text{ and } \cdots \text{ and } s_n \in S_n\}.\end{align*}

This set operation is ubiquitous in probability and data science applications, since it corresponds to the common act of combining multiple pieces of information into an ordered pair, an ordered triple, or a higher-order tuple.

For example, a patient data record might be an ordered quintuple of the form (first name, last name, date of birth, height, blood pressure reading). This record is in S \times S \times D \times H \times B, where S is the set of all strings (sequences of characters), D is the set of all dates, H is the set of positive length measures, and B is the set of possible blood pressure readings.

Exercise
If |S| = 4 and |T| = 100, then |S \times T| = .

Solution. In the coin-and-die example, the cardinality of the Cartesian product was 12, which is equal to the product of the cardinalities of the original sets. We listed the elements of S in a way which suggests why this is the case: the elements of S \times T can always be arranged in a |S| by |T| grid.

Therefore, |S \times T| = 400.

Exercises

Exercise
Select the most appropriate set theory term for each of the following real-world scenarios.

  • You have a list of patients which have a particular risk factor and a second list of patients who have another risk factor. You want to identify the patients with both risk factors.
  • Your company is merging with another company and you want to combine your customer database with their customer database to get a collection of all of the customer records.
  • You have a table containing information about all of the Champions League goals this year, and you want to look at the ones which were not scored by Ronaldo.
  • You have 68 clients to call, and you want to split them among your four salespeople.

Exercise
Establish the first and third of the following four identities. Use the following strategy: show that the left-hand side is a subset of the right-hand side and vice versa. To demonstrate that A\subset B, consider an element s of A and—assuming only that s \in A—apply reasoning to conclude that it must be in B as well.

\begin{align*}S \cap (R \cup T) &= (S \cap R) \cup (S \cap T) \\ S \cup (R \cap T) &= (S \cup R) \cap (S \cup T) \\ \left( \bigcup_{i=1}^n S_i \right)^{\mathsf{c}} &= \bigcap_{i=1}^n S_i^\mathsf{c} \\ \left( \bigcap_{i=1}^n S_i \right)^{\mathsf{c}} &= \bigcup_{i=1}^n S_i^\mathsf{c}\end{align*}

Solution. If an element s is in S \cap (R \cup T), then it is in S and it is either in R or T. This implies that either (i) s\in S and s\in R, or (ii) s\in S and s\in T. In other words, either s\in S \cap R or s \in S \cap T. In other words, s \in (S \cap R) \cup (S \cap T). Therefore, the left-hand side is a of the right-hand side.

Conversely, if s \in (S \cap R) \cup (S \cap T), then either s \in S \cap R or s \in S \cap T. In the former case, it is true that s \in S and that s \in R \cup T. Therefore, s \in S \cap (R \cup T) in this case. Similarly, in the latter case, we have s\in S and s \in R \cup T. Therefore, s \in S \cap (R \cup T) in this case as well. So the right-hand side is also a of the left-hand side.

For the third identity, note that if

\begin{align*}s\in \left( \bigcup_{i=1}^n S_i \right)^{\mathsf{c}}, \end{align*}

then it is not true that s is in the union of the S_i's. In other words, s must be in none of the S_i's. This means that for each S_i, the element s is in its complement. It follows by the definition of intersection that

\begin{align*}s \in \bigcap_{i=1}^n S_i^{\mathsf{c}}\end{align*}

Similarly, if

\begin{align*}s \in \bigcap_{i=1}^n S_i^{\mathsf{c}}, \end{align*}

then s is in none of the S_i's, which in turn means that it is not in the union of the S_i's. Thus, s is in the complement of the union of the S_i's.

Bruno
Bruno Bruno