[FOM] proofs by contradiction in (classical?)
Taylor Dupuy
taylor.dupuy at gmail.com
Tue Sep 20 20:06:12 EDT 2011
There is a combinatorial version of EPR called the Kochen-Specker paradox
which essentially says that entangled spin 1 particles cannot have a
predetermined states before measurement. It is a great example of a proof by
contradiction in physics.
John H Conway gave a lecture on this topic here:
Geometry, Logic and Physics
http://www.math.princeton.edu/facultypapers/Conway/
An extended version of can be found in his free will theorem series.
Best Wishes,
Taylor
On Tue, Sep 20, 2011 at 9:15 AM, <fom-request at cs.nyu.edu> wrote:
> Send FOM mailing list submissions to
> fom at cs.nyu.edu
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://www.cs.nyu.edu/mailman/listinfo/fom
> or, via email, send a message with subject or body 'help' to
> fom-request at cs.nyu.edu
>
> You can reach the person managing the list at
> fom-owner at cs.nyu.edu
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of FOM digest..."
>
>
> Today's Topics:
>
> 1. Re: About Paradox Theory (Zvonimir Sikic)
> 2. Re: proofs by contradiction in (classical?) Physics
> (Vaughan Pratt)
> 3. Re: proofs by contradiction in (classical?) Physics (Hendrik Boom)
> 4. Re: About Paradox Theory (T.Forster at dpmms.cam.ac.uk)
> 5. origin of "real" (Thomas Lord)
> 6. Re: About Paradox Theory (Aatu Koskensilta)
> 7. Re: proofs by contradiction in (classical?) Physics
> (Antonino Drago)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 19 Sep 2011 19:35:10 +0200
> From: Zvonimir Sikic <zvonimir.sikic at gmail.com>
> To: FOM at cs.nyu.edu
> Subject: Re: [FOM] About Paradox Theory
> Message-ID:
> <CAHSSBL4C=nCgSFpjWYq4EG7uwxCBhmH=ckWBGzQfxRxyizh8iw at mail.gmail.com
> >
> Content-Type: text/plain; charset="iso-8859-1"
>
> A class defined by
>
> x el z iff (Ey)( y el x & -(x el y) )
>
> is contradictory because
>
> sngl(z) el z iff -( sngl(z) el z ).
>
> But there is no logical contradiction in the defining formula because it is
> satisfiable in natural numbers by interpreting "el" as "> or =" and z as 0.
>
> This class is just the beginning of a sequence generated from Cantors
> theorem by using iterated intersections, instead of identity that Russell
> used to generate his class.
>
> It is interesting that his class, but also those generated by iterated
> unions (that turned out to be Quines classes), are logically contradictory.
> What an unexpected difference between unions and intersections
>
> C.f.
> http://www.fsb.unizg.hr/matematika/sikic/download/ZS_cantors_theorem.pdf
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: </pipermail/fom/attachments/20110919/ad6591bd/attachment-0001.html>
>
> ------------------------------
>
> Message: 2
> Date: Mon, 19 Sep 2011 10:36:09 -0700
> From: Vaughan Pratt <pratt at cs.stanford.edu>
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: Re: [FOM] proofs by contradiction in (classical?) Physics
> Message-ID: <4E777D89.5020107 at cs.stanford.edu>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> On 9/18/2011 12:41 PM, Fouche wrote:
> > Can one use proofs by contradiction in Physics? And if it is possible,
> > why they are so rare?
>
> Because proofs are rare in physics?
>
> To find a proof in a physics book I had to go through several in my
> collection before coming to Byron and Fuller's "Mathematics of Classical
> and Quantum Physics." Flipping pages at random, the first proof I ran
> across was a five-line argument for the Fundamental Theorem of Algebra,
> of all things. As luck would have it, it began "Assume the contrary."
>
> Logical thought could be considered to arise from taking the concept of
> "most significant bit" to the extreme of "only significant bit" in a
> given context. That's the currency in the courtroom: guilty or not guilty.
>
> It is natural to want more bits (was it murder in the first degree or
> merely manslaughter?), but this need is dealt with in the language
> rather than its semantics: the jury may be asked to deliver binary
> verdicts on more than one charge: murder, and separately manslaughter.
>
> The same goes for other areas. Instead of refining the semantics one
> refines the language with suitable modalities for that purpose, such as
> "maybe," "usually," "rarely," in natural language discourse, "inside the
> unit circle," "on the punctured plane," in mathematics, and so on.
>
> Intuitionism arose from Brouwer's insight into the impossibility of 100%
> confidence in asserting the first bit to be zero without first ruling
> out the possibility that all the remaining bits are one. Brouwer wanted
> to embed this uncertainty into the semantics of mathematics, but this
> can just as readily be handled in its language, which most
> mathematicians seem to find more convenient. When one says "practically
> zero" one does not mean something precise such as "plus or minus .001%"
> since that just relocates the problem, rather one means that there is
> some associated uncertainty, which if desired can be quantified but only
> to within limits that themselves are uncertain.
>
> > Is there some intrinsical problem in proving a
> > physical fact assuming its contrary? Is it "formally" correct, in the
> > system we use to build physical models? Is the "tertium non datur" true
> > in classical or quantum Physics?
>
> See above. What we can say about physics is as much a question about
> language as it is about physics. LEM can be falsified in one logical
> framework that embeds naturally in another that validates it. In
> particular every Heyting algebra extends canonically to a Boolean
> algebra by taking its Stone-Priestley dual, forgetting the Priestley
> order to make it a Stone space, and dualizing back.
>
> >
> > My two cents are that everybody studying Physics must face an intrinsic
> > fuzzyness given by indeterminacy;
>
> Exactly so.
>
> > but even if we restrict to a classical
> > framework things are not so easy: what does "assuming ~P" mean, in a
> > framework where P can be a _real_ phenomenon (hence true or false by
> > mere perception; maybe in a framework where "P is true" is a necessary
> > truth)?
> > Take this as a joke, but there's a big number of mathematicians
> > convinced that Physics is nothing more than a branch of Geometry
> > (classical, differential or algebraic, it's not here the place to
> > discuss this);
>
> That could work if geometry could be made a natural setting for the
> study of linear operators and their eigenvectors. Can it? Its
> underlying geometry is projective, but this forgets crucial structure.
>
> If not, those reducing physics to geometry may find it hard to imagine a
> God that plays dice.
>
> can the previous questions be restated into a more
> > general one, say "Is geometry intrinsically non-boolean/without tertium
> > non datur?"
>
> Again, this can be reduced to a question about language. However not
> all geometries have that concern. One appealing feature of
> combinatorial topology is that it's a discrete discipline, like number
> theory, that is not burdened with the precision questions that arise
> with continuum-based geometry. It has this in common with the rational
> field, which suffices for the objects of affine geometry at all finite
> dimensions, though not their transformations, which introduce
> multilinearity. The Euclidean field (closure of the rationals under
> square root) suffices for the objects of Euclidean geometry (again at
> all finite dimensions) but I'm not aware of any practical way of
> exploiting its discreteness, unlike the rationals where it's easy. It's
> therefore easier to fall back on the continuum for Euclidean objects,
> and *a fortiori* for either affine or Euclidean transformations, than to
> try to live by the Euclidean field alone.
>
> Intuitionism is alive and well in computer science, but you asked about
> physics.
>
> Vaughan Pratt
>
>
> ------------------------------
>
> Message: 3
> Date: Mon, 19 Sep 2011 17:09:52 -0400
> From: Hendrik Boom <hendrik at topoi.pooq.com>
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: Re: [FOM] proofs by contradiction in (classical?) Physics
> Message-ID: <20110919210952.GA31391 at topoi.pooq.com>
> Content-Type: text/plain; charset=us-ascii
>
> On Sun, Sep 18, 2011 at 09:41:45PM +0200, Fouche wrote:
> > Can one use proofs by contradiction in Physics? And if it is possible,
> why
> > they are so rare? Is there some intrinsical problem in proving a physical
> > fact assuming its contrary? Is it "formally" correct, in the system we
> use
> > to build physical models? Is the "tertium non datur" true in classical or
> > quantum Physics?
>
> It has been argued (does anyone remember where?) that intuitionistic
> math is adequate for physics, because physics theories are established
> by failing to be falsified. The resulting negativity means that any
> classical arguments can be translated by the double-negation
> interpretation into an intuitionistic argument without loss of
> applicability to the physics.
>
> -- hendrik
>
>
> ------------------------------
>
> Message: 4
> Date: 19 Sep 2011 22:47:15 +0100
> From: T.Forster at dpmms.cam.ac.uk
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: Re: [FOM] About Paradox Theory
> Message-ID: <Prayer.1.0.20.1109192247150.20106 at moa.dpmms.cam.ac.uk>
> Content-Type: text/plain; format=flowed; charset=ISO-8859-1
>
> While we are on the subject of wellfoundedness and paradox, perhaps i might
> mention an open problem that has been bothering me for some time. It is
> easy to prove by $\in$-induction that every set has nonempty complement.
> The proof is even constructive. (I know of no constructive proof by
> $\in$-induction that every set has inhabited complement). The assertion
> that $x$ has nonempty complement is parameter-free, and is stratified in
> Quine's sense, and we can prove by $\in$-induction that every set has this
> property. My question is this: is there any other formula $\phi(x)$ -
> stratified and without parameters - for which we can prove $\forall x
> phi(x)$ by $\in$-induction? Put it another way: is there any parameter-free
> stratified $\phi$ s.t we have an elementary proof that (\forall x)[(\forall
> y)(y \in x \to \phi(y)) \to \phi(x)]
> My expectation is that the answer is `no', but i can't prove it - nor
> can i find a counterexample!
>
>
>
>
> ------------------------------
>
> Message: 5
> Date: Mon, 19 Sep 2011 15:40:56 -0700
> From: Thomas Lord <lord at emf.net>
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: [FOM] origin of "real"
> Message-ID: <1316472056.2757.21.camel at dell-desktop.example.com>
> Content-Type: text/plain; charset="UTF-8"
>
>
> I have a history and semantics question that this
> group might easily be able to answer (but elsewhere
> is hard to find an answer for):
>
> Who coined the term "real" as in "real number"
> and *why* did they pick that word?
>
> I ask because in a discourse on the programming
> language theory website "Lambda the Ultimate"
> someone wrote:
>
> "The reason real numbers have the name 'real' is
> because they correspond to measures of the real
> world."
>
> Retrospectively that sounds plausible but is it
> in fact the origin of the term?
>
> It's not a particularly important point in that persons argument
> so I'm not looking to go argue against it -- it's just
> that, while plausible, that explanation is not one I've
> heard before. Is it a "just so story" is that really
> the reason?
>
> So I'm curious if there is any more concrete
> information about the origin of the term.
>
> http://lambda-the-ultimate.org/node/4351#comment-67191
>
>
> -t
>
>
>
>
> ------------------------------
>
> Message: 6
> Date: Tue, 20 Sep 2011 11:18:31 +0300
> From: Aatu Koskensilta <Aatu.Koskensilta at uta.fi>
> To: Foundations of Mathematics <fom at cs.nyu.edu>, Daniel Mehkeri
> <dmehkeri at gmail.com>
> Cc: fom at cs.nyu.edu
> Subject: Re: [FOM] About Paradox Theory
> Message-ID: <20110920111831.25682ecnmlc82qtz at imp1.uta.fi>
> Content-Type: text/plain; charset=ISO-8859-1; DelSp="Yes";
> format="flowed"
>
> Quoting Daniel Mehkeri <dmehkeri at gmail.com>:
>
> > I don't think it is what you want anyway. The classical foundation
> > axiom is not constructively valid. Yes it is true we can make it
> > valid by contraposition: no inhabited set intersects all of its
> > members. However (and this is the sort of thing Nik Weaver keeps
> > reminding us about) this is weaker than set induction over all
> > first-order formulas.
>
> Arguably even classically foundation isn't the right formal
> expression of the idea that sets are obtained from the empty set (or
> urelements) by repeatedly applying the "set-of"-operation:
> second-order Zermelo set theory with foundation, for instance, has
> ill-founded models. (This is because without replacement we can't
> prove every set has a transitive closure.)
>
> --
> Aatu Koskensilta (aatu.koskensilta at uta.fi)
>
> "Wovon man nicht sprechen kann, dar?ber muss man schweigen"
> - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
>
>
> ------------------------------
>
> Message: 7
> Date: Tue, 20 Sep 2011 14:09:53 +0200
> From: "Antonino Drago" <drago at unina.it>
> To: "Foundations of Mathematics" <fom at cs.nyu.edu>
> Subject: Re: [FOM] proofs by contradiction in (classical?) Physics
> Message-ID: <8AD3886F1EF34922AD18F3CE6A4EC871 at Drago>
> Content-Type: text/plain; charset="utf-8"
>
> Sunday, September 18, 2011 9:41 PM
> Fouche fom at cs.nyu.edu wrote.
> Can one use proofs by contradiction in Physics?
>
>
>
> Surely. Many results - also in mechanics - have been obtained (since the
> time of Stevin) by arguments relying on the impossibility of the perpetual
> motion, a principle from which no direct proof can be obtained.
>
> The most celebrated proof in theoretical physics is Sadi Carnot's proof,
> reported by most textbooks on thermodynamics.
>
>
>
> F.: And if it is possible, why they are so rare?
>
>
>
> Because since Descartes and Newton's time theoretical physicists argued by
> starting from necessary statements (if not metaphysical notions as absolute
> space and absolute time and divine gravitational force). Only a minority of
> theoretical physicists argued without the idealistic notions (included in
> the necessary principles), i.e. by relying on only empirical data. Einstein
> and Poincar? stressed that there exist two ways of organising a physical
> theory from experimental data. A century before them, Lazare Carnot
> illustrated this point by means of the following words concluding his
> formulation of mechanics, which is at all different from Newton's mechanics
> (see my paper ?A new appraisal of old formulations of mechanics?, Am. J.
> Phys., 72 (3) 2004, 407-9):
>
>
>
> ?Among the philosophers who are occupied with research into the laws of
> motion, some make of mechanics an experimental science, the others, a purely
> rational science; that is to say, the former in comparing the phenomena of
> nature break them up [?] in order to know what they have in common, and
> thereby reduce them to a small number of principal facts [?]; the others
> begin with hypotheses, then reasoning in consequence upon their
> suppositions, come to discover the laws which bodies follow in their
> motions, if these hypotheses conform to nature, then comparing the results
> with the phenomena, and finding them to be in accord, conclude from this
> that their hypothesis is exact.? (L. Carnot, Essai sur les Machines en
> g?n?ral, Defay, Dijon, 1783, p. 102).
>
> Before him, D'Alembert stressed the same poiint in the issue "Elemens" of
> Encyclop?die Fran?aise.
>
> Another physical theory which argued in only this way was chemistry. See my
> paper ?Atomism and the reasoning by non-classical logic?, HYLE, 5 (1999)
> 43-55 (with R. Oliva)
>
>
>
> F.: Is there some intrinsical problem in proving a physical fact assuming
> its contrary? Is it "formally" correct, in the system we use to build
> physical models?
>
>
>
> The only intrinsic problem is given by the way of dealing with the
> conclusion of an indirect argument starting form a negative statement. The
> indirect argument reaches the negation of the negative thesis; to obtain the
> corresponding affrimative statement one has to apply the principle of
> sufficient reason: nothing is without reason; from which one obtains: there
> exists a reason for everything; and hence the affirmative thesis. This
> Leibnizian principle is useful only when direct evidence is lacking, just
> when the theory does not start from necessary principles, but it is aimed to
> solve a problem by making use of either common knowledge or experimental
> data only ; in the case of Sadi Carnot: the problem of which bound exists in
> the efficiency of the transformations of heat in work; in the case of
> chemistry, the problem of which are the elements constituting matter.
>
>
>
> Is the "tertium non datur" true in classical or quantum Physics?
>
>
>
> The physical theories including indirect proofs argue through double
> negated statements (chemistry: It is not possible that matter is divisible
> at infinity) which are not equivalent to the corresponding affirmative
> statements, owing to the lack of evidence of the latter ones (in previous
> case one has to exhibit the dimension of the finite elements; that was
> impossible before early 1900, i.e. along one century of development of
> chemistry.
>
>
>
> F.: My two cents are that everybody studying Physics must face an intrinsic
> fuzzyness given by indeterminacy; but even if we restrict to a classical
> framework things are not so easy: what does "assuming ~P" mean, in a
> framework where P can be a _real_ phenomenon (hence true or false by mere
> perception; maybe in a framework where "P is true" is a necessary truth)?
> Take this as a joke, but there's a big number of mathematicians convinced
> that Physics is nothing more than a branch of Geometry (classical,
> differential or algebraic, it's not here the place to discuss this); can the
> previous questions be restated into a more general one, say "Is geometry
> intrinsically non-boolean/without tertium non datur?"
>
>
>
> Geometry may be non-boolean. Please, read propositions 17-22 of Geometrical
> studies on Parallel lines by Lobachevsky (as an Appendix to R. Bonola: The
> Theory of Parallels, Dover); you will recognise both indirect proofs and
> some conclusions which are double negated statements: e.g. the final one:
> "The second assumption [of two parallel lines] can likewise be admitted
> without leading to any contradiction in the results..."; this conclusion is
> not equivalent to to the statement ?The second assumption is consistent?,
> because Lobachevsky could offer only indirect proofs. However, in the
> propositions following the no. 22 he argues from the affirmative version of
> this hypothesis; this fact shows that he applied the princple of suffcient
> reason to the above double negated statement.
>
>
>
> All the best
>
> Antonino Drago
>
>
>
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: </pipermail/fom/attachments/20110920/88246f82/attachment.html>
>
> ------------------------------
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>
> End of FOM Digest, Vol 105, Issue 20
> ************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20110920/2c5e19cd/attachment-0001.html>
More information about the FOM
mailing list