HDTenEightyP/NetNews huggingface dataset:
From: paul@mtnmath.UUCP (Paul Budnik)
Newsgroups: sci.logic,sci.physics
Subject: Re: Continuos vs. discrete models Was: The size of electrons, ...
Date: 17 Nov 92 17:45:14 GMT
Followup-To: sci.logic
Organization: Mountain Math Software, P. O. Box 2124, Saratoga. CA 95070

In article <1992Nov16.131202.17710@sei.cmu.edu>, firth@sei.cmu.edu (Robert Firth) writes:
> In article <350@mtnmath.UUCP> paul@mtnmath.UUCP (Paul Budnik) writes:
> 
>...
> >theorems. The names of all real numbers created by such a program are
> >obviously countable.
> 
> Well, yes, the names of any set of things created by an "enumeration"
> program muct be countable, by definition.  But that's not what you
> originally claimed.  You said:
> 
> >For example the real numbers definable in any consistent formal system
> >are countable.
> 
> By what sleight of hand did "definable" change into "enumerable"?  Isn't
> that the old constructivist premise (or fallacy, as most of us think).

A real number is not definable in a formal system unless it is named
in some theorem in that system. The reals definable in a formal system
are limited to these. Of course there are always additional reals not
definable in the system that still satisfy the definition of a real number
in the system. Mathematicians who believe there is a Platonic heaven
of completed infinite totalities intend for their definition of reals to
encompass all residents of this heaven that satisfy that definition.
This is a philosophical not a mathematical definition and a highly
questionable one in my opinion.

The constructivist position is different. It does not accept proof
by contradiction as a valid argument for the existence of a mathematical
object. The constructivist position involves more than this and has
variations, but this is a universal requirement. Reals definable in
this way are nameable and thus definable in the sense
I used the term.

Follow ups are directed to sci.logic.

Paul Budnik
From: paul@mtnmath.UUCP (Paul Budnik)
Newsgroups: sci.logic
Subject: Re: Lowneheim-Skolem theorem
Date: 21 Nov 92 16:08:41 GMT
Organization: Mountain Math Software, P. O. Box 2124, Saratoga. CA 95070

In article <1992Nov20.140159.4770@sun0.urz.uni-heidelberg.de>, gsmith@lauren.iwr.uni-heidelberg.de (Gene W. Smith) writes:
> In article <361@mtnmath.UUCP> paul@mtnmath.UUCP (Paul Budnik) writes:
> 
> >This would be a valid argument if uncountable had an absolute definition.
> >I think uncountable is only meaningful relative to some formal system. 
> 
> "Uncountable" means no one-to-one relation with the integers
> can be given.  This does not refer to a formal system.

Unless you have a formal system in which to determine what constitutes
a one-to-one relationship you are not doing mathematics. You are doing
philosophy. All mathematical proofs are derivable from within a formal
system even if the proof is given informally. 

> >There are plenty of examples of sets uncountable in one system that
> >are countable in stronger systems.
> 
> If they are countable in the stronger system, that means that
> a one-one map can be found in it, which means that these sets
> are countable.

You believe that the real numbers have an absolute meaning. I do not.
That is a philosophical difference between us that we will not resolve
by argument. I do not think countable is meaningful except in the
context of a formal system. You do. Everyone is entitled to his own
opinion. You are not entitled to call your philosophical opinion mathematics
even if many mathematicians hold the same opinion. Many but not all
mathematicians agree with you, but most recognize that this is an
issue of philosophy of mathematics.

> >The question of whether uncountable has an absolute definition is a
> >philosophical one that I expect we have different opinions on.
> 
> I say "uncountable" means what mathematicians mean by it.  This is
> more a linguistic question than a philosophical one.

Mathematics is what is done in the context of formal systems or can
be formalized. Philosophy of mathematics involves the interpretation
and meaning of those systems. When you talk about uncountable as having
an absolute meaning you have gone beyond what can be formalized.
Mathematicians can usually reach a consensus if a proof is valid in
a particular formal system. They will *never* reach a consensus about
what is the correct philosophy of mathematics.

Paul Budnik
Newsgroups: sci.logic
From: mclean@itd.nrl.navy.mil (John McLean)
Subject: Re: implication truth table
Reply-To: mclean@itd.nrl.navy.mil
Organization: Information Technology Division, Naval Research Laboratory
Date: Tue, 17 Nov 1992 21:25:47 GMT

From cmitchell@falcon.aamrl.wpafb.af.mil ()
>My question is: WHY is the implication relation defined as it is?


