Method of 'Formal Logic'



Diagrams

 

Logical levels and criteria





Meta-truth: logical criteria



Logical quality




Level I:

 

Truth / Falsity

of statements



1.1. Truth-values table for PPL for two variables.



In a formal logical system all possible logical relations are completely defined by a chosen vocabulary by means of a Truth values-table.
The Truth-values table for the most simple logical system, propositional logic (PPL), covers - for any chosen formalism or format - in any way all basic combinations that are involved in the most elementary beginning of any form of reasoning. Because of this, it really provides the very first, necessary foundings of accurate combinatory thinking.

Truth-values table PPL - for one variable.


This Truth-values table contains all possible orderings of values of two variables (propositions) in PPL, than can adopt two values.
The basis consists of one variable by two values = two basic combinations. With this, two order s are possible of series of truth values: each of which reflects a unique logical relation. Thus the following table arises of the most simple nature, of two rows by two columns is four cells.

1 2
1 0
0 1
T F
A ¬A
¬B B


Truth values


1

±

0

True

,
verum: Verification.

Unspecified

,
uninterpreted: Indefinite.

False

,
falsum: Falsification.

Truth value

(value, valor):

$

(G)

=

1.
(0

<

$

(G)

<

1).

$

(G)

=

0.

Truth value assignment

(valuation):
V!(G) :=1.
¬V!(G) {0,1}.
V!(G) :=0.

Truth value determination

(evaluation), through a finite proof:
i E![i] G.
i E![i] G) j E![j] ¬G).
i E![i] ¬G.

Interpretation

(denotation, assignment):
m

M

![m] G.
m

M

![m] G) n

M

![n] ¬G).
m

M

![m] ¬G.



Level II:

 

Satisfiability / validity



2.1. Truth-values table for PPL - bivalid.



This truth-values table contains all possible ordenings of values under the combination of two variables that each can adopt two values.
Its base consists of 2 values to the power of 2 variables = 4 basic combinations or (possible) domain states.
With this, 2 to the power of 4 = 16 orders are possible of series of truth values.
Each of these reflects a unique logical relation, or (possible) domain states-relation.
Thus the following table arises of 4 rows by 16 columns is 64 cells; each containing one precise truth value.

