Jump to content


Senior Members
  • Posts

  • Joined

  • Last visited

Posts posted by John

  1. Having read through the above posts, I'm still having trouble with this consideration -


    Suppose we say "divide 5 by 0", Isn't that the same as saying "divide 5 by nothing" . And "nothing" literally means "no thing", And if you divide 5 by no thing, surely that means 5 ought to stay as 5.


    Just as when you "subtract" no thing from 5, it stays 5. As in: "5 - 0 = 5" That doesn't seem to cause any problems in maths. So I can't see why division should either.


    I mean, isn't "division" just a shorthand word for repeated subtraction? You can subtract 0 from 5 as many times as you like, 5 - 0 - 0 - 0 ..... and the answer is always 5, without apparently causing absurdity.


    Which is why this whole business of "division by 0" causing a problem, has always puzzled me. Can't mathematicians just stipulate that "5/0" means "5 - 0" ie, still 5. Would that resolve the problem?


    Division is defined as the inverse of multiplication, i.e. when we say "a divided by b," we're really saying "a multiplied by the multiplicative inverse of b." Thus, 5/0 is a shorthand for 5 * 0-1.


    Now, by definition, the multiplicative inverse x-1 of a field element x is the unique element such that xx-1 = 1. Thus, we have that 0(0-1) = 1. This is problematic, first because the proposed definition means 0(0-1) should equal 0 (which also follows from the demonstrable fact that 0 times any field element equals 0), and second because it yields inconsistency, e.g. 3 * 0 = 0 yields 3 = 1.


    I think all of the problems you came up with involve treating 0/0 as a real number, with a definite value and sharing the properties of real numbers. But wouldn't you be able to do the same thing with say i, deriving contradictions if i is treated as real and using rules that apply to reals?


    I think this is the only way it could be done. As a mathematical object it would have to be able to retain the property of being indeterminate, and it could not be consistently treated as a real. It could be useless... I can't conceive of a case otherwise.

    Indeed. All my points in this thread have been made in the context of the field of real numbers. Exotic structures may permit operations that we usually think of as being undefined, as mentioned in my first post in this thread.

  2. Do you have examples?


    I can think of an example only if you don't properly treat it as indeterminate, for example if we say "Since it is unknown we can replace 0/0 with x, where x is unknown", and we've mistakenly implied that if 0/0 is used several times then it should have the same value everywhere it's used.

    An equation like "0/0 = 0/0" would have to be treated as indeterminate forms, not as unknown reals, and understood to mean that "the indeterminate forms are the same" and not "the forms have the same unknown real value." Either that, or simply avoid defining 'equality' for indeterminate forms. Seems messy and tricky, but I can't think of any absurdity.

    Well, to be clear, I'm speaking in the context of the field of real numbers. Thus, the expression "0/0" is meaningless to begin with, since 0 (more generally, the additive identity) has no multiplicative inverse in this field or any other. Even if we ignore that fact, admitting 0/0 means it must be taken as a real number to maintain closure under multiplication and retain the field structure.


    By the definition of multiplicative inverse, 0/0 = 1. Given any a ≠ 1, we have 0a = 0, thus 0-1(0a) = 0-1(0), so a = 0-1(0) = 0/0 = 1, a contradiction. Specifically, we have 0(0) = 0, so 0 = 0/0 = 1. Thus the additive and multiplicative identities are equal, which by definition is impossible in a field.


    Just taking 0/0 to be a unique element leads to two possibilities. If 0/0 is allowed to "mingle" with other reals through addition and multiplication, then (I think) we end up just finding 0/0 = 0, i.e. it's just another symbol for the additive identity. Other values can probably be determined as well, in which case we can derive that given two elements a1a2, we have a1 = a2, a contradiction. If, on the other hand, we isolate 0/0 into a separate class of "indeterminates," then it doesn't seem to add anything to the structure, rendering the expression rather useless.

  3. No. Zero is certainly a real number, whereas infinity is not.


    However, division by zero cannot be defined in the usual structure of the real numbers without leading to logical inconsistency. That is to say, give me any reasonable and useful value for the expression x/0 and we can use it to deduce a false statement.


    Also, it seems 0/0 is sometimes referred to as "indeterminate" even outside the context of limits, which is news to me. Admitting 0/0 as a valid arithmetical expression still leads to absurdity, however.

  4. One way we might (begin to) construct the natural numbers is to define 0 as the empty set Ø and define the successor function S(x) = x ∪ {x} for any set x. It follows that each natural number n ≠ 0 equals {0, 1, 2, ..., n - 1}. So we have


    0 = Ø

    1 = S(0) = {0} = {Ø}

    2 = S(1) = {0, 1} = {Ø, {Ø}}

    3 = S(2) = {0, 1, 2} = {Ø, {Ø}, {Ø, {Ø}}}


    etc. Of course, only heretics take zero to be a natural number, and this construction still works if we begin with 1 = Ø instead of 0 = Ø, but I think the latter is slightly easier to conceptualize. :P


    In any case, we can then define the relation < in terms of elementhood such that a < b a b. Thus, from the construction given above, 1 < 2.


    Of course, there are other possible constructions (though as far as I know, they all follow the same general process). A nice example, along with a more detailed definition and discussion of <, can be found here.

  5. x/0 is inconsistent but 0/0 isn't, so it is called "indeterminate" instead of "undefined" as x/0 is.

    I don't know if this is debatable, or if it's a rule or if it depends on context or what.


    "Indeterminate form" is used in the context of limits in analysis, when simple substitution gives a result that doesn't determine the value of the limit itself.


    Division by zero, itself, is undefined, even if the numerator is also zero.

  6. The structure of the real numbers, as we usually take it to be, does not allow for division by zero, for the reason that assigning a definition leads to logical inconsistency. Therefore, the correct answer in this context is that "division by zero is undefined."


    I suppose that it's possible, in principle, to define a structure in which 0/0 is defined, but I'd imagine we'd have to abandon certain intuitive properties of numbers in that case.


    Numberphile has a decent video covering this and other operations involving zero.

  7. If your system is inconsistent, then it isn't a good foundation on which to build a mathematical theory. There are some attempts to develop logics that tolerate inconsistencies, but they involve abandoning certain intuitive properties of logical reasoning (see the Wiki page for details).

    It is not correct to say an inconsistent formal system doesn't admit theorems. On the contrary, as noted above, an inconsistent formal system has all statements as theorems. Keep in mind I am speaking formally here. If we take a system containing both p and ¬p as axioms, then the statement p ¬p is a theorem of the system, despite the fact that such a statement doesn't really "make sense." The fact that p ¬p is a theorem of the system then allows us to deduce any statement (this is explained in some detail on the Wiki page linked above).


    However, you say you aren't being formal. I'm not sure precisely what you mean by that, but in the usual sense, a lack of formal rigor may hinder the development and acceptance of any mathematical theory. I'm also not sure what you mean when you talk about the "natural sense of Mathematics" or axioms not perceived in that way.

    I'm not sure what the requirements are for two systems to be "completely different." The axioms of Peano arithmetic (the first-order theory of the natural numbers with addition and multiplication) are mostly different from the axioms of Zermelo-Fraenkel set theory (though the former's axiom schema of induction is similar to the latter's axiom of infinity, and maybe some other similarities can be found), but there are theorems deducible from both. In fact, I think the axioms of PA are deducible from ZF.

  8. I'm not sure I understand your notation, but if I'm understanding you correctly, then you're considering a formal system which has a contradiction as a theorem. Such a system is inconsistent.

    It's a fact of logic that an inconsistent formal system (at least in the usual sense) can be used to prove any statement. Therefore it's trivially complete but its structure is fairly uninteresting.

    From the last few lines of your description, it sounds like you're thinking about something similar to Russell's paradox in naïve set theory (allowing the "set of all sets that aren't members of themselves") and the formal statement Gödel constructed as part of his proof of the incompleteness theorems.

  9. For some sets of axioms, perhaps. However, I think it's difficult to precisely define what we mean when we talk about enumerating simplified theorems.


    For instance, by "theorem," do we mean a result we find interesting? Do we mean "theorem" in the sense of proof theory, where it refers to a well-formed formula of a formal language? I would assume the latter, based on the context of the conversation and because the former is subjective, but in the latter case I would imagine there are infinitely many theorems except perhaps in certain extremely simple or restrictive languages.


    This brings us to the question of simplification. Where do we draw the line? If we're talking about a formal proof of some theorem in a formal language, then what we have is a list of statements following from previous statements. In a precise sense, at what point do we divide the list into a "simplified" section and a "redundant" section? Ultimately, would it make sense to regard anything besides the axioms themselves as simplified, since everything else just follows from them?

  10. That depends on what you mean by an automated theorem prover. While they used computer algorithms to be proved, there was a specific task for such a proof given to the algorithm. What I am referring to is a generalized form of an algorithm.


    While I agree that the point of proofs are to give a human understanding of mathematics, it is important to realize that computers would give much help to providing an understanding if this algorithm were produced. In fact, if such an algorithm were developed it would provide a way for mathematicians to use similar patterns of proofs to understand theorems and conjectures.

    Certain results can be proved via computer program, and I agree the output of such a program can potentially aid a human user in deepening his understanding. However, no general algorithm exists that's capable of deciding the truth of arbitrary statements. This is the essence of the halting problem as it relates to automated theorem proving.


    And I'm referring to "automated theorem provers" in the sense of http://en.wikipedia.org/wiki/Automated_theorem_proving.


    I can see the issue here. Machines are limited to how they can interpret truth because truth is ultimately defined by their own rules as well.


    However, doesn't this also apply to Mathematics in general? We base proofs off of theorems that are based off of theorems, which are eventually based off axioms of Mathematics. As the definition of an axiom states, an axiom is a starting point of reasoning(http://en.wikipedia.org/wiki/Axiom). Therefore, the same principle could apply to a machine as axioms would be defined for a machine from which it would know truth from in the same way we hold truth to our axioms of Mathematics. Therefore, wouldn't truth be defined by the axioms presented to such a machine and provide an end point of a proof just like how we use axioms to provide an end point to our proofs? This is a very interesting topic, I must say.

    The issue is a bit more fundamental than that, and in some ways is connected to Gödel's incompleteness theorems, which are very deep results about the nature of formal systems. I won't venture too far into details (mainly because there's a lot I've forgotten since I really studied mathematical logic :P), but proofs of and discussions about the halting problem, the incompleteness theorems, and their relationship to each other, can be found all over the Web.


    Suffice it to say that, in any sufficiently strong formal system (and this includes a choice of axioms), there are statements which are true but unprovable, and it's impossible for the system to prove its own consistency. These are fundamental limitations on what we can deduce from any given set of axioms.


    Though there isn't really a fundamental theorem of mathematics, it seems there must be because of the existence of many other fundamental theorems that exist that are potentially semi-fundamental theorems of mathematics. That is what I was approaching.

    Well, in various areas of mathematics, there are certain results considered important enough that we call them "fundamental," but I'm not sure the word is being used in quite the way you're taking it.


    It's a minor point, anyway. I just wondered if you had some specific theorem in mind.

  11. There is also the falsum [math]\bot[/math], used to denote a general contradiction. For instance, in your simple example, you might say [math](1 = 0) \vdash \bot[/math], i.e. "1 = 0 yields a contradiction".


    For the formal statement of Fermat's Last Theorem, there are many ways to go about it, including


    1. [math](\forall x, y, z \in \mathbb{N})(n \in \mathbb{N}_{>2} \implies x^n + y^n \neq z^n)[/math],


    2. [math](\forall x, y, z \in \mathbb{N})(\forall n \in \mathbb{N}_{>2})(x^n + y^n \neq z^n)[/math],


    3. [math](\forall x, y, z, n \in \mathbb{N})(x^n + y^n = z^n \implies n \leq 2)[/math], and


    4. [math]\{x, y, z, n \in \mathbb{N} \mid (n > 2) \wedge (x^n + y^n = z^n)\} = \varnothing[/math].

  12. What is the Fundamental Theorem of Mathematics?

    As for the general idea of an automated theorem prover, let me post some thoughts, with the caveat that my own study of logic is limited. Hopefuly, if any logicians turn up, they won't find anything completely objectionable.


    The halting problem limits what can be accomplished by an automated theorem prover under current physically realizable models of computation. There is no general algorithm capable of deciding the truth or lack thereof of an arbitrary statement regarding the natural numbers. We can use a Gödel numbering system to encode formal statements as natural numbers, thus it follows that there is no general algorithm capable of deciding the truth or lack thereof of an arbitrary formal statement.


    There is the concept of the oracle machine, which is essentially a Turing machine paired with a "black box" capable of solving the halting problem for Turing machines. Certain conjectures (including the Collatz conjecture, I believe) would be relatively easy for such a machine to solve. However, even an oracle machine would still be incapable of solving the halting problem for equivalent oracle machines, and in fact we don't know whether such a machine can be built in the first place.

    As far as I know, it's also an open question whether human brains can solve the halting problem, and so we may someday discover we share this limitation with computers. Certainly we share a more fundamental limitation in that, by Gödel's first incompleteness theorem, any "sufficiently strong" formal system (examples of which include Peano arithmetic and Zermelo-Fraenkel set theory) contains true statements which aren't provable in the system. Thus, even ignoring the infinitude of formal statements, generating a complete set of theorems (and leaving out false statements) in a given theory is impossible, using a computer program or otherwise.

    Now, automated theorem provers have been in use for years now, and programs have been used to assist in proofs (perhaps most notably in the case of the four-color theorem). However, it's difficult (and perhaps impossible) for a computer program to determine what results are mathematically interesting, and it's difficult (and perhaps impossible) for a computer to take a bird's eye view of mathematical theory and develop deep insights into how everything works. Simply spitting out results isn't the aim of mathematics. Rather, we seek human understanding of how mathematics works. An automated theorem prover doesn't, and perhaps can't, offer that generally.

    Of course, if we develop a true AI, then maybe all bets are off. :P

  13. I'm not sure I completely understand what you're asking here.

    To be precise, your original relation [math]R[/math] isn't transitive.


    You could probably recursively define your desired relation [math]R'[/math] as follows.


    Given a relation [math]R_{1}[/math] on a set [math]S[/math]:


    [math]\begin{array}{rcl}R_{n} & = & R_{n-1} \cup \{(a,b) \mid \exists x(aR_{n-1}x \wedge xR_{n-1}b) \}, \\ R' & = & R_{\min \{n \mid R_{n} = R_{n-1}\}}.\end{array}[/math]


    There's probably a prettier way to express this, but that's the gist.

  14. All that's been claimed is that Dr. Susskind (or anyone else) is fallible, regardless of experience. I don't know what part of physics research you think magically renders someone unable to make a mistake, but I can assure you no such part exists.

    Anyway, there isn't much more to say here. You've demonstrated that you know something about what you're talking about, professional scientist or no, but don't be so quick to dismiss the knowledge and experience of our other members.


    Take care.

  15. Your original post claimed someone had denounced The Cosmic Landscape, and your more recent post implied that someone had called Dr. Susskind a crank. I've read the recent threads where the book and author were discussed, and I don't recall either of those things taking place.

    You may be reading too much into what's been said.

  16. You're allowed to reference whatever you like. If it's nonsense, it will be called out as nonsense (and you'll probably be asked not to reference that particular source again). If it's valid, then it will be treated as such. Keep in mind, though, that as you alluded to in your own post, several of the books you've mentioned (including The Cosmic Landscape) are pop-sci. They sacrifice some accuracy and rigor in the name of understanding by the general public. We have quite a few professional scientists (and amateurs with excellent understanding) among our members, and simplifications that seem misleading will be called out.

    Indeed, even seemingly rigorous statements are challenged on a fairly regular basis here. This is a science forum, and part of science is debate in the name of establishing scientific truth. The proper response in such situations is to defend the statement if possible, and to reevaluate the statement otherwise. Saying something like, "Well, Susskind wrote it," isn't a valid defense, as without loss of generality, Dr. Susskind's status as a brilliant theoretical physicist in no way makes his publications inerrant.

    It seems like you're taking what disagreements you've had here a bit personally. That's not the way to go.

  17. Keep in mind that w can be *any* string in L with length at least p. Then it's a matter of checking the various valid ways in which w can be decomposed into uvz to see whether iterating v fails to give a new string in the language.

    For instance, in this new problem (where mn), consider the string w = apbp+1 (spoiler alert: this one won't work--it's just an example of the reasoning). Decompose it into the substrings u = ap-1, v = a, and z = bp+1. Then for i = 2, we have uv2z = ap-1a2bp+1 = ap+1bp+1, which isn't in the language. This is all well and good, but we have to consider *all* possible decompositions of w. So consider u = ap-2, v = a2, and z = bp+1. Now, for i = 1, we have our original string uvz = ap-2a2bp+1 = w. For i = 2, we have uv2z = ap-2a4bp+1 = ap+2bp+1, which is in the language. For i = 3, we have uv3z = ap-2a6bp+1 = ap+4bp+1, which is in the language. And so on. Thus we have found a decomposition of w for which we generate a new string in L for any choice of i.


    The question is, can you find a valid string w such that, given any valid decomposition of w, we generate a new string not in L for some value of i ≥ 1?

    A hint: The empty string ɛ is a substring of any string.

  18. If the language consists of strings meeting two conditions, then showing that one condition fails is enough. If the language consists of strings meeting *at least one of* two conditions, then you must show that both conditions fail.


    For your last question, I'm assuming you're referring to your original problem, in which L = {ambn: n = 4m}. Here you simply need to show that, in the resulting string, the required relation n = 4m doesn't hold, i.e. there are no longer four times as many b's as a's.

  19. I don't really know how to explain better than the way the Wikipedia article I linked earlier explains.

    The general process is as follows. Given a language L:

    1. Assume L is regular.

    2. Choose a string w in L of length greater than p, where p is the pumping length guaranteed by the pumping lemma for regular languages.

    3. Decompose w into three substrings xyz such that |xy| ≤ p and |y| ≥ 1.

    4. Show that for some positive integer i, xyiz is not in L.

    In your argument above, you haven't guaranteed the reader that w is of length greater than p, since m is an arbitrary value (which could be zero, making w the empty string ɛ). You also say that |uv| = n, but we aren't told what n is and it's never made clear from context in the rest of the argument.


    Proof-writing doesn't come naturally for most people (myself included). Even in cases like this, where there's a general outline that seems to work, the details can be a pain, and learning to work through them proficiently is a matter of practice.

    Bed-time for me, anyway. Best of luck on your assignment. :) Going back over your textbook, or whatever learning resources you're using, is probably a good idea. Sometimes you just have to stare at the material until it clicks. And of course, there are other pumping lemma proofs and examples around the Web if you care to Google.

  20. Well, once you've decomposed your string w into uvz (I changed uvw to uvz because the entire string is w), the restrictions are that |uv| ≤ p and |v| ≥ 1. As far as I can tell, for any valid string and any valid decomposition uvz, pumping once (which corresponds to setting i = 2 such that the resulting string is uv2z) is enough, but the idea is to show that it's enough for some string w in L, which you halfway did in your OP, but there are, as mentioned, gaps.


    The last question in your original post asks whether the given statements constitute a valid proof. :P But no matter.

  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.