One justification for having

	A	B	A->B
	T	T	 T
	T	F	 F
	F	T	 T
	F	F	 T

as the truth table for A->B is that there is no better alternative.
The first two lines are noncontroversial.  This leaves us with
only three alternatives for truth tables.

(1)	A	B	A->B
	T	T	 T
	T	F	 F
	F	T	 F
	F	F	 F

(2)	A	B	A->B
	T	T	 T
	T	F	 F
	F	T	 T
	F	F	 F

(3)	A	B	A->B
	T	T	 T
	T	F	 F
	F	T	 F
	F	F	 T

(1) equates A->B with A&B; (2) equates A->B with B; and (3)
equates A->B with A<->B.  Hence, all the alternative make
A->B redundant.

A->B is not meant to capture the English "if..then.." completely.  What
we really want to do is to prevent someone from denying B if A and A->B
are both true; from accepting A->B if A is true and B is false; and
from either accepting or denying B solely because A->B is true if A is
false. The truth table for A->B does this.  It does have the
unfortunate consequence of making assertions such as "If you eat that
mushroom, you'll die" usually true (since the person addressed will
rarely take the chance).

A good discussion of the relationship between formal logic and
English can be found in Paul Grice's "Logic and Conversation."

John McLean

Newsgroups: sci.logic
From: sasghm@theseus.unx.sas.com (Gary Merrill)
Newsgroups: sci.logic
Subject: Re: recursive definitions and paradoxes
Date: 23 Nov 92 15:54:54 GMT
Organization: SAS Institute Inc.
Originator: sasghm@theseus.unx.sas.com


In article <1emo86INN4de@roche.csl.sri.com>, rar@csl.sri.com (Bob Riemenschneider) writes:
|> In article <By174J.JBM@unx.sas.com> sasghm@theseus.unx.sas.com (Gary Merrill) writes:
|> 
|>    In article <26841@optima.cs.arizona.edu>, gudeman@cs.arizona.edu (David Gudeman) writes:
|>    |> 
|>    |> Exactly.  Actually, my notion of definition does not satisfy either of
|>    |> the two notions you mention.  Recursive definitions are creative and
|>    |> non-eliminable, and for that reason they have to be protected with an
|>    |> axiom that limits their use.  Non-creative, eliminable definitions are
|>    |> no more than abbreviations, and mathematics cannot be done with such a
|>    |> sparse notion of definition.
|> 
|>    I have a vague recollection of a result that any recursive definition
|>    is eliminable in favor of an explicit definition (Scott? Montague?  A faulty
|>    memory?).  ...
|> 
|> Beth's theorem ("Padoa's method is general"), a more-or-less immediate
|> consequence of the Craig interpolation lemma.  (No doubt Mr. Gudeman
|> will be unimpressed, however.)
|> 
|>                                                         -- rar

Also, apparently the general technique of converting recursive definitons
to explicit definitions is provided by Frege.  There is an old paper
of Quine's ("Tarski's Theory of Truth", reprinted in _Selected Logic
Papers_) in which he demonstrates a theory containing a "recursive
definition" that cannot be eliminated without rendering the theory
inconsistent.  However, since the extended theory contains the protosyntax
of the base theory, it is not clear what can be made of this for
claims about eliminability or uneliminability in general.
-- 
Gary H. Merrill  [Principal Systems Developer, C Compiler Development]
SAS Institute Inc. / SAS Campus Dr. / Cary, NC  27513 / (919) 677-8000
sasghm@theseus.unx.sas.com ... !mcnc!sas!sasghm
Newsgroups: sci.logic
From: torkel@sics.se (Torkel Franzen)
Subject: Re: implication truth table
Organization: Swedish Institute of Computer Science, Kista
Date: Wed, 18 Nov 1992 09:09:20 GMT

In article <1992Nov16.162733.1831@falcon.aamrl.wpafb.af.mil> cmitchell@falcon.
aamrl.wpafb.af.mil writes:

   >My expectation was that:
   >if   it is not sunny,
   >then I would have no way of determining the truth of the implication.

  You're asking why "if A then B" is a consequence of "not A", as we
understand "if-then" in (classical or constructive) mathematics.

  Here's one answer: although we don't often explicitly make this
inference, it is implicit in ordinary mathematical reasoning of a kind
that does not usually strike people as puzzling. Or more properly, if
we try to make the rules of ordinary mathematical reasoning precise
and explicit, we will be faced with such consequences as the one you
are asking about.

   Consider the following three rules of logic:

  1) From A follows "A or B"

  2) If B follows from some premisses together with the assumption A,
     then "if A then B" follows from those premisses alone.

  3) From "A or B" together with "not A" follows B.

  We reason in mathematics in accordance with these rules all the
