CIS-375 Help Session Note 2 (Spring 2020)

Example: Toyota numbers

The following definitions of Toyota numbers are all equivalent:

Let \(\mathbb{Z}^+\) be the set of positive integers.

• $\{ x : x \in \mathbb{Z}^+, 3 \mid x^2 + 5x \}$
• $\{ x \in \mathbb{Z}^+ : 3 \mid x^2 + 5x \}$
• $\{ x \mid \quad x \in \mathbb{Z}^+, 3 \mid x^2 + 5x \}$
• $\{ x \in \mathbb{Z}^+ \mid \quad 3 \mid x^2 + 5x \}$

Important facts:

1. A set is always a subset of itself.
2. \(\emptyset\) is the subset of any set.

Difference between \(\subseteq\) and \(\in\):

\(\subseteq\) is an operator between two sets; \(\in\) is an operation between an element and a set.

Proving one set is a subset of another:

To show \(A \subseteq B\), you need to prove that every element of \(A\) is also an element of \(B\). That is, for any given \(x \in A\), if you can show \(x \in B\) also holds, then \(A \subseteq B\).

Proving \(A = B\) iff \(A \subseteq B\) and \(B \subseteq A\):

(\(\Rightarrow\)) If \(A = B\), then both sets contains exactly the same elements. For any element \(x \in A\), \(x \in B\) holds, which indicates \(A \subseteq B\). For any element \(y \in B\), \(y \in A\) holds, which indicates \(B \subseteq A\).

(\(\Leftarrow\)) If both \(A \subseteq B\) and \(B \subseteq A\) are true, we know that every element of \(A\) is also an element of \(B\); every element of \(B\) is also an element of \(A\). That is to say, \(A\) and \(B\) must contain exactly the same elements. Therefore, we have \(A = B\).

Proving two sets \(A\) and \(B\) are equal:

Method 1: Show \(A \subseteq B\) and \(B \subseteq A\).

Method 2: Using set builder notation, show that two sets can be represented using the same set-builder notation.

Example: the power set of \(\{1, 2, 3\}\) is the set

\(\left\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \right\}.\)

Number of elements in the power set:

Suppose \(\lvert A \rvert = n\), then \(\lvert 2^A \rvert = 2^n\). This is true because for each element in the set, there are two possibilities: it is either an element of the subset or not an element of the subset. Therefore, the total number of combinations is given by

\[\prod_{i=1}^{n} 2 = 2^n.\]

The notation of power set is \(2^A\) because \(\lvert 2^A \rvert = 2^{\lvert A \rvert}\).

Important conclusion (try to prove it yourself):

\(x \in A \Leftrightarrow \{x\} \subseteq A \Leftrightarrow \{x\} \in 2^A\).

Examples:

Suppose \(A = \{1, 2, 3, 4\}\), \(B = \{3, 4, 5, 6\}\), then:

• $A \cup B = \{1, 2, 3, 4, 5, 6\}$
• $A \cap B = \{3, 4\}$
• $A - B = \{1, 2\}$
• $A \symd B = \{1, 2,5, 6\}$
• $\begin{aligned}[t] A \symd B =~& (1, 3), (1, 4), (1, 5), (1, 6),\\ & (2, 3), (2, 4), (2, 5), (2, 6),\\ & (3, 3), (3, 4), (3, 5), (3, 6),\\ & (4, 3), (4, 4), (4, 5), (4, 6) \end{aligned}$

Important facts (try to prove them yourself):

• $A \symd B = (A \cup B) - (A \cap B)$
• $A - (B \cup C) = (A - B)\cap(A - C)$
• $A - (B \cap C) = (A - B)\cup (A - C)$

Each operation in terms of set-builder notation:

• $A \cup B = \{x : x \in A \lor x \in B\}$
• $A \cap B = \{x : x \in A \land x \in B\}$
• $A - B = \{x : x \in A \land x \notin B\}$
• $A \symd B = \{x : (x \in A \land x \notin B) \lor (x \in B \land x \notin A)\}$
• $A \times B = \{(x, y) : x \in A \land y \in B\}$

Remarks

1. When you are asked to prove set equalities, you have two options: 1) proving mutual inclusion; 2) showing set-builder notations are equal. Personally, I prefer the latter because we only need to prove one direction to show the two sets are equal. Also, the use of pure mathematical language will help you understand and solve the problem faster.
2. Think of \(x \in A\) as a Boolean variable. If \(x\) is an element of \(A\), then \(x \in A\) is True; otherwise, it is False.
3. \(x \notin A\) is also a Boolean variable, which is logically equivalent to \(\neg x \in A\).
4. Set difference is not the same as numerical difference. Some student write \(U-(U-A) = A\) in their homework. This is basically assuming two facts:
   • Associativity: because you think \(U-(U-A) = (U-U)-(-A)\)
   • \(-A\) exists, and \(-(-A) = +A\)

   However, these properties cannot be used without proof! Therefore, do not assume these operations have any similarity to other numerical operations you know before. If you really need to use these properties, please prove them first.

