flexibeast.space - gemlog - 2020-11-08
Beyond bivalence
‘Bivalence’ is the notion that a proposition (e.g. “It's raining”) is either true or false. If the ‘or’ is ‘exclusive’, meaning “the statement is true, or its negation is true, but not both”, it's equivalent to both the law of excluded middle (LEM) and the law of non-contradiction (LNC). If the ‘or’ is ‘inclusive’, meaning “the statement is true, or its negation is true”, it's equivalent only to LEM.
LEM is often used in mathematical ‘proof by contradiction’: assume something, work on that basis, reach an absurdity, conclude via LEM that the negation of something must be true. Unfortunately, there's a general tendency to conflate ‘proof of negation’ and ‘proof of contradiction’, as described in a post by Andrej Bauer.
"Proof of negation and proof by contradiction"
Consequently, a number of people think that not using LEM means one is deprived of proof by contradiction in general. However, as Bauer's post shows, not using LEM only means you can't do:
- Assume not-A. But that results in absurdity. So A must be the case.
You can still do:
- Assume A. But that results in absurdity. So not-A must be the case.
What can be asserted in the first case is not-not-A. But in the absence of LEM, we can't do double-negation elimination to get from not-not-A to A. The difference between not-not-A and A is, roughly, that the former says that a solution exists, without saying what that solution actually is; the latter actually provides the solution. There's an old joke about this:
An engineer, a physicist and a mathematician are staying in a hotel. The engineer wakes up and smells smoke. She goes out into the hallway and, seeing a fire, fills a trash can with water and douses the fire. Later, the physicist wakes up and smells smoke. Opening her door and seeing a fire in the hallway, she walks down the hall to a fire hose and after calculating the flame velocity, distance, water pressure, trajectory, etc. extinguishes the fire with the minimum amount of water and energy needed. Later, the mathematician wakes up and smells smoke. Going into the hall, seeing the fire, and then the fire hose, she thinks for a moment, exclaims, "Ah, a solution exists!", and goes back to bed.
A recent SMBC comic also riffed on it:
Another perspective is provided by topological semantics, in which logic is interpreted topologically. Quoting from another post by Bauer:
LEM says that, no matter which `D` and `P` we consider,
`forall x in D . P(x) or not P(x)`. ...
Imagine that the set `D` in the above formulation of LEM is not just an ordinary set but a metric space, or more generally a topological space. Imagine furthermore that the property `P` is restricted to be an open subset of `D`, that `not P` means the topological exterior of `P`, and that `or` is union (which it is, actually). So now, is it necesssarily the case that `P or not P` covers all of `D`? It depends on `P`, does it not? For example, if we take `D = RR`, the real numbers with the usual metric, and `P = {x in RR ; x > 0}` then `not P = {x in RR ; x < 0}` so `P or not P = RR - {0} != RR`!
— "The Law of Excluded Middle"
A hundred years ago, rejecting LEM on philosophical grounds, as done in Brouwer's Intuitionism[a], seemed to be hobbling the practice of mathematics for no practical reason. The advent of computers, however, changes this.
"Why I no longer believe in computational classical type theory"
Basically, the problem is that computing often involves branching: if A, then do X. More concretely, we frequently have things like “if A is less than 100, do this”. So it's not enough to say “we know that A has a value, but we don't know the actual value”; we need to know the actual value. If we only need to know whether or not A is true, we could try assuming one branch and see where that takes us, but in the presence of side-effects[b], this creates problems: “Do we open the flood gates? Well, let's open them and see what happens. Oh, that was wrong. Can we put the water back, please?”
Another issue raised by computing is that, in terms of data and data manipulation, we need to be able to work with the fact that particular data might not exist, for whatever reason. A database might have a table listing people's first and last names[c]. If someone doesn't have a last name, we might leave that field empty. But what if we don't know whether or not they have a last name? SQL, a language used in many relational database management systems, uses three-valued logic: the field either contains the name (‘true’), is empty (‘false’), or is NULL (‘unknown’)[d]. As Wikipedia notes:
Attempting to apply the law of the excluded middle to SQL's 3VL is effectively a false dichotomy.
Wikipedia: ‘Null (SQL)’ / ‘Law of the excluded fourth (in WHERE clauses)
In fact, E.F. Codd, the creator of the relational database model, has argued for a four-valued logic for database management:
Codd indicated in his 1990 book The Relational Model for Database Management, Version 2 that the single Null mandated by the SQL standard was inadequate, and should be replaced by two separate Null-type markers to indicate the reason why data is missing. In Codd's book, these two Null-type markers are referred to as 'A-Values' and 'I-Values', representing 'Missing But Applicable' and 'Missing But Inapplicable', respectively.
Wikipedia: ‘Null (SQL) / ‘History’
Going even further, there other many-valued logics such as fuzzy logic, in which a ‘truth value’ is represented by any real number between 0 and 1, inclusive.
Fuzzy logic has found applications in control theory, which deals with the control of engineered processes and machines.
Personally, i find non-classical logics interesting for their own sake. But there are also very practical reasons for moving beyond bivalence.
☙
☙
Note that rejecting LEM does not automatically make one an adherent of Intuitionist philosophy. There's more to the latter than simply rejecting LEM.
[b] ‘Side-effects’ here has a specific technical meaning:
Wikipedia: ‘Side effect (computer science)’
[c] Even if you're not a programmer, it's worth reading the classic article “Falsehoods programmers believes about names”.
“Falsehoods programmers believe about names”
[d] Further details at:
Wikipedia: ‘Null (SQL)’ / ‘Comparisons with NULL and the three-valued logic (3VL)’