Table   bivalid value combinations - with two variables, interpreted for PPL


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0
1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1
1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0
T F A B ¬A ¬B A B A ¬B ¬A B ¬A ¬B A B A ¬B ¬A B ¬A ¬B A B A # B
¬F ¬T ¬¬A ¬¬B ¬A ¬B ¬(¬A ¬B) ¬(¬A B) ¬(A ¬B) ¬(A B) ¬(¬A ¬B) ¬(¬A B) ¬(A ¬B) ¬(A B) ¬(A # B) ¬(A B)
                  A \ B   A B A B A

||

B
   


2.2. Truth-values table for PDL - bivalid.



In predicate logic (PDL) attributes (or predicates) may be applied to various domain elements.
Because of this, the combinatory possibilities again increase in hyper-exponential ways.
Next, in PDL so-called quantors may be applied to predications on object-variables, to represent systematic relations between predications with identical predicate names, on identical variable names in a concise manner (conjunctive relations through universal quantors, disjunctive relations through existential quantor). However, before we succeed in finding these regularities, we still have tot deal with that combinatory explosion.
Following here is a simple example: for a bivalid system, of a 'tiny' size: consisting of one predicate, of arity one, and a domain of only two elements. With this we end up again with 16 possible logical relations.

Table   bivalid value combinations - with two variables, interpreted for PDL


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0
1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1
1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0
T F A1 A2 ¬A1 ¬A2 A1 A2 A1 ¬A2 ¬A1 A2 ¬A1 ¬A2 A1 A2 A1 ¬A2 ¬A1 A2 ¬A1 ¬A2 A1 A2 A1 # A2
¬T ¬F ¬¬A1 ¬¬A2 ¬A1 ¬A2 ¬(¬A1 ¬A2) ¬(¬A1 A2) ¬(A1 ¬A2) ¬(A1 A2) ¬(¬A1 ¬A2) ¬(¬A1 A2) ¬(A1 ¬A2) ¬(A1 A2) ¬(A1 # A2) ¬(A1 A2)
                  A1 \ A2   A1 A2 A1 A2 A1

|

A2
   
            x A[x]     ¬x A[x] x A[x]     ¬x A[x]    
            ¬x ¬A[x]     x ¬A[x] ¬x ¬A[x]     x ¬A[x]    



2.3. Truth value and logical power.



Logical power is inversely proportional to truth value.
Given a formula F - that is a each possible logical relation under formal system

L!

- of set T* (with size t

=

v**(v**d)). The following applies:
(a)

Logical power and contradiction.


F is derivable from the maximum logical power in

L!

: i.e. contradiction (falsity under all conditions); or falsity; or truth value

$

0.
{ j ( (F[j] T*)   ($0 F[j]) )j;
j ($0 F[j]) j;
($0 ( j F[j]) );
($0 ( j F[j]) );
($0 ( j F[j]) );
($0 ( T*)) }.
(b)

Logical power and truth.


F serves to derive the minimum logical power in

L!

: i.e. validity (truth under all conditions); or truth; or truth value

$

1.
{ j ( (F[j] T*)   (F[j]

$

1) )j;
j (F[j]

$

1) j;
(( j F[j])

$

1 );
(( j F[j])

$

1 );
((j F[j])

$

1 );
(( T*)

$

1 ) }.
(c)

Contradiction, Logical power and truth.


Combining (a) and (b).
{ j ( (F[j] T*)   ( ($0 F[j]) (F[j]

$

1) ) )j;
j ( ($0 F[j]) (F[j]

$

1 ) )j;
( ($0 (j F[j]) ) ( (j F[j])

$

1 ) );
( ($0 (j F[j]) ) ( (j F[j])

$

1 ) );
( ($0 (j F[j]) ) ( (j F[j])

$

1 ) );
( ($0 (j F[j]) ) ( (j F[j])

$

1 ) );
( ($0 ( T*)) ( ( T*)

$

1) );
($0

$

1) }.


2.4. Formulas in standarized vorm.



In formal logic a set of logical formulas is called a theory. The formulas in the set in general refer to statements or arguments (propositions).

In formal logic a number of standarized forms exists by which formulas or sets of formulas can be represented in a clear, precise and compact manner, so that they can be processed and be judged efficiently, so-called normal forms. ]-->
A convenient form for formulas when we want to judge them is the Conjunctive Normal Form (

CNF

). A formula in

CNF

consists of a conjunction of disjunctions. In other words, on the mainline of argumentation a juxtaposition of one or more conjuncts exists, while each conjunct is a disjunction consisting of at least one simple formula (an atom or a literal).
A

CNF

thus makes only use of the connectives {¬, , }.

General structure of a

CNF

set:


{ (T*

=

WFF*(

L!

PDl));
( k ( (K*[k]

CNF

*(T*))
(K*[k]

=

{ [ F[1] [ F[2] .. ] ] F[n[k]] } )
(n[k]

=

|

K*[k]

|

)
(K*[k]

=

{ (j[k]=1,..n[k]) F[j[k]] } )
( ( j ( (F[j] K*[k])
F[j]

=

{ [ G[j,1] [ G[j,2] .. G[m[j[k]]] ] ] } )
(m[j[k]]

=

|

F[j]

|


( (F[j]

=

{ (h[j[k]]=1,..h[n[k]]) G[h[j[k]]]) } )
( (0

>

j[k]

n[k] )   (0

>

h[j[k]]

m[j[k]]) ) ) )j )k ) }.


2.5. Judging theories (sets of propositions).



How can we judge the logical 'status', or semantical value, of such a set? This is dependent of the formal system, or the logical language in which the set has been formulated.

We can only mention some preconditions that in general apply to judge a set of formulas.

General requirements for judging a theory :


(a)

The set is valid (is a tautology).


{ k ( (K*[k]

CNF

*(T*))
( ( j ( (F[j] K*[k])
( (F[j]

$

=

1)
( (

|

F[j]

|

>

1) ( h ( (G[h[j[k]]] F[j]) (G[h[j[k]]]

$

=

1) )h ) ) ) )j )
) (K*[k]

$

=

1) )k }.

(b)

The set is inconsistent (contains contradiction).


{ k ( (K*[k]

CNF

*(T*))
( ( j ( (F[j] K*[k])
( (F[j]

$

=

0)
( (

|

F[j]

|

>

1) ( h ( (G[h[j[k]]] F[j]) (G[h[j[k]]]

$

=

0) )h ) ) ) )j )
) (K*[k]

$

=

0) )k }.

(c)

The set is contingent (is undecided).


Neither (a) nor (b).


2.6. Contingency and Presupposition.



To be distinguished:
(1) Logical presupposition is what completes the grounds of an invalid inference pattern (in particular, contingency), thus making the latter valid.
She is only bounded to universal abstract patterns following laws and principles of a system of (formal, or combinatory) logic.
(2) Linguistic presupposition is different: namely, what is implied by a language expression or sign-giving regardless of any truth value of the latter in her references (is as it where a consequens in termines).
She is bounded to specific language symbols and structures following conventional rules of syntax and lexicon of a (human) language system.
Both are therefore not directly physically-bound (i.e. not to time, space, energy, matter).
(3) A prejudice is an internal, mental or psychological content, in particular of cognitive nature.
Thus she is bounded to a person or group (performative, author, source). Because of this, she is at least in part, and at least first - through neuro-physiology - physically-bound. Thus she is essentially incidental of nature (although possibly of relative long duration). She precedes in time actual conclusions, decisions, utterances, behavior, etc..
The mutual relations:
(·) Any given language expression may imply a linguistic presupposition.
(·) A linguistic presupposition may originate from the presence of a psychological (cognitive) content - or, not too rarely, absence of such.
(·) A psychological (cognitive) content may entirely or partly be construed on basis of the presence of prejudice.
(·) A prejudice may come from an invalid inference c.q. contingency.
(·) An invalid inference, in particular a contingency, necessarily and simultaneously implies a logical presupposition.

Notice how only the latter relation is necessarily always valid, and may also be derivable in a explicit, complete, precise and secure way .. (although dependent of finitely-provability and Decidability).

{ A formula F[j] is contingent:
j ( CONTIN(F[j] );
F[j] is neither true, nor false;
( ((¬ F[j]) ¬F[j]))
• The truth-value pattern c[t] of F[j] lies between

$

0[00..] and

$

1[11..].
( t ( (F[j]$ = c[t]) ($0

<

c[t]

<

$

1) )t;
• There exists a formula X[i]) that is logically equivalent to F[ j], and that is syntactically identical to the maximal semantical reduct of F[j], i.e. F[j]

equiv-reduc

.
( i ( ( (F[j] X[i])
(F[j]

equiv-reduc

=

(

syn

)
X[i])
((¬ X[i]) ¬X[i])) );
(X[i] F[j]);
(X[i] ( F[j]));
('Assuming X[i] satisfies F[j])' *
('F[j] presupposes X[i])' * )i ) )j }.


2.7. Basic Valid and Invalid derivations.



(a)

Equivalent-validity.


(Semantical equivalent-reduction; Paraphrase).
E.g.: { h j ( (¬F[h] G[j]) (F[h] G[j]) )j ,h }.
(b)

Degressive-validity.


(Semantical degressive-reduction; Subsumption).
E.g.: { h j ( (F[h] G[j]) (

degres

)
( k l ( (F[h] C[k]) (G[j] D[l]) )l ,k ) )j ,h }.
(c)

Contingent-invalidity.


(non sequitur [nonseq] fallacy).
E.g.: { h j ( (F[h] G[j]) (

nonseq

)
( ( k ( (F[h] D[k]) G[j] )k ) ( l ( F[h] (G[j] C[l]) )l ) ) )j ,h }.
(d)

Inconsistent-invalidity.


(Contradiction; Reductio ad absurdum).
E.g.: { h j ( (F[h] G[j]) (

contrad

)
(F[h] ¬G[j]) )j ,h }.

Inference in Logic - Basic valid and
      invalid derivations


2.8. Validity, Satisfiability and Contingency.




Diagram   Validity / Satisfiability / Contingentie


1

±

0

Not necessarily untrue

:

Satisfiable

,
'Logically possible'.
(Is not yet equivalent to 'possibly true').

SATBL(G);
(TAUT(G) CONTIN(G);
¬ ¬G;
(( G ) ( ¬G ) ) );
    { k ( (G$ = c[k]) (c[k]

>

$

0) )k };
    { j F[j] G };
    { m

M

![m] G }.

    { j ((F[j] ¬F[j]) G) };

Impossibly true

:

Unsatisfiable

,
Logically excluded.
'Excluded grounds'.

¬SATBL(G);
 
¬G;
 
    { k ( (G$ = c[k]) (c[k] =

$

0) )k };
    j ((¬ ¬F[j]) (F[j] G)) };
    m

M

![m] G }.

    { j ((F[j] ¬F[j]) G) };

Consistency

,
Widerspruchsfreiheit.

Set K* is consistent:
From K* no contradiction is derivable.

CONSIS(K*);

{ ¬( (K* G) (K* ¬G) ) };
{ ¬(K* ) };

{ j ( ¬( (K* F[j]) (K* ¬F[j]) )j };
{ j ( ¬( {K* F[j]} )
  ¬( {K* ¬F[j]} ) )j };
    { ¬j ( ( F[j] K* )
      ( ¬F[j] K* ) )j }.

Inconsistency

,
Inconsistent-invalidity.

Set K* is inconsistent.
From K* a contradiction can be derived.

INCNS(K*);
¬CONSIS(K*);
{ (K* G) (K* ¬G) };
{ K* };

{ j ( (K* F[j]) (K* ¬F[j])j };
{ j ( ( {K* F[j]} )
  ( {K* ¬F[j]} ) )j };
    { j ( ( F[j] K* )
    ( ¬F[j] K* ) )j }.

Consistency theorem

,
Fundamental theorem (Model-existence theorem):

'Consistency implies Satisfiability'.
(Every subset : (Consistent Satisfiable)).

{CONSIS(K*) SATBL(K*)};
{¬(K* ) ¬(K* )}.

Necessarily / always true

:

Valid

,
Tautology,
Valid-satisfiability.


TAUT(G);

G;
    { k ( (G$ = c[k]) (c[k] =

$

1) )k };
    j ((¬ ¬F[j]) (F[j] ¬G)) };
    m

M

![m] ¬G }.

    j (F[j] ¬F[j] G) };

