Uniqueness of solution in Arden's theorem

Question

Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below.

My question is:

What is the logical reasoning to prove that any equation is the unique (only solution)? Particularly in this case, how can the procedure below logically lead to the proof that R=QP* must be the unique (only solution)?

Here is my understanding of the proof:

1. Recursively substitute $R$ in $R=Q+RP$ with $Q+RP$
2. Establish the recursive definition of $R$
3. Generalize the definition to $R=QP^*$

Disclaimer: The proof below is second part of a 2-parts proof from the original Geeksforgeeks's proof of Arden’s Theorem. Originally, the proof starts out to prove $R=QP^*$ is a solution to $R=Q+RP$. I omitted this part here because I want to focus on the second part of the proof, which is to prove uniqueness. However, to clear any confusions, please allow the proof below to be based on the assumption that $R=QP^*$ is a solution to $R=Q+RP$ has been correctly proven prior and that $R=QP^*$ can be used as a corollary for proof below, which try to prove $R=QP^*$ is the unique solution to $R=Q+RP$, given P does not contain $\epsilon$

Given that $P$ and $Q$ are two regular expressions over $\Sigma$, and $P$ does not contain $\epsilon$. Start with: $$R = Q + RP$$

Now, replace $R$ by $R = Q + RP$: $$ \begin{align*} R &= Q + (Q + RP)P \\ &=Q + QP + RP^2 \end{align*} $$

Again, replace $R$ by $R = Q + RP$: $$ \begin{align*} R &= Q + QP + (Q+RP)P^2 \\ &= Q + QP + QP^2 + RP^3 \\ &= \cdots \\ &= Q + QP + QP^2 + \cdots + QP^n + RP^{n+1} \end{align*} $$

Now, replace $R$ by $R = QP^*$ to get $$ R = Q + QP + QP^2 + \cdots + QP^n + QP^*P^{n+1} $$

Taking $Q$ as a common factor, $$ \begin{align*} R &= Q(\epsilon + P + P^2 + \cdots + P^n + P^*P^{n+1}) \\ &= QP^*, \end{align*} $$ as $\epsilon + P + P^2 + \cdots + P^n + P^* P^{n+1}$ represents the closure of $P$.

Thus, $R = QP^*$ is the unique solution to $R = Q + RP$.

Clarifications:

I asked this question with the assumption that this is a valid proof $R=QP^*$ is the unique solution to $R=Q+RP$ (a). There are two basis for my assumption:

(1) This is the most popular proof found on the Web, I have included multiple sources as samples below. Across different authors, the proof takes exactly the same form as the procedure demonstrated above. Therefore, through inductive reasoning, I believe that this proof and its similar forms is a valid proof of (a). Otherwise, all those authors somehow collectively give a false proof.

(2) The procedure is logically and mathematically valid at each and every step, including the generalization of P* given that P does not contain $\epsilon$ as demonstrated above. Therefore, through deductive reasoning and (1), I believe that this proof and its similar forms is a valid proof of (a) until otherwise disproved through valid and sound counterargument.

Of course, what missing here is the intuitive reasoning from which one can derive that this proof indeed validly proves (a) to be true. Moreover, I am very curious and interested in the general intuitive and logical reasoning to prove anything as a unique solution.

I am not asking for a new proof. If for logical and/or mathematical reason, you can prove that this proof is invalid and MUST be discarded. Please present your evidence/counterargument in your answer. Please note that though I am not in any way qualify to be a
mathematician, I am quite aware of logical reasoning, as well as most fallacies and cognitive biases. So it might happen that I reject your proposed answer on the ground of invalid and/or unsound argument. This is in no way means that I want to offend you. If I made anyone feel so, I would like to apologize with my deepest sincerity. I am very appreciative of all the help I can get. Lastly, thank you Yuval Filmus, Hendrik Jan and D.W. who had been awesome people because you guys spent valuable time and efforts to put up with me for this question. Thanks guys.

Other sources from simple search of "Arden's Theorem Proof" on Google and Youtube

