This paradox arises for the same reason as the paradox of the dead football team:
- Fan 1 asks football player: How did your team do against the other
team?
- Football player: We killed them!
- Fan 1: When do you play them again?
- Football player: In two weeks
- Fan 2: You can't play them again...didn't you just say they were dead??
--
What is death
Biblically, death is a separation.
Physical death--separation of body & spirit:
Then shall the dust return to the earth as it was: and the spirit
shall return unto God who gave it. (Ecclesiastes 12:7)
Spiritual death (separation from God) is described in Isaiah & 2 Thess.
But your iniquities have separated between you and your God, and your
sins have hid his face from you, that he will not hear (Isaiah 59:2)
Such people will suffer the punishment of eternal destruction by being
separated from the Lord's presence and from his glorious power (2
Thess 1:9)
The parable of the prodigal son demonstrates this worldview very effectively (see Luke 15:24)--the son never physically dies in the story--but his father describes him as having been dead. His father isn't killing the fatted calf for a dia de los muertos celebration & dressing the boy up for a viewing at the morgue--he knows his son is alive. His son was separated (from his family, from his faith) and he has now rejoined.
Consider Paul's words in the second chapter to the Colossians:
13 And you, who were dead in your trespasses and the uncircumcision of
your flesh, God made alive together with him, having forgiven us all
our trespasses
These people aren't physically dead; they were separated from God by sin; now they have been (or are being, if you like) born again.
See further discussion of death as separation on this site by Dave here & on bible.org here.
--
The opposite of dying
What is the opposite of dying?
Wouldn't it be birth? Yes, but if death is a separation, birth is a joining together:
And the Lord God formed man of the dust of the ground, and breathed
into his nostrils the breath of life; and man became a living soul. (Genesis 2:7)
This definition offers substantial insight to Jesus' words to Nicodemus in John 3:
6 That which is born of the flesh is flesh; and that which is born of
the Spirit is spirit.
7 Marvel not that I said unto thee, Ye must be born again.
(to be fair, Nicodemus was puzzled by this at first too)
Jesus is not saying that we stop being physical entities and become only spirit; when we are physically born our self (more on that below) receives a physical body; when we are spiritually born our self receives the Holy Ghost.
(Is birth a process or an event? I've attended a childbirth up close--twice--and I can quite confidently describe it as a process)
And so Nicodemus could be as understandably confused--"how can someone be born if they are already born"--as we could be to ask "how can someone die if they're already dead?"
--
Eternal life & eternal death
The paradox in the OP appears because, like the aforementioned story of the football team, different kinds of death are being discussed.
Jesus taught that we shouldn't fear those who can physically kill (separate body & spirit); but we should fear separation from God--specifically, eternal separation from God in Gehenna.
("Hell" is sometimes used in English to refer to Sheol and sometimes used to refer to Gehenna, but this is not the message conveyed by the Biblical text--these are distinct states/places--further discussion here)
The death Jesus warns against is not the separation of body & spirit so often inflicted by the Romans, but this:
And whosoever was not found written in the book of life was cast into
the lake of fire. (Revelation 20:15)
This is an eternal separation--a separation from God from which there is no return. (But wait, aren't we separated from God right now?? Yes, but it's temporary. We will return to God's presence to be judged--see Revelation 20:12)
Eternal life, on the other hand, describes more than just living forever (that's immortality). Life is a joining together--eternal life is a joining together described at length in John 17 (that's a full discussion on its own--my thoughts on immortality vs. eternal life here).
--
The eternal self
I used the word "self" above to avoid the soul/spirit distinction.
Soul:
a. Sometimes ψυχή "psuché" (and its Hebrew counterpart נֶפֶשׁ "nephesh")
is used to describe the entity created by the combination of a body &
spirit (as in Genesis 2:7)
b. Sometimes it's used synonymously with spirit (as in Acts 20:10)
As noted by Rajesh, Thayer has an excellent discussion of two primary uses and 6 sub-uses of the word (see here).
That Matthew 10:28 uses the word to refer to the "spirit" is evident by comparing the two possible renderings of the passage:
a. If "soul" in this context = body + spirit: "fear him which is able to destroy both [spirit and body] and body in hell"
b. If "soul" in this context = spirit: "fear him which is able to destroy both [spirit] and body in hell"
Option a (as in Genesis 2:7) does not require appending the word "body" to the last clause; since "body" is appended to the statement, option b (as in Acts 20:10) is to be preferred.
Humans have a self--an identity--an inner person (Churchill called it an "inner sanctum") that changes at birth and death but doesn't cease to exist.
The idea of a person's complete destruction is known as annihilationism; The earliest clear source for annihilationism would be Arnobius of Sicca in the 4th century; the idea is discussed in detail by Talbot here. Talbot points out that Arnobius' ideas were repeatedly opposed by his contemporaries and later generations.
I respectfully suggest that annihilationism is inconsistent with the Biblical understanding of death as a separation. At physical death the unique body + spirit entity created at the beginning of mortal life is separated; but the "self" is neither destroyed nor killed (separated eternally from God). The person may later be eternally separated from God, but that comes at God's hand at the time of judgement, not at man's hand at the time of death.
--
Rewriting the argument
(modifications in italics)
P1: a living soul_type_a is a combination of physical body and soul_type_b (aka breath of life aka ruach aka pneuma) (from Gen 2:7 and 1 Cor 15:44-45)
P2: a human becomes a living soul_type_a (from Gen 2:7)
P3: if human A separates the physical body & soul_type_b of human B, the soul_type_b of human B is NOT eternally separated from God (from Matthew 10:28)
P4: if human A separates the physical body & soul_type_b of human B, human B no longer has a physical body (from common sense)
C1: if human A separates the physical body & soul_type_b of human B, human B is no longer a living soul_type_a (from P4, P2, P1)
Contradiction/Paradox: if human A separates the physical body & soul_type_b of human B, human B still has a soul_type_b (from P3) BUT no longer is a living soul_type_a (from C1)
--
Conclusion
There is no contradiction/paradox, because P3 refers to two different kinds of death, and Genesis 2:7 & Matthew 10:28 refer to 2 different usages of the word "soul".
Jesus is making a play on words (or ideas), as is so common in Matthew. He's pointing out that there is a separation far more significant than a temporary absence of the spirit from the body.