$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

1.1: An Overview of Discrete Mathematics

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

What is discrete mathematics? Roughly speaking, it is the study of discrete objects. Here, discrete means “containing distinct or unconnected elements.” Examples include:

• Determining whether a mathematical argument is logically correct.
• Studying the relationship between finite sets.
• Counting the number of ways to arrange objects in a certain pattern.
• Analyzing processes that involve a finite number of steps.

Here are a few reasons why we study discrete mathematics:

• To develop our ability to understand and create mathematical arguments.
• To provide the mathematical foundation for advanced mathematics and computer science courses.

In this text, we will cover these six topics:

1. Logic and Proof Techniques: Logic allows us to determine if a certain argument is valid. We will also learn several basic proof techniques.
2. Basic Number Theory: Number theory is one of the oldest branches of mathematics; it studies properties of integers. We will use the proof techniques we learned to prove some basic facts in number theory.
3. Sets: We study the fundamental properties of sets, and again we will use the proof techniques we learned to prove important results in set theory.
4. Relations and Functions: Relations and functions describe the relationship between the elements from two sets. They play a key role in mathematics.
5. Combinatorics: Combinatorics studies the arrangement of objects. For instance, one may ask, in how many ways can we form a five-letter word. It is used in many disciplines beyond mathematics.
6. Big O:  A stand-alone topic on growth of functions.

All of these topics are crucial in the development of your mathematical maturity. The importance of some of these concepts may not be apparent at the beginning. As time goes on, you will slowly understand why we cover such topics. In fact, you may not fully appreciate the subjects until you start taking advanced courses in mathematics.

This is a very challenging course partly because of its intensity. We have to cover many topics that appear totally unrelated at first. This is also the first time many students have to study mathematics in depth. You will be asked to write up your mathematical argument clearly, precisely, and rigorously, which is a new experience for most of you.

Learning how to think mathematically is far more important than knowing how to do all the computations. Consequently, the principal objective of this course is to help you develop the analytic skills you need to learn mathematics. To achieve this goal, we will show you the motivation behind the ideas, explain the results, and dissect why some solution methods work while others do not.