Example: prove \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\).

$\small \begin{aligned} A \cap (B \cup C) &= \{x : x \in A \land (x \in B \lor x \in C)\} && ( \mbox{definition of } \cap)\\ &= \{x : (x \in A \land x \in B) \lor (x \in A \land x \in C)\} && (\mbox{theorem 7.2, distributive properties})\\ &= \{x : (x \in A \cap B) \lor (x \in A \cap C)\} && (\mbox{definition of } \cap)\\ &= \{x : x \in (A \cap B) \cup (A \cap C)\} && (\mbox{definition of } \cup)\\ &= (A \cap B) \cup (A \cap C). \end{aligned}$

In your homework/exams, remember to point out the details of key steps (e.g. here, the use of distributive properties).

Example: prove \(A \subseteq B\) iff \(A - B = \emptyset\).

Now you may see why you cannot treat set difference as numerical difference, because \(A - B = \emptyset\) does not indicate \(A = B\)!

The definition of \(A-B\) is \(\{x : x \in A \land x \notin B\}\).

(\(\Rightarrow\)) If \(A \subseteq B\), then for every \(x \in A\), \(x \in B\) must be also true. As a result, there is no element in \(A\) that satisfies \(x \in A \land x \notin B\), which means \(A-B\) is \(\emptyset\).

(\(\Leftarrow\)) If \(A - B = \emptyset\), it means that for all \(x \in A\), \(x \in A \land x \notin B\) must be false. Because \(x \in A\) is always true, it means that \(x \notin B\) must be always false. That is to say, for all \(x \in A\), \(x \notin B\) must be always false, which means \(x \in B\) must be always true, which indicates \(A \subseteq B\).

Example: suppose \(f(x)\) is a function defined on \(\mathbb{R}\). Use quantifiers to express “\(f(x)\) has a maximum (denoted by \(m\))”.

\(\exists m \in \mathbb{R}\), \(\forall x \in R\), \(f(x) \leq m\).

Remarks.

Can you swap the order of the two quantifiers and say \(\forall x \in R\), \(\exists m \in \mathbb{R}\), \(f(x) \leq m\)?

No, you cannot. If you swap the order, it becomes for all \(x \in \mathbb{R}\), I can find a value \(m \in \mathbb{R}\), such that \(f(x) \leq m\). Intuitively, I can just let \(m = f(x) + 1\), and the assertion always holds. In this case, \(m\) has nothing to do with the maximum of \(f(x)\).

Example: \(\epsilon - \delta\) definition of limits (wiki)

\(\displaystyle \lim_{x \rightarrow c} f(x) = L\) means \(\forall \epsilon > 0\), \(\exists \delta > 0\), such that \(\forall x \in R\), if \(\lvert x - c \rvert < \delta\), then \(\lvert f(x) - L \rvert < \epsilon\).

Suppose we know \(\displaystyle \lim_{x \rightarrow 0} \frac{\sin x}{x} = 0\), think about this: we can assign an arbitrary number \(\epsilon\) that is greater than zero, then their must exist a radius \(\delta\), such that when the “distance” between \(x\) and \(c=0\) (\(\lvert x - 0 \rvert\)) is less than \(\delta\), we have the “distance” between \(f(x)\) and \(L\) (\(\lvert f(x) - 0 \rvert\)) is less than \(\epsilon\). Think about when \(\epsilon\) is very small, it indicates that the value of \(f(x)\) will be very close to \(L\), but also you need to make sure that \(x\) is very close to \(c\). This definition concisely and accurately describes the behavior of limits.

Example: On set \(A = \{1, 2, 3\}\), the \(<\) relation can be represented by

\[< ~ = \{(1, 2), (1, 3), (2, 3)\}.\]

Note: \(a \rrel b\) means \((a, b) \in R\).

Example: On set \(A = \{1, 2, 3\}\), the inverse relation of \(<\) is

\[<^{-1} ~ = \{(2, 1), (3, 1), (3, 2)\},\]

which is clearly identical to the \(>\) relation.

Important fact: \((R^{-1})^{-1} = R\) (try to prove it yourself)

Consider the relation \(R\) on \(\mathbb{Z}\), where \(R = \emptyset\). It can be clearly seen that \(\forall x, y \in \mathbb{Z}\), \(x \rrel y\) will be False.

1. It is not reflexive.
2. It is irreflexive.
3. It is symmetric, because \(x \rrel y\) is False, \(x \rrel y \rightarrow y \rrel x\) will be True due to vacuous truth.
4. It is antisymmetric, because \(x \rrel y\) is False, \((x \rrel y \land y \rrel x) \rightarrow x = y\) will be True due to vacuous truth.
5. It is transitive, because \(x \rrel y\) is False, \((x \rrel y \land y \rrel z)\) will be False, and \((x \rrel y \land y \rrel z) \rightarrow x \rrel z\) will be True due to vacuous truth.

Let \(A = \{1, 2, 3\}\), consider the relation \(R\) on \(A\), where \(R = \{(1, 1)\}\).

