1. What “Number of Relations” Means
A relation is any subset of a Cartesian product. So the total number of possible relations depends on how many ordered pairs exist in the product. Every pair can either be included or not included, which leads to a simple counting formula.
2. Counting Total Possible Relations
If A and B are two sets, and we form the Cartesian product A × B, then every ordered pair has two choices:
- Included in the relation
- Not included in the relation
This is why we use powers of 2 to count relations.
2.1. Formula
|A \times B| = |A| \cdot |B|
\text{Number of possible relations} = 2^{|A| \cdot |B|}
3. Example: Relation Between Two Sets
Let:
A = \{1,2\}, \quad B = \{x,y,z\}
Then:
|A| = 2, \; |B| = 3
|A \times B| = 6
So number of possible relations:
2^6 = 64
4. Number of Relations on a Single Set
If the relation is on one set A (meaning R ⊆ A × A), then the Cartesian product has |A|² ordered pairs.
4.1. Formula
\text{Number of relations on } A = 2^{|A|^2}
4.2. Example
If A = {a,b,c}, then:
|A| = 3
|A|^2 = 9
\text{Number of relations} = 2^9 = 512
5. Understanding What These Numbers Represent
These counts include every possible form of relation:
- Empty relation
- Universal relation
- All combinations of ordered pairs
Even though most of these relations may not satisfy special properties, they are all valid subsets of the product, so they are all counted.
6. Why Counting Matters
Knowing how many relations can exist helps understand how large the universe of possible relations is. This becomes important when studying special relations (like equivalence relations or partial orders), since these form only a tiny fraction of all possible relations.