6.1 Finite sets and their properties

Finite sets are the building blocks of set theory, helping us understand how to count and compare collections of objects. They're crucial for grasping more complex concepts in mathematics and computer science.

In this section, we'll explore the properties of finite sets, including cardinality, subsets, and power sets. We'll also dive into bijections and the pigeonhole principle, which are key tools for analyzing and comparing finite sets.

Finite Sets and Cardinality

Defining and Measuring Finite Sets

Top images from around the web for Defining and Measuring Finite Sets

• 

  Set Theory | Mathematics for the Liberal Arts View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

• 

  Set Theory | Mathematics for the Liberal Arts View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

1 of 2

Top images from around the web for Defining and Measuring Finite Sets

• 

  Set Theory | Mathematics for the Liberal Arts View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

• 

  Set Theory | Mathematics for the Liberal Arts View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

1 of 2

• A finite set contains a countable number of distinct elements
• The cardinality of a set, denoted as $|A|$, measures the number of elements in the set
  • For a finite set $A$, the cardinality is a non-negative integer (0, 1, 2, ...)
  • Example: If $A = \{a, b, c\}$, then $|A| = 3$
• The empty set, denoted as $\emptyset$ or $\{\}$, contains no elements
  • The cardinality of the empty set is 0, i.e., $|\emptyset| = 0$
• A singleton set contains exactly one element
  • Example: $\{a\}$ is a singleton set with cardinality 1

Properties of Finite Sets

• The union of two finite sets $A$ and $B$ is also a finite set
  • $|A \cup B| = |A| + |B| - |A \cap B|$
• The intersection of two finite sets $A$ and $B$ is a finite set
  • $|A \cap B| \leq \min(|A|, |B|)$
• The difference of two finite sets $A$ and $B$ is a finite set
  • $|A - B| = |A| - |A \cap B|$
• The Cartesian product of two finite sets $A$ and $B$ is a finite set
  • $|A \times B| = |A| \cdot |B|$

Subsets and Power Sets

Defining Subsets and Power Sets

• A set $A$ is a subset of set $B$, denoted as $A \subseteq B$, if every element of $A$ is also an element of $B$
  • Example: If $A = \{1, 2\}$ and $B = \{1, 2, 3\}$, then $A \subseteq B$
• The power set of a set $A$, denoted as $\mathcal{P}(A)$, is the set of all subsets of $A$
  • For a finite set $A$ with cardinality $|A| = n$, the cardinality of its power set is $|\mathcal{P}(A)| = 2^n$
  • Example: If $A = \{a, b\}$, then $\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$

Properties of Subsets and Power Sets

• The empty set is a subset of every set
  • $\emptyset \subseteq A$ for any set $A$
• Every set is a subset of itself
  • $A \subseteq A$ for any set $A$
• If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$ (transitivity)
• The power set of a set always contains the empty set and the set itself
  • $\emptyset \in \mathcal{P}(A)$ and $A \in \mathcal{P}(A)$ for any set $A$

Bijections and Counting Principles

Bijections and Their Applications

• A bijection is a one-to-one correspondence between the elements of two sets
  • A bijection from set $A$ to set $B$ implies that $|A| = |B|$
  • Example: The function $f(x) = 2x$ is a bijection from the set of non-negative integers to the set of even non-negative integers
• Bijections can be used to prove the equality of cardinalities between sets
  • If a bijection exists between sets $A$ and $B$, then $|A| = |B|$

The Pigeonhole Principle and Its Applications

• The pigeonhole principle states that if $n$ items are placed into $m$ containers, with $n > m$, then at least one container must contain more than one item
  • Example: If you have 10 pigeons and 9 pigeonholes, and all pigeons are placed in the holes, then at least one hole must contain more than one pigeon
• The pigeonhole principle can be used to prove the existence of certain elements or properties in sets
  • Example: In any group of 367 people, there must be at least two people who share the same birthday (assuming 366 possible birthdays, including February 29)
• The generalized pigeonhole principle states that if $n$ items are placed into $m$ containers, then at least one container must contain at least $\lceil \frac{n}{m} \rceil$ items
  • Example: If 20 items are placed into 6 containers, then at least one container must contain at least $\lceil \frac{20}{6} \rceil = 4$ items