Undecided:


Contingency

,
Contingent-invalidity,
Contingent-satisfiability.
Insufficiently grounded,
Indefinite.

CONTIN(G);
{SATBL(G) ¬TAUT(G)};
{(¬ G) ¬G)};
    { k ( (G$ = c[k])
    ($0

<

c[k]

<

$

1) )k };
    { j ((¬ ¬F[j]) (F[j] G)) }
        { k ((¬ ¬F[k]) (F[k] ¬G)) };
    { (m

M

![m] G)
        (n

M

![n] ¬G) }.

Not necessarily-true

:

Invalid

,
non sequitur [nonseq]:

NONSEQ(G);
¬TAUT(G);
(CONTIN(G) ¬SATBL(G);
¬ G;
    { k ( (G$ = c[k]) (c[k]

<

$

1) )k };
    { j ((¬ ¬F[j]) (F[j] ¬G)) };
    { m

M

![m] ¬G }.

Correctness


(Soundness in-formele-zin):
'Derivable implies logical consequence'.

Set K* is correct.
(Every subset :
  (Derivable Logical consequence).

CORRECT(K*);
{DRVBL(K*,G) SEQUIT(K*,G)};
{ (K* G) (K* G) };
{ j ( (K* F[j]) (K* F[j]) ) }.

 

Completeness


(Vollständigkeit).
'Validity implies Derivability'.

Set K* is complete:
(Every subset :
  (Logical consequence Derivable)).

COMPLET(K*);
{SEQUIT(K*,G) DRVBL(K*,G)};
{ (K* G) (K* G) };
{ j ( (K* F[i]) (K* F[j]) ) }.

 

Maximal consistency:



Set K* is maximally consistent:
(Every subset :
  (Logical consequence Derivable)).

MAXCONS(K*);
{ CONSIS(K*) COMPLET(K*) };
{ (K* G) (K* G) };
{ j ( (K* F[j]) (K* F[j]) )j };
{ j ( CONSIS(K* \ {F[j]})
  ¬CONSIS(K* {F[j]}) )j };
{ j ( ( (F[j] K*)
    ( {K* ¬F[j]} ) )
  ( ¬(F[j] K*)
      ¬( {K* F[j]} ) ) )j };
Implications:
  { j ( (F[j] K*)
     

||

F[j] K*) )j };


(·) Completeness of PPL:
proof by Emil L. Post (1920, Introduction to a general theory of elementary propositions).
(·) Completeness of PDL-I:
proof by Kurt F. Gödel (1929/1930, Über die Vollständigkeit des Logikkalküls).

(·) Incompleteness of elementary arithmetic (first-order theory of natural numbers according to the logicistic research program, that was based on classic logic in the Organon of Aristotelis, and had been further developed in the Grundgesetze der Arithmetik of F.L. Gottlob Frege (1893, 1903) and the Principia Mathematica of Bertrand Russell and Alfred North Whitehead, parts I-III (1910, 1912, 1913):
proved by Kurt Gödel (1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme 1).



2.9. Relations between logical criteria of level II.



(1)

Valid statement or inference.


(By assumption or (re)presentation).
'From strong to weak'.
( Valid Satisfiable /Consistent ).

( Unsatisfiable /Inconsistent /Contradiction Invalid ).

(2)

Invalid statement or inference: Fallacy.


(By assumption or (re)presentation).
'From Weak to stromg'.
¬ ( Valid Contingent ).
¬ ( Valid Invalid ).
¬ ( Valid Unsatisfiable /Inconsistent /Contradiction ).

¬ ( Satisfiable /Consistent Valid ).
¬ ( Satisfiable /Consistent Contingent ).
¬ ( Satisfiable /Consistent Invalid ).
¬ ( Satisfiable /Consistent Unsatisfiable /Inconsistent /Contradiction ).

¬ ( Contingent Valid ).
¬ ( Contingent Satisfiable /Consistent ).
¬ ( Contingent Invalid ).
¬ ( Contingent Unsatisfiable /Inconsistent /Contradiction ).

¬ ( Invalid Valid
¬ ( Invalid Satisfiable /Consistent ).
¬ ( Invalid Contingent ).
¬ ( Invalid Unsatisfiable /Inconsistent /Contradiction ).

¬ ( Unsatisfiable /Inconsistent /Contradiction Valid ).
¬ ( Unsatisfiable /Inconsistent /Contradiction Satisfiable /Consistent ).
¬ ( Unsatisfiable /Inconsistent /Contradiction Contingent ).



Level III.

 

Decidability and Recursivity of formal systems




Diagram   Decidability and Recursivity


1

±

Decidable

:

The question whether an expression G has a definite (truth) value, can always be answered:
The (truth) value of G is always derivable through a finite proof.

UnDecidable

:

The question whether an expression G has a definite (truth) value, can not always be answered:
The (truth) value of G is not always derivable through a finite proof.

G is Truth-value Decidable:
DECIDBL(G);
{(   ( G  

$

1) )  

||

(   ( G  

$

0) ) };
{(   (   G ) )  

||

(   (   ¬G ) ) };
Implications:
    {   ( (   G )  

||

(   ¬G ) ) }.
    {   (   ( G  

||

¬G ) ) };
    {   ( G  

||

¬G ) };
    { G  

||

¬G } (always logical value).
   

$

1 (truth).

G is Not truth-value deDecidable:
¬DECIDBL(G);
{ (¬   ( G  

$

1) )     ( G  

$

0) ) };
{ (¬   (   G ) )     (   ¬G ) ) };
Implications:
    { ¬   ( (   G )  

||

(   ¬G ) ) };
    { ¬   (   ( G  

||

¬G ) ) };
    { ¬   ( G  

||

¬G ) };
    { } (no logical value);
   

$

0 (no truth).

G is Validity Decidable:
{ (   (   G) )  

||

(   (¬   G) ) };
Implications:
    {   ( (   G )  

||

( ¬   G ) ) };
    { (   G )  

||

( ¬   G ) }.
    { TAUT(G)  

||

¬SATBL(G) } (always validity value).
   

$

1 (truth).

G is determinate.

G is Not validity Decidable:
{ (¬   (   G) )     (¬   G) ) };
Implications:
    { ¬   ( (   G )  

||

( ¬   G ) ) }.
    { ¬(   G )   ¬(   ¬G ) }.
    { CONTIN(G) } (no validity value).
   