time.  It's instructive to verify that "if A then B" can be derived
from "not A" using these rules. What this tells us is that if we want
to reason in mathematics in a way that does not justify the step from
"not A" to "if A then B", then we must think hard about which rules of
reasoning we should accept. As soon as one does this one finds that it
is no simple matter to formulate a logic that does not contain the
rules 1)-3) above in full generality. Such logical systems do exist -
e.g.  relevant logic - but they have little to do with ordinary mathematical
reasoning.
Newsgroups: sci.logic
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: recursive definitions and paradoxes
Organization: Computer Science Department,  Stanford University.
Date: Thu, 19 Nov 1992 21:50:48 GMT

In article <26788@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>But consider the paradoxical definitions
>
>  S := {{},R}
>  R := {x E S : ~(x E x)}                                (8)
>
>where the definition of R has exactly the same form as the definition of
>Russell's paradoxical set (replacing S with the universal set).  But
>here, S is a set with only two elements!  Given such a clear example of
>Russell's paradox by quantifying over a finite set, I don't see how
>anyone can still claim that Russell's paradox is somehow caused by a
>universal set that is "too big".  Size has nothing to do with it, the
>only consideration is how it is defined.  Clearly in this example the
>problem is an ill-founded mutual recursion between the two set
>definitions.

Russell's paradox denies the existence of the paradoxical set of all
sets.  Denial of an existential is a universal, and the universal
statement asserted by Russell's paradox is that every set has a
nonmember.  The universal set is "too big" by one element, having no
nonmember.  From that perspective size has everything to do with it.
-- 
Vaughan Pratt	  		A fallacy is worth a thousand steps.
From: martinc@hatteras.cs.unc.edu (Charles R. Martin)
Newsgroups: sci.logic
Subject: Re: Are all crows black? => Logic as an essential
Date: 15 Nov 92 23:05:40 GMT
	<1e1cnoINN74a@columbia.cs.ubc.ca>
	<1992Nov14.032808.17103@CSD-NewsHost.Stanford.EDU>
Organization: UNC Department of Computer Science
In-reply-to: pratt@Sunburn.Stanford.EDU's message of 14 Nov 92 03:28:08 GMT

In article <1992Nov14.032808.17103@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:

   In article <1e1cnoINN74a@columbia.cs.ubc.ca> kean@cs.ubc.ca (Alex Kean) writes:


   All men are mortal/Madonna is mortal -> Madonna is a man.  

Ooooooh!  An *amphiboly*!
--
		Charles R. Martin/(Charlie)/martinc@cs.unc.edu
     Dept. of Computer Science/CB #3175 UNC-CH/Chapel Hill, NC 27599-3175
	    3611 University Dr #13M/Durham, NC 27707/(919) 419 1754
     "Oh God, please help me be civil in tongue, pure in thought, and able
      to resist the temptation to laugh uncontrollably.  Amen." -- Rob T
Newsgroups: sci.logic
Subject: Re: Why invalid?
From: wft@math.canterbury.ac.nz (Bill Taylor)
Date: Fri, 20 Nov 1992 03:15:32 GMT
 <1992Nov17.164246.18220@uklirb.informatik.uni-kl.de> <1992Nov18.002216.15277@magnus.acs.ohio-state.edu>
Organization: Department of Mathematics, University of Canterbury

|> >Can anyone give me a counterexample of the following:
|> >
|> >Let T a consistent first order theory with equality which
|> >decidable set of quatifier-free logical consequences:
|> >
|> >  QF(T) = { B  |   t |= B, B quantifier-free }
|> >
|> >Let A be a T-consistent quantifier-free formula.
|> >Then (T,A) is also a consistent first order logic with
|> >equality and QF(T,A) is ALSO DECIDABLE.

|> Solution follows.
|> 
|> Take the theory over the language with one constant  0 , one function  f(x) ,
|> one unary predicate  P(x), and a binary relation  R(x,y), as follows:
|> 
|> For all  x  R(0,f(x))
|> R(0,0)
|> and for each  n  in a non-recursive r.e. set, the axioms:
|> 
|> [ There exists an  x  such that  not R(0,x) ]  -->  [ P(n) ]
|> 
|> (where  n  is the abbreviation of  f(x)  applied  n  times to  0 )
|> 
|> Then one can check that the set of quantifier free sentences that are logical
|> consequences of this axioms is recursive.
|> 
|> However if one expands the language with one more constant  c , and add the
|> sentence   not R(0,c), then that set becomes non-recursive.  [if you dont allow
|> an expansion of the language, then it can be shown that there is no counter-
|> example].

