You can always fool any system into a paradox. Very grossly speaking, this comes out of Godel's incompleteness theorem; that with any set of laws you can always get P=~P out of the set. How this paradox looks, acts, or feels is interesting and possibly artistic, as the OP shows. If anything, I think there is a bit of beauty, art, and cleverness in that.
That isn't quite right. With a sufficiently powerful formal system, you're forced to either have inconsistency or incompleteness - you're describing a system that is inconsistent. It's usually much better to have consistency and to sacrifice completeness. Then you'll have Ps that are true but unprovable, but at least you won't have P=~P which makes the system rather useless.
I'm not a logician by a long shot, so I probably can't explain that correctly. I think Gödel found a way to make a logical proposition refer to itself, and then found a way to assert provability. He could then construct the sentence "this sentence is not provable". He showed that such a sentence must exists within any system of sufficient power. Thus the system must be self-contradictory (inconsistent), or the sentence must be true (and the system must be incomplete). I'm not sure if such a sentence still refers to itself when negated, so I can't answer the last one.
My understanding of the incompleteness theorem is that, for a given set of axioms, there will be unprovably true things. Changing the axioms would change which things were unprovable.
