Of paradoxes and proofs (not a puzzle)

[bonanova]

The paradox of self reference

Statements have attributes, among them is their truth value. And the act of making a statement is the act of asserting its truth. The sky may be blue. Making that statement is tantamount to saying I assert that 'the sky is blue' is a true statement. Thus, this statement is false is immediately a paradox, for it asserts both truth and falsity: I assert that the truth value of 'false' is 'true.' Or, what I assert to be true is false. Self-referential paradoxes lead logicians to modify the rules, to accommodate (or avoid) them.

It does not help to deny the premise that by making a statement you have asserted that something is true. If you deny that you are a truth asserter, by saying I am a liar (as if that would remove the problem of your saying This statement is false) all you have done is to revoke your permission to speak. Thus you cannot be the person who informs others that you lie. It's perfectly alright for a person to say bonanova is a liar, but bonanova can't logically be that person.

Impossible statements of this type provide us not only with paradoxes, but with proofs. Specifically, those of the reductio ad absurdum variety. I found it interesting after posting to find one such connection: Russell's paradox lays the foundation for a simple proof that the cardinality of a set is less than that of its powerset. Do you see the connection between the two sets R in what follows?

Russell's paradox

 

According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. Does R contain itself? This question is paradoxical, for if R is not a member of itself, then its definition dictates that it must contain itself; but if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves.

Cardiality of powersets  

 

Suppose a set and its powerset have the same cardinality. Then there is a bijection (pairing) between a set's subsets and its elements. Color an element blue if it is a member of its paired subset and red if it is not. Consider the subset R that comprises all the red elements. It cannot be paired with a blue element (it contains no blue elements) nor with a red element (which cannot be a member of its paired subset.) R is thus a subset that is not paired with an element.

 

This violates our assumption, and it shows by example that sets have more subsets than elements.