Science and Technology news... :: View topic

translogi · Guest

Hello

following another discussion

http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6abeff9b#

What is completeness exactly?

what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I forgot what the difference was.)

can anybody refresh my memory?

Chris Menzel · Guest

On Mon, 07 Jul 2008 19:03:55 +0200, Jan Burse <janburse@fastmail.fm> said:
[quote]translogi schrieb:
Hello

following another discussion

http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6abeff9b#

What is completeness exactly?

what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I forgot what the difference was.)

can anybody refresh my memory?

A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

A theory T is complete and has witnesses :<=> T is complete
and forall "exists A" (T |- exists A => exists t T |- A[x/t])
[/quote]
That>s often referred to as "negation" completeness. There is also a
notion of completeness -- often referred to as "semantic" completeness
-- that applies to logics rather than theories. Say that a logic is a
language L together with a semantics and a proof theory. A logic is
*complete* if every logical truth of L (i.e., every sentence that is
true in every interpretation of L according to the semantics) is a
theorem of the proof theory. This is sometimes referred to as "weak"
(semantic) completeness. A logic is strongly complete if, whenever a
set S of sentences of L entails a sentence A of L, there is a proof of A
from S. (S entails A if every interpretation that makes all the
sentences in S true also makes A true.)

Jan Burse · Guest

translogi schrieb:
[quote]Hello

following another discussion

http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6abeff9b#

What is completeness exactly?

what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I forgot what the difference was.)

can anybody refresh my memory?
[/quote]
A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

A theory T is complete and has witnesses :<=> T is complete
and forall "exists A" (T |- exists A => exists t T |- A[x/t])

Bye

bRAINS · Guest

On Jul 7, 6:03 pm, Jan Burse <janbu...@fastmail.fm> wrote:
[quote]translogi schrieb:

Hello

following another discussion

http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6a...

What is completeness exactly?

what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I forgot what the difference was.)

can anybody refresh my memory?

A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

A theory T is complete and has witnesses :<=> T is complete
and forall "exists A" (T |- exists A => exists t T |- A[x/t])

Bye
[/quote]
I was quite interested, then it went all math, math don>t help much
here I feel

Sorry
bRaInS
http://www.justservices.com/9ukp.html

Rupert · Guest

On Jul 7, 7:48 am, translogi <wilem...@googlemail.com> wrote:
[quote]Hello

following another discussion

http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6a...

What is completeness exactly?

what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I forgot what the difference was.)

can anybody refresh my memory?
[/quote]
Hintikka distinguishes three kinds of completeness, deductive
completeness, descriptive completeness, and semantic completeness.

A theory in some language containing all the propositional connectives
is deductively complete with respect to a certain logic, if for any
sentence either the sentence or its negation is in the theory.

A theory is descriptively complete with respect to a certain semantics
if it only has one model up to isomorphism.

A logic is semantically complete with respect to a certain semantics
if every validity is provable in the logic.

You can have second-order theories which are deductively incomplete
with respect to second-order logic as standardly axiomatised, but
descriptively complete. Second-order Peano arithmetic and real
analysis are examples. This is because second-order logic is
semantically incomplete. On the other hand, first-order logic is
semantically complete, so a first-order theory will be deductively
complete if and only if it is descriptively complete.

One speaks of "strong completeness" and "weak completeness" for the
propositional calculus and for the first-order predicate calculus.
These are both forms of semantic completeness. The "weak completeness
theorem" for the first-order predicate calculus says that a finite set
of sentences is consistent if and only if it has a model. The "strong
completeness theorem" generalises this to sets of sentences which are
not necessarily finite. This is related to the compactness theorem.

Jan Burse · Guest

Chris Menzel schrieb:

[quote]That>s often referred to as "negation" completeness. There is also a
notion of completeness -- often referred to as "semantic" completeness
-- that applies to logics rather than theories. Say that a logic is a
language L together with a semantics and a proof theory. A logic is
*complete* if every logical truth of L (i.e., every sentence that is
true in every interpretation of L according to the semantics) is a
theorem of the proof theory. This is sometimes referred to as "weak"
(semantic) completeness. A logic is strongly complete if, whenever a
set S of sentences of L entails a sentence A of L, there is a proof of A
from S. (S entails A if every interpretation that makes all the
sentences in S true also makes A true.)
[/quote]
Yep,

And roughly if deduction theorem
and compactness holds, then weak = strong.

Proof:

=>: S |- A
<=>
S'|- A with S' finite
<=>
|- S' -> A
<=>
|= S' -> A
<=>
S' |= A with S' finite
<=>
S |= A

<=: |- A
<=>
{} |- A
<=>
{} |= A
<=>
|= A

Yes, maybe translogic was refering to this completness
of the |- in the other thread.

But it would be an add on to consider |=, as we
defined con() via |- in the other thread.