$

0 (no truth).

G is indeterminate.

Recursive:


For all input, the system will be 'halting' (terminating in finite time).

Non-recursive:


For some input the system will be infinitely 'looping'.

RC(G);
{ RE(G) CO-RE(G) };
{ (   (   G) )  

||

(   (¬   G) ) };
Implications:
    {   ( (   G)  

||

  (¬   G) ) }.

¬RC(G);
{ ¬RE(G) ¬CO-RE(G) }.
{ (¬   (   G) )     (¬   G) ) };
Implications:
    { ¬   ( (   G)  

||

  (¬   G) ) }.

Recursively
  enumerable
:



Formula G
is Recursively enumerable:
If G has a result,
then that will always be provable.

RE(G);
{ j ( (G F[j])
  (G F[j]) )j }.

Co-recursively
  enumerable
:



Complement of G
is Recursively enumerable:
If G has no result,
then that will always be provable.

CO-RE(G);
{ j ( ¬(G F[j])
  ¬(G F[j]) )j }.

Not

recursively
  enumerable
:



Formula G
is not Recursively enumerable:
If G has a result,
then that will not always be provable.

¬RE(G);
{ j ( (G F[j])
  ¬ (G F[j]) )j }.

Not

co-recursively
  enumerable
:



Complement of G
is not Recursively enumerable:
If G has not a result,
then that will not always be provable.

