Science and Technology news... :: View topic

herbzet · Guest

Balthasar wrote:
[quote]
On Wed, 16 Jul 2008 20:57:27 -0700 (PDT), MoeBlee <jazzmobe@hotmail.com
wrote:

... by just taking the Lesniewski axioms (or is it Lukaciewz [sp]?

Lukasiewicz

You should try to memorize his name. He gave propositional logic its
modern form.

So I decided it was better anyway just to use an ordinary ~ -> system,

As Frege and later Lukasiewicz (simplifying Frege>s system) did.
(Actually, Lukasiewicz & Tarski, btw.)

for sake of not getting bogged down with axioms harder to intuit and
read. Also, using ~ -> makes my system more familiar to most readers

Right.

You know that there>s a nice variant of this system, where "f" is a
primitive and "~" is defined.

A1 A -> (B -> A)
A2 (A -> (B -> [C])) -> ((A -> B) -> (A -> C))
A3 ((A -> f) -> f) -> A

Def. ~A =df A -> f.

Hence A3 can (could) be reformulated the following way

A3' ~~A -> A.

Which highlights that this system embodies _classical_ propositional
logic. :-)

B.

Reference: A. Church, Introduction to Mathematical Logic I, 1956
[/quote]
Another nice variant by Lukasiewicz is given in a recent post
by Jan Burse: news:g5iidf$gsm$1@news.albasani.net

--
hz

Balthasar · Guest

On Thu, 17 Jul 2008 15:11:41 -0700 (PDT), MoeBlee <jazzmobe@hotmail.com>
wrote:

[quote]
T1 E!xPhi[x] -> Phi[ixPhi[x]]
T2 ~E!xPhi[x] -> ixPhi[x] = 0.

Yes, that>s what I have too.

Sure. But I like Bernays' idea to take the operator i_t as a primitive.[/quote]
Hence not being forced to fix a "dummy object".

[quote]
But to make it truly rigorous, with 'i'
as a primitive variable binding operator, then requires double
induction to define the set of terms and formulas together. Then also
simultaneous recursion to define certain other syntactic operations.
Also, the semantics for such a language are at least a little more
involved than the usual Tarski recursive definition. So, it takes at
least a bit of maneuvering to compare such a theory with theories in
plain vanilla predicate logic.

Sure, it comes with a price. But the gain in expressive power (-not[/quote]
meant as a technical term here-) is considerable, imho. For example this
way you get "functions" for free!

With

AxE!yF(x,y)

we may define the total function

f(x) =df iyF(x,y).

etc.

B.

translogi · Guest

Ahh

At least two different kinds of completeness.

In this post I stick to (modal) propositional logic

A (Uppercase) is a well formed formula
p (lowercase) is a propositional variable

1 the opposite of soundness

|= A -> |-A

if (using a truthtable, or other mechanical means) a formula is always
true then that formula is provable .

also
if a formula A is unsatisfiable (never true) then |- ~A

(or is this a step to far)

2 negation completeness

All well formed formula>s are (provable) true or false.

for every A |-A or |- ~A

this is more complicated.

for this
all propositional variables need to have a fixed truth value
(otherwise neither |-p or |- ~p can be deduced)

am i forgetting something?

On Jul 16, 10:35 pm, MoeBlee <jazzm...@hotmail.com> wrote:
[quote]
That is a DIFFERENT sense of completeness. We>re not talking about
that sense of completeness. Also, it does not make sense to talk about
a formula being true if it is not known that the formula is a
sentence. Open formulas are not true or false in a model; rather open
formulas are satifisfied or not satisified in a model with an
assignment to the variables.

[/quote]
My question was about completeness in any sense.

Chris Menzel · Guest

On Sun, 20 Jul 2008 12:18:50 -0700 (PDT), translogi
<wilemien@googlemail.com> said:
[quote]Ahh

At least two different kinds of completeness.

In this post I stick to (modal) propositional logic

A (Uppercase) is a well formed formula
p (lowercase) is a propositional variable

1 the opposite of soundness
[/quote]
Better: the converse.

[quote]|= A -> |-A

if (using a truthtable, or other mechanical means) a formula is always
true
[/quote]
Whether one has a mechanical means of determining validity is completely
irrelevant to the definition. We do have such a means, of course, in
classical propositional logic and some modal logics, but we don>t in
predicate logic, yet the definition of (semantic) completeness still
applies.

[quote]then that formula is provable .

also
if a formula A is unsatisfiable (never true) then |- ~A