Bye

LauLuna · Guest

On Jul 7, 10:47 pm, Chris Menzel <cmen...@remove-this.tamu.edu> wrote:
[quote]On Mon, 07 Jul 2008 19:03:55 +0200, Jan Burse <janbu...@fastmail.fm> said:

translogi schrieb:
Hello

following another discussion

http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6a....

What is completeness exactly?

what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I forgot what the difference was.)

can anybody refresh my memory?

A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

A theory T is complete and has witnesses :<=> T is complete
and forall "exists A" (T |- exists A => exists t T |- A[x/t])

That>s often referred to as "negation" completeness. There is also a
notion of completeness -- often referred to as "semantic" completeness
-- that applies to logics rather than theories. Say that a logic is a
language L together with a semantics and a proof theory. A logic is
*complete* if every logical truth of L (i.e., every sentence that is
true in every interpretation of L according to the semantics) is a
theorem of the proof theory. This is sometimes referred to as "weak"
(semantic) completeness. A logic is strongly complete if, whenever a
set S of sentences of L entails a sentence A of L, there is a proof of A
from S. (S entails A if every interpretation that makes all the
sentences in S true also makes A true.)- Hide quoted text -

- Show quoted text -
[/quote]
So, let>s distinguish for logics between 'logical truth
completeness' (LTC) and 'logical consequence completeness' (LCC). You
say LCC is called 'strong' while LTC is called 'weak'.

I see that LCC entails LTC. But not vice versa? Are there any counter-
examples?

Thanks

MoeBlee · Guest

On Jul 7, 6:11 pm, bRAINS <BrainsH...@hotmail.co.uk> wrote:

[quote]I was quite interested, then it went all math, math don>t help much
here I feel
[/quote]
Yeah, definitely want to keep math out of mathematical logic.

I mean, what>s next, pepperoni on a pepperoni pizza? "Sir, I asked for
a pepperoni pizza. Why is there pepperoni on my pizza? When I order a
pepperoni pizza, that>s exactly what I expect to receive; not a pizza
with pepperoni all over it!"

MoeBlee

Jan Burse · Guest

bRAINS schrieb:
[quote]On Jul 7, 6:03 pm, Jan Burse <janbu...@fastmail.fm> wrote:
translogi schrieb:

Hello
following another discussion
http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6a...
What is completeness exactly?
what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I forgot what the difference was.)
can anybody refresh my memory?
A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

A theory T is complete and has witnesses :<=> T is complete
and forall "exists A" (T |- exists A => exists t T |- A[x/t])

Bye

I was quite interested, then it went all math, math don>t help much
here I feel

Sorry
bRaInS
http://www.justservices.com/9ukp.html
[/quote]
Stop Whining

http://www.sonofthesouth.net/uncle-sam/stop-whining.htm

Chris Menzel · Guest

On 09 Jul 2008 19:46:33 +0300, Aatu Koskensilta <aatu.koskensilta@uta.fi> said:
[quote]Rupert <rupertmccallum@yahoo.com> writes:

One speaks of "strong completeness" and "weak completeness" for the
propositional calculus and for the first-order predicate calculus.
These are both forms of semantic completeness. The "weak completeness
theorem" for the first-order predicate calculus says that a finite
set of sentences is consistent if and only if it has a model. The
"strong completeness theorem" generalises this to sets of sentences
which are not necessarily finite. This is related to the compactness
theorem.

The more usual definition is that a logic is weakly complete if there
is a deductive system in which all of its validities are provable and
strongly complete if there is a deductive system such that if A is a
logical consequence of B then B is derivable from A.
[/quote]
A from B, of course.

translogi · Guest

On Jul 9, 7:53 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
[quote]Chris Menzel <cmen...@remove-this.tamu.edu> writes:
On 09 Jul 2008 19:46:33 +0300, Aatu Koskensilta
aatu.koskensi...@uta.fi> said:

The more usual definition is that a logic is weakly complete if there
is a deductive system in which all of its validities are provable and
strongly complete if there is a deductive system such that if A is a
logical consequence of B then B is derivable from A.

A from B, of course.

That is an even more usual definition, yes.