¬CO-RE(G);
{ j ( ¬(G F[j])
  ¬ ¬(G F[j]) )j }.

Set K*
is Recursively enumerable:
If K* has a result,
then that will always be provable.

RE(K*);
{ k ( (Ks*[k] K*)
  j ( (Ks*[k] F[j])
    (Ks*[k] F[j]) )j )k }.

Complement of K*
is Recursively enumerable:
If K* has no result,
then that will always be provable.

CO-RE(K*);
{ k ( (Ks*[k] K*)
  j ( ¬(Ks*[k] F[j])
    ¬(Ks*[k] F[j]) )j )k }.

Set K*
is not Recursively enumerable:
If K* has a result,
then that will not always be provable.

¬RE(K*);
{ k ( (Ks*[k] K*)
  j ( (Ks*[k] F[j])
    ¬ (Ks*[k] F[j]) )j )k }.

Complement of K*
is not Recursively enumerable:
If K* has no result,
then that will not always be provable.

¬CO-RE(K*);
{ k ( (Ks*[k] K*)
  j ( ¬(Ks*[k] F[j])
    ¬ ¬(Ks*[k] F[j]) )j )k }.

Set K*
is Recursively enumerable
(through Turing Machine procedure):
If K* has a result,
then that will always be computable.

RE(K*)TM;
{ k ( (Ks*[k] K*)
  j h (
    (TM[h](Ks*[k]) F[j])
      m (TM[m](K*)
        (TM[h](Ks*[k]) F[j]) )m   )h ,j )k }.