(or is this a step to far)
[/quote]
No, it is exactly equivalent in classical logic.

[quote]2 negation completeness

All well formed formula>s are (provable) true or false.
[/quote]
No, negation completeness has nothing whatever to do with truth. It is
a purely proof theoretic notion.

[quote]for every A |-A or |- ~A

this is more complicated.
[/quote]
No, this is wrong. Negation completeness is a property of theories, not
of logics. Perhaps you missed my earlier post, but a theory T is
negation complete if, for any formula A in the language of T, T |- A or
T |- ~A.

[quote]for this all propositional variables need to have a fixed truth value
(otherwise neither |-p or |- ~p can be deduced)
[/quote]
Again, the concept of negation completeness has absolutely nothing to do
with truth.

[quote]am i forgetting something?
[/quote]
Forgetting isn>t exactly the right concept.

Jan Burse · Guest

translogi schrieb:
[quote]am i forgetting something?
[/quote]
I will not deal with the completness of a calculus |-
versus a semantic |= now, i.e. |= => |-.

Lets deal with the completness of a theory T in
a calculus |-. We can define two completness
notions:

Formally Complete:

fcmp(T) :<=> forall A (T |/- A => ~con(T u A))

Negation Complete:

ncmp(T) :<=> forall A (T |- A v T |- ~A)

Theorems, for any theory T:
1) T Formally Complete => T Negation Complete
2) T Negation Complete => T Formally Complete

Proof: Left as an exercise to the reader.

Bye

Balthasar · Guest

On Thu, 17 Jul 2008 10:34:27 -0700 (PDT), MoeBlee <jazzmobe@hotmail.com>
wrote:

[quote]
But, as to oxymoronic sounding terminology, we still have 'singulary
connective' such as '~'. I mean, 'connective' suggests connecting one
thing to another, but the negation symbol doesn>t connect one formula
with another as do the binary connectives.

Let>s be precise: a n-ary connective "connects" n things in the sense[/quote]
that it "takes" n things (sentences) and results in a thing (sentence).
Now clearly a unary connective takes one thing (sentence) and results in
a sentence. And in the limit case we even have: a 0-ary connective takes
zero things (sentences) and results in a thing (sentence). The 0-ary
connective T results in a sentence which is always true. And the 0-ary
connective F results in a sentence which is always false.

Of course, I guess another possibility would be to treat "T" and "F" as
certain fixed sentences. I.e. "T" would denote a (the) sentence which is
always true, and "F" a (the) sentence which is always false). Hence no
need for 0-ary connectives in this case.

B.

MoeBlee · Guest

On Jul 18, 11:57 am, Balthasar <nomail@invalid> wrote:

[quote]Sure, it comes with a price.
[/quote]
You gonna pay it for us?

I think part of that price would include:

(1) Formulate and prove a theorem for double induction. (Torkel
Franzen showed me some of the key steps in the particular case of
double induction to together define the set of terms and set of
formulas, but I>ve not gotten around to finishing it up.)

(2) Provide the definitions by simultaneous recursion to define the
various syntactical operations that are ordinarily defined by
recursion.

(3) Reformulate, with simultaneous recursion, Tarski>s semantics for
the denotation of terms and satisfication of formulas.

MoeBlee

MoeBlee · Guest

On Jul 20, 12:18 pm, translogi <wilem...@googlemail.com> wrote:
[quote]Ahh

At least two different kinds of completeness.

In this post I stick to (modal) propositional logic
[/quote]
Modal logic? I thought we were talking about plain propositional logic
and plain predicate logic.

[quote]A (Uppercase) is a well formed formula
p (lowercase) is a propositional variable

1 the opposite of soundness

|= A -> |-A

if (using a truthtable, or other mechanical means) a formula is always
true then that formula is provable .
[/quote]
That>s completeness for propositional logic.

[quote]also
if a formula A is unsatisfiable (never true) then |- ~A
[/quote]
That>s another way of stating completeness for propositional logic.

[quote](or is this a step to far)

2 negation completeness

All well formed formula>s are (provable) true or false.

for every A |-A or |- ~A
[/quote]
Just say,

For every well formed formula, eihter it or its negation is provable.
For every A |-A or |- ~A

[quote]this is more complicated.

for this
all propositional variables need to have a fixed truth value
(otherwise neither |-p or |- ~p can be deduced)
[/quote]
No, rather it is just not the case that propositional logic itself is
negation-complete. We don>t WANT propositional logic itself to be
negation complete. Rather, we seek for certain THEORIES to be negation
complete. The propositional theory that is just the pure set of
formulas derivable from propositional logic ALONE (i.e., no non-valid
axioms) is NOT and SHOULD NOT BE negation complete.

