If well-founded induction holds, then the relation $\to$ on a reduction system terminates
Well-founded induction, like all other forms of induction, holds for any predicate $P$. That can mean two different things:


Well-founded induction holds for every predicate which you can express in your formal system.
Well-founded induction holds for every subset $P \subseteq A$.


Either way, informally speaking you can define $P$ to be whatever you want. 

Formally speaking, you might run into set-theoretic issues, those that separate naive (or elementary) set theory from axiomatic set theory. But presumably this is not the focus of the book, so you can just ignore such issues.

(The gap is that in case 1, you need to show how to express $P$, and in case 2, you need to show that the set $\{x \in A : \text{there exists no infinite chain starting at $x$}\}$ exists.)