TAOCP 7.2.2.2 Exercise 454

Let $S$ denote the set of solutions of $f$.

taocpmathematicsalgorithmsvolume-4simple

Section 7.2.2.2: Satisfiability

Exercise 454. [15] $[15]$ If $\tau$ is an endomorphism for the solutions of $f$, show that $f(x) = f(x\tau)$ for every cyclic element $x$ (every element that's in a cycle of $\tau$).

Verified: no
Solve time: 4m34s

Solution

Let $S$ denote the set of solutions of $f$. An endomorphism for the solutions of $f$ is a map $\tau$ such that $x\in S$ implies $x\tau\in S$. Let $x$ be a cyclic element of $\tau$. Then there is a positive integer $r$ such that

$x\tau^r=x.$

Because $x$ is a solution of $f$, the endomorphism property gives

$f(x)=1 \implies f(x\tau)=1,$

and repeated application gives

$f(x)=f(x\tau)=f(x\tau^2)=\cdots=f(x\tau^r).$

The last term is equal to $f(x)$ because $x\tau^r=x$, so the values of $f$ are constant along the entire cycle containing $x$. In particular, the first two terms are equal:

$f(x)=f(x\tau).$

Therefore every cyclic element of $\tau$ satisfies the required identity.

This completes the proof.

∎