research-relations-functions

1. Total Number of Relations on a Set

Given a set $A$ with $n$ elements, the total number of binary relations that can be defined on $A$ is based on all possible ordered pairs $(a,b)$ where $a,b\in A$.

• The number of possible ordered pairs in $A\times A$ is $n^2$.
• Each pair can either be included or excluded from the relation, giving us 2 choices for each pair.

Thus, the total number of relations on a set $A$ with $n$ elements is:

$2^{n^2}$

2. Number of Reflexive Relations

A relation is reflexive if it includes all the pairs $(a,a)$ for each element $a\in A$. This means that the $n$ diagonal elements $(a,a)$ are fixed and must be included in the relation.

• The remaining $n(n-1)$ pairs (off-diagonal pairs) can either be included or excluded independently.

Therefore, the number of reflexive relations on a set $A$ with $n$ elements is:

$$2^{n(n-1)}$$

3. Number of Symmetric Relations

A relation is symmetric if, for every pair $(a,b)$ in the relation, the reverse pair $(b,a)$ must also be included. For each pair of distinct elements $a\ne b$, we have two choices: either include both $(a,b)$ and $(b,a)$, or exclude both.

• The number of distinct unordered pairs is $n(n-1)/2$.
• Each unordered pair gives us 2 choices (include both or exclude both).
• Diagonal pairs $(a,a)$ can independently be included or excluded.

Thus, the number of symmetric relations on a set $A$ with $n$ elements is:

$$2^{n(n+1)/2}$$

4. Number of Reflexive and Symmetric Relations

A relation that is both reflexive and symmetric must include:

1. All diagonal pairs $(a,a)$ (due to reflexivity).
2. For each unordered pair of distinct elements $(a,b)$, either both $(a,b)$ and $(b,a)$ are included or both are excluded (due to symmetry).

• The number of choices for unordered pairs of distinct elements is $n(n-1)/2$.

Thus, the number of reflexive and symmetric relations on a set $A$ with $n$ elements is:

$$2^{n(n-1)/2}$$

5. Number of Transitive Relations

A relation is transitive if, whenever $(a,b)\in R$ and $(b,c)\in R$, it follows that $(a,c)\in R$. This property creates dependencies between multiple pairs, making it more complicated to count transitive relations. There is no simple closed-form formula for counting transitive relations.

• Transitive relations are typically counted using algorithms, as they involve dependencies between different pairs in the relation.

6. Combining Properties Using Set Operations

When you want to count the number of relations that satisfy combinations of properties like reflexivity, symmetry, and transitivity, you use set operations (intersection for “and”, union for “or”).

Intersection (“And”)

If you’re asked to find the number of relations that satisfy both properties (like reflexive and symmetric), you count the relations that satisfy both conditions.

For example, for reflexive and symmetric relations:

$$2^{n(n-1)/2}$$

Union (“Or”)

To find the number of relations that satisfy either property (like reflexive or symmetric), use the inclusion-exclusion principle:

$$|S\cup T|=|S|+|T|-|S\cap T|$$

where $S$ is the set of relations that are symmetric, and $T$ is the set of relations that are reflexive. This formula avoids double-counting relations that satisfy both properties.

For Three Properties

If you are combining three properties (like reflexive, symmetric, and transitive), the inclusion-exclusion principle becomes:

$$|S\cup T\cup R|=|S|+|T|+|R|-|S\cap T|-|S\cap R|-|T\cap R|+|S\cap T\cap R|$$

where:

• $S$ is the set of symmetric relations.
• $T$ is the set of transitive relations.
• $R$ is the set of reflexive relations.

7. Algorithm for Counting Non-Transitive Relations

When asked to find relations that are not transitive (or that violate some property), you need to construct relations that fail to satisfy the transitive condition.

Example Algorithmic Process:

1. Generate all reflexive and symmetric relations on the set.
2. Test each relation for transitivity: Check whether, for all pairs $(a,b)\in R$ and $(b,c)\in R$, the pair $(a,c)$ is also in the relation.
3. Exclude transitive relations and count only those that fail the transitivity test.

