Tag Archives: foundations
Note that I have removed the factorization requirement from the definition of a language in Fundamental Knowledge Part 1; so we will just have This will remove some triviality in examples of fuzzy logic systems in the upcoming post. The original motivation behind the factorization was that traditionally compound terms are considered formulas, but terms themselves are not considered formulas. I don’t really see why we can’t let terms be formulas; let us assume “substitutions” have already been made.
I have also removed the requirement that for all in a theory where is a logic system. Instead I have defined a logic system that satisfies this condition as a normal logic system.
1. Math isn’t useful.
Quite the contrary. As math is fundamental to all knowledge, developments in it trickle down to economics, physics, and computer science. From there they make their way into business and political decision making, chemistry, biology, engineering, and then onto the social sciences. Thus it may not be immediately useful; rather, it is a long-term investment whose payoff is slowest in return, but greatest in magnitude.
2. Math is just arithmetic: numbers and computation.
It’s no surprise that this conception exists given high school and lower division curriculum that strictly emphasize this. While computation is an integral component to math, it is merely the mechanism by which genuine math is done. Math is the epitome of science: it simply consists of making assumptions and proving what follows (computation is the process generating the proof). Of course one hopes the assumptions made do not contradict eachother–otherwise anything is provable (at least in traditional binary logic). In this sense, any experiment is math, with assumptions being hypotheses and results being true if they are consistent with the hypotheses. Even the practice of law is math, with assumptions being “people follow laws for all laws”, and true/false therefore coinciding with legal and illegal behaviors. Everyday decision making of individuals (and hence social science) is math: the assumptions being “biological predispositions and existence of a well-ordering of a set of possible decisions under given circumstances” and true decisions coinciding with those that are optimal (in the sense of the ordering).
3. Humans don’t have to be mathematical.
This is actually a contradiction. The human body in fact can be thought of as nothing more than a computer whose hardware is biology (even though our biology is soft/flimsy material–hopefully due for a big upgrade in the upcoming centuries) and whose software is a bundle of cognitive schemas. Mathematically, we simply have that the assumptions are the hardware and arbitrary software installed at a later point, and the true consequences are just the perceptions that are consistent relative to the hardware and software (versus the false ones which are not). For what we conventionally call a computer, the software is installed by humans. For humans, the software is installed by the environment. Sometimes the software itself may contradict the hardware–or other software for that matter. Statements (computations) that follow which are in contradiction to the assumptions (hardware/other software) can lead to run on and halting problems (or in the case of humans, perceptions/schemas contradicting other schemas or hardware, possibly leading to psychological disorders).
4. Any statement is either true or false.
This statement is (naively)false and undecidable. The (meta)assumptions we have made so far are that true statements are simply those that follow from (direct)assumptions, and false statements are those whose negation follows from the (direct)assumptions. Given those (meta)assumptions, the statement is (naively)false since the lack of (direct)assumptions (naively)contradicts the (meta)assumptions. If a statement or its negation do not follow from a set of assumptions, we say it is undecidable/independent with respect to that set of assumptions. Since we made no (direct)assumptions regarding statement 4, it is undecidable.
The next task is to absorb the traditional area of mathematical logic. One key missing ingredient is a model. Let us recall the traditional setup (taken from ).
Definition 2.1. Let be a set (of symbols). An -structure is a pair where is a nonempty set, called a universe, and is a map sending symbols to elements, functions, and relations of . An assignment of an -structure is a map . An -interpretation is a pair where is an -structure and is an assignment in .
For shorthand notation, the convention (with some of my modifications) is to write: , , and . These are the terms. Formulas are then built from the terms using traditional (although this can be generalized) logical connectives.
The notion of a model is then defined via induction on formulas.
Definition 2.2. Let be an -interpretation. We say that satisfies a formula (or is a model of ), denoted , if holds, where is defined via its components and and where necessary.
Formal languages in convention are built up from the formulas mentioned above, which are nothing more than special cases of Alt Definition 1.3. A model for a language is hence nothing more than an -interpretation into a structure, where is an alphabet (provided it is equipped with a logic system). This is precisely what I have constructed in Part 1; the symbols of are mapped to the universe . The next thing to establish is that every model is a language model. This is trivial since a model by definition satisfies a set of formulas as well as compounds of them (i.e. it must satisfy a language). Hence we have no need to trouble ourselves with interpretations and may simply stick to the algebra of Part 1.
While we have absorbed model theory, there are a few more critical topics to absorb from mathematical logic. We return to the language of Part 1 (no pun). Let be a theory of and be a binary logic system. A formula is derivable in if it is a proposition (i.e. is in ). We may write . This definition is in complete agreement with the traditional definition (namely, there being a derivation, or finite number of steps, that begin with axioms and use inference rules); it is nothing more than saying it is in . Similarly is valid if , or equivalently, it is derivable in any theory. In our setup this would imply . Hence no formula is valid.
Let have a unary operation and be a logic system on a theory .
If we assume to be idempotent (), then since is a homomorphism, we have . That is, the corresponding unary operation in must also be idempotent on .
Definition 2.3. A unary operation (not necessarily idempotent) is consistent in if for all , .
If we assume is consistent in and that is a binary logic system, then the corresponding in is idempotent since
Again, proofs in a binary system are independent of the choice of valence. If we assume consistency and idempotency, then we have a nonidentity negation which is idempotent on the range. The case for assuming binary system and idempotency yields either a trivial mapping of propositions (all to or all to ), or that is consistent and idempotent on . And lastly if we assume all three (idempotency and consistency of together on a binary system), we obtain a surjective assignment with idempotent negation in .
Let be a binary logic system where is a boolean algebra. Then the completeness and compactness theorems are trivial. Recall these statements:
Completeness Theorem. For all formulas and models ,
Compactness Theorem. For all formulas and models ,
Traditionally these apply to, what we would call, a binary logic system where is a boolean algebra (hence has a consistent, idempotent negation) under traditional operations, and in particular this fixes the operational/relational structures of , and , but is arbitrary. In this setup, all “formulas” (or what we would hence call propositions since they are generated by a theory) are trivially satisfiable since they have a language model. Hence Compactness is true. Moreover since they are propositions in a binary logic system, they are in some for a theory and are hence derivable; so we have Completeness.
Lastly we wish to address Godel’s Second Incompleteness Theorem; recall its statement:
Godel’s Second Incompleteness Theorem. A theory contains a statement of its own consistency if and only if it is inconsistent.
We have only defined what it means for a unary operation in a logical system to be consistent. Hence we can say that a binary logic system with a unary operation is consistent if its unary operation is consistent. But all of these traditional theorems of mathematical logic are assuming a binary logic system where is a boolean algebra , is idempotent, and the map is surjective. Hence is consistent (from above discussion), and the consequence in the theorem is false.
The weakest possible violation of the antecedent of Godel’s theorem is to use a structure to create itself (i.e. that it is self-swallowing), which makes no sense, let alone using it to create a larger structure within which is a statement about the initial structure. That a binary logic system with unary operation could contain a statement of its own consistency is itself a contradiction, since the theory itself, together with the statement , are in a metalanguage. It is like saying that one need only the English language to describe the algebraic structure of the English language. As we previously said at the end of Part 1, one can get arbitrarily close to doing this–using English to construct some degenerate form of English, but you can never have multiple instances of a single language in a language loop. Another example would be having the class of all sets, then attempting to prove, using only the sets and operations of them, that there is a class containing them.
Hence the antecedent is also false. So both implications are true.
 Ebbinghaus, H.-D., J. Flum, and W. Thomas. Mathematical Logic. Second Edition. Undergraduate Texts in Mathematics. New York: Springer-Verlag. 1994.
