Day 45 – Intro to Discrete Mathematics

Discrete mathematics 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.

Syllabus

Sets

• Set theory is a branch of mathematics that deals with properties of well-defined collection of objects.
• was introduced by George Cantor, a German mathematician.
• forms the basis of several other fields of studies, such as counting theory, relations, graph theory, and finite state machines.
• refer to a collection of any kind of objects: people, ideas or numbers.
• well-defined collection of any kind of objects.

Set E – set of positive even integers less than 10.

Set V – set of vowels in the English alphabet.

Set C – set of colors

Empty set – an empty set

Set Notation

Set of positive even integers less than 10:

E\,=\,\{2, 4, 6, 8\}

Set of vowels in the English alphabet:

V\,=\,\{a, e, i, o, u\}

Empty Set

Empty\,Set\,=\,\emptyset

It can also be presented with:

Empty\,Set\,=\,\{\}

A set is also an unordered collection of unique objects.

unordered and unique – the order of elements in a set is not important, and no duplicates are allowed in sets, then the following three sets are all the same.

These three sets are all the same (equal):

\{2,4,6,8\}\,=\,\{4,6,2,8\}\,=\,\{2,4,2,6,8,8\}

Notations

\in

• refer to elements of a set, or a member of a set

\notin

• refer to elements that are not in a set, or not a member of a set

Example:

E\,=\,\{2,6,4,8\}\\2\,\in\,E\\3\notin\,E

V\,=\,\{a,e,i,o,u\}\\a\,\in\,V\\s\,\notin\,V

Cardinality of a set

• the number of elements in a set. For example, the cardinality of set S is written as |S|.

Examples:

E\,=\,\{2,4,6,8\}\\E\,contains\,4\,elements:\\|E|\,=\,4

V\,=\,\{a,e,i,o,u\}\\V\,contains\,5\,elements:\\|V|\,=\,5

For empty set:

|\{\}|\,=\,|\empty|\,=\,0

Subset of a set

\subseteq

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\,\subseteq\,B

A\,=\,\{x,y,h,j\}\\B\,=\,\{b,f,r,x\}\\Therefore:\\A\,\subseteq\,B\,\iff\,x\,\in\,A\;then\;x\,\in\,B

Examples:

E\,=\,\{2,4,6,8\}\\\{2,6\}\,\subseteq\,E\\\{2,3\}\,\nsubseteq\,E

V\,=\,\{a,i,e,o,u\}\\\{a,i\}\,\subseteq\,V\\\{a,b\}\,\nsubseteq\,V

Empty set is a subset of any set.

Any subset is a subset of itself.

E\,=\,\{2,4,6,8\}\\\{2,4,6,8\}\,=\,E\\Therefore:\\E\,\subseteq\,E

Quick Review:

Natural Numbers – Natural numbers are only positive integers, excluding zero, fractions, decimals, or negative numbers, and they are part of real numbers. Natural numbers are also called counting numbers.

Integers – a whole number (not a fractional number) that can be positive, negative, or zero. Examples of integers are: -5, 1, 5, 8, 97, and 3,043. Examples of numbers that are not integers are: -1.43, 1 3/4, 3.14, .09, and 5,643.1.

Rational Numbers – A rational number is a number that is in the form of p/q, where p and q are integers, and q is not equal to 0. Some of the examples of rational numbers include 1/3, 2/4, 1/5, 9/3, and so on.

Difference between Integers and Real Numbers – Integers are a type of real number that just includes positive and negative whole numbers and natural numbers. Real numbers can include fractions due to rational and irrational numbers, but integers cannot include fractions.

There is an infinite number of real numbers between any two integers

The number 0 is neither positive nor negative integer, and finite.

The set of all integers contains all natural numbers.

The set of all rational numbers contains all integers.

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(integers) and b is not equal to 0)
• R = set of real numbers

N\,\subseteq\,Z\,\subseteq\,Q\,\subseteq\,R