Complement of K*
is Recursively enumerable
(through Turing Machine procedure):
If K* has no result,
then that will always be computable.

CO-RE(K*)TM;
{ k ( (Ks*[k] K*)
  j h (
    ¬(TM[h](Ks*[k]) F[j])
      m ( (TM[m](K*)
        ¬(TM[h](Ks*[k]) F[j]) )m   )h ,j )k }.

Set K*
is not Recursively enumerable
(through Turing Machine procedure):
If K* has a result,
then that will not always be computable.

¬RE(K*)TM;
{ k ( (Ks*[k] K*)
  j h (
    (TM[h](Ks*[k]) F[j])
      ¬m (TM[m](K*)
        (TM[h](Ks*[k]) F[j]) )m   )h ,j )k }.

Complement of K*
is not Recursively enumerable
(through Turing Machine procedure):
If K* has no result,
then that will not always be computable.

¬CO-RE(K*)TM;
{ k ( (Ks*[k] K*)
  j h (
    ¬(TM[h](Ks*[k]) F[j])
      ¬m (TM[m](K*)
        ¬(TM[h](Ks*[k]) F[j]) )m   )h ,j )k }.


(·) 'Effective procedure' (Hilbert, 1900, 1928).
(·) 'Recursive function' (Gödel, 1930, 1931).
(·) 'Lambda definable function' (Church, 1935, 1936).
(·) 'Turing Machine computable function' (Turing, 1936, 1937).


(·) UnDecidability/ non-recursivity
of elementary calculus of natural numbers (elementary number theory):
proof by Alonzo Church, (1935/1936, An Unsolvable Problem of Elementary Number Theory).
(·) UnDecidability/ non-recursivity
of entire elementary arithmetic (first order arithmetic):
proof by Alan M. Turing (1936/1937, On computable numbers, with an application to the Entscheidungsproblem).




4.

Table with Some Milestones in Meta-logic



Author Year Formalism Domain Criterion
Hilbert 1900,1928 Effective procedure (hypothetical) Mathematics, Logic Decidability;
Entscheidbarheit;
Entscheidungs-definitheit;
Post 1920 Truth table method
PPL Completeness;
Vollständigkeit.
Gödel 1929/1930 Deduction PDL-I Completeness;
Vollständigkeit.
Recursively enumerable
Gödel 1931 Gödel-numbering PDL-I, Arithmetic of Natural numbers
First-order theory of natural numbers
(Principia Mathematica)
Einige formal unentscheidbare Satze:
Incompleteness;
Unvollständigkeit.
Not recursively enumerable.
Church 1935/1936 Lambda-calculus
(Lambda-definable):
Recursive functions of positive integers
PDL-I, Arithmetic of Natural numbers:
Elementary number theory
Unsolvable problem:
UnDecidability;
Unentscheidbarheit.
Turing 1936/1937 (Universal) Turing machine
(Turing machine computability)
PDL-I, Arithmetic:
First order arithmetic
UnDecidability;
Unentscheidbarheit.



5. Criteria in formal logic



In the overview ' Criteria in Formal Logic' the most important criteria in formal logic are being discussed.
These criteria may be applied to formulas, sentences, sets, theories and (language) systems in logic.
They are meant to represent entirely accurate the most essential characteristics of certain data: quality, scope, possibilities but also limitations.

Criteria in Formal Logic



(1)

Semantic criteria


Criteria for decisions about content aspects of language expressions.
A.o. satisfiability, validity, contingency, finite-satisfiability, compactness, etc..
(1a) Satisfiability: (Logical possibility): Truth under at least one possible interpretation.
((Well-formed not-Refuted) Satisfiable).
(1b) Validity (tautology):) Truth under any possible interpretation.
((Well-formed always-True) Valid).
(1c) Contingency: Satisfiable, but not valid.
(Truth under at least one possible interpretation, maar not all).
((Well-formed (Satisfiable not-Valid)) Contingent).
(1d) Finite-satisfiability: A (sub)set of formulas is finite and satisfiable.
(((Sub)set (Well-formed (Finite Satisfiable))) Finite-satisfiable).
(1e) Compactness: If every finite subset of a - possibly infinite - set is satisfiable, that the entire set is satisfiable.
(((Every subset:   (Well-formed Finitely satisfiable)) Satisfiable) Compact).

