Weak boolean algebras
From PuB
Weak boolean algebras are used to extend classic computer programming's notions of True and False.
At their mathematical foundations, weakbools are nothing else than Heyting algebras defined over finite tosets (finite weakbools) or over non-finite posets (non-finite, indeterminate weakbools ) that satisfies an additional set of requirements, so just a concept, more like a mental symbol intended to be used in computer programming and not a new algebra. Weakbools are meant to correctly define another concepts used in computer programming like tribools
Contents |
Notes on the text
Regarding the introductive materials, this text contains notions rather than complete definitions.For a proper understanding the reader is encouraged to follow the references.
This is the work of a math infidel. The definitions may seem to be more like metaphysics than math and probably not very clearly written. I will do my best to clarify the terms in my free time.
This article is public domain, you, the reader, are granted with any rights you want as long as you will mention my name in conjunction with weakbools, if you will ever use it and i will not be held responsible for any disasters that may happen because of improper use of weakbools by other persons than me. ... damn this sounds so political... sorry! ;)
I must say this ... after refreshing the last updates on the article google served me on this page with adsense entries with pills against depression. What the....!
Abstract
Altough different non-classical boolean algebras implementations are widely used in many programming languages - those aren't built on top of mathematical concepts to support their definition. Most implementations are taking in consideration only an "Indeterminate" state that can mean anything and everything and it is usually Determinate by definition. One needs to strongly define intermediate degrees of truth and the Indeterminate and keep some compatibility with the classical Either-True-Or-False decision mechanism based on law of excluded middle.
The Indeterminate
What is the purpose of Indeterminate in computing? The Indeterminate is to be taken in consideration when necessary with the solely purpose of elimination (if possible).
There is a small problem when talking about the Indeterminate because being indeterminate, we dont know what is it. So how would you define it? Does it have a name? What is the Indeterminate 's quiddity, its whatness? Because altough indeterminacy of something means that something is unquantifiable, untestable, if we want to work with Indeterminates in computer programming we have to represent them somehow and safely bypass the philosophical debates over the subject.
As you will see below, i decided to represent the Indeterminate with the help of a heyting algebra defined over a non-finite poset, with the partial order defined for 0 and 1 in the eventuality of an infinite set members but at least 2 (not counting 0 and 1), with no order defined between them, but only against the greatest and the smallest. That is, for me, the Indeterminate is an eventually-infinite set with at least 2 elements (not counting 0 and 1) with no order defined between them bounded by the greatest 1 and the smallest 0: 0≤{...,M,...,W,...}≤1
The Indeterminate is any possibly-infinite poset of at least 2 elements (not counting the lower/upper bounds defined implicitly for any bounded lattice, 0 or 1) with no order relation defined explicitly for them. The only weakness that may be subject to a debate is the fact that i consider the absolute 1 and 0 as being above and below the Indeterminate, in other words one could say i am bounding the infinite by defining the partial order as described above. Not really a weakness but it matches the philosophical debates over Truth and False as we target them as absolute meanings of things and any eventual circularities created between (not not including) them are the Indeterminate. I hope i will have time in this life to extend this article with more explanations as of what i have in mind.
- Why at least 2? If there will be at least one then there will be an implicit total order so there is no Indeteterminate. A Heyting algebra with one element (excluding 0 and 1) is a finite weakbool algebra, having an implicit total order defined. The Indeterminate can also be seen as a (possibly infinite) number of random eventual circularities which cant be build against totally ordered sets like the 1-element.
- Why the partial-order only constraint? Because of the Indeterminate nature. I have no chance of defining a total order to include the Indeterminate since its not determinate, do I.
- Why eventually-inifinite? As you will see, the proof tables are the same either for 2 or more (possibly infinite). I would rather say one should always consider the eventuality of the infinite when representing the Indeterminate in its mind and use 2 unknowns to write the Indeterminate in real life for the sake of clearly representing the information in both worlds. I would say it is safe enough to write the indeterminate with the help of 2 elements with no order defined for them, bound by 0 and 1. Just dont take it too alphabeticaly. Think of it as the human soul, the yin and the yang, the man and the woman, the object and its mirror image, the iahve, whatever. its the-what-it-is and the-what-it-is-not, the mystical bitch :) I will write them M and W in the tables for clarity or M|W sometimes because taken separately they have no meaning whatsoever
Theoretical background
These are very simplistic, almost subjective definitions of terms summarized with the help of Wikipedia that are to be considered when digesting the text related to Weakbools:
- Axiom (postulate): a sentence taken for granted, either as self-evident truth or subject to necessary decision
- Premise: an assertion - either a reason-for or an objection-against another assertion.
- Conclusion: a declarative sentence
- Argument: a set of one or more premises and a conclusion
- Valid argument: taken the premises for granted, the conclusion verifies. Premises: {Whatever can fly, its delicious; Crows can fly }. Conclusion: {Crows are delicious}.
- Sound argument: a valid argument with all premises true. The above is not a sound argument.
- Inference rule: a function f with domain a set of premises and codomain a conclusion f:{P1,...,Pn}->{C}. C is said to be inferable (deducible)
- Soundness: having and argument and a set of inference rules inside a logical system then whatever you prove must be true with respect to the semantics of the system (must have a meaning).That is, all provables are true.
- Formal system: a set of proposition symbols (call them letters), a set of inference rules and a set of axioms
- Propositional Logic: a formal system with a set of logical connectives (and,or,...) and a well defined manner to construct formulæ
- First Order Logic: propositional logic with quantifiers. While propositional logic is purely declarative, first order logic adds predicates (there is:
) and quantifiers (for all x in A 
)
- First-Order Theory: a theory built on first-order logic sentences
- Complete Theory: a theory is complete if it contains either P or nonP for any P written in its language.
- Consistent Theory: a theory that contains no contradictions
- Proof (formal): a finit set of sentences, where a sentence is either an axiom or another sentence infered from the precedings and the last sentence being a syntactic consequence.
- Proof (logic): an argument (premises+conclusion)
Classical vs Intuitionistic logic
Classical approach: The existence of an entity can be proved by refuting its non-existence. That is, ¬¬A gives A
Intuitionistic approach: The above does not hold. Refutation of non-existence does not give proof of existence. In other words, the truth of a sentence does not equate its provability. Hence, A ∨ ¬ A (tertium non datur) is to be disallowed.
The strength of intuitionistic approach is given by the Gödel's first incompletness theorem. Using this theorem one can construct a sentence based on a theory that is neither proven or disproven.
A theory needs to be consistent and complete. However, the above theorem says that a theory expressing elementary arithmetic can't be both,as it follows:
Given a theory T and a sentence G that asserts "This sentence cannot be proved in theory T" we have the following:
- suppose G is 'provable in T: then T has a proof for the sentence G so G can be proved in theory T and hence the inconsistency G ∧ ¬G
- suppose anyway that T is consistent: in this case G can't be proved in T so the sentence G is true because it states that i can't be proved in T. Since G can't be proven and G is true we have incompletness: G ∧ ¬ G. Hence our belief stated above that truth does not equate provability
- if one defines a supertheory of T: T' - that contains axiom G to satisfy completness and consistency, there will always be a sentence G' showing the incompletness of T'. All the theories are incomplete.
The above can be compared with liar's paradox (this sentence is false)
Since there is no tertium non datur anymore one can safely conclude that negation has a different meaning as well, which is true. If in classical logic negation of sentence IS sentence is false, now IS there is a proof that there is no proof for sentence.
By not having a proof that there is no proof for a sentence P one cannot conclude that P has a proof. Hence, P is stronger than ¬¬P
These are the first steps in what is called intuitionistic logic where one will be working with justification and not truth. Heyting algebras quickly described in the next section are a good model of intuitionistic logic that weakbools are based on.
Heyting algebras
Supporting definitions
- Join: the least upper bound of two elements in a set. That is if z=join{a,b} then z is the smallest element in the set for which a≤z and b≤z. Join is noted ∧
- Meet: the greatest lower bound of two elements in a set. That is if z=meet{a,b} then z is the greatest element in the set for which a≥z and b≥z. Meet is noted ∨
- Poset (partially ordered set): a set with a binary relation usually noted ≤ that describes precedence on one element to the other for certain pairs of elements
- Lattice: a poset (L,≤) in which ∀ a,b ∈ L: ∃ a∧b, a∨b
- Bounded lattice: a lattice with a top ( a greatest) and a bottom (a least) element noted 0 and 1
- Complement: the tertium non datur: b is said to be a complement of a, noted ¬a iff ¬a∨a
- Pseudo-complement: b is said to be a pseudo-complement of a if b∧a=0 and b is the greatest element in the set that satisfies the condition. Thats it, ∀c∈L that satisfy c∧a=0 then c≤b
- Relative pseudo-complement: b is said to be a pseudo-complement of a relative to d if b∧a≤d and b is the greatest element in the set that satisfies the condition. We write pseudo-complement of a relative to d as : a → d. You may also say that b is a pseudo-complement of a in the sublattice {x∈L | d≤x }.Think as of a translation of d in 0. One can easily note that in relation to relative pseudo-complements a and b are at least d.
Definition
A Heyting algebra is a relatively pseudo-complemented bounded lattice, so a lattice that satisfies:
- it has 0 and 1 as the bottom and the top
- ∀ a ∈ L, ∃ b ∈ L such that a → b ∈ L
The pseudo-complement of x∈L, written ¬x is x→0. It can be also named as the pseudo-complement of x relative to 0.
x∧¬x=0 with ¬x being the greatest in the set satisfying it but x∨¬x=1 does not always verify.
A heyting algebra must be verified by the following:
- a→a=1
- a∧(a→b)=a∧b
- b∧(a→b)=b
- a→(b∧c)=(a→b)∧(a→c)
Check the complete article on heyting algebras at Wikipedia.
Notes on boolean and heyting algebras
- every boolean algebra is a heyting algebra with a→b = ¬a∨b
- The second De Morgan law ¬(P ∨ Q) = ¬P ∧ ¬Q verifies but the first must be weaken: ¬(P ∧ Q) = ¬¬(¬P ∨ ¬Q). Additional conditions must be met for a heyting algebra to satisfy both strong forms of De Morgan laws (see the De Morgan laws in a heyting algebra for a complete image.
Finite weak boolean algebras
- A heyting algebra defined over a finite totally-ordered set (toset) is a finite weak boolean algebra (F-Weakbool).
or
- A bounded lattice defined over a non-empty finite toset (which is a heyting algebra) is a finite weakbool algebra
Example: T = { Cold=0, AlmostCold, Warm, Warmer, AlmostHot, Hot=1}
The linearly ordered set {0,A,1} altho it can be used to build a weakbool algebra doesn't match a logical mind-view of a F-Weakbool (and i assume generally speaking a multi-value boolean algebra). If we would want to define T={Cold,AlmostCold,Hot} this should be as well written as T={Cold,AlmostHot,Hot}. This is some kind of dummy indeterminate state , the EitherColdOrHot state. The purpose of finite weakbools is to write strong definitions of intermediate truth values and generally speaking any toset with an odd number of states does not match a strong definition. Basically, the intermediates should be written in pairs that tend to form transitions to both upper and lower bounds of the lattice. So if you would have a state AlmostHot this should have an "opposite" state AlmostCold, where (AlmostCold,AlmostHot) build transitions to Cold and Hot bounds. Its a brain scratcher to have {Cold,AlmostHot,Hot} and to transit directly AlmostHot to Cold.
As a rule of thumb: any intermediate truth that tends to build a transit to the upper/lower bound must be paired with a different intermediate truth that tends to build a transit to the lower/upper bound. The defintions of such a pair in the toset must be written to respect a simmetry relative to the distance they give to absolute truths
We can now give a complete definition of a F-Weakbool algebra:
F-Weakbool Definition
A heyting algebra defined over a finite toset T with |T| = 2n,n≥1,n∈Ν may be used to build a well defined F-Weakbool algebra.
Examples
- The SomewhatFalse/SomewhatTrue truth table defined over the toset T={0,θ,λ,1} is left as a an exercise to the reader. Use the join,meet and pseudo-complement definitions to fill the truth tables. If you need, you get get inspired from heyting algebras example section. I use θ for writing SomewhatFalse and λ for writing SomewhatTrue because of their design resembling the absolute truths they build transits to. You can go on by building the truth tables for T={Cold=0,SomewhatCold,Warm,Warmer,SomewhatHot,Hot=1}. Always remember, they're just heyting algebras that satisfy an additional set of conditions.
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- The TrueOrFalse,TrueAndFalse don't do this at home revisited: taken the example above, if one would want to use a single intermediary truth value it will get to build a not-so-well defined F-Weakbool algebra. the MaybeTrueMaybeFalse ressembles in a wrong way some kind of Indeterminate, a paradoxical Indeterminate because implicitly by the way it is defined it's determinate but its meaning is indeterminate.
Non-Finite weak boolean algebras
The case of the Indeterminate as described above is modeled pretty straight-forward with the help of a non-finite weakbool algebra.
NF-Weakbool Definition
A Heyting algebra defined over a eventually-infinite poset P with |P|≥4 equipped with a partial order written only for 0 and 1 in relation with all the other elements is a non-finite weak boolean algebra or a partially-indeterminate weakbool algebra (NF-Weakbool).
One will use a NF-Weakbool algebra to work with the Indeterminate
NF-Weakbool truth tables
As mentioned above in the Indeterminate debate, the Indeterminate is represented by an infinite number of intermediate truth degrees. It can be easily prooved by induction that the truth tables are the same for any number of such states, possibly infinite. For the ease of representation, we will use 2 intermediate truth values, noted M and W. Altho the M and W truths as results of operations are interchangeable, both as notation and value (M may be as well W and W may be as well M) we choose to write the result as the first operand if both are either M or W and as M or W when one of the operands is either M or W and the other is an absolute truth value (0 or 1)
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Some clarifications on solving the truth tables
- remember the partial order is defined for the absolute truth values only, in relation with themselves and the Indeterminate. There is no order defined for the Indeterminate but only in operation with absolute truth values
- as you will notice, we tend to approximate the infimums and the supremums or better, we intuite the best choice for infimums and supremums. welcome to what is the world of Indeterminate. here are some samples of truth tables entries:
- a∧b, where a,b ∈ {0,M,W,1} (where {0,M,W,1} should be clarified as {0,...,M,...,W,...,1}):
- M∧0 = join(M,0) = 0
- M∧W = join(M,W) = 0 - since there is no relation between M and W the most well known infimum is 0.
- M∧1 = join(M,1) = M - we know for sure 0 is a good infimum for M∧1 but we also know the partial order 0 ≤ {...,M,...,W,...} ≤ 1 so we may safely write the infimum of M and 1 as M. i leave as a mind exercise the solving of the entire ∧ truth table.
- a∨b, where a,b ∈ {0,M,W,1}: follow the intuitive methods written above for a∧b but now for meet operations instead of join operations
- a→b, where a,b ∈ {0,M,W,1}: use the relative pseudo-complement definition and the ∧ table.
- W→1: the greatest X for which X∧W≤1. lookup the X satisfying this condition in the ∧ table
Some interesting observations on NF-Weakbools
some morphisms and compatibilities with boolean algebra. to be written.
TODO
- define the Weakbool as a hybrid between NF-Weakbools and F-Weakbools. One should be able to define Indeterminates between any two intermediate truth values.