We must start with a language. A language can be defined in two ways. First let us begin with the axioms of pairing, union, and powerset and schema of separation. This gives us a cartesian product of sets, and hence functions.
Definition 1.1. An –ary operation on a set is a map . A structure is a set together with an -ary operation. The signature of a structure is the sequence where is the number of -ary operations.
Definition 1.2. Let and be structures with the same signature such that each -ary operation of is assigned to a -ary operation of (i.e. where is the th -ary operation of ). A homomorphism between structures and is a map such that
Note that a nullary operation on is a map . That is, it is simply an element of . Now let be a set which we will call an alphabet, and its elements will be called letters. A monoid has a nullary operation, called a space, and a binary operation, which will simply be denoted by concatenation. We define the free monoid on as the monoid consisting of all strings of elements in . We now have two definitions of a language, of which the first is traditional and the second is mine:
Definition 1.3. A language is a subset of .
Alt Definition 1.3. Let , be a relational structure (a set together with an -ary relation), and be a structure. The language is defined as where is the free -structure on . In particular elements of are called words, elements of are called terms, and elements of are called formulas.
Definition 1.4. A theory of is a subset . Elements of a theory are called axioms. Elements of are called propositions. A theory of is called a reduced theory if for all , for all -ary operations of and all placements of in evaluation of the operation. (That is, the theory is reduced if no axiom is in the orbit of another).
For example, the theory is called the trivial theory. The theory is called the empty (or agnostic) theory.
Definition 1.5. An –ary logic system on a theory is a homomorphism where and have the same signature and has cardinality We may also say the logic system is normal if for all
In traditional logic is a two element boolean algebra. Traditional logic also has a special kind of function on its language.
Definition 1.6. A quantifier on is a function . We may write:
In particular it is a pseudo operation, and gives the language a pseudo structure. This is similar to modules, where in this case a product of a term and a formula are sent to a formula.
Hence our initial assumption of four axioms (as well as the ability to understand the English language), have in turn given us the ability to create a notion of a language of which a degenerate English can be construed as a special case. This is certainly circular in some sense, but in foundations we must appeal to some cyclic process. One subtlety worth noting is that the secondary language created will always be “strictly bounded above” by the initial language; they aren’t truly equivalent. (In fact this last statement is similar to the antecedent of Godel’s Second Incompleteness theorem).