(2)

Syntactical criteria.


Criteria for decisions about aspects of form and structure of statements.
A.o. derivability, provability, consistency.
(2a) Derivability: Derivable through syntactical production rules.
((Well-formed result of purely formal operations) Derivable).
(2b) Provability (finite-derivability): Syntactical derivable through a finite derivation chain.
(((Well-formed result of finite series of purely formal operations) Finite-derivable) Provable).
(2c) Consistency: Derivable guarantees non-contradiction.
((Derivable Non-contradiction) Consistent).
(2d) Maximal consistency: Consistency guarantees inconsistency with every possible (nonredundant, conjunctive) expansion.
((Consistent (adding of any other formula inconsistent)) Maximally consistent).
(2e) Negation-completeness: A set K* contains for every well-formed formula in the language either the confirmation, or the negation.
((Every subset:   (Well-formed (Truth decision (either True, or False)))) Negation-complete).

(3)

Semantical criteria, in relation to syntax:


Ie. projections from semantics to syntax.
A.o. completeness.
(3a) Syntactical - Adequacy.
Satisfiability guarantees Consistency.
((Every subset:   (Satisfiable Consistent)) Adequate).
(3b) Syntactical - Completeness (proof potential, Vollständigkeit): Truth/ validity guarantees Derivability.
((Every subset:   (True/ valid Derivable)) Complete).

(4)

Syntactical criteria, in relation to semantics:


Ie. projections from syntax to semantics.
A.o. consistency theorem, correctness, Decidability.
(4a) Fundamental theorem, consistency theorem: Consistency guarantees satisfiability.
((Every subset:   (Consistent Satisfiable)) Fundamental theorem).
(4b) Logical correctness of formal systems ('soundness', in weak sense, deductive power): Derivability guarantees Validity.
((Every subset:   (Derivable True/ Valide)) Correct)).
(4c) Logical 'soundness' of formal systems (in strong sense): Derivability guarantees Logical Consequence.
((Every subset:   (Derivable Logical consequent)) Sound).
(4d) Reductio ad absurdum: Logical validity guarantees Non-contradiction.
In other words, from provability of contradiction derived from the opposite, follows logical validity.
Principle of proof by 'refutation of the opposite'.
((Well-formedness (Opposite/Negation (Some conjunct subset: (Contradiction derivable: inconsistent)))) True/ Valid).
(4e) Decidability (decision capacity) of formal systems: Syntactical well-formedness guarantees validity decision.
(Well-formedness (Validity decision: (either Valid, or Invalid))) Validity Decidable).

C.P. van der Velde © 2006, 2018.