Conclusion

• The total number of relations on a set $A$ with $n$ elements is $2^{n^2}$.
• Reflexive relations, symmetric relations, and reflexive + symmetric relations have simple formulas that depend on the number of choices for pairs.
• Transitive relations require algorithmic methods for exact counting.
• Combining properties uses set operations like union and intersection, along with the inclusion-exclusion principle for avoiding double-counting.

1. Basic Concepts of Relations

• A relation on a set ( A ) is a set of ordered pairs $(a,b)$, where both $a$ and $b$ are elements of $A$.
• For a set $A$ with $n$ elements, the total number of ordered pairs is $n^2$, and the total number of possible relations is:

$$2^{n^2}$$

2. Reflexive Relations

• A relation is reflexive if every element relates to itself. This means all diagonal pairs $(a,a)$ must be in the relation.
• The number of reflexive relations for a set of $n$ elements can be calculated by including all diagonal pairs and considering the remaining $n(n-1)$ off-diagonal pairs, each of which can either be included or not:

$$2^{n(n-1)}$$

3. Symmetric Relations

• A relation is symmetric if for every pair $(a,b)\in R$, the reverse pair $(b,a)$ is also in the relation.
• For symmetric relations, you make decisions for unordered pairs $(a,b)$ where $a\ne b$. There are $n(n-1)/2$ such pairs.
• Each unordered pair can either be included or excluded, and the number of symmetric relations is:

$$2^{n(n+1)/2}$$

4. Transitive Relations

• A relation is transitive if whenever $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)$ must also be in $R$.
• There is no simple formula for counting transitive relations because it depends on the relationships between multiple pairs.

5. Combining Reflexivity and Symmetry

• A relation that is both reflexive and symmetric must satisfy both properties:

  1. Reflexivity forces all diagonal elements $(a,a)$ to be included.
  2. Symmetry forces that for any $(a,b)$, both $(a,b)$ and $(b,a)$ must be included or excluded together.

• The number of reflexive and symmetric relations is:

$$2^{n(n-1)/2}$$

6. Combinations of Properties

Intersection (“And”)

• To find relations that are both symmetric and transitive, or reflexive and symmetric, etc., we take the intersection of these sets.

  For example, to find symmetric and reflexive relations, use:

$$2^{n(n-1)/2}$$

Union (“Or”)

• To count relations that satisfy either symmetric or transitive (or both), use the inclusion-exclusion principle:

$$|S\cup T|=|S|+|T|-|S\cap T|$$

where $S$ is the set of symmetric relations and $T$ is the set of transitive relations.

For Three Properties

• The inclusion-exclusion principle extends to three sets for counting relations that are either symmetric, transitive, or reflexive:

$$|S\cup T\cup R|=|S|+|T|+|R|-|S\cap T|-|S\cap R|-|T\cap R|+|S\cap T\cap R|$$

7. Algorithm for Excluding Transitivity

• To exclude transitive relations, you need to ensure the relation violates the transitive condition. Specifically, check that for $(a,b)\in R$ and $(b,c)\in R$, the pair $(a,c)$ is not in the relation.

Example Process

1. Generate all reflexive and symmetric relations.
2. For each relation, check the transitivity condition and exclude those that satisfy it.

Summary of Steps

1. Find the reflexive and symmetric relations using the formula $2^{n(n-1)/2}$.
2. Fix the specific elements that are required to be in the relation.
3. Check for transitivity and exclude transitive relations using an algorithm.
4. Use inclusion-exclusion to count relations that satisfy combinations of properties (like symmetric or transitive).

8. Specific Case: Reflexive and Symmetric but Not Transitive

e

• To find relations that are reflexive, symmetric, but not transitive, first find the reflexive and symmetric relations using:

$$2^{n(n-1)/2}$$

• Then exclude the transitive ones by testing the transitive property for each relation. This can be done using an algorithmic approach to check if $(a,b)\in R$ and $(b,c)\in R$, but $(a,c)\notin R$.