nesoacademy's Youtube Channel | Bhai Bhai Tutorials's Youtube Channel | Palak Chhajed's Youtube Channel | Theory of Automata and Formal Languages By Anand Sharma | tutorialspoint | sanfoundry

Answer 1

Suppose $R = Q + RP$, where $\epsilon \notin P$.

Let us first prove by induction that $QP^i \subseteq R$ for all $i \geq 0$. The base case $Q \subseteq R$ is clear. Now suppose that we know that $QP^i \subseteq R$. Then $QP^{i+1} \subseteq RP \subseteq R$.

Since $QP^i \subseteq R$ for all $i \geq 0$, it follows that $QP^* \subseteq R$.

Conversely, let us prove by complete induction on $|w|$ that if $w \in R$ then $w \in QP^*$. Let $w \in R$, and assume (by induction) the claim for all shorter words. Since $R = Q + RP$, either $w \in Q$ or $w \in RP$. In the former case, clearly $w \in QP^*$. In the latter case, $w = xy$, where $x \in R$ and $y \in P$. Since $\epsilon \notin P$, $y \neq \epsilon$, and so $|x| < |w|$. Hence by the induction hypothesis, $x \in QP^*$. It follows that $w \in QP^*P \subseteq QP^*$.

We have shown that $R \subseteq QP^*$, and so $R = QP^*$.

For the case $\epsilon \in P$, see this answer.

The "proof" you provided isn't a proof. It is a very convoluted way to show that $QP^∗$ is a solution, but it doesn't prove uniqueness at all. I suggest ignoring it.

Answer 2

This is not a valid proof.

You ask for the intuitive reasoning that makes this proof valid, but there's no amount of intuitive reasoning you can add to make it valid. It's just simply not a good proof. It's not a matter of adding intuition; there is no rescuing it.

A valid proof starts with facts that are known to be true; then each derives a new fact from previously known facts, using a valid inference rule or axiom. The so-called proof you have listed does not take that form. For instance, let me highlight two flaws:

• The first step of the "proof" you refer to says "Now, replacing R by R = QP*, we get". This first step is already not valid. It makes an assumption that is not justified (it assumes that we know that R = QP*); so this step is not valid. Basically, the proof is flawed because it uses a circular argument: it starts by assuming what is to be proved, and derives what is to be proved. That proves nothing. Since you said you know logical fallacies, this is the fallacy of circular reasoning.

• The second part of the "proof" again has the same flaw, where it says "Now, replace R by R = QP*". Here it is assuming what is to be proven.

• The "proof" doesn't have the right structure to prove uniqueness. You can't prove that $x=5$ is the unique solution to an equation by first assuming that $x=5$ and then proving that it follows that $x=5$. It doesn't do anything to show that the solution is unique. It just claims "Thus, R = QP* is the unique solution", but without any justification for that statement. It doesn't even try to explain the justification -- we are forced to guess.

---

I think the primary lesson here is that I suggest you adjust how you judge the credibility of sources of technical information.

I realize you found this proof on a popular website, but popularity is not a guarantee of correctness; it is merely a hint that is sometimes useful. I realize that you found it on multiple websites, but that is not strong evidence; it's not unusual on the Internet to find multiple people copy-pasting the same wrong thing. I realize that GeeksforGeeks is highly regarded by some and might be useful for some purposes (e.g., particularly for coding-contest-style questions and interview-style questions), but in my experience, its quality is highly variable, and in particular, it is not a reliable resource for mathematical and theoretical topics. I have personally seen multiple articles there that are sloppy, a poor reference, or just plain wrong. Now I've seen one more. It might also be useful to mention that articles on Geeksforgeeks are not written by a single person -- they are written by many different authors, some of whom might be more knowledgeable than others, and in any case, the authors are only people, so they can make mistakes.

If you want to find credible resources, a better place is to find a well-regarded textbook on automata theory or the theory of formal languages. That will be a much more reliable reference than Geeksforgeeks.

I'd also encourage you to reflect on why you've been having a hard time believing it when three separate people have told you that the article was wrong -- two of whom are, as it happens, experts on this subject. That might be an enlightening exercise.