1. It is not reflexive, because \(\exists 2 \in A\), \(2 \not\rrel 2\).
2. It is not irreflexive, because \(\exists 1 \in A\), \(1 \rrel 1\).

Remarks.

We have shown that a relation can be symmetric and antisymmetric at the same time. We also show that a relation can be reflexive and irreflexive at the same time. Therefore, when dealing with relations, do not assume any properties. Use the definitions to form a rigorous proof.

Prove: \(2^{A \cap B} = 2^A \cap 2^B\)

It is not difficult to see that:

$\begin{aligned} LHS &= 2^{A \cap B} &&\\ &= \{S : S \in 2^{A \cap B}\} &&\\ &= \{S : S \subseteq A \cap B\} && (\mbox{definition of power set})\\ \end{aligned}$ $\begin{aligned} RHS &= 2^A \cap 2^B &&\\ &= \{S : S \in 2^A \cap 2^B\} &&\\ &= \{S : S \in 2^A \land S \in 2^B\} && (\mbox{definition of set union})\\ &= \{S : S \subseteq A \land S \subseteq B\} && (\mbox{definition of power set}) \end{aligned}$

To proceed with the proof, we want to show that \(S \subseteq A \cap B\) iff \(S \subseteq A\) and \(S \subseteq B\).

(\(\Rightarrow\)) If \(S \subseteq A \cap B\), every element of \(S\) must be an element of \(A\) and \(B\) at the same time. Therefore, both \(S \subseteq A\) and \(S \subseteq B\) hold.

(\(\Leftarrow\)) If both \(S \subseteq A\) and \(S \subseteq B\) are true, then every element of \(S\) must be in \(A\) and \(B\) at the same time. Therefore, \(\forall x \in S\), \(x \in A \cap B\) holds, which indicates \(S \subseteq A \cap B\).

This allows us to write \(LHS=RHS\).

Prove/disprove: \(2^{A \cup B} = 2^A \cup 2^B\)

Using similar technique above, we have:

$\begin{aligned} LHS &= 2^{A \cup B} &&\\ &= \{S : S \in 2^{A \cup B}\} &&\\ &= \{S : S \subseteq A \cup B\} && (\mbox{definition of power set})\\ \end{aligned}$ $\begin{aligned} RHS &= 2^A \cup 2^B &&\\ &= \{S : S \in 2^A \cup 2^B\} &&\\ &= \{S : S \in 2^A \lor S \in 2^B\} && (\mbox{definition of set union})\\ &= \{S : S \subseteq A \lor S \subseteq B\} && (\mbox{definition of power set}) \end{aligned}$

Right now, we need to consider: is \(S \subseteq A \cup B\) equivalent to \(S \subseteq A \lor S \subseteq B\)? Definitely not! Suppose \(A = \{1, 2\}\), \(B = \{3, 4\}\) and \(S = \{2, 3\}\). Obviously \(S \subseteq A \cup B\) but \(A\) is not a subset of \(A\) nor a subset of \(B\). Therefore, this statement is false.

A more formal disproof can be formulated in this way:

Let \(A = \{1, 2\}\) and \(B = \{3, 4\}\). Then we have \(A \cup B = \{1, 2, 3, 4\}\), which means \(S = \{2, 3\} \in 2^{A \cup B}\). However, it is clear that \(S \notin 2^A\) and \(S \notin 2^B\), so \(S\) must not be a member of \(2^A \cup 2^B\). Therefore, these two sets are not equal.

Which of the following statements are true and which are false?

1. $\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, x \leq y$

   This is false. We can set \(x = 1\), \(y = 0\), then \(x \not\leq y\).

2. $\exists x \in \mathbb{Z}, \forall y \in \mathbb{Z}, x \leq y$

   This is false. No matter what value of \(x \in \mathbb{Z}\) we choose, we can always set \(y = x-1\) so that that \(x \not\leq y\).

3. $\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}, x \leq y$

   This is true. No matter what value of \(x\) is, we can always choose \(y = x + 1\) so that \(x \leq y\).

4. $\exists x \in \mathbb{Z}, \exists y \in \mathbb{Z}, x \leq y$

   This is true. We can choose \(x = 0\), \(y = 1\).

(In following propositions, suppose \(\mathbb{N} = \{0, 1, 2, \ldots\}\))

5. $\forall x \in \mathbb{N}, \forall y \in \mathbb{N}, x \leq y$

   This is false. We can set \(x = 1\), \(y = 0\), then \(x \not\leq y\).

6. $\exists x \in \mathbb{N}, \forall y \in \mathbb{N}, x \leq y$

   This is true. We can choose \(x = 0\), then it is less than or equal to all \(y \in \mathbb{N}\).

7. $\forall x \in \mathbb{N}, \exists y \in \mathbb{N}, x \leq y$

   This is true. No matter what value of \(x\) is, we can always choose \(y = x + 1\) so that \(x \leq y\).

8. $\exists x \in \mathbb{N}, \exists y \in \mathbb{N}, x \leq y$

   This is true. We can choose \(x = 0\), \(y = 1\).