Fundamental structures: Functions; relations pigeonhole principle

 

Fundamental Structures in Discrete Mathematics

Functions

A function is a relation between a set of inputs and a set of permissible outputs where each input is related to exactly one output. Formally, a function \( f \) from a set \( A \) to a set \( B \) (denoted \( f: A \to B \)) is defined such that for every \( a \in A \), there exists a unique \( b \in B \) such that \( f(a) = b \).

Functions can be classified into various types:

• Injective (One-to-One): A function \( f \) is injective if different inputs map to different outputs, i.e., if \( f(a_1) = f(a_2) \), then \( a_1 = a_2 \).
• Surjective (Onto): A function \( f \) is surjective if every element in the output set \( B \) is mapped by some element in the input set \( A \), i.e., for every \( b \in B \), there exists an \( a \in A \) such that \( f(a) = b \).
• Bijective: A function is bijective if it is both injective and surjective. Bijective functions have an inverse function.

Relations (Specifically Recursions)

A relation on a set is a way of describing a connection between elements of the set. A specific type of relation is a recursion, which defines elements in terms of other elements of the same set.

Recursion is a fundamental concept in computer science and mathematics where a function calls itself to solve smaller instances of the same problem. For example, the Fibonacci sequence is defined recursively:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1

This recursive definition expresses each term as a function of its preceding terms.

Pigeonhole Principle

The Pigeonhole Principle states that if \( n \) items are put into \( m \) containers and \( n > m \), then at least one container must contain more than one item. This principle is simple yet powerful and is used to prove various results in combinatorics and other fields.

For example, if there are 13 people in a room, at least two of them must have been born in the same month since there are only 12 months in a year.

Cardinality and Countability

Cardinality refers to the number of elements in a set. Two sets have the same cardinality if there is a one-to-one correspondence between the elements of the sets. Countability distinguishes between finite sets, countably infinite sets, and uncountably infinite sets.

• Finite Set: A set with a limited number of elements.
• Countably Infinite Set: A set with the same cardinality as the set of natural numbers. Examples include the set of integers and the set of rational numbers.
• Uncountably Infinite Set: A set with a greater cardinality than the set of natural numbers. The set of real numbers is an example of an uncountably infinite set.

Probabilistic Methods

Probabilistic methods involve using probability theory to solve problems in discrete mathematics. These methods are often used to prove the existence of a certain structure within a set, even if the structure cannot be explicitly constructed.

An example of a probabilistic method is the probabilistic proof of the existence of a graph with certain properties. By randomly constructing a graph and calculating the probability that it has the desired properties, one can often show that such a graph must exist.

Conclusion

Understanding the fundamental structures of functions, relations (specifically recursions), the Pigeonhole Principle, cardinality and countability, and probabilistic methods is crucial in discrete mathematics. These concepts provide the foundation for more advanced topics and have wide-ranging applications in computer science, mathematics, and related fields.