# CIS-375 Help Session Note 2 (Spring 2020)

Scire ad trascendere - Learn to transcend.

Topics covered:

• Set-builder notation
• Set operations: union, intersection, set difference, symmetric difference
• Subset, power set
• Using Boolean logic to prove set-related propositions
• Logical quantifiers
• Relation

## Basic set theory

### Conventions of notations

Special sets:

• $$\mathbb{N}$$ the set of natural numbers: $$\{0, 1, 2, 3, \ldots\}$$1
• $$\mathbb{Z}$$ the set of integers: $$\{\ldots, -2, -1, 0, 1, 2, \ldots\}$$
• $$\mathbb{Q}$$ the set of rational numbers: $$Q = \{a/b \mid a, b \in \mathbb{Z}, b \neq 0 \}$$
• $$\mathbb{R}$$ the set of real numbers
• $$\mathbb{C}$$ the set of complex numbers
• $$\emptyset$$ empty set: $$\emptyset = \{\}$$

Reserved symbols:

• $$U$$: universal set

### Set-builder notation

Four ways to write set-builder notations:

Example: Toyota numbers

The following definitions of Toyota numbers are all equivalent:

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

### Cardinality

The cardinality of set $$A$$ (denoted by $$\lvert A \rvert$$) is the number of objects in the set. We also call $$\lvert A \rvert$$ the size of the set $$A$$.

### Subset

Suppose $$A$$ and $$B$$ are sets. We say that $$A$$ is a subset of $$B$$ provided every element of $$A$$ is also an element of $$B$$. The notation $$A \subseteq B$$ means $$A$$ is a subset of $$B$$.

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$$.

### Equality of sets

If two sets have exactly the same elements, they are said to be equal.

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.

### Power set

Let $$A$$ be a set. The power set of $$A$$ (denoted by $$2^A$$) is the set of all subsets of $$A$$.

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$$.

### Set operations

• Union: the union of $$A$$ and $$B$$ (denoted by $$A \cup B$$) is the set of elements that are in $$A$$ or $$B$$ (or both).
• Intersection: the intersection of $$A$$ and $$B$$ (denoted by $$A \cap B$$) is the set of elements that are in both $$A$$ and $$B$$.
• Difference: the difference of $$A$$ and $$B$$ (denoted by $$A - B$$) is the set of all elements of $$A$$ that are not in $$B$$. $$\newcommand{\symd}{\mathbin{\triangle}}$$
• Symmetric difference: the symmetric difference of $$A$$ and $$B$$ (denoted by $$A \symd B$$) is the set of elements in $$A$$ but not in $$B$$ or in $$B$$ but not in $$A$$. More concretely, $$A \symd B = (A - B) \cup (B - A)$$.
• Cartesian product: the Cartesian product of $$A$$ and $$B$$ (denoted by $$A \times B$$) is the set of all ordered pairs (two-element lists) formed by taking an element from A toghther with an element from $$B$$ in all possible ways.

Examples:

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

Important facts (try to prove them yourself):

Each operation in terms of set-builder notation:

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)$$.

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$$.

## Logical quantifiers

• Existential quantifier: $$\exists x \in A$$, assertions about $$x$$

Meaning: There exists $$x$$ in set $$A$$, such that the assertion holds.

• Universal quantifier: $$\forall x \in A$$, assertion about $$x$$

Meaning: For all $$x$$ in $$A$$, the assertion holds.

• Combination of quantifiers:

• $$\exists x \in A$$, $$\forall y \in B$$, assertion about $$x$$ and $$y$$: there exists an element $$x$$ in $$A$$, such that for all $$y \in B$$, the assertion holds.

• $$\forall x \in A$$, $$\exists y \in B$$, assertion about $$x$$ and $$y$$: for all $$x$$ in $$A$$, there exists $$y \in B$$, such that the assertion holds.

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.

## Relations

• A relation is a set of ordered pairs. $$\newcommand{\rrel}{\mathrel{R}}$$

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

$< ~ = \{(1, 2), (1, 3), (2, 3)\}.$
• $$x \rrel y$$ means $$x$$ is related to $$y$$ by relation $$R$$.

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

• Let $$R$$ be a relation and let $$A$$ and $$B$$ be sets. We say $$R$$ is a relation on $$A$$ provided $$R \subseteq A \times A$$, and we say R is a relation from $$A$$ to $$B$$ provided $$R \subseteq A \times B$$.
• Let $$R$$ be a relation. The inverse of $$R$$, denoted by $$R^{-1}$$, is the relation formed by reserving the order of all ordered pairs in $$R$$. In symbols, $$R^{-1} = \{(x, y) : (y, x) \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)

• Properties of relations:
• If $$\forall x \in A$$, we have $$x \rrel x$$, we call $$R$$ reflexive.
• If $$\forall x \in A$$, we have $$x \not\rrel x$$, we call $$R$$ irreflexive.
• If $$\forall x, y \in A$$, we have $$x \rrel y \rightarrow y \rrel x$$, we call $$R$$ symmetric.
• If $$\forall x, y \in A$$, we have $$(x \rrel y \land y \rrel x) \rightarrow x = y$$, we call $$R$$ antisymmetric.
• If $$\forall x, y, z \in A$$, we have $$(x \rrel y \land y \rrel z) \rightarrow x \rrel z$$, we call $$R$$ transitive.

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.

## Sample Q&A

Prove: $$2^{A \cap B} = 2^A \cap 2^B$$

It is not difficult to see that:

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:

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. This is false. We can set $$x = 1$$, $$y = 0$$, then $$x \not\leq y$$.

2. 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. This is true. No matter what value of $$x$$ is, we can always choose $$y = x + 1$$ so that $$x \leq y$$.

4. This is true. We can choose $$x = 0$$, $$y = 1$$.

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

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

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

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

9. This is true. We can choose $$x = 0$$, $$y = 1$$.

1. Sometimes it is defined excluding 0