https://www.explainxkcd.com/wiki/api.php?action=feedcontributions&user=162.158.167.35&feedformat=atomexplain xkcd - User contributions [en]2022-09-30T07:07:46ZUser contributionsMediaWiki 1.30.0https://www.explainxkcd.com/wiki/index.php?title=1724:_Proofs&diff=1258611724: Proofs2016-08-29T07:23:59Z<p>162.158.167.35: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 1724<br />
| date = August 24, 2016<br />
| title = Proofs<br />
| image = proofs.png<br />
| titletext = Next, let's assume the decision of whether to take the Axiom of Choice is made by a deterministic process ...<br />
}}<br />
<br />
==Explanation==<br />
[[Miss Lenhart]] is back teaching a math class. She begins a proof when one of her students ([[Cueball]]) interrupts her asking if this is one of those dark-magic (unclear, incomprehensible) proofs. She says no, but it soon turns out that it is; Cueball exclaims that he just knew it would be.<br />
<br />
The proof she starts setting up resembles a {{w|proof by contradiction}}. This kind of proof assumes that a particular condition is true, and shows that this assumption leads to a contradiction, which disproves the initial assumption. For example assumption that √2 is a {{w|rational number}} means that, for some natural ''a'' and ''b'', √2=''a/b'', where ''a/b'' is an {{w|irreducible fraction}}. Yet, multiplying this equation by itself, we get 2=''a²/b²'' which in turn rearranges to 2''b²''=''a²''. Therefore ''a²'' is even (as any integer multiplied by 2 is even), which means that ''a'' is an even number, as an even number squared is always even and an odd number squared is always odd. This means, that ''a=2k'' and ''2b²=(2k)²=4k²'', meaning ''b²''=2''k²'', so ''b'' must be even too. But if both ''a'' and ''b'' are even, ''a/b'' cannot be irreducible. Contradiction means that the initial assumption is false, and √2 cannot be a rational number.<br />
<br />
Alternatively, instead of a proof by contradiction the setup could be for a one way function. For example, it is relatively easy to test that a solution to a differential equation is valid but choosing the correct solution to test can seem like black magic to students.<br />
<br />
The way that Ms Lenhart's proof refers to the act of doing math itself, is characteristic of metamathematical proofs, for example {{w|Gödel's incompleteness theorems}}, which, at first sight, may indeed look like black magic, even if in the end they must be a "perfectly sensible chain of reasoning" like the rest of good mathematics. While typical mathematical theorems and their proofs deal with such mathematical objects as numbers, functions, points or lines, the metamathematical theorems treat other theorems as objects of interest. In this way you can propose and prove theorems about possibility of proving other theorems. For example, in 1931 {{w|Kurt Gödel}} was able to prove that any mathematical system based on arithmetics (that is using numbers) has statements that are true, but can be neither proved nor disproved. This kind of metamathematical reasoning is especially useful in {{w|set theory}}, where many statements become impossible to prove and disprove if the {{w|axiom of choice}} is not taken as a part of the axiomatic system.<br />
<br />
Using a position on the blackboard as a part of the proof is a joke, but it bears a resemblance to {{w|Cantor's diagonal argument}} where a position in a sequence of digits of a real number was a tool in a proof that not all infinite sets have the same {{w|cardinality}} (rough equivalent of the number of elements). This "diagonal method" is also often used in metamathematical proofs.<br />
<br />
The axiom of choice itself states that for every collection of nonempty sets, you can have a function that draws one element from each set of the collection. This axiom, once considered controversial, was added relatively late to the axiomatic set theory, and even contemporary mathematicians still study which theorems really require its inclusion. In the title text the decision of whether to take the axiom of choice is made by a deterministic process, that is a process which future states can be developed with no randomness involved. {{w|Determinacy}} of infinite games is used as a tool in the set theory, however the deterministic process is rather a term of the {{w|stochastic process|stochastic processes theory}}, and the {{w|dynamical systems theory}}, branches of mathematics far from the abstract set theory, which makes the proof even more exotic. The axiom of choice was mentioned earlier in [[804: Pumpkin Carving]].<br />
<br />
Although Miss Lenhart did retire a year ago after [[1519: Venus]], she seems to have returned here for a math course at university level, but continues the trend she finished with in her prior class.<br />
<br />
'''TL;DR''' Cueball suspect Ms Lenhart already made-up an answer for a made-up mathematical function (hence ''magic''), which is confirmed at the last panel.<br />
<br />
==Transcript==<br />
:[Miss Lenhart is standing facing left in front of a whiteboard writing on it. Eleven left aligned lines of writing is shown as unreadable scribbles. A voice interrupts her from off-panel right.]<br />
:Miss Lenhart: ... Let's assume there exists some function ''F''(''a,b,c''...) which produces the correct answer-<br />
:Cueball (off-panel): Hang on.<br />
<br />
:[In a frame-less panel Cueball is sitting on a chair at a desk with a pen in his hand taking notes.]<br />
:Cueball: This is going to be one of those weird, dark magic proofs, isn't it? I can tell.<br />
<br />
:[Miss Lenhart has turned right towards Cueball, who is again speaking off-panel. The white board is also off-panel.]<br />
:Miss Lenhart: What? No, no, it's a perfectly sensible chain of reasoning.<br />
:Cueball (off-panel): All right...<br />
<br />
:[Miss Lenhart is facing the whiteboard again writing more scribbles behind some of the lines from before (the first line has disappeared). The lines that have more text added are now number three and five (four and six before). Cueball again speaks off-panel.]<br />
:Miss Lenhart: Now, let's assume that the correct answer will eventually be written on the board at the coordinates (''x, y''). If we—<br />
:Cueball (off-panel): I ''knew'' it!<br />
<br />
{{comic discussion}}<br />
<br />
[[Category:Comics featuring Miss Lenhart]]<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Math]]</div>162.158.167.35https://www.explainxkcd.com/wiki/index.php?title=Talk:1724:_Proofs&diff=125860Talk:1724: Proofs2016-08-29T07:20:04Z<p>162.158.167.35: </p>
<hr />
<div>Judging from my experience when I first encountered proofs in math classes (or my general experience from math classes), the teacher is going to write down a "proof" which makes absolutely no sense to students and is also never explained in a way that actually makes them understand. Instead, they are just going to use "dark magic" and write what seems to be completely senseless to students.<br />
[[Special:Contributions/141.101.91.223|141.101.91.223]] 04:24, 24 August 2016 (UTC)<br />
:: 'Dark magic' might also refer to the supernatural, so when the teacher said that an answer 'will be written' in a specific location, Cueball took this to mean that a spirit would be summoned to write it, like a ouija chalk board. [[Special:Contributions/141.101.70.67|141.101.70.67]] 09:27, 25 August 2016 (UTC)<br />
<br />
Transcript generated by the BOT was murdering me, had to change it. Proposing miss Lenhart is party 1. [[User:EppOch|EppOch]] ([[User talk:EppOch|talk]]) 04:45, 24 August 2016 (UTC)<br />
:: I support that. [[Special:Contributions/141.101.91.223|141.101.91.223]] 06:13, 24 August 2016 (UTC)<br />
:: Me to, but I am on mobile, so editing is a pain [[Special:Contributions/162.158.86.71|162.158.86.71]] 06:51, 24 August 2016 (UTC)<br />
:: Done [[User:Elektrizikekswerk|Elektrizikekswerk]] ([[User talk:Elektrizikekswerk|talk]]) 08:26, 24 August 2016 (UTC)<br />
:::Note that the BOT doesn't create any text - [http://www.explainxkcd.com/wiki/index.php?title=1724:_Proofs&oldid=125654 see here]. The transcript was made by several people. Agree completely that this is Miss Lenhart, but even if it was not "[http://www.explainxkcd.com/wiki/index.php?title=1724:_Proofs&direction=next&oldid=125660 party 1 and party 2]" is not the way to describe a woman with long blonde hair and Cueball ;-) There is at the moment [[explain_xkcd:Community_portal/Proposals#New_character_category_for_blonde_woman_news_reporter_.28from_1699.29|a discussion]] what to call other women looking like this (i.e. those that are not clearly Miss Lenhart, [[Mrs. Roberts]] or her daughter [[Elaine Roberts]]). Chip in there if you have any opinions on that regard... --[[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 11:01, 24 August 2016 (UTC)<br />
<br />
<br />
Irrationality proof isn't really a proof by contradiction (it doesn't use double negation elimination). You're showing (exists a,b. ...) -> False by assuming (exists a, b. ...) and showing False, which is implication introduction --[[Special:Contributions/162.158.85.105|162.158.85.105]] 07:33, 24 August 2016 (UTC)<br />
<br />
I'm thinking she's doing one of those proof that write down a formula or function out of nowhere, and proceeds to proof everything with it. [[Special:Contributions/108.162.222.125|108.162.222.125]] 08:43, 24 August 2016 (UTC)<br />
<br />
This comic reminds me of "divination" rituals, where a magical spirit is summoned to write out an answer. Usually not something as complex as here, but hey, XKCD! --[[User:Henke37|Henke37]] ([[User talk:Henke37|talk]]) 10:04, 24 August 2016 (UTC)<br />
<br />
Man, Reductio ad absurdum never made any logic. If we could assume any thing, why use logic?<br />
Oh wait, it has already been covered in XKCD {{unsigned ip|162.158.49.12}}<br />
<br />
"Dark magic" proofs are centered around properties of functions, and abstract concepts, rather than manipulating the functions themselves?? [[Special:Contributions/108.162.246.113|108.162.246.113]] 11:26, 24 August 2016 (UTC)<br />
<br />
My assumptions is that the "Dark Magic" being referred to here is more "A technique that works, though nobody really understands why." [see http://catb.org/jargon/html/B/black-magic.html] In this case, the teacher is setting up a proof in an manner which will lead to the desired goal, but to the student it is exceedingly unobvious as to why one would do it this way, other than "it works" [[Special:Contributions/108.162.219.52|108.162.219.52]] 15:30, 24 August 2016 (UTC)<br />
<br />
I was thinking that a "dark magic proof" referred to those ridiculous "party trick" proofs like 'proving' that 1 = 0 via some confusing train of logic, and mathematical sleight of hand. {{unsigned ip|108.162.237.213}}<br />
<br />
Maybe he meant "dark patterns"? {{unsigned ip|162.158.126.139}}<br />
<br />
It seems pretty obvious to me that by "weird, dark magic proofs", the student is talking about proofs that drag in far-flung reaches of mathematics so distant that they no longer appear to be mathematics, especially ones that involve meta-reasoning. Gödel's proof of the incompleteness of Peano arithmetic is the archetypical example, but others include Lob's theorem and any proof by contradiction involving the halting problem. Ms Lenhart's proof starts out by setting up a proof-by-contradiction, already a warning sign, and she then escalates it at the end by implying that this proof will somehow involve the actual physics of where the solution can and cannot be written. [[Special:Contributions/108.162.241.123|108.162.241.123]] 17:27, 24 August 2016 (UTC)<br />
<br />
:: Agreed, although I think starting out with a proof by contradiction setup is by itself not that much of a warning sign. However it heads straight into meta-space by making the assumption of the existence of a function that produces a solution of something. [[User:Zmatt|Zmatt]] ([[User talk:Zmatt|talk]]) 18:52, 24 August 2016 (UTC)<br />
<br />
:: The fact that the proof mentions the actual blackboard on which it is written is of course problematic in numerous ways, as is predicating on whether something "will eventually" happen. This is well outside the scope of the [https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory usual mathematical foundations]. Since careless use of meta-recursion is a [https://en.wikipedia.org/wiki/Curry's_paradox trap], such a proof would have to very very carefully consider foundational issues and cannot handwave over them. [[User:Zmatt|Zmatt]] ([[User talk:Zmatt|talk]]) 19:13, 24 August 2016 (UTC)<br />
<br />
----<br />
"''In the title text the decision of whether to take the axiom of choice is made by a deterministic process. The axiom of determinacy is incompatible with the axiom of choice...''" The axiom of determinacy is not really relevant to deterministic processes - it is about (certain types of two-players-) games and says that any such game is determined (that is, some player has a winning strategy). So this axiom is not relevant to the title text --[[Special:Contributions/162.158.83.66|162.158.83.66]] 17:39, 24 August 2016 (UTC)<br />
:I agree. I read the title text in almost exactly the opposite way - that the proof relies on the existence of a deterministic process for selecting objects, and therefore the invocation of the axiom of choice as a part of the process is superfluous (but not a contradiction). Anyhow, the axiom of determinacy isn't ever mentioned, so it probably shouldn't be shoehorned in here. [[Special:Contributions/162.158.74.53|162.158.74.53]] 20:36, 24 August 2016 (UTC)<br />
<br />
I feel like it is a stretch to assert Lenhart is setting up a proof by contradiction. It sounded to me more like an prior knowledge proof (not sure it's technical name). For example, "calculate the space between two concentric circles of differing diameter when the longest straight line you can draw is length d." If you assume there is a function F(r1, r2) which has been previously proven to calculate this space, then it is easy to show that the space is in fact .5*pi*(.5*d)^2 (as you have a degenerative case where r1=0, and you have an ordinary circle). I also think this type of proof is more "dark magic"-feeling than a simple proof by contradiction. {{unsigned ip|108.162.216.87}}<br />
<br />
:While technically the same pattern, I would assume something more like NP-complete proofs: Assume we have function F which solves this problem in polynomial time ... then we can solve that problem in polynomial time as well. Just, instead of "polynomial time", the existence of function is the question here, so it will likely be something around {{w|Recursively enumerable set|recursively enumerable}}/{{w|countable set|countable}} stuff. -- [[User:Hkmaly|Hkmaly]] ([[User talk:Hkmaly|talk]]) 13:02, 25 August 2016 (UTC)<br />
<br />
I don't like how this explanation uses the word "standard". Non-standard mathematical objects are subjects of non-standard analysis, not metamathematics. --[[Special:Contributions/108.162.218.185|108.162.218.185]] 02:25, 27 August 2016 (UTC)<br />
<br />
Simplest explanation would be Cueball suspect Ms Lenhart already made-up an answer for a made-up function (hence ''magic''), which is confirmed at the last panel. Laymen like myself wouldn't grasp any of those methamathematical stuff explanation. :) [[Special:Contributions/162.158.167.35|162.158.167.35]] 07:20, 29 August 2016 (UTC)</div>162.158.167.35