--
Aatu Koskensilta (aatu.koskensi...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
[/quote]
Thanks all.

Where i am struggeling with
Completeness seems to presume universal substitution. (every variable
is replaceble with another variable of formula)

While deduction itself doesn>t presumes universal substitution

.so i guess
A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

is false

if a is an variable/ contingent neither T |- A nor T |- ~A

or am i mistaken?

.

MoeBlee · Guest

On Jul 9, 10:50 am, translogi <wilem...@googlemail.com> wrote:

[quote].so i guess
A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

is false

if a is an variable/ contingent neither T |- A nor T |- ~A
[/quote]
Do you mean where A is a formula that may have free variables in it?

If so, then, yes, "T is negation complete" does not say that for every
formula (even if it has free variables) A in the language of T, we
have T |- A or T |- ~A.

Rather, "T is negation complete" says that for every SENTENCE A in the
language of T, we have T |- A or T |- ~A.

MoeBlee

Aatu Koskensilta · Guest

Rupert <rupertmccallum@yahoo.com> writes:

[quote]One speaks of "strong completeness" and "weak completeness" for the
propositional calculus and for the first-order predicate calculus.
These are both forms of semantic completeness. The "weak completeness
theorem" for the first-order predicate calculus says that a finite set
of sentences is consistent if and only if it has a model. The "strong
completeness theorem" generalises this to sets of sentences which are
not necessarily finite. This is related to the compactness theorem.
[/quote]
The more usual definition is that a logic is weakly complete if there
is a deductive system in which all of its validities are provable and
strongly complete if there is a deductive system such that if A is a
logical consequence of B then B is derivable from A.

--
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Aatu Koskensilta · Guest

Chris Menzel <cmenzel@remove-this.tamu.edu> writes:

[quote]On 09 Jul 2008 19:46:33 +0300, Aatu Koskensilta
aatu.koskensilta@uta.fi> said:

The more usual definition is that a logic is weakly complete if there
is a deductive system in which all of its validities are provable and
strongly complete if there is a deductive system such that if A is a
logical consequence of B then B is derivable from A.

A from B, of course.
[/quote]
That is an even more usual definition, yes.

--
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

herbzet · Guest

translogi wrote:
[quote]
On Jul 9, 7:53 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
Chris Menzel <cmen...@remove-this.tamu.edu> writes:
On 09 Jul 2008 19:46:33 +0300, Aatu Koskensilta
aatu.koskensi...@uta.fi> said:

The more usual definition is that a logic is weakly complete if there
is a deductive system in which all of its validities are provable and
strongly complete if there is a deductive system such that if A is a
logical consequence of B then B is derivable from A.

A from B, of course.

That is an even more usual definition, yes.

--
Aatu Koskensilta (aatu.koskensi...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Thanks all.

Where i am struggeling with
Completeness seems to presume universal substitution. (every variable
is replaceble with another variable of formula)

While deduction itself doesn>t presumes universal substitution

.so i guess
A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

is false

if a is an variable/ contingent neither T |- A nor T |- ~A

or am i mistaken?

.
[/quote]
Propositional logic, Hilbert style, system A:

Three axioms:

1) p -> (q -> p)
2) (p -> (q -> r)) -> ((p -> q) -> (p -> r))
3) (~p -> ~q) -> (q -> p)

Definitional axioms for other propositional operators:

1) (phi & psi) =def ~(phi -> ~psi)
2) (phi v psi) =def (~phi -> psi)
3) and so on, ad lib.

Two inference rules:

1) Modus ponens (MP) -- From phi and (phi -> psi) deduce psi.
2) Universal substitution (US) -- In any theorem replace any variable
throughout the formula with any wff whatever.

This system is weakly complete: all tautologies are derivable from the
three axioms. It is not negation complete: neither the formula "p" nor
the formula "~p" is derivable. The system has strong completeness (also
called Post completeness, after Emil Post) in that the addition of any
formula as an axiom that is not already derivable, that is, the addition
of any non-tautology as a fourth axiom, will make the system inconsistent.

(An inconsistent system, BTW, is negation-complete.)

Propositional logic, Hilbert style, system B:

Three axiom schemas:

1) phi -> (psi -> phi)
2) (phi -> (psi -> chi)) -> ((phi -> psi) -> (phi -> chi))
3) (~phi -> ~psi) -> (psi -> phi)

Definitional axioms for other propositional operators:

1) (phi & psi ) =def ~(phi -> ~psi)
2) (phi v psi) =def (~phi -> psi)
3) and so on, ad lib.

One inference rule:

1) Modus ponens (MP) -- From phi and (phi -> psi) deduce psi.

This system differs from the first in that it has an infinite number
of axioms, and only one inference rule. The system may also be
conceptualized as the /exact same/ as system A, except that US
is restricted in its application to the three axioms only.

This system is weakly complete: all tautologies are derivable.
The system does NOT enjoy Post (or strong) completeness: we can
add, for example, the formula p as an axiom without the system
becoming inconsistent, because we have no substitution rule to
change p to, say, ~p.

Can this system be made negation complete (while remaining consistent)
by the addition of a finite or (r.e.) infinite number of axioms? I don>t
know.

Is this definition of strong (or Post) completeness equivalent to the
definition that has been proffered previously by other posters? I don>t
know.

But you are correct to notice how the rule of universal substitution
is involved here.

--
hz


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Logic Forum	Goto page 1, 2, 3, 4, 5, 6 Next
Page 1 of 6