[quote]am i forgetting something?
[/quote]
You seem to have been expecting that pure propositional logic is
negation complete or should be negation complete.

MoeBlee

MoeBlee · Guest

On Jul 21, 5:14 am, Balthasar <nomail@invalid> wrote:
[quote]On Thu, 17 Jul 2008 10:34:27 -0700 (PDT), MoeBlee <jazzm...@hotmail.com
wrote:

But, as to oxymoronic sounding terminology, we still have 'singulary
connective' such as '~'. I mean, 'connective' suggests connecting one
thing to another, but the negation symbol doesn>t connect one formula
with another as do the binary connectives.

Let>s be precise: a n-ary connective "connects" n things in the sense
that it "takes" n things (sentences) and results in a thing (sentence).
[/quote]
Sure, if that is the sense of 'connect', then, of course, 'unary
connective' is not oxymoronic sounding.

MoeBlee

translogi · Guest

Thank for your comments,

as far as i understand them i have put them in my new sumary. comments
are between {}
Did also do some studying from other sources.

In this post I stick to (modal) propositional logic.
{Ok not much modal at the moment but maybe later }

A (Uppercase) is a well formed formula

p (lowercase) is a propositional variable
an propositional variable is a well formed formula.
{there is no general agreement over this so just for this thread}

There are at least two different types of completeness.

1 the converse of soundness
{semantic completeness?, completeness of a logic/ calculus???}

|= A -> |-A
if a formula is true then it is provable

if (using a truthtable, or other means) a formula is always
true then that formula is provable.

Also within this catagory
1b the converse of soundness / negation completeness
if a formula A is unsatisfiable (never true) then |- ~A

{this is just one form of negation completeness there are others.}

{classical propositional logic is negation complete in this sense,
Intuitionistic logic is, which logic isn>t?}

intuitionistic logic is because it is only about adding an ~
if a formula ~A is unsatisfiable (never true) then |- A
is NOT valid in intuitionistic logic

2 completeness in relation to theories.
{can I as well say models?}
{what is a theory exactly?}
{from Jan Burse}

A a Theory is formaly complete if and only if
if you add a formula that isn>t provable to the theory that theory
becomes inconsistent.

{in a formula}
fcmp(T) :<=> forall A (T |/- A => ~con(T u A))

B a Theory is negation complete if and only if
every formula is provable or disprovable
{in a formula}
ncmp(T) :<=> forall A (T |- A v T |- ~A)

{for this all propositional variables need to have a fixed truth
value, (otherwise neither |-p or |- ~p can be proven}

Am i still missing something?

from Jan burse
Theorems, for any theory T:
1) T Formally Complete => T Negation Complete
2) T Negation Complete => T Formally Complete

Not sure yet looks like 2 is OK

MoeBlee · Guest

On Jul 22, 9:23 am, translogi <wilem...@googlemail.com> wrote:
[quote]Thank for your comments,

as far as i understand them i have put them in my new sumary. comments
are between {}
Did also do some studying from other sources.

In this post I stick to (modal) propositional logic.
{Ok not much modal at the moment but maybe later }

A (Uppercase) is a well formed formula

p (lowercase) is a propositional variable
an propositional variable is a well formed formula.
{there is no general agreement over this so just for this thread}

There are at least two different types of completeness.

1 the converse of soundness
{semantic completeness?, completeness of a logic/ calculus???}

|= A -> |-A
if a formula is true then it is provable
[/quote]
No, it should be:

If a formula is valid then it is provable.

[quote]if (using a truthtable, or other means) a formula is always
true then that formula is provable.

Also within this catagory
1b the converse of soundness / negation completeness
if a formula A is unsatisfiable (never true) then |- ~A
[/quote]
Fine, but the word 'negation completeness' does not belong there.

[quote]{this is just one form of negation completeness there are others.}
[/quote]
No, you>ve already set yourself up for terminological confusion. Leave
'negation completeness' out of this until you get to actual negation
completeness.

[quote]{classical propositional logic is negation complete in this sense,
Intuitionistic logic is, which logic isn>t?}

intuitionistic logic is because it is only about adding an ~
if a formula ~A is unsatisfiable (never true) then |- A
is NOT valid in intuitionistic logic
[/quote]
Intuitionistic logic has a much different kind of semantics.

[quote]2 completeness in relation to theories.
{can I as well say models?}
{what is a theory exactly?}
[/quote]
There are different defintions of 'theory'. One nice simple definition
is that a theory is a set of sentences closed under entailment.

[quote]{from Jan Burse}

A a Theory is formaly complete if and only if
if you add a formula that isn>t provable to the theory that theory
becomes inconsistent.
[/quote]
I>d put it this way:

A theory is complete (negation complete) iff adding a sentence that is
not already a member of the theory results in an inconsistent theory.

And that follows from the definition of 'completeness' in the sense of
negation completeness.

[quote]{in a formula}
fcmp(T) :<=> forall A (T |/- A => ~con(T u A))
[/quote]
I>d write it this way:

For any theory T, we have T is a complete theory iff As(~seT -> Tu{s}
is inconsistent), where 's' ranges over sentences in the language of
T.

[quote]B a Theory is negation complete if and only if
every formula is provable or disprovable
{in a formula}
ncmp(T) :<=> forall A (T |- A v T |- ~A)

{for this all propositional variables need to have a fixed truth
value, (otherwise neither |-p or |- ~p can be proven}
[/quote]
No, propostitional variables are ordinarily also taken to be
sentences. UNLESS you truly mean that they>re variables, which would
be a somewhat different formulation of the language. So, getting back
to what seems to me to be a more ordinary approach: drop the
terminology 'propositional variable' and use 'sentential letter' or
'propositional letter' or something like that.

[quote]Am i still missing something?
[/quote]
Did you understand my explanation that the pure predicate calculus is
SUPPOSEED to be NOT negation complete? That is, the bare theory that
is the set of valid formulas is not negation complete and is not
desired to be negation complete.

[quote]from Jan burse
Theorems, for any theory T:
1) T Formally Complete => T Negation Complete
2) T Negation Complete => T Formally Complete

Not sure yet looks like 2 is OK
[/quote]
Both are correct.

MoeBlee

Jan Burse · Guest

Jan Burse schrieb:
[quote]translogi schrieb:
am i forgetting something?

I will not deal with the completness of a calculus |-
versus a semantic |= now, i.e. |= => |-.

Lets deal with the completness of a theory T in
a calculus |-. We can define two completness
notions:

Formally Complete:

fcmp(T) :<=> forall A (T |/- A => ~con(T u A))

Negation Complete:

ncmp(T) :<=> forall A (T |- A v T |- ~A)

Theorems, for any theory T:
1) T Formally Complete => T Negation Complete
2) T Negation Complete => T Formally Complete

Proof: Left as an exercise to the reader.

Bye
[/quote]
And because formally complete and negation complete
are the same, we normally only talk about "complete"
theories, not about "negation complete" theories.

Bye

translogi · Guest

On Jul 22, 5:29 pm, Jan Burse <janbu...@fastmail.fm> wrote:
[quote]Jan Burse schrieb:

translogi schrieb:
am i forgetting something?

I will not deal with the completness of a calculus |-
versus a semantic |= now, i.e. |= => |-.

Lets deal with the completness of a theory T in
a calculus |-. We can define two completness
notions:

Formally Complete:

fcmp(T) :<=> forall A (T |/- A => ~con(T u A))

Negation Complete:

ncmp(T) :<=> forall A (T |- A v T |- ~A)

Theorems, for any theory T:
1) T Formally Complete => T Negation Complete
2) T Negation Complete => T Formally Complete

Proof: Left as an exercise to the reader.

Bye

And because formally complete and negation complete
are the same, we normally only talk about "complete"
theories, not about "negation complete" theories.

Bye- Hide quoted text -

- Show quoted text -
[/quote]
Not so sure about this

But how do you call a theory that can prove true facts but cannot
disprove false facts?

PA is half complete but it not negation complete.

translogi · Guest

On Jul 22, 5:49 pm, MoeBlee <jazzm...@hotmail.com> wrote:
[quote]On Jul 22, 9:23 am, translogi <wilem...@googlemail.com> wrote:

Thank for your comments,

as far as i understand them i have put them in my new sumary. comments
are between {}
Did also do some studying from other sources.

In this post I stick to (modal) propositional logic.
{Ok not much modal at the moment but maybe later }

A (Uppercase) is a well formed formula

p (lowercase) is a propositional variable
an propositional variable is a well formed formula.
{there is no general agreement over this so just for this thread}

There are at least two different types of completeness.

1 the converse of soundness
{semantic completeness?, completeness of a logic/ calculus???}

|= A -> |-A
if a formula is true then it is provable

No, it should be:

If a formula is valid then it is provable.

Puzzeling about valid[/quote]
what i did learn .
a formula is valid if the antecedents are true then the conclusion is
true.
But here there are no antecedents.
maybe replacing antecedents with axioms and inference rules.

[quote]
if (using a truthtable, or other means) a formula is always
true then that formula is provable.

Also within this catagory
1b the converse of soundness / negation completeness
if a formula A is unsatisfiable (never true) then |- ~A

Fine, but the word 'negation completeness' does not belong there.

Not sure here, think i read books that do use negation completeness in[/quote]
this way.

[quote]{this is just one form of negation completeness there are others.}

No, you>ve already set yourself up for terminological confusion. Leave
'negation completeness' out of this until you get to actual negation
completeness.

{classical propositional logic is negation complete in this sense,
Intuitionistic logic is, which logic isn>t?}

intuitionistic logic is because it is only about adding an ~
if a formula ~A is unsatisfiable (never true) then |- A
is NOT valid in intuitionistic logic

Intuitionistic logic has a much different kind of semantics.

But why does that mean that it doesn>t fit in this classification?[/quote]

[quote]2 completeness in relation to theories.
{can I as well say models?}
{what is a theory exactly?}

There are different defintions of 'theory'. One nice simple definition
is that a theory is a set of sentences closed under entailment.

I agree but is that enough[/quote]
It sounds almost like a definition of a logic..

[quote]{from Jan Burse}

A a Theory is formaly complete if and only if
if you add a formula that isn>t provable to the theory that theory
becomes inconsistent.

I>d put it this way:

A theory is complete (negation complete) iff adding a sentence that is
not already a member of the theory results in an inconsistent theory.

member of a theory ia the same as an theorem, or axiom of the theory.[/quote]
Did want to try tu use as less concepts as possible.

[quote]And that follows from the definition of 'completeness' in the sense of
negation completeness.

{in a formula}
fcmp(T) :<=> forall A (T |/- A => ~con(T u A))

I>d write it this way:

For any theory T, we have T is a complete theory iff As(~seT -> Tu{s}
is inconsistent), where 's' ranges over sentences in the language of
T.

B a Theory is negation complete if and only if
every formula is provable or disprovable
{in a formula}
ncmp(T) :<=> forall A (T |- A v T |- ~A)

{for this all propositional variables need to have a fixed truth
value, (otherwise neither |-p or |- ~p can be proven}

No, propostitional variables are ordinarily also taken to be
sentences. UNLESS you truly mean that they>re variables, which would
be a somewhat different formulation of the language. So, getting back
to what seems to me to be a more ordinary approach: drop the
terminology 'propositional variable' and use 'sentential letter' or
'propositional letter' or something like that.

Am i still missing something?

Did you understand my explanation that the pure predicate calculus is
SUPPOSEED to be NOT negation complete? That is, the bare theory that
is the set of valid formulas is not negation complete and is not
desired to be negation complete.
[/quote]
I think i did.
But i am still wondering about it. maybe it is better to speak over
the decidability that about the completeness of a theory.

I do prefer the term propositional variable, because that makes clear
that it is an statement with an unknown truth value.

[quote]
from Jan burse
Theorems, for any theory T:
1) T Formally Complete => T Negation Complete
2) T Negation Complete => T Formally Complete

Not sure yet looks like 2 is OK

Both are correct.

why is it so handy to have two names for one and the same concept?[/quote]

MoeBlee · Guest

On Jul 24, 1:17 pm, translogi <wilem...@googlemail.com> wrote:

[quote]But how do you call a theory that can prove true facts but cannot
disprove false facts?
[/quote]
Do you mean proves ALL the true statements or do you mean proves SOME
of the true statements?

If a theory proves all true statements then the theory disproves all
false statements (because the negation of a false statement is a true
statement, so the theory proves that negation, so the theory disproves
the false statement).

Now, EVERY theory proves SOME true statement, since every theory
proves the validities (the statements true in every model) and every
validity is true.

And if a theory proves ONLY true statements, then we call that a
'sound theory'.

[quote]PA is half complete but it not negation complete.
[/quote]
What is "half complete"?

PA is a sound but incomplete theory (negation incomplete).

PA proves ONLY true statements. But PA does not prove ALL true
statements.

(In this post, 'true' is used as ellipsis for 'true in the standard
model for the language of PA', and 'all' and 'some' are over sentences
in the language of PA.)

MoeBlee


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 Previous 1, 2, 3, 4, 5, 6 Next
Page 5 of 6