Discrete Mathematics - Week 1 - Summary

Definition of Discrete Mathematics

* It is the study of discrete objects, which are different from connected objects
* Discrete objects are those which are separated or distant from each other. Such as integers, rational numbers, houses, people, etc
* Course is concerned with objects such as integers, propositions, sets, relations, and functions, which are all discrete
* We will learn concepts associated with them, their properties, and relationships among them
* It's being applied to the practical fields of mathematics and CS
* Improves reasoning and problem-solving capabilities

The definition of a set

* Set theory branch of mathematics that deals with the properties of well-defined collections of objects.
* Set theory forms the basis of several other fields of study such as counting theory, relations, graph theory and finite state machines.

What is a set

Mathematicians use the term set to refer to a collection of any kind of objects: people, ideas, or numbers, for example. A set is a well-defined collection of any kind of objects.

A =  { 2, 4, 6, 8 } // set of positive even integers less than 10
V = { a', 'e', 'i', 'o', 'u' } // set of vowels in English alphabet
E = {} // empty set, or Ø

Definition: A set is an unordered collection of unique objects (in Portuguese, "conjuntos")

Set notation: element of a set

∈ AKA "element of": used to refer to elements of a set
∉ AKA "not element of": used to refer to elements that are not in a set

Examples:

A = {2,4,6,8}
2 ∈ A
3 ∉ A

Set notation: cardinality of a set

Definition: Given a set S, the cardinality of S is the number of elements contained in S. We write the cardinality of S as | S |

> Note: think of it as new Set().size

Examples:

A = { 2,4,6,8 }
A contains 4 elements, hence, | A | = 4

E = {}
| {} | = | Ø | = 0

Set notation: subset of a set

Definition: A is said to be a subset of B if and only if every element of A is also an element of B. In this case we write A ⊆ B

That is, we have the equivalence:

A ⊆ B <-> if x ∈ A then x ∈ B (for all x)

Examples:

A = { 2,4,6,8 }
{ 2,6 } ⊆ A
{ 2,3 } ⊄ A

Note: An empty set is a subset of any set (Ø ⊆ S)

Example:
A = { 2,4,6,8 }
{} = Ø ⊆ A

Note2: Also Ø ⊆ Ø

Note3: Any set is a subset of itself (S ⊆ S)

Special sets: N, Z, Q, R

* N = set of natural numbers = {1,2,3,4,...}
* Z = set of integers {..., -3,-2,-1,0,1,2,3,... }
* Q = set of rational numbers (of form a/b where a and b are elements of Z and b != 0)
* R = set of real numbers

N ⊆ Z ⊆ Q ⊆ R

Representing a set: The listing method and rule of inclusion

Listing method

Description:
* S1 = set of all vowels in the English alphabet
* S1 = { a,e,i,o,u }

Builder notation (also called the rules of inclusion)

Assume we want to describe the set of all odd integers

Odd = { 2n+1 | n ∈ Z }

Example:

Thee set of things in my bag:
Bag = { pen, book, laptop, ... }

Can be transformed into

Bag = { x | x is in my bag }

Practical example:

Rewrite the following sets using the listing method:

S1 = { 3n | n ∈ N and n < 6 } -> S1 = { 3*1, 3*2, 3*3, 3*4, 3*5 } -> S1 = { 3,6,9,12,15 }

The powerset of a set

Recap: subsets

A set can have another set as its element
A = { 1,2,3,4,5,6,7,8,9 }
B = { {2,3,4,5}, {5,6}, {7,8,9}}

{ 5,6 } ⊆ A
{ 7,8, 9} ⊆ A

{ 5,6 } ∈ B
{ 7,8,9 } ∈ B

Definition of a powerset of a set

Definition: given the set S, the powerset of S, P(S), is the set containing all the subsets of S.

Example:

Given a set S = {1,2,3}

The subsets of S are:

Ø,{1},{2},{3},
{1,2},{1,3},{2,3},
{1,2,3}

P(S) = {Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

P(Ø) = { Ø }; then

Ø ⊆ Ø
Ø ⊆ P(Ø)
{Ø} ⊆ P(Ø)
P(P(Ø)) = { Ø, {Ø}}

Cardinality of a powerset of a set

Note: Question could be asking about the number of subsets which can be formed from A. Same rule applies.

Given a set S, then |P(S)| = 2^|S|

Example:

S={1,2,3}. |S| = 3

P(S) = { Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {123}}

| P(S) | = 8 = 2^3  = 2^|S|