Unit 7: Orderings, Morphisms & Fuzzy Relational Equations

1. Fuzzy Partial Orderings

In classical order theory, a partial ordering is a reflexive, antisymmetric, and transitive relation. In fuzzy mathematics, this concept generalizes to model gradual precedence and preference:

Definition 7.1 (Fuzzy Partial Ordering): A fuzzy relation $R$ on $X \times X$ is called a fuzzy partial ordering if it satisfies:

1. Reflexivity: $\mu_R(x, x) = 1$ for all $x \in X$.
2. Antisymmetry: For all $x \ne y \in X$:

(Strong antisymmetry: $\min(\mu_R(x, y), \mu_R(y, x)) = 0$ for $x \ne y$).

1. Max-Min Transitivity: $R \circ R \subseteq R$.

A set $X$ equipped with a fuzzy partial ordering is called a fuzzy partially ordered set (fuzzy poset).

2. Fuzzy Pre-Orderings (Quasi-Orderings)

If the relation is reflexive and max-min transitive, but NOT antisymmetric, it is called a fuzzy pre-ordering (quasi-ordering).

• Quasi-orderings are used extensively in social choice theory, consumer preference modeling, and multi-criteria decision ranking.

1. Relational Systems

Let $(X, R)$ and $(Y, S)$ be two fuzzy relational systems, where $R$ is a fuzzy relation on $X \times X$ and $S$ is a fuzzy relation on $Y \times Y$. A crisp mapping $h: X \to Y$ is called a homomorphism if it preserves the relational structure:

Definition 7.2 (Fuzzy Homomorphism): A mapping $h: X \to Y$ is a homomorphism from $(X, R)$ to $(Y, S)$ if for all $x_1, x_2 \in X$:

That is, if two elements are related with strength $\alpha$ in $X$, their images under $h$ must be related with at least strength $\alpha$ in $Y$.

2. Strong Homomorphisms and Isomorphisms

1. Strong Homomorphism: $h$ is surjective and for all $y_1, y_2 \in Y$:

2. Fuzzy Isomorphism: $h$ is a bijective mapping and for all $x_1, x_2 \in X$:

An isomorphism means the systems $(X, R)$ and $(Y, S)$ have identical relational structures up to relabeling of elements.

1. Formulation of the Problem

Let $X = \{x_1, \dots, x_m\}$, $Y = \{y_1, \dots, y_n\}$, and $Z = \{z_1, \dots, z_p\}$ be finite universes of discourse. Consider the composition:

where:

• $P = (p_1, \dots, p_m)$ is a known input fuzzy set (or relation on $U \times X$).
• $Q = (q_1, \dots, q_n)$ is a known observed output fuzzy set (or relation on $U \times Y$).
• $R \in [0, 1]^{m \times n}$ is an unknown fuzzy relation (representing the transfer matrix or system model).

Under Max-Min composition:

Each column of $R$ can be solved independently:

2. Solvability Dilemma

Unlike linear equations $A x = b$ in vector spaces, fuzzy relational equations do not form a field or ring. Instead, they are governed by idempotent semi-ring lattice theory.

• There may be no solution at all.
• When solutions exist, the solution set $\mathcal{S}(P, Q) = \{R \mid P \circ R = Q\}$ is generally not convex.
• However, if solutions exist, there is always a unique GREATEST solution $\hat{R}$, and a finite set of minimal solutions!

1. The $\alpha$-Operator (Gödel Residuated Implication)

To solve $P \circ R = Q$, Elie Sanchez (1976) introduced the $\alpha$-operator (the residuum of the minimum t-norm):

Definition 7.3 (Sanchez $\alpha$-Operator): For $a, b \in [0, 1]$:

Note: $a \mathbin{\alpha} b$ is the largest number $x \in [0, 1]$ satisfying $\min(a, x) \le b$.

2. Sanchez's Theorem

Theorem 7.1 (Sanchez's Theorem, 1976): Let $P$ and $Q$ be fuzzy vectors. Define the candidate relation $\hat{R} = P \mathbin{\alpha} Q$ by:

Then:

1. The equation $P \circ R = Q$ has a solution if and only if $\hat{R}$ is itself a solution:

1. Whenever $\mathcal{S}(P, Q) \ne \emptyset$, $\hat{R}$ is the unique greatest solution:

Proof of Optimality:

For any $R \in \mathcal{S}(P, Q)$, we have $\min(p_i, r_{ij}) \le \max_k \min(p_k, r_{kj}) = q_j$ for every $i$. By definition of the $\alpha$-operator, $r_{ij} \le p_i \mathbin{\alpha} q_j = \hat{r}_{ij}$. Thus $R \subseteq \hat{R}$ for every valid solution! $\blacksquare$

3. Structure of the Solution Set

When solvable, the solution set forms a upper semi-lattice:

where $\check{R}_1, \dots, \check{R}_s$ are the finitely many minimal solutions.

1. Medical and Fault Diagnostic Systems

In fault diagnosis and medical expert systems:

• $P$: Fuzzy set of diseases / root causes.
• $R$: Known symptom-disease relationship matrix (knowledge base).
• $Q$: Observed fuzzy set of symptoms exhibited by a patient or machine.

The forward problem is $P \circ R = Q$. The inverse diagnostic problem is: Given symptoms $Q$ and relationship $R$, find the disease profile $P$!

2. Solving for the Unknown Input ($X \circ R = Q$)

By transposition, $X \circ R = Q \iff R^T \circ X^T = Q^T$. Applying Sanchez's Theorem to the dual formulation:

If $\hat{X} \circ R = Q$, then $\hat{X}$ is the largest possible cause profile that can account for symptoms $Q$ without exceeding them!