Definitions

Make sure to know what these mean!

$\mathbb{B} = $ Boolean Values
$\mathbb{N} = $ Natural Numbers
$\mathbb{Z} = $ Integers
$\mathbb{R} = $ Real Numbers
$\mathbb{W} = $ Whole Numbers
$\mathbb{C} = $ Complex Numbers
$\mathbb{Q} = $ Rational Numbers
$\mathbb{R} - \mathbb{Q} = $ Irrational Numbers
$\mid \: \text{or} : \:= $ such that
$\in \: = $ 'is an element of' or 'inside of'

Set Definitions

Set - a collection of distinct elements where order does not matter

Empty Set - a set containing no elements, represented by $\emptyset$

Member - an element contained in a set

Set Equality - sets are equal if every element of $A$ is a member of $B$, and vice versa

Subset - $A$ is a subset of $B$ if every element of $A$ is also an element of $B$, represented by $A \subseteq B$

Cardinality - a measure of a sets size, it is the number of distinct elements in a set

Disjoint Sets - two sets with no elements in common

Union - a set that contains elements in $A$ or $B$, represented by $A \cup B$

Intersection - a set that contains elements in $A$ and $B$, represented by $A \cap B$

Difference - a set that contains elements in $A$ which are not in $B$, represented by $A \setminus B$

Power Sets - the power set of $A$, represented by $\mathcal{Pow}(A)$, is the set that contains all the subsets of $A$, or $\mathcal{Pow}(A) = \{S \mid S \subseteq A\}$

Relation Definitions

Pair - contains component a and b and is denoted by $(a, b)$, two pairs $(a, b) \: \text{and} \: (c, d)$ are equal iff "if and only if" $a = c \: \text{and} \: b = d$ order matters for pairs

Tuples (n-Tuples) - is a pair of n components, a pair is a 2-tuple, tuples take the form $(a_1, a_2, \dots, a_n)$

Cartesian Product - represented by $A \times B$, gives the set of all pairs whose first component is from set $A$, and whose second component is from set $B$

Relation (n-ary relation) - subset of n-product, represented by $R \subseteq A_1 \times \dots \times A_n$

Binary Relation - if we are finding the cartesian product for two sets then we have a binary relation, represented as $R \subseteq A_1 \times A_2$

Relations on a set - if $A_1 = A_2 = A$ then we have a relation on $A$, that is $R \subseteq A \times A$, we shorten 'set of a relation' into $R$ (not to be confused with $\mathbb{R}$)

Reflexive - if every node forms a loop then we have a reflexive relation on $A$, if for any $a \in A$ we have $(a, a) \in R$

Symmetric - if every pair in the relation has an 'inverse', if elements $a, b \in A$, and if we have $(a, b) \in R$ then we also need to have $(b, a) \in R$

Transitive - if every connected pair has a 'shortcut', if elements $a, b, c \in A$ and we have $(a, b) \in R$ and $(b, c) \in R$, then we must also have $(a, c) \in R$ for our relation or $R$ to be transitive

Closures - the relation we obtain by adding the minimum number of ordered pairs to $R$ to get the property of the relation (Reflexive, Symmetric, Transitive)

Equivalence Relations - $R$ is an equivalence relation if it is Reflexive, Symmetric, and Transitive at the same time

Sets

Sets Introduction

Sets are unordered collection of elements, we represent sets with capital letters $A, B, \dots$

Set example:

$A = \{0, 1, 2, 3, 4\}$

$B = \{\text{January, February, March,} \dots \}$

$C = \{\frac{1}{2}, \frac{2}{3}, \frac{5}{4}, \dots\}$

$\emptyset = \text{an empty set}$

We can't represent all sets by listing them out explicitly, hence we use
Set Comperehension Notation

Note: 0 is usually a part of $\mathbb{W}$ not $\mathbb{N}$, however as per CSCI 1315 we will consider 0 as part of $\mathbb{N}$

if we have $\{0, 1, 2, 3, 4, \dots\}$ which is the set of natural numbers $\mathbb{N}$ we can represent this in set notation as $\{x \mid x \in \mathbb{N}\}$

Set notation example:

$\Bigl\{0, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}\Bigl\} \: = \Bigl\{\frac{a}{b} \in \mathbb{Q} \mid a \in \{0, 1\} \: \text{and} \: b \in \{3, 4, 5\}\Bigl\}$

$\Bigl\{\dots, -9, -4, -1, \;0, \;1, \;4, \;9, \dots\Bigl\} \: = \{\pm \: x^2 \mid x \in \mathbb{Z}\}$

Set Equality
Two sets are considered equal if all the elements of set $A$ are also a part of set $B$ and vice versa.

Equality examples:

$\{1, 2, 3\} = \{3, 1, 2, 2, 3\}$

$\{\emptyset, \{\}, 1\} = \{1, \emptyset, \emptyset\}$

$\{5, \{\}, 4, 2\}$ $ \neq$ Show Answer $\{5, \{\emptyset, 4\}, 2\}$

Subsets There are two types of subsets:

'Improper' subset: denoted by $A \subseteq B$, if every element of $A$ is also an element of $B$

Proper subset: denoted by $A \subset B$, if every element of $A$ is also an element of $B$ and $A \neq B$

Subset example:

$\{1, 2, 3\} \subseteq \{1, 2, 3\}$

$\{1\} \not\subseteq \Bigl\{\{1\}, 2, 3, 4\Bigl\}$

$\{a, b\} \subset \{a, b, c\}$

$\emptyset \subset \text{non-empty sets}$

The number of distinct elements inside a set indicates its size, we call this
Cardinality, denoted by $\vert A \vert$

Cardinality example:

$A = \{\emptyset, \emptyset, \emptyset\}, \text{then } \vert A \vert = 1$

$B = \{2, 4, 6, 8, 10\}, \text{then } \vert B \vert = 5$

$C = \biggl\{\emptyset, \Bigl\{1, \{2, 3\}, 4\Bigl\}, 5, 6\biggl\}, \text{then } \vert C \vert = 4$

$D = \emptyset, \text{then } \vert D \vert = 0$

Set operation

Using our knowledge of sets we can now perform set operations

Operators

Union: denoted by $A \cup B$, gives the set which contains the elements in $A$ or $B$

Intersection: denoted by $A \cap B$, gives the set which contains the elements in $A$ and $B$

Difference: denoted by $A \setminus B$, gives the set which contains elements in $A$ that are not in $B$

Power Set: denoted by $\mathcal{Pow}(A)$, the set which contains all subsets of $A$, Note: the empty set and the entire set are part of the set of subsets!

Operations example:

$\{1, 2, 3\} \cup \{1, 4, 5, 6\} = \{1, 2, 3, 4, 5, 6\}$

$\Bigl\{4, 5, \{8, 2\}\Bigl\} \: \cap \: \Bigl\{\{8, 2\}, 5\Bigl\} \: = \Bigl\{\{8, 2\}, 5\Bigl\}$

$\{1, 2, 4, 8, 16\} \setminus \{0, 1, 2\} = \{4, 8, 16\}$

$\mathcal{Pow}\Bigl(\{1, \emptyset, \mathbb{N}\}\Bigl) = \Bigl\{\emptyset, \{1\}, \{\emptyset\}, \{\mathbb{N}\}, \{1, \emptyset\}, \{1, \mathbb{N}\}, \{\emptyset, \mathbb{N}\}, \{1, \emptyset, \mathbb{N}\} \Bigl\}$

$\pmb{\textit{Given}} \: A = \{5, 7, 9\} \text{, } \: B = \{1, 4, 9, 25\} \: \text{and} \: C = \{1, 7, 6, 25\}$

$C \setminus ( B \cap ( A \cup C ) ) = $ $\{7, 6\}$ Show Answer

$\mathcal{Pow}\Bigl(\{1, 2, 3\}\Bigl) =$ $\Bigl\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \Bigl\}$ Show Answer

Relations

Relations Introduction

Pair - a pair of components $(a, b)$, order matters for pairs, $(a, b) $ and $ (c, d)$ are equal iff "if and only if" $a = c$ and $b = d$

Tuples - a pair of n components, a standard pair is a 2-tuple, tuples take the form $(a_1, a_2, \dots, a_n)$

Pairs and Tuples example:

$(a, b) \neq (b, a)$

$(1, 3) = (1, 3)$

$(a_1, a_2, \dots, a_n)$

Cartesian Product

denoted by $A \times B$, is the set of all pairs where the first component is from $A$, and the second component is from $B$

Cartesian Product example:

$A \times B = \{(a, b) \mid a \in A, b \in B\}$

$\{b, c, d\} \times \{e, f\} = \{(b, e), (b, f), (c, e), (c, f), (d, e), (d,f)\}$

$\{A, B\}^2 =$ $\{(A, A), (A, B), (B, A), (B, B)\}$ Show Answer

n-Products

just like cartesian products but instead we are multiplying multiple sets together, that is $A \times B \times C$

n-Product example:

$A_1 \times A_2 \times \dots \times A_n = \{(a_1, \dots, a_n) \mid a_1 \in A_1, \dots, a_n \in A_n\}$

$\{a, b\} \times \{1, 2\} \times \{A\} = \{(a, 1, A), (a, 2, A), (b, 1, A), (b, 2, A)\}$

Discrete Math

Sets, Relations, and Functions!