“There is a problem of double spend here. Maybe there are two parallel transactions which transfer the same coin to two different recipients.”
This is not true. Proof of Work creates blocks with an ordered list of transactions. Therefore it is impossible to run parallel transactions such that one is not processed before the other. This is how Proof of Work prevents the double spend attack.