logic

I don’t remember the first time I heard about the Liar’s Paradox, but it was definitely in college, because it came up in my computer theory classes in discussions on formal grammars. As such, I’ve been thinking about it on and off, for about 20 years. Wikipedia says that the first correct articulation of the Liar’s Paradox is attributed to a Greek philosopher named Eubulides, who stated it as follows: “A man says that he is lying. Is what he says true or false?” For purposes of this note, I’m going to distill that to the modern formulation of, “This statement is false.”

As an initial matter, we must accept that not all statements are capable of meaningful truth values. For example, “Shoe”. This is just a word, that does not carry any intrinsic truth value, nor is there any meaningful mechanical process that I can apply to the statement to produce a truth value. Contrast this with, “A AND B”, where we know that A = “true” and B = “false”, given the typical boolean “AND” operator. There is in this case a mechanical process that can be applied to the statement, producing the output “false”. Now, all of that said, there is nothing preventing us from concocting a lookup table where, e.g., the statement “Shoe” is assigned the value “true”.

Now consider the distilled Liar’s Paradox again: “This statement is false”. There is no general, mechanical process that will evaluate such a statement. However, it is plainly capable of producing a truth value, since it simply asserts one for itself, much like a lookup table. Typically, this is introduced as producing a paradox, because if we assume the truth value is false, then the truth value of false is consistent with the truth value asserted in the statement. Generally speaking, when assertion and observation are consistent, we say the assertion is true, and this is an instance of that. As such, the statement is true, despite the fact that the statement itself asserts that it is false. Hence, the famous paradox.

Now instead approach the problem from the perspective of solving for the truth value, rather than asserting the truth value. This would look something like, “This statement is A”, where $A \in \{true, false\}$ . Now we can consider the two possible values of $A$ . If $A = true$ , then the statement asserts a truth value that is consistent with the assumed truth value, and there’s nothing wrong with that. If instead $A = false$ , then we have a contradiction, as noted above. Typically, when engaging in mathematics, contradictions are used to rule out possibilities. Applying that principle in this case yields the result that $A = true$ , which resolves the paradox.

In summary, not all statements are capable of mechanical evaluation, and only a subset of those mechanically evaluable statements resolve to true or false. This however does not prevent us from simply assigning a truth value to a statement, whether by a lookup table, or within the statement itself. However, if we do so, we can nonetheless apply basic principles of logic and mathematics, and if we adhere to them, we can exclude certain purported truth values that are the result of mere assertion. In this case, such a process implies that a statement that asserts its own truth value, is always true.

I was reading my favorite book on mathematics, Mathematical Problems and Proofs, in particular, a section on basic Set Theory. The book discusses the transitive relation, where if A is related to B, and B is related to C, then A is related to C. In this case, A, B, and C are abstract mathematical objects, but you can assign practical meaning by e.g., making them all integers, and considering ordinal relationships between them, where e.g., A is greater than B, B is greater than C, and therefore, A is greater than C. Note that this example of ordinal relationships has a “therefore” clause, but relations are abstract statements of fact, not consequences of logic. That is, we simply posit relations between objects, whereas I’ve phrased the concrete example in terms of a logical conclusion, which is very different. That is, this example is consistent with the stated set of relations among A, B, and C, which are simply posited to exist, whereas the integers have properties that imply that A is greater than C as a matter of logic.

With that introduction, it dawned on me that we can consider higher order sets of relations that probably don’t have names like “transitive”. One obvious such set of relations is as follows, where A is related B, B is related to C, C is related to D, and A is related to D. All I did was add an extra object D, and extend the relations analogously. Specifically, we can express this as a graph, where A through D are connected by a path, and A is connected directly to D by an extra edge, creating what would be a circuit in an undirected graph. Though note that even if A is related to B, this does not imply that B is related to A, and as such, any graph expressing relations is directed. This is probably known, given how simple it is, and I’m certain through my own studies that people express relations using graphs.

The interesting bit is the possibility of using machines to discover meaningful higher order relations that e.g., require at least four or more objects. Because it’s at least possible for these relations to arise over any number of objects, we can’t give them all special names in a human language like “transitive”, but a machine can. The point being that, most of mathematics is probably accessible only to machines or other sentient beings capable of handling that much information, which plainly do not inhabit this planet in any appreciable number.

Information Overload

Solution to the Liar’s Paradox

Higher Order Relations