## 2.4 Outline

- Infinite sets
- finite
- infinite
- one-to-one
- correspondence
- countable/uncountable
- rational numbers are countable
- real numbers are uncountable

- Cartesian product of sets
- definition
- cardinality of a Cartesian product
- fundamental counting principle

## 2.4 Essential Ideas

**One-to-one Correspondence**

Two sets *A* and *B* are said to be in a **one-to-one correspondence** if we can find a pairing so that: (1) Each element of *A* is paired with precisely one element of *B *; and (2) Each element of *B* is paired with precisely one element of *A*.

**Finite and Infinite**

A set is **infinite** if it can be placed in a one-to-one correspondence with a proper subset of itself. A set is **finite** if it is not infinite.

**Fundamental Counting Principle**

If task *A* can be performed in *m* ways, and after task *A* is performed, a second task *B *can be performed in *n *different ways, then the **fundamental counting principle** is that task *A* followed by task *B* can be performed in *mn *different ways.