I don't quite get this comment. If the constant c is in the original language,
but with no extra axioms, isn't the original theory still decidable for
quantifier-free formulas ? And thus isn't the example now a counterexample
of the type originally required ?

Help sort me out please, somebody.
------------------------------------------------------------------------------
              Bill Taylor              wft@math.canterbury.ac.nz
------------------------------------------------------------------------------
                       Kleeneness is next to Godelness.
------------------------------------------------------------------------------
 
Newsgroups: sci.logic
From: ayala@uklirb.informatik.uni-kl.de (Mauricio Ayala R.)
Subject: Re: Why invalid?  (was:  Why logic?)
Organization: University of Kaiserslautern, Germany
Date: Tue, 17 Nov 1992 16:42:46 GMT

Can anyone give me a counterexample of the following:

Let T a consistent first order theory with equality which
decidable set of quatifier-free logical consequences:

  QF(T) = { B  |   t |= B, B quantifier-free }

Let A be a T-consistent quantifier-free formula.
Then (T,A) is also a consistent first order logic with
equality and QF(T,A) is ALSO DECIDABLE.

M. Ayala
Universitaet Kaiserslautern
FRG
ayala@informatik.uni-kl.de
From: columbus@strident.think.com (Michael Weiss)
Newsgroups: sci.logic
Subject: Truth and large cardinals (was: Lowenheim-Skolem theorem)
Followup-To: sci.logic
Date: 23 Nov 92 14:11:11
Organization: Thinking Machines Corporation, Cambridge MA, USA
	<368@mtnmath.UUCP> <1992Nov22.230633.12855@galois.mit.edu>
	<373@mtnmath.UUCP>
NNTP-Posting-Host: strident.think.com
In-reply-to: paul@mtnmath.UUCP's message of 23 Nov 92 16:38:49 GMT

In article <373@mtnmath.UUCP> paul@mtnmath.UUCP (Paul Budnik) writes:

       [...] The way mathematicians extend logic
   today is by postulating the existence of large cardinals.
   These abstractions are so far removed from the computational roots of
   mathematics that there is no intuitive basis for deciding between them.
   However these large cardinal axioms have combinatorial implications.
   For example they allow us to decide the halting problems for a wider
   class of Turing Machines. 


I assume that last sentence refers to this sort of situation: in ZFI, one
can prove Con(ZF), which in turn says that a Turing machine that spent its
time searching for a contradiction in ZF would never halt.

                            It is my contention that if one focused
   on understanding these combinatorial implications and forgot about the
   Platonic heaven of completed infinite totalities, real progress could
   be made in extending logic.

Suppose we have some large cardinal axiom, say R (for Really Big Cardinal).
In ZFR one can prove (say) that Turing machine T never halts.  Are you
saying that one should add that combinatorial statement (call it TR) as a
new axiom, but not R?

I can see a certain philosophical appeal, in that the combinatorial
statement TR is in principle falsifiable.  One might regard TR as having a
truth value in some absolute philosophical sense, but not R.  On the other
hand, what reason do I have for believing that TR is true, if I reject R as
meaningless?

Of course, I could always adopt a formalist attitude-- "let's play around
with this new axiom TR, and see what happens."  But I could do that with ZFR.
Newsgroups: sci.logic
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: recursive definitions and paradoxes
Date: Mon, 23 Nov 1992 16:33:57 GMT
Organization: Security APL, Inc.

In article <26922@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>In article  <1992Nov21.230530.117800@Cookie.secapl.com> Frank Adams writes:
>]In article <26788@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>]>I propose for discussion the
>]>
>]>  Axiom of Definition: (X := E /\ Exist! X.X=E) => X = E
>]>
>]>where "Exist! x" means "there exists a unique x such that".
>]
>]Actually, no.  Unless I am much mistaken, this kind of definition is
>]eliminable.  If we have a definition X := E, we can rewrite a wff of
>]the form P(X) as (All X.((Ex! X.X=E) => X=E) => P(X)).
>
>I'm not sure what you mean.  If you mean that the definition plus the
>axiom is eliminable, then of course you are right.

(I am leaving out the discussion of exactly how to eliminate the definition;
it suffices that we agree it is eliminable.)

In my previous article, I quoted:
>  And by adding some of the well-known machinery
>from recursion theory to prove Exist!... you could also talk about a lot
>of self-containing sets.  Wouldn't this theory be much more powerful
>than ZF?

Perhaps I misunderstood; I though David was asserting that his definitions
and axiom thereof would make a theory much more powerful than ZF.  If they
are eliminable, they don't.

So I must have misinterpreted "the well-known machinery from recursion
theory".  I think I know recursion theory fairly well, and I don't know just
what is being referred to here.  Thus I have to ask David to explicate just
exactly what machinery he wishes to import.
From: ard@cs.bham.ac.uk (Antoni Diller)
Newsgroups: sci.logic
Subject: Re: Will a mathematician locked up in a little room be happy?
Date: 23 Nov 92 15:59:58 GMT
Organization: School of Computer Science, University of Birmingham, UK

I thought the follwoing joke was well known:

  What's the difference between a mathematician and a philosopher?
  Well, to work a mathematician needs a chair, a desk, a paper and
  some writing implements and a waste paper basket; in the case of
  a philosopher you can throw away the waste paper basket.
Xref: sparky sci.logic:2105 sci.physics:19240
From: sasghm@theseus.unx.sas.com (Gary Merrill)
Subject: Re: implication truth table
Originator: sasghm@theseus.unx.sas.com
Date: Wed, 18 Nov 1992 13:49:39 GMT
Organization: SAS Institute Inc.


In article <TORKEL.92Nov18100921@isis.sics.se>, torkel@sics.se (Torkel Franzen) writes:
	[ Good example of relations among inference rules omitted. ]

Perhaps another way of putting this is that the usual truth-functional
interpretation of the material conditional is about the weakest
interpretation that satisfies all the "usual" rules of inference.
-- 
Gary H. Merrill  [Principal Systems Developer, C Compiler Development]
SAS Institute Inc. / SAS Campus Dr. / Cary, NC  27513 / (919) 677-8000
sasghm@theseus.unx.sas.com ... !mcnc!sas!sasghm
Newsgroups: sci.logic
From: torkel@sics.se (Torkel Franzen)
Subject: Re: Do completed infinite totalities exist? Was: Lowneheim-Skolem theorem
Organization: Swedish Institute of Computer Science, Kista
	<371@mtnmath.UUCP>
Date: Sun, 22 Nov 1992 22:12:54 GMT

In article <371@mtnmath.UUCP> paul@mtnmath.UUCP (Paul Budnik) writes:

 >I disagree that most people who use this concept do not need to know or care
 >about formal systems. It may be a pragmatic reality given the way mathematics
 >functions today. I do not think it makes for good mathematics in the long
 >run.

  The "pragmatic reality" of present day mathematics is what my comments
have been about. The mathematics you envisage, which is pretty opaque
to me, may or may not be viable. By all means develop and present it.
I see no point in arguing about hypothetical mathematics.
Newsgroups: sci.logic
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: Why Logic?
Organization: Computer Science Department,  Stanford University.
Distribution: world 
Date: Sun, 22 Nov 1992 01:42:08 GMT

In article <GUTTMAN.92Nov19120734@circe.mitre.org> guttman@circe.mitre.org (Joshua D. Guttman) writes:
>In article <1992Nov16.091653.1@woods.ulowell.edu> cotera@woods.ulowell.edu writes:
>
>   Can anyone explain why we use logic? Unfortunately, any logical arguments to
>   support logic, are unfortunately, invalid.
>   --Ray Cote
>
>On the contrary, logical arguments may be not only valid, but also informative.
>
>For instance, to explain why we use classical first order logic (for many
>important purposes), logical theorems such as soundness and completeness are
>very relevant.  So are fancier theorems such as the non-enumerability of
>consequence in 2nd order logic, or Lindstrom's theorem.  
>
>Of course it depends what the argument is intended to accomplish.  A truly
>illogical person (perhaps a child) must be trained, not convinced.  A logical
>person who wants to gain insight into what he's doing and why can learn a lot
>from mathematical logic.  

This seems to fall far short of addressing the basic question of why we
use logic.  Why not do all our thinking with just the equations of
arithmetic?  Or the equations of binary relations under composition and
converse as suggested by Tarski and Givant in "A Formalization of Set
Theory without Variables."

To me the chief characteristic of logic is its emphasis on sorting out
situations into *two* cases, whether always successfully (Boolean
logic) or sometimes not (intuitionistic logic).  See my message of Nov.
16 arguing this viewpoint in considerable detail.
-- 
Vaughan Pratt	  		A fallacy is worth a thousand steps.
Newsgroups: sci.logic,alt.uu.future