Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2018 February 19

From Wikipedia, the free encyclopedia
Mathematics desk
< February 18 << Jan | February | Mar >> February 20 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


February 19

[edit]

Algebra

[edit]

So, Yikes! Haven't done algebra in nearly 20 years.

I was given a sample problem of: 7 + 18f = 20f - 5

The solution says to "Subtract 20f from both sides"

Ok, when I was trying to figure it out, I added 5 to both sides, to clear out the -5.

Why was that not correct? I'm way confused now!

Actually, maybe I am starting to get it...you want to get an F by itself? Ok, if that's right, why not subtract 18f from both sides?

CTF83! 06:14, 19 February 2018 (UTC)[reply]

It would be a little easier to subtract 18f from both sides. Then add 5 to both sides, giving 12 = 2f, so f = 6. Bubba73 You talkin' to me? 06:24, 19 February 2018 (UTC)[reply]
Oh, ok, I see. Thanks! CTF83! 06:41, 19 February 2018 (UTC)[reply]
It can be done in many ways. Your method would also be a correct start but it's common to start by removing the variable on one side. Some people may prefer to keep the variable on the left. It's also possible some learning materials specify a fixed algorithm demanding this. Subtracting 20f on both sides gives 7 - 2f = -5. Subtract 7 on both sides to get -2f = -12. Then divide by -2 to get f = 6. Most people would find this harder than subtracting 18f at the start. PrimeHunter (talk) 13:59, 21 February 2018 (UTC)[reply]
The main point is not the method but the result; anything that does the same thing to both sides of the equation and ends up with f on its own on one side is fair game. Both you and the sample solution are correct, even if you decide to add 5 to both sides first instead of subtracting 18f. Double sharp (talk) 14:27, 21 February 2018 (UTC)[reply]

First Order Logic: Completeness vs. Decidability

[edit]

Something that has been puzzling me lately: my understanding is that FOL is complete, that all theorems in FOL that are true can be proven to be true. But I know that Turing and Church proved that FOL is not decidable, that there is no algorithm that given any arbitrary theorem can tell whether it is true or false. I know I'm missing something but these two facts seem inconsistent to me. I used to think that the answer was that while all the true theorems can be proven true there are some false theorems that can't be proven false. But someone pointed out to me that if that is the case just take the negation of any theorem. One of them has to be true and hence since FOL is complete you can prove that one which will prove the negation of that theorem to be false. I know I'm making some fundamental error here would appreciate someone helping me understand what it is. --MadScientistX11 (talk) 19:44, 19 February 2018 (UTC)[reply]

First-order logic is complete - see Gödel's completeness theorem. It is the higher stuff that is incomplete and indecidable, right? Bubba73 You talkin' to me? 19:52, 19 February 2018 (UTC)[reply]
No, unfortunately, the term "complete" is a bit overloaded here. First-order logic is complete in the sense that every statement that is true in all models is also provable. I think this might be called "model-completeness"? Not sure; you usually work it out from context.
That's different from negation-completeness, which says that for every statement, either the statement or its negation is provable. First-order logic is very far from being negation-complete. --Trovatore (talk) 20:02, 19 February 2018 (UTC)[reply]
It has been 35 years since I had this stuff. My memory from those days is that first-order logic did not include "there exists" and "for all", and was decidable by building a truth table. Please correct me if I'm, wrong, and it has been a long time... Bubba73 You talkin' to me? 20:50, 19 February 2018 (UTC)[reply]
I think you're thinking of propositional logic rather than first-order logic. Propositional logic is indeed negation-complete. But the language is too restrictive to express anything very interesting. --Trovatore (talk) 21:01, 19 February 2018 (UTC) Oops, sorry, that was silly. Propositional logic is not negation-complete. But it is decidable, which first-order logic is not. --Trovatore (talk) 21:05, 19 February 2018 (UTC)[reply]
Thanks - it has been a long time. Bubba73 You talkin' to me? 22:28, 19 February 2018 (UTC)[reply]
"But someone pointed out to me that if that is the case just take the negation of any theorem. One of them has to be true and hence since FOL is complete you can prove that one which will prove the negation of that theorem to be false."
I believe this is the fundamental error. It is not always the case that either a statement or its negation is provable. For a simple example, suppose we have a single axiom and ask whether is provable from that axiom. Obviously it is not, but neither is . The second statement (and its negation) is independent of the axioms. Anon126 (notify me of responses! / talk / contribs) 20:00, 19 February 2018 (UTC)[reply]
@Trovatore: and @Anon126: Thanks. I think I've got it now. I'm just going to try restating what I think was said to make sure: so I think my error is confusing validity (which I believe is the same as true in all models) with provability. Completeness means that all valid theorems are provable and FOL is complete. But many theorems (e.g., that there is no number between X and it's successor which is true for Natural numbers but not for reals) are not true in all models. And some of those FOL theorems that are not valid are also not provable by the Turing/Church proof. --MadScientistX11 (talk) 22:52, 19 February 2018 (UTC)[reply]
Um. I think you've sort of got it, but maybe not exactly. Try it this way:
  • Validity is truth in all structures. Equivalently, validity is the same as provability without using axioms (though the equivalence is not obvious).
  • Provability from a set of axioms is the same as truth in all models of those axioms. This is by the completeness of first-order logic.
  • Truth of (for example) a statement about the natural numbers is distinct from provability. Any statement about the natural numbers is either true or false, but not necessarily either provable or refutable (from a particular axiomatic system).
  • The basic source of the confusion in your first post is the overloading of the term "complete", as I said in my post of 20:02, 19 February 2018.
Does that help? --Trovatore (talk) 23:38, 20 February 2018 (UTC)[reply]
@Trovatore: Yes, that definitely helps. I think I've really got it this time. Fantastic answers, you guys are awesome! Thanks again. --MadScientistX11 (talk) 22:32, 21 February 2018 (UTC)[reply]
  • Interesting discussion, but, @Trovatore:, @Anon126:, @MadScientistX11: (sorry to arrive so late, just super-curious): have we really hit the nail on the head? I can't find what seems to be the exact statement of the problem, although it may be there, and maybe my brain is a bit soggy, here goes ...
--FOL is complete: this means true statements can be proven true. "True statements" means they are effectively tautologies, such as "If all oranges are orange, and there exists at least one orange, then there is at least one orange that is orange". So far so good, we nailed that.
--But: undecidable: "If all oranges are orange, then there exists at least one orange that is orange." Oops, we didn't specify that there actually exists at least one orange. This is true or false depending on whether oranges exist. But if FOL is not decidable, this "theorem", which is not true (nor is its negation) possibly cannot be discredited by any algorithm. An algorithm might stop and say "NOT a theorem of FOL", or it might just go on forever (without giving the wrong answer, just giving no answer)
--I don't think we really spelled this out - Anon126 says, "independent of the axioms", which is not as strong as saying, provably (by a universal algorithm) independent, ie, provably not a universally valid theorem, using (of course) a finite number of steps in the proof. Am I right, and is this something people didn't quite specify? I know it was alluded to above, but I can't see where it is made explicit. IBE (talk) 22:09, 26 February 2018 (UTC)[reply]
  • On your first point: That FOL is complete means that logically valid statements can be proven. "Valid" is stronger than "true"; it means "true in all structures". 2+2=4 is true (in the intended interpretation), but it isn't valid, because you can invent a structure where it's false. And you can't prove 2+2=4 without using axioms.
  • "Undecidable" is another overloaded term; unfortunately some people use it to mean "independent" (without always specifying what axioms it's independent of). However, in this context, "FOL is undecidable" means that there is no algorithm that will always terminate in finite time and tell you correctly whether a given statement is valid.
    But this is important and slightly subtle: It does not mean that there is any particular statement that cannot be determined whether it is valid or not.
  • I don't quite follow your third paragraph. --Trovatore (talk) 22:31, 26 February 2018 (UTC)[reply]
Thankyou - my 3rd par isn't that important. I was referencing the foregoing discussion, about whether Anon126 had stated the same thing as me, and I was clarifying why I thought s/he hadn't. It doesn't matter so long as no one is trying to correct me/ chasten me for repeating what others may have said in a better form.
Regarding my first point, your wording is better, but I think that is what I am saying, they are effectively tautologies, structurally necessary. Your wording seems clearer and better, but I think it's the same basic point, which had been made quite well.
Regarding the second point, you have clarified and refined it, although it seems effectively much the same as my point (for the purposes of this discussion). This was the bit that I thought no one had really said above (either my version or your more precise refinement). This is what I thought was needed (with thanks to your precision) - the difference between the things you can prove (all true things) and the things you possibly cannot prove to be non-theorems (which is not the same as saying they are false - they might be contingent.) This was the bit I couldn't find above, though I thought maybe someone would point out, no we said that here, here and here. IBE (talk) 23:44, 26 February 2018 (UTC)[reply]
I think my response has generated some confusion, so let me clarify.
As I understand it, MadScientistX11 understands the concepts of completeness and decidability as you've described. (And to be clear, I don't think there is any confusion about different definitions of completeness.)
But they don't understand how a system can be both complete and undecidable. I imagine their thought process went something like, "Surely if you can prove all valid statements, then you can determine if a statement is valid by attempting to prove it. If no proof is found, then the statement is invalid." And they had previously resolved this confusion, stating, "I used to think that the answer was that while all the true theorems can be proven true there are some false theorems that can't be proven false." This is essentially correct, although you should replace "true" with "valid" and "false" with "invalid."
But someone has brought that resolution into question: "But someone pointed out to me that if that is the case just take the negation of any theorem. One of them has to be true and hence since FOL is complete you can prove that one which will prove the negation of that theorem to be false." My response was a rebuttal to this questioning: I showed that it is not necessarily the case that either a theorem or its negation is valid.
In conclusion, the takeaway for MadScientistX11 is that what they "used to think" was correct, and that this "someone's" statement is incorrect. Anon126 (notify me of responses! / talk / contribs) 23:07, 26 February 2018 (UTC)[reply]
@Anon126: That bit is clear, yes, but I thought it wasn't enough to explain the concept of undecidability. You are clearly right about the existence of the third class, so roughly speaking, we have "always right", "always wrong" and "contingent". But I thought to explain undecidability, we had to add, that in a decidable theory (such as propositional logic, I think??), there exists an algorithm that will also tell us that those contingent things are non-theorems. Its not just that the contingent category is separate from the yes/no groups, it's that the issue of decidability relates to this, whether these also can be proven to be non-theorems. That was the reason for my post, because it seemed the earlier answers were all correct, but I couldn't find where the final point was made explicit. Perhaps it was clear to the OP anyway, but at least this clarifies for me. IBE (talk) 23:54, 26 February 2018 (UTC)[reply]
@Anon126:@It's Been Emotional: Just wanted to let you know I've been following the additional discussion. One of the things that surprised me when I started studying logic in some detail is how loose some logicians are with their language. I was reading a discussion of Goedel's proof last year and part of it was "the only variables we have are x', x'',... and then in the next paragraph "now suppose we have x and y" and for the longest time I puzzled over WTF I was missing until I asked the professor and he said "oh he (the author) is just using x and y to stand for x' and x'' because it's more convenient" I think people who just know this stuff know the context so well they often use terms like true and valid and just assume that it's clear from the context, which it is for guys like you (other commenters) but for people like me it can be confusing. I know none of this is relevant, just saying discussions like the above really help an amateur like me understand this and I appreciate the extra comments here very much, they've added more clarity to my understanding. Thanks. --MadScientistX11 (talk) 18:09, 2 March 2018 (UTC)[reply]

Can a light bulb be two functions in two dimensions and one in three dimensions?

[edit]

Is a pair of functions possible which looks like a light bulb? In two dimensions, to the left of the y-axis is a half circle with radius a, with a curve above the x-axis and a mirror image of it below, ending where the bulb screws in with the value of y approaching b above the x-axis and -b below it. In three dimensions, there is one function where half a sphere is above the xy plane and the radius is again a, with a circle of radius b below the xy plane.— Vchimpanzee • talk • contributions • 21:31, 19 February 2018 (UTC)[reply]

I'm not quite sure what you're talking about (English isn't my native language), but you could try something like this. Admittedly that isn't much of a light bulb but playing with coefficients and increasing the polynomial's degree enough you can get as close to the real light bulb as you want, and later it shouldn't be hard to find the function for the rotational shape (sp?). If you want to have a better approximation of a real light bulb, you can pick out enough points and find the polynomial that passes through them using this method, although the polynomial might end up with a really large degree for a passable light bulb.
Although, if you want to have an exact half-circle/hemisphere on the round side of the bulb (x^2+y^2[+z^2]=r^2), you will probably have to define it piecewise (is that what you meant by two functions?) or do something with absolute value function, a polynomial won't do then. 78.1.172.210 (talk) 00:04, 20 February 2018 (UTC)[reply]
Correction to my original question: In three dimensions it is still a pair of functions which are mirror images, on either side of the x-axis.— Vchimpanzee • talk • contributions • 15:11, 20 February 2018 (UTC)[reply]
I took a second look at your response. Two functions means absolute value, two mirror images. If you're saying this cannot be a polynomial, I think I have my answer.— Vchimpanzee • talk • contributions • 16:44, 20 February 2018 (UTC)[reply]

The surface has rotational symmetry around the x-axis. Choose for in order to make a spherical bulb to the left. Choose for in order to make a thinner cylindrical shape to the right. Close the cylinder by a spherical surface for . Choose such that and choose such that . Bo Jacoby (talk) 21:48, 20 February 2018 (UTC).[reply]