HDTenEightyP/NetNews huggingface dataset:
From: hvdberg@math.utwente.nl (Harmen van den Berg)
Subject: sorted (typed) logic
Originator: hvdberg@math.utwente.nl
Keywords: sorted logic, references
Organization: University of Twente (Dept. Applied Math.), Enschede, the Netherlands.
Date: Mon, 17 Aug 1992 11:04:44 GMT

Hi there,

I am looking for a (introductory)
book on sorted (typed) logic. If
you have any references, please
send them to
hvdberg@math.utwente.nl

thanks, Harmen

--------------------------------------------------------------------------
                                       Department of Applied Mathematics
  Harmen van den Berg                  University of Twente   
                                       P.O. Box 217 
  hvdberg@math.utwente.nl              7500 AE Enschede
                                       The Netherlands
==========================================================================
-- 



--------------------------------------------------------------------------
From: alti@dcs.ed.ac.uk (Thorsten Altenkirch)
Newsgroups: sci.logic
Subject: New Scientist 21 Mar 92
Date: 18 Aug 92 14:03:26 GMT
Organization: LFCS, Edinburgh

Has anybody had a look at Paul Davies article "Is nature
mathematical?". I only browsed over it but I got the impression that
he confuses the questions of undecidability ("1st order logic is
undecidable" [Church]) and incompleteness ("Every consistent extension
of Peano arithmetic is incomplete"[G"odel]). Any comments?

T.

--
************************************************************
Thorsten Altenkirch		alti@dcs.ed.ac.uk
LFCS, Edinburgh
Scotland
From: martinc@grover.cs.unc.edu (Charles R. Martin)
Newsgroups: sci.logic
Subject: Re: New Scientist 21 Mar 92
Date: 18 Aug 92 22:20:50 GMT
Organization: UNC Department of Computer Science
In-reply-to: alti@dcs.ed.ac.uk's message of 18 Aug 92 14:03:26 GMT

In article <ALTI.92Aug18150326@tanera.dcs.ed.ac.uk> alti@dcs.ed.ac.uk (Thorsten Altenkirch) writes:

   Has anybody had a look at Paul Davies article "Is nature
   mathematical?". I only browsed over it but I got the impression that
   he confuses the questions of undecidability ("1st order logic is
   undecidable" [Church]) and incompleteness ("Every consistent extension
   of Peano arithmetic is incomplete"[G"odel]). Any comments?

I believe they're very closely connected.  See e.g. Chaitin's
Algorithmic Information Theory (Cambridge Tract in Theoretical CS, I
think is the series.)
--
Charles R. Martin/(Charlie)/martinc@cs.unc.edu/(ne crm@cs.duke.edu) 
O/Dept. of Computer Science/CB #3175 UNC-CH/Chapel Hill, NC 27599-3175
H/3611 University Dr #13M/Durham, NC 27707/(919) 419 1754
----------------------------------------------------------------------
"I am he who walks the States with a barb'd tongue, questioning every
one I meet,/Who are you that wanted only to be told what you knew
before?/ Who are you that wanted only a book to join you in your
nonsense?"  _Leaves of Grass_ xxiii.4.
From: solovay@math.berkeley.edu (Robert M. Solovay)
Newsgroups: sci.logic
Subject: Re: Non-standard integers.
Date: 18 Aug 1992 18:55:19 GMT
Organization: U.C. Berkeley Math. Department.
Distribution: world
NNTP-Posting-Host: math.berkeley.edu
Summary: Kemeny's conjecture is wrong.

In article <1992Aug18.133344.385@csc.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:

>
>Thus, the n-tuple-primes conjectures of Hardy would all be false. The only
>problem with this whole operation is showing that there can be a model with
>*all* the "rows" having such an `n' in them. Kemeny reluctantly left this 
>loop-hole unplugged.
>

>--------------------------------------------------------------------------
>            Bill Taylor              wft@math.canterbury.ac.nz 
>--------------------------------------------------------------------------

	Kemeny's conjecture is false: If M is a non-standard model of
PA, then there is a non-standard integer n such that no integer in the
"standard row" of n is divisible by all standard integers.

	To see this, take n which is odd but is divisible by all
standard odd integers. If m differs from n by a standard integer, then
there must be a standard odd prime which does not divide the
difference. Hence m is not divisible by that prime.
Newsgroups: sci.logic
Subject: Non-standard integers.
From: wft@math.canterbury.ac.nz (Bill Taylor)
Date: 17 Aug 92 14:10:16 +1200
Distribution: world
Organization: Department of Mathematics, University of Canterbury

I recall once seeing an article by Kemeny, in which he looked at a nonstandard
model of the integers, in which there would be two (nonstandard) integers,
n and n+2, both of which would be divisible by all standard integers. The
hope was to be able to use this model to decide the twin-prime (or related)
conjectures.

Did any follow-up work ever occur on this subject ? If so, could someone
post/mail references please ?

Thanks,      Bill Taylor.         wft@math.canterbury.ac.nz
Newsgroups: sci.logic
From: jamie@cs.sfu.ca (Jamie Andrews)
Subject: Re: Presburger arithmetic axiomatization
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
Date: Mon, 17 Aug 1992 23:22:31 GMT

In article <1992Aug16.175540.10118@waikato.ac.nz> maj@waikato.ac.nz writes:
>Should we be saying 'Bratislava arithmetic' now ?!

     Only if the Presburger family retroactively Slovakized
their name...  :-)

     By the way, thanks to all for the suggestions.  I was
thinking erroneously that standard Presburger arithmetic had
negative numbers, which it doesn't.  That makes things easier,
and in the restricted context in which I want to use it, I
think it turns out that I can just use the Peano axioms plus
those for addition and claim to be doing Presburger arithmetic.

--Jamie.
  jamie@cs.sfu.ca
"Every \item command in item_list must have an optional argument." LaTeX pg.168
Newsgroups: sci.logic
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: The poor parachutist...
Date: Sat, 22 Aug 1992 02:33:22 GMT
Organization: Security APL, Inc.

In article <1992Aug19.090212.1658@gacvx2.gac.edu> logic@gacvx2.gac.edu writes:
>Now for a riddle of a different flavor..  I first saw this in an interview
>article with Paul Halmos in the Mathematical Intelligencer..  I offer it here
>because it is (1) not as widely known as the riddle above, (2) more difficult
>than the riddle above, and (3) its solution offers some surprises..  Here we
>go.  My wife and I go to a party..  There are 4 other couples there for a total
>of 5 couples.  (No funny business here..  a couple is husband and wife..)  As
>is usual at a social gathering a certain amount of handshaking takes place.. 
>After the handshaking has completed, I interview all of the people at the party
>including my wife.  I ask them how many hands they shook.  (note: spouses don't
>shake hands and no one shakes their own hand)..  Now each person, therefore,
>could have shook as few as 0 hands or as many as 8..  Now, in fact, that range
>of answers is exactly what i get for answers!  I.e., the first person I
>interview responds 0, the second 1, the third 2, ..., the ninth 8..  The riddle
>is "How many hands did my wife shake?"..  I'll even give you the answer..  It
>is 4..  The real riddle, of course, is explaining why this is the correct
>answer..

While this isn't particularly difficult, it's much easier if we are allowed
to assume that there is a unique answer.  If you just have each person shake
hands with exactly the people (s)he previously did not shake hands with, you
get the same distribution, but each person shook hands with 8-n people.  The
assumption that you know how many people one person shook hands with means
that n=8-n, so n=4.
From: jnjohann@cip.informatik.uni-erlangen.de (Jan Johannsen)
Newsgroups: sci.logic
Subject: Re: Presburger arithmetic axiomatization
Date: 17 Aug 92 10:42:14 GMT
Organization: CSD., University of Erlangen

jamie@cs.sfu.ca (Jamie Andrews) writes:

>     Where can I expect to find easily a precise and elegant
>axiomatization of Presburger arithmetic?  (I know it's
>"arithmetic without multiplication" and I can think of some
>horrible axiomatizations; I wanted to find a nice one.)

In ZML 12 (1966), pp. 131 - 168, H. Apelt gives the following
axiom system for Presburger Arithmetic:

  a+b = b+a
  a+(b+c) = (a+b)+c
  \exists b  ( a+b = c  \or  c+b = a )
  c+a = c+b \to a=b
  a+b = 1 \to ( a=1 \or b=1 )
  a+b = 0 \to b=0
  \not 0=1

plus the schema

 \exists b ( b+...+b = a \or b+...+b+1 = a \or ... \or b+...+b+1+...+1 = a )
               p b's          p b's                     p b's  p-1 1's

for every prime number p.

>thanks
>--Jamie.

No matter

Jan Johannsen   jnjohann@immd1.informatik.uni-erlangen.de
From: andrew@rentec.com (Andrew Mullhaupt)
Newsgroups: sci.logic
Subject: Re: The poor parachutist...
Date: 20 Aug 92 03:23:04 GMT
Organization: Renaissance Technologies Corp., Setauket, NY.

In article <1992Aug18.131259.14667@wisipc.weizmann.ac.il> jhsegal@wiscon.weizmann.ac.il (Livy) writes:
>Remember:The man he is asking could be a liar or a honest man.HE (the
>parchutist) doesn't know it.

Usually, you encourage the parachutist to ask "What name would a liar give to
the other city?". However, I am not convinced that this "works". It makes some
assumptions about lying which are not clear. For example, it assumes (which is
reasonable) that the honest people have noticed the "liars" and have come to
some understanding of what is involved. However, what lying means to the liars
is difficult to say, especially since they can't agree on it. Since the truthful
citizens know this as well, they give you an answer which a liar would give you,
but this is no use unless the liar's answer is well defined.

Right?

Later,
Andrew Mullhaupt
From: martinc@grover.cs.unc.edu (Charles R. Martin)
Newsgroups: sci.logic
Subject: Re: The poor parachutist...
Date: 19 Aug 92 02:40:04 GMT
Organization: UNC Department of Computer Science
In-reply-to: jhsegal@wiscon.weizmann.ac.il's message of 18 Aug 92 13:12:59 GMT

In article <1992Aug18.131259.14667@wisipc.weizmann.ac.il> jhsegal@wiscon.weizmann.ac.il (Livy) writes:


   Ok..Now let's see you,logic gguys resolving this question: Let's
   assume that somewhere(on other planet??) there are 2 cities:a city
   with honest people ,who NEVER lie,and a city with crooks,who NEVER
   TELL the TRUTH.  One day per year they are going to shoping to the
   other city,so they are all mixed together in both cities.On the very
   same crazy day,a poor parachutist jumped exactly in one of the two
   cities.The guy know he is in one of those cities,but he doesn't know
   in which of them.Now THE BIG QUESTION is:What question should he ask
   one of the people he sees,so he could deduce in which city he
   is.Remember:The man he is asking could be a liar or a honest man.HE
   (the parchutist) doesn't know it.

   NOW,let's see your brains working!!
   Livy. (I know the answer!!)

That's easy: he should ask "Have you ever heard the puzzle about the guy
who has to figure out whether he's in the city of all completely
truthful people, or the city of all complete liars?"

If the random person says "no" he knows he's in the city of liars.

Don't teach your grandma to suck eggs, bubela.
--
Charles R. Martin/(Charlie)/martinc@cs.unc.edu/(ne crm@cs.duke.edu) 
O/Dept. of Computer Science/CB #3175 UNC-CH/Chapel Hill, NC 27599-3175
H/3611 University Dr #13M/Durham, NC 27707/(919) 419 1754
----------------------------------------------------------------------
"I am he who walks the States with a barb'd tongue, questioning every
one I meet,/Who are you that wanted only to be told what you knew
before?/ Who are you that wanted only a book to join you in your
nonsense?"  _Leaves of Grass_ xxiii.4.
Newsgroups: sci.logic
Subject: Re: Presburger arithmetic axiomatization
From: wft@math.canterbury.ac.nz (Bill Taylor)
Date: 18 Aug 92 14:07:16 +1200
Distribution: world
Organization: Department of Mathematics, University of Canterbury

(Apologies if this reference has appeared on the list already.)

There is a very readable acount of the decidability of Presburger arithmetic in
chapter 21, Boolos & Jeffrey, "Computability & Logic", Cambridge U Press (1974).

They also mention the interesting result that arithmetic with successor and
multiplication but *without* addition, is essentially no restriction, by the
neat trick of identifying  
                             a + b = c
           with    (a.c)' . (b.c)' = ( (a.b)' . (c.c) )'

------------------------------------------------------------------------------
            Bill Taylor              wft@math.canterbury.ac.nz 
------------------------------------------------------------------------------
Free will - the result of chaotic amplification of quantum events in the brain.
------------------------------------------------------------------------------
Newsgroups: sci.logic
Subject: Re: Non-standard integers.
From: wft@math.canterbury.ac.nz (Bill Taylor)
Date: 19 Aug 92 17:29:20 +1200
 <1992Aug18.133344.385@csc.canterbury.ac.nz> <16rh2nINN6og@agate.berkeley.edu>
Distribution: world
Organization: Department of Mathematics, University of Canterbury

>	Kemeny's conjecture is false: If M is a non-standard model of
>PA, then there is a non-standard integer n such that no integer in the
>"standard row" of n is divisible by all standard integers.
>
>	To see this, take n which is odd but is divisible by all
>standard odd integers. If m differs from n by a standard integer, then
>there must be a standard odd prime which does not divide the
>difference. Hence m is not divisible by that prime.

Looking at this bit...

>take n which is odd but is divisible by all standard odd integers.

...at first it wasn't clear to me that every nonstandard model would have
such an  n .  But I suppose this can be seen by taking any odd nonstandard k,
and forming  n = k(k-2)(k-4)(k-6).....  .

Presumably this operation can be made legitimate in some simple way ?
--------------------------------------------------------------------------
            Bill Taylor              wft@math.canterbury.ac.nz 
--------------------------------------------------------------------------
                  Kleeneness is next to Godelness.
--------------------------------------------------------------------------
jhsegal
Newsgroups: sci.logic
Subject: The poor parachutist...
From: jhsegal@wiscon.weizmann.ac.il (Livy)
Date: Tue, 18 Aug 1992 13:12:59 GMT
Organization: Weizmann Institute of Science, Computation Center

Ok..Now let's see you,logic gguys resolving this question:
Let's assume that somewhere(on other planet??) there are 2 cities:a city with
honest people ,who NEVER lie,and a city with crooks,who NEVER TELL the TRUTH.
One day per year they are going to shoping to the other city,so they are all
mixed together in both cities.On the very same crazy day,a poor parachutist
jumped exactly in one of the two cities.The guy know he is in one of those
cities,but he doesn't know in which of them.Now THE BIG QUESTION is:What
question should he ask one of the people he sees,so he could deduce in which
city he is.Remember:The man he is asking could be a liar or a honest man.HE (the
parchutist) doesn't know it.

NOW,let's see your brains working!!
Livy. (I know the answer!!)
Newsgroups: sci.logic
From: tycchow@riesz.mit.edu (Timothy Y. Chow)
Subject: ZFC+~Con(ZFC)
Organization: None.  This saves me from writing a disclaimer.
Date: Sun, 16 Aug 92 00:07:26 GMT

Assuming ZFC is consistent, there are models of ZFC+~Con(ZFC).  Are such
models interesting?  Have they been studied?  Or to put it another way, are
there any interesting consequences of assuming that ZFC is INconsistent?
-- 
Tim Chow     tycchow@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons.                               ---Popular Mechanics, March 1949
From: chanm@server.uwindsor.ca (CHAN HENRY               )
Newsgroups: sci.logic
Subject: Logic Minimization
Keywords: logic
Date: 12 Aug 1992 17:13:30 GMT


Does anyone know that is there any book on "Logic Minimization"?
Please reply it to my email address:
hchan@engn.uwindsor.ca

I will post a summary after I get the reply!

Thanks!

Henry
hchan@engn.uwindsor.ca
chanm@server.uwindsor.ca

12-8-92
Newsgroups: sci.logic
From: wjcastre@magnus.acs.ohio-state.edu (W.Jose Castrellon G.)
Subject: Re: Non-standard integers.
Organization: The Ohio State University,Math.Dept.(studnt)
Date: Wed, 19 Aug 1992 15:14:19 GMT

In article <1992Aug19.172922.410@csc.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>>	Kemeny's conjecture is false: If M is a non-standard model of
>>PA, then there is a non-standard integer n such that no integer in the
>>"standard row" of n is divisible by all standard integers.
>>
>>	To see this, take n which is odd but is divisible by all
>>standard odd integers. If m differs from n by a standard integer, then
>>there must be a standard odd prime which does not divide the
>>difference. Hence m is not divisible by that prime.

>
>Looking at this bit...
>

>>take n which is odd but is divisible by all standard odd integers.

>
>...at first it wasn't clear to me that every nonstandard model would have
>such an  n .  But I suppose this can be seen by taking any odd nonstandard k,
>and forming  n = k(k-2)(k-4)(k-6).....  .

If what is meant here is that n equals to the product of the odd predecessors
in the _row_ of k, then there is no model with such n, just as there is no
number equal to the product of all standard integers; the reason for that is
overspill, or else that by being able to do that you could pin down the
standard integers.(Boolos&Jeffry surely discusses that).
To see that there is an odd non-standard divisible by all odd standard naturals
just take any non-standard that is divisible by all standard numbers and get
its greatest odd divisor. You can prove that there is always such a divisor in
PA for all numbers, therefore it is true in all models of PA.

>
>Presumably this operation can be made legitimate in some simple way ?

Yes, by Godel coding, but n will necessarily be divisible by some non-standard
naturals.
WJCG
Newsgroups: sci.logic
From: sanjiva@ecrc.de (Sanjiva Prasad)
Subject: Question about Intuitionistic/Constructive logics
Reply-To: sanjiva@ecrc.de (Sanjiva Prasad)
Organization: European Computer-Industry Research Centre, Munich
Date: Wed, 12 Aug 1992 11:07:47 GMT


Hi,  I have just started trying to learn about intuitionistic logic,
and constructive logics in general, and am a little puzzled by some notions
there, particularly of implication. Perhaps someone would be kind enough to
help me. (By e-mail please, I don't read this newsgroup regularly).

From what I could understand from the book I was reading ("Intuitionism" by
Heyting -- but I don't any more have access to the book ),  a mathematical 
proposition demands a construction *with certain properties*  and can be 
asserted when such a construction (in what seems to be an extremely general 
sense of the term) is carried out.  

About implication: P->Q can be asserted iff there is a construction r such 
that "joined to" any construction, say s, proving P, would automatically effect
a construction proving Q. 

I am a little puzzled by what "joined to" exactly means.  In all the 
examples I've seen, it has been juxtaposition of r and s -- which is
okay for applications such as the type system for functional languages etc.
(I think Heyting, in fact, says something to the effect of "by the definition 
of  implication, the construction consists of simply the juxtaposition of
r and s").

My first question is whether (and if so, what) constructions C[r,s] 
more complicated than juxtaposition can be used for defining implication
in an object language different from propositional intuitionistic logic. 
That is, in general, what are these "certain properties" that the 
constructions must have? 

Thanks,

Sanjiva Prasad			(sanjiva@ecrc.de)
From: miner@kuhub.cc.ukans.edu
Newsgroups: sci.philosophy.tech
Subject: some problems with Q-implicatures
Date: 20 Aug 92 18:31:39 CDT
Organization: University of Kansas Academic Computing Services

Some problems with Q-Implicatures:

1.   Consider the following exchange (heard at home):
          1(a). Did you turn the AC on?
          1(b). Well, I turned it _back_ on.
This appears quite parallel to:
          2(a). Did you clean your room?
          2(b). Well, I cleaned up _part_ of it.
The Q-Implicature of 2(b) is of course
          I didn't clean up all of it
since there is a Horn scale <clean up all, clean up part>; and it
seems that a Q-Implicature of 1(b) should be
          I didn't turn it on originally
even though 1(a) does not entail 1(b) as should be the case if
there is a Horn scale <turn on, turn back on>.

2.   In Gracian's _Manual_ (a book of neat medieval commonsense
wisdom) #17 we find "a gambler does not play the card which his
opponent expects, much less that which he desires" which gives
another example:
          A. Did he desire it?
          B. Well, he expected it.
Surely B has the Q-Implicature "he didn't desire it" even though
there is no Horn scale <desire, expect>.

So are there contextual constrains on Horn scales, or what?

	- Ken <miner@kuhub.cc.ukans.edu>
From: tomh.bbs@cybernet.cse.fau.edu
Newsgroups: sci.philosophy.tech
Subject: Re: nano-replicator assumptions
Keywords: nanotechnology, replicator, assembler
Date: 17 Aug 92 20:44:07 GMT
Organization: Florida Atlantic University, Boca Raton

> >>>       (In fact, I dispute the suggestion that any finite mechanical
> >>>system can build a copy of itself. I find this notion to contain an
> >
> To my view, system A does not have complete knowledge of system B,
> it has a set of rules the following of which yields a copy of system
> B.  I'm not sure of what comprises "complete knowledge".
> 
Robert Rosen has written a book:
Life Itself
Robert Rosen
Columbia University Press, NY, 1992
Complexity in Ecological Systems Series
ISBN 0-231-07564-2

He discusses these issues and give a mathematical proof that simple
mechanisms cannot replicate themselves without infinite regress.

He also shows how it IS possible for organisms to do this by being,
in his terminology, "closed to effective causation".  He gives a
mathematical definition of what it means to be closed in this
manner.  The closure of the system means there is no infinite
regress, for one thing.

This closure is like having "complete knowledge".  I find the
suggestion that matter may be infinitely layered with self-organizing
systems interesting - it certainly is over quite a large set of
scales, but perhaps it is not necessary (if Rosen is correct).

Tom Holroyd
tomh@bambi.ccs.fau.edu