0982: "Set Theory"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
Steve the Pocket
Posts: 705
Joined: Mon Apr 23, 2007 4:02 am UTC
Location: Going downtuuu in a Luleelurah!

0982: "Set Theory"

Postby Steve the Pocket » Fri Nov 25, 2011 7:18 am UTC

Image

Rollover text: Proof of Zermelo's well-ordering theorem given the Axiom of Choice: 1: Take S to be any set. 2: When I reach step three, if S hasn't managed to find a well-ordering relation for itself, I'll feed it into this wood chipper. 3: Hey, look, S is well-ordered.

Yeah... the "violent persuasion approach" that works so well for things like getting a stubborn engine to run isn't especially useful in the more abstract sciences.

Actually, the alt-text reminds me of another comic we had hanging up in our math classroom back in like eighth grade, where someone is doing some calculation on a whiteboard and between two steps he writes "Then a miracle occurs..." with arrows showing the progression to and from that step. And the professor next to him says something like "You need to be more explicit here in step three."

(This one must have been just late enough for people to stop refreshing. Or are you all too busy camping out in front of stores for Black Friday? Heh.)
cephalopod9 wrote:Only on Xkcd can you start a topic involving Hitler and people spend the better part of half a dozen pages arguing about the quality of Operating Systems.

Baige.

ijuin
Posts: 1111
Joined: Fri Jan 09, 2009 6:02 pm UTC

Re: 0982: "Set Theory"

Postby ijuin » Fri Nov 25, 2011 7:23 am UTC

Yes, violent persuasion is quite ineffective when used upon entities that are not actually capable of feeling fear.

carolineee
Posts: 17
Joined: Mon Nov 21, 2011 6:26 pm UTC

Re: 0982: "Set Theory"

Postby carolineee » Fri Nov 25, 2011 7:27 am UTC

Hadn't heard of this method before although there are numerous "proof by ..." jokes among math students.
I found this site for a list of them: http://www.onlinemathlearning.com/math-jokes-mathematical-proofs.html
But they're missing the most widely used one, which is proof by coffee break: "We'll prove this after the break." (5 minutes pass) "As shown before the break ..."
It works even better if you say "We'll prove this next time." (2 days) "As shown in the last lecture ..."

YpsilonOmega
Posts: 9
Joined: Fri Nov 25, 2011 7:29 am UTC
Location: Tartu, Estonia
Contact:

Re: 0982: "Set Theory"

Postby YpsilonOmega » Fri Nov 25, 2011 7:32 am UTC

Actually the axiom of choice holds only for nonempty sets... But if she's persuasive enough, her students might even pick an element from the empty set.

Bringer
Posts: 10
Joined: Mon Jun 25, 2007 5:38 pm UTC

Re: 0982: "Set Theory"

Postby Bringer » Fri Nov 25, 2011 7:40 am UTC

This one made me read up on the various theories and decide, after the fact, that the comic was funny.

One thing confuses me though. The Banach-Tarski paradox supposedly counters the Axiom of Choice. From my (very limited!) understanding of Maths:

1. The Axiom of Choice (and therefore the well-ordering theorem) states that there is a least element, even in continuous (i.e. infinite) sets.
2. The Banach-Tarski paradox shows that an infinite number of infinitely small parts (using geometric sets) implies that you can "turn a pea into the sun", given that there is a least element.

Surely this means that the Axiom of Choice only applies to a subset of the set of all non-empty sets that have a valid least element (e.g. a closed continues set between 0 and 1 has a minimum element 0 whereas the open set of that range does not). Is there a mathematically useful case where a continuous non-empty set benefits from the well-ordering theorem? Or do they only benefit from the Axiom of Choice?

Of course, the correct answer to this in the vain of the comic is: "Unless you want to have your neck snapped by my little friend here gestures towards tall man to the left there is a mathematically useful case for a continuous non-empty set and the well-ordering theorem."
SSBM - Best Yoshi player in Australia

User avatar
Djehutynakht
Posts: 1546
Joined: Thu Feb 10, 2011 1:37 am UTC

Re: 0982: "Set Theory"

Postby Djehutynakht » Fri Nov 25, 2011 7:47 am UTC

My teacher tends to do this for her printer.


I guess now the only explanation for CERN not finding the Higgs Boson is that they're too soft on it. A few more threats and it may emerge from hiding.

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: 0982: "Set Theory"

Postby Proginoskes » Fri Nov 25, 2011 7:59 am UTC

carolineee wrote:Hadn't heard of this method before although there are numerous "proof by ..." jokes among math students.
I found this site for a list of them: http://www.onlinemathlearning.com/math-jokes-mathematical-proofs.html
But they're missing the most widely used one, which is proof by coffee break: "We'll prove this after the break." (5 minutes pass) "As shown before the break ..."
It works even better if you say "We'll prove this next time." (2 days) "As shown in the last lecture ..."


I once heard about a seminar at a university which lasted 2 years (4 semesters). At the beginning of the first meeting in th e second fall semester, the presenter picked up a piece of chalk and said, "And now, by Theorem X ..."

No review.

Actually, I have to ask: Why does it say "x is an element of the empty set" in the comic?

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: 0982: "Set Theory"

Postby Proginoskes » Fri Nov 25, 2011 8:01 am UTC

YpsilonOmega wrote:Actually the axiom of choice holds only for nonempty sets... But if she's persuasive enough, her students might even pick an element from the empty set.


It's easy to show that the axiom of choice holds for nonempty finite sets, so all you have to do is to deny the axiom of infinity. ("Infinite sets exist.") Viola!

mjh2539
Posts: 2
Joined: Wed Sep 28, 2011 4:24 am UTC

Re: 0982: "Set Theory"

Postby mjh2539 » Fri Nov 25, 2011 8:33 am UTC

Given ZF with the axiom of choice, and a sock-drawer that has uncountably many identical white socks, there is a well-ordering of the white socks in the sock-drawer.

Layra
Posts: 1
Joined: Fri Nov 25, 2011 8:25 am UTC

Re: 0982: "Set Theory"

Postby Layra » Fri Nov 25, 2011 8:44 am UTC

Bringer wrote:This one made me read up on the various theories and decide, after the fact, that the comic was funny.

One thing confuses me though. The Banach-Tarski paradox supposedly counters the Axiom of Choice. From my (very limited!) understanding of Maths:

1. The Axiom of Choice (and therefore the well-ordering theorem) states that there is a least element, even in continuous (i.e. infinite) sets.
2. The Banach-Tarski paradox shows that an infinite number of infinitely small parts (using geometric sets) implies that you can "turn a pea into the sun", given that there is a least element.

Surely this means that the Axiom of Choice only applies to a subset of the set of all non-empty sets that have a valid least element (e.g. a closed continues set between 0 and 1 has a minimum element 0 whereas the open set of that range does not). Is there a mathematically useful case where a continuous non-empty set benefits from the well-ordering theorem? Or do they only benefit from the Axiom of Choice?


The Banach-Tarski paradox tells us one of two things. Either it tells us that something's wrong with the Axiom of Choice or it tells us that geometric size isn't as nice as we might want it to be.
If there's something wrong with the Axiom of Choice, then we'd have to weaken it somehow, but there isn't a nice way to do so. Certainly you can say "restrict to non-empty sets that have a valid least element", but then the Axiom of Choice doesn't tell you anything new, since if you know that the axiom applies to a given set then you already know that the set has a least element.
We do need the Axiom of Choice in the uncountable case for things like Tychonoff's theorem, which underlies a lot of modern mathematics, from algebra to analysis to geometry and even to combinatorics and discrete mathematics. A very large and happy chunk of mathematics dies without the full-powered Axiom of Choice. And since the Axiom of Choice is equivalent to the Well-Ordering Principle under the Zermelo-Fraenkel axioms, well, we kind of need the Well-Ordering Principle too.
Instead we just accept that there are sets that we can't attach a good notion of "geometric size" to. It wouldn't be the first time we've had to accept apparent abominations in order to progress. We can, however, say quite a bit about which sets we can attach a notion of size to, so it's easier to weaken the notion of geometric size than it is to weaken the Axiom of Choice.

Zoid
Posts: 1
Joined: Fri Nov 25, 2011 8:35 am UTC

Re: 0982: "Set Theory"

Postby Zoid » Fri Nov 25, 2011 8:48 am UTC

Bringer wrote:This one made me read up on the various theories and decide, after the fact, that the comic was funny.

One thing confuses me though. The Banach-Tarski paradox supposedly counters the Axiom of Choice. From my (very limited!) understanding of Maths:

1. The Axiom of Choice (and therefore the well-ordering theorem) states that there is a least element, even in continuous (i.e. infinite) sets.
2. The Banach-Tarski paradox shows that an infinite number of infinitely small parts (using geometric sets) implies that you can "turn a pea into the sun", given that there is a least element.

Surely this means that the Axiom of Choice only applies to a subset of the set of all non-empty sets that have a valid least element (e.g. a closed continues set between 0 and 1 has a minimum element 0 whereas the open set of that range does not). Is there a mathematically useful case where a continuous non-empty set benefits from the well-ordering theorem? Or do they only benefit from the Axiom of Choice?


The Banach-Tarski Paradox doesn't contradict the Axiom of Choice. It is counter-intuitive, but it doesn't entail a logical contradiction like Russell's Paradox does.

User avatar
Linux0s
Posts: 247
Joined: Sat Dec 29, 2007 7:34 pm UTC

Re: 0982: "Set Theory"

Postby Linux0s » Fri Nov 25, 2011 9:17 am UTC

Definitely not enough "shock and awe" in mathematics.
If the male mind truly were a machine it would consist of a shaft and a bushing.

User avatar
schrodingersduck
Posts: 130
Joined: Mon Aug 13, 2007 2:20 pm UTC
Location: People's Democratic Republic of Leodensia
Contact:

Re: 0982: "Set Theory"

Postby schrodingersduck » Fri Nov 25, 2011 9:46 am UTC

This formulation of the axiom of choice certainly would make Banarch-Tarski easier to understand.

1. Take a sphere
2. Shoot it to pieces
3. Rearrange the pieces and the shrapnel
4. Look, two spheres!

lalop
Posts: 210
Joined: Mon May 23, 2011 5:29 pm UTC

Re: 0982: "Set Theory"

Postby lalop » Fri Nov 25, 2011 11:23 am UTC

Proginoskes wrote:It's easy to show that the axiom of choice holds for nonempty finite sets, so all you have to do is to deny the axiom of infinity. ("Infinite sets exist.") Viola!


I think you mean for finite collections. If you deny the axiom of infinity, however, would you be able to prove it happens for any natural number n, rather than just for specific ones? Remember that you wouldn't be able to say "forall n in N ..."


schrodingersduck wrote:This formulation of the axiom of choice certainly would make Banarch-Tarski easier to understand.

1. Take a sphere
2. Shoot it to pieces
3. Rearrange the pieces and the shrapnel
4. Look, two spheres!


That's not actually Banach-Tarski; that only shows there's a bijection between one sphere and two spheres, a relatively easy exercise.

DoMakeSayThink
Posts: 10
Joined: Mon Aug 16, 2010 9:46 pm UTC

Re: 0982: "Set Theory"

Postby DoMakeSayThink » Fri Nov 25, 2011 11:39 am UTC

lalop wrote:
schrodingersduck wrote:This formulation of the axiom of choice certainly would make Banarch-Tarski easier to understand.

1. Take a sphere
2. Shoot it to pieces
3. Rearrange the pieces and the shrapnel
4. Look, two spheres!


That's not actually Banach-Tarski; that only shows there's a bijection between one sphere and two spheres, a relatively easy exercise.


Well, assuming you only have a finite number of bullets...

User avatar
rhomboidal
Posts: 797
Joined: Wed Jun 15, 2011 5:25 pm UTC
Contact:

Re: 0982: "Set Theory"

Postby rhomboidal » Fri Nov 25, 2011 11:42 am UTC

Wow, I never knew Zermelo was from Fargo.

User avatar
NoodleIncident
Posts: 88
Joined: Thu Jul 23, 2009 1:07 am UTC

Re: 0982: "Set Theory"

Postby NoodleIncident » Fri Nov 25, 2011 1:06 pm UTC

mjh2539 wrote:Given ZF with the axiom of choice, and a sock-drawer that has uncountably many identical white socks, there is a well-ordering of the white socks in the sock-drawer.


If the socks were identical, then they wouldn't be in a set. Elements of a set are by definition unique within the set. Try harder! :D
Zagibu wrote:Don't ask how many times I've accidentially spawned an alligator completely covered in adamantine with a battle axe strapped to its tail.

User avatar
radtea
Posts: 137
Joined: Mon Mar 03, 2008 8:57 pm UTC
Contact:

Re: 0982: "Set Theory"

Postby radtea » Fri Nov 25, 2011 1:18 pm UTC

THIS is what people opposed to science and mathematics have been missing! Intimidating scientists has been an abject failure. If only someone had told them they should be intimidating reality!

Damnit Randall, you've let the cat out of the bag now!
Coming on Midsummer's Day to a Web Browser Near You: http://www.songsofalbion.com

User avatar
radtea
Posts: 137
Joined: Mon Mar 03, 2008 8:57 pm UTC
Contact:

Re: 0982: "Set Theory"

Postby radtea » Fri Nov 25, 2011 2:36 pm UTC

Bringer wrote:2. The Banach-Tarski paradox shows that an infinite number of infinitely small parts (using geometric sets) implies that you can "turn a pea into the sun", given that there is a least element."


There is no paradox here because neither a pea nor the sun remotely resemble the objects the Banach-Tarski are talking about.

For comparison, consider the Radcliffe-Drunken "paradox": I can prove that 1 litre of alcohol mixed with 1 litre of water is equal to exactly 2 litres of liquid, using the well-known mathematical axiom 1+1 = 2. Yet in fact 1 litre of water plus 1 litre of alcohol only adds up to 1.92 litres of fluid! Fortunately, the confusion this paradox entails can be assuaged by imbibing the results of the experiment (in fairness, you'll still be confused... you'll just have a legitimate reason for it.)

If you don't see my toy-model example as a paradox, you have no business seeing the Banach-Tarski argument as a paradox. It's simply an example of people drawing inappropriate conclusions about real-world objects to which a particular mathematical description does not apply.
Coming on Midsummer's Day to a Web Browser Near You: http://www.songsofalbion.com

Elbirn
Posts: 5
Joined: Mon Aug 03, 2009 11:00 pm UTC

Re: 0982: "Set Theory"

Postby Elbirn » Fri Nov 25, 2011 3:11 pm UTC

^ Radtea, about that paradox..I found it interesting. So like any sane person I tried to look it up, but all I've managed to find are links about Daniel Radcliffe being a drunk. :P
Can you either point me to some resources about it / explain why 1+1 = 1.92? Is it something to do with the weight of the liquids or some other such nonsense? (I'm not very good with sciences/maff..I'm just a poor wannabe who lieks xkcd) :mrgreen:

alreadytaken4536
Posts: 34
Joined: Thu Jun 10, 2010 10:56 pm UTC

Re: 0982: "Set Theory"

Postby alreadytaken4536 » Fri Nov 25, 2011 3:24 pm UTC

Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin.


... isn't that obvious? Why is this such a useful and pivotal theorem in mathematics?

capefeather
Posts: 98
Joined: Sun Dec 14, 2008 4:23 am UTC

Re: 0982: "Set Theory"

Postby capefeather » Fri Nov 25, 2011 3:29 pm UTC

Every time you invoke a Vitali set, a real number dies.

When m({dead real numbers}) = 0, it is a tragedy. When m({dead real numbers}) > 0, it is a statistic.

alreadytaken4536 wrote:
Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin.


... isn't that obvious? Why is this such a useful and pivotal theorem in mathematics?


The thing is, it's not a theorem. The axiom of choice is one of the fundamental rules of the modern framework of mathematics that are considered given (or "obvious", if you'd like). In mathematics, you can't invoke a statement as true unless it is one of these "axioms" or it follows from them. It turns out that the axiom of choice, in its most general sense, doesn't follow from any of the other axioms.

The real power of the axiom of choice is that it allows us to pick objects out from an infinite number of bins. In the absence of this axiom, you'd need a rule of some sort to do this. In an infinite pile of pairs of socks, it's possible to pick out all of the left socks without invoking AC. However, in an infinite pile of left socks, the ability to do something similar is not so clear, and in fact, this requires you to invoke AC.
Last edited by capefeather on Fri Nov 25, 2011 3:50 pm UTC, edited 2 times in total.

User avatar
Tyrannosaur
Posts: 107
Joined: Thu Sep 02, 2010 5:39 am UTC

Re: 0982: "Set Theory"

Postby Tyrannosaur » Fri Nov 25, 2011 3:40 pm UTC

Elbirn wrote:^ Radtea, about that paradox..I found it interesting. So like any sane person I tried to look it up, but all I've managed to find are links about Daniel Radcliffe being a drunk. :P
Can you either point me to some resources about it / explain why 1+1 = 1.92? Is it something to do with the weight of the liquids or some other such nonsense? (I'm not very good with sciences/maff..I'm just a poor wannabe who lieks xkcd) :mrgreen:


It's because alcohol is actually water soluble. It gets dissolved into the water. This makes a bigger difference when you have powdered alcohol, but it is the same reason why when you mix (for example) 50 mL of Water and 5 mL of salt, you get less than 55 mL of saltwater.

Sorry I can't find a relevant wikipedia article at the moment.

The apparent confusion about 1 + 1 = 1.92 is that mixing water and alcohol is not the same as adding two of the same thing together, it's more like mixing a quantity of larger rocks with sand; a simple sum of respective volumes is not complicated enough to accurately model what happens.
djessop wrote:The t-shirt should read "There are 11 types of people in the world, those who understand binary, those who don't and those who insist the number above is pronounced as eleven no matter what base you're in".

User avatar
addams
Posts: 10269
Joined: Sun Sep 12, 2010 4:44 am UTC
Location: Oregon Coast: 97444

Re: 0982: "Set Theory"

Postby addams » Fri Nov 25, 2011 3:51 pm UTC

Elbirn wrote:^ Radtea, about that paradox..I found it interesting. So like any sane person I tried to look it up, but all I've managed to find are links about Daniel Radcliffe being a drunk. :P
Can you either point me to some resources about it / explain why 1+1 = 1.92? Is it something to do with the weight of the liquids or some other such nonsense? (I'm not very good with sciences/maff..I'm just a poor wannabe who lieks xkcd) :mrgreen:


Really? Oh. I don't know much. But, it is a chemistry, thing.

The hydrogens get all cozy with one another and poof. There is a miracle. See?

Yes. There are personalities on this forum that can lead you down the Rabbit Hole. It can be fun. I do know that my first year of Chemistry I was walking in Faith.
http://en.wikipedia.org/wiki/Chemistry

The instructor said do the math. I did the math. None of it made intuitive sense to me. The little star nosed biological mole was all that got me through some days.
http://en.wikipedia.org/wiki/Star-nosed_mole

The Chemists kept a taxidermied specimen in a case for biology students.
The details can be difficult. I was told that, "The devil is in the details." Chemistry turns into ALL details. Then, it smells bad or blows up; Or; Both.
Life is, just, an exchange of electrons; It is up to us to give it meaning.

We are all in The Gutter.
Some of us see The Gutter.
Some of us see The Stars.
by mr. Oscar Wilde.

Those that want to Know; Know.
Those that do not Know; Don't tell them.
They do terrible things to people that Tell Them.

Stig Hemmer
Posts: 30
Joined: Wed Feb 28, 2007 4:46 pm UTC
Location: Trondheim, Norway

Re: 0982: "Set Theory"

Postby Stig Hemmer » Fri Nov 25, 2011 6:52 pm UTC

I choose not to accept the Axiom of Choice.

It is a good thing I don't practice math for a living or I would be deprived of an important tool.
This is not true.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0982: "Set Theory"

Postby Yakk » Fri Nov 25, 2011 7:17 pm UTC

The Well-ordering theorem is obviously false, the infinite cross product of nonempty sets is obviously nonempty, and who the hell knows about Zorn's lemma?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

chapel
Posts: 121
Joined: Mon Dec 01, 2008 8:52 am UTC

Re: 0982: "Set Theory"

Postby chapel » Fri Nov 25, 2011 9:05 pm UTC

Proginoskes wrote:Actually, I have to ask: Why does it say "x is an element of the empty set" in the comic?


Because that particular element was executed as an example to the others.

[imath]x \in S[/imath] thus [imath]x \in \emptyset[/imath]

User avatar
jc
Posts: 354
Joined: Fri May 04, 2007 5:48 pm UTC
Location: Waltham, Massachusetts, USA, Earth, Solar System, Milky Way Galaxy
Contact:

Re: 0982: "Set Theory"

Postby jc » Fri Nov 25, 2011 10:24 pm UTC

alreadytaken4536 wrote:
Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin.

... isn't that obvious? Why is this such a useful and pivotal theorem in mathematics?

Um, it's not a theorem; it's an axiom. It can't be derived as a theorem from the axioms of any of the popular formulations of the basic number theory or set theory. But it's needed to proved a lot of the theorems about numbers and sets. As someone else remarked, without the Axiom of Choice, you lose all theorems whose proofs include anything of the form "for X in set S ...". The Axiom of Choice gives you permission to use this line of reasoning.

This situation isn't unusual in mathematics. Logicians like to point out that in most mathematical proofs, you need a number of axioms in addition to the axioms that are officially listed by the authors. You need the axioms of basic inferential logic. Without them, you can't do any proofs at all, because your axioms don't give you permission to reason. The field of logic started off basically as a way of formalizing the (usually unstated) logical axioms, so we can verify that someone's proof uses valid reasoning.

It is sometimes observed that, for a proof to be valid, the author really should state all of the axioms used, including the logical axioms. However, very few mathematical papers ever bother with this. They often don't list any axioms at all; they just use a few key terms that tell mathematicians what axiom set(s) they are using. Thus, "natural numbers", "integers", "real numbers" and "complex numbers" specify four different sets of axioms, each one including the previous term's set of axioms. Other terms such as "Abelian group" or "Hilbert space" or "Cartesian N-space" tip off the reader that other axiom sets are in use. They usually casually assume the same well-known set of logical axioms, too, except when they want to point out that a specific logical axiom (e.g. the Axiom of Choice) is or is not being used.

Usually, this sort of casualness about axioms works pretty well. There have been a few cases where it has led to misunderstanding, though, with theorems being used in proofs that didn't assume the same axiom set. There have been a few "Oops!" retractions when someone discovers this sort of problem, but not many.

itaibn
Posts: 142
Joined: Mon Dec 29, 2008 7:06 pm UTC

Re: 0982: "Set Theory"

Postby itaibn » Fri Nov 25, 2011 11:27 pm UTC

<flamewar>
The problem is that you're implicitly assuming the axiom of excluded middle...
I NEVER use all-caps.

User avatar
Pfhorrest
Posts: 5448
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 0982: "Set Theory"

Postby Pfhorrest » Fri Nov 25, 2011 11:32 pm UTC

jc wrote:It is sometimes observed that, for a proof to be valid, the author really should state all of the axioms used, including the logical axioms.


Aren't there problems with infinite recursion if you try to do this, though?

Say we have a simple argument:

P
.: Q

Well, how do we know whether that is valid or not? We'd need to know in advance that propositions of the form of P entail propositions of the form of Q. Ok, so lets include one of those:

P -> Q
P
.: Q

Seems obviously valid now. But wait? How do we know we can get from "P -> Q" and "P" to Q? Who says that's a valid inference? So we need to list that as well:

((P -> Q) ^ P) -> Q
P -> Q
P
.: Q

Ok that's better... but wait again! How do we know we get get from "((P -> Q) ^ P) -> Q" and "P -> Q" and "P" to Q? We need to list that as a valid inference too:

((((P -> Q) ^ P) -> Q) ^ (P -> Q) ^ P) -> Q
((P -> Q) ^ P) -> Q
P -> Q
P
.: Q

And so on. It seems that you cannot demand the inclusion of logical necessities as premises as a condition of the validity of an argument without leading to an infinite regress.

Addendum: I am annoyed that apparently mathematical HTML entities get filtered out somehow here. Why bother with all this laggy jsMath TeX bullshit when I can just write &rarr; and &and; and &there4; and let the browser substitute the appropriate unicode without all this overhead?
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

rmsgrey
Posts: 3633
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 0982: "Set Theory"

Postby rmsgrey » Fri Nov 25, 2011 11:39 pm UTC

itaibn wrote:<flamewar>
The problem is that you're implicitly assuming the axiom of excluded middle...

I'm not not assuming the axiom of excluded middle...

User avatar
Pfhorrest
Posts: 5448
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 0982: "Set Theory"

Postby Pfhorrest » Fri Nov 25, 2011 11:45 pm UTC

rmsgrey wrote:
itaibn wrote:<flamewar>
The problem is that you're implicitly assuming the axiom of excluded middle...

I'm not not assuming the axiom of excluded middle...

Similarly, I both affirm and deny the principle of non-contradiction.
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

TheAbstractor
Posts: 33
Joined: Wed Apr 30, 2008 7:32 pm UTC

Re: 0982: "Set Theory"

Postby TheAbstractor » Sat Nov 26, 2011 2:07 am UTC

Much like how Vin Diesel once solved Fermat's Last Theorem by pistol-whipping a mathematician.

Turing Machine
Posts: 98
Joined: Fri Feb 19, 2010 5:48 am UTC

Re: 0982: "Set Theory"

Postby Turing Machine » Sat Nov 26, 2011 6:26 am UTC

itaibn wrote:<flamewar>
The problem is that you're implicitly assuming the axiom of excluded middle...


Yes, the logic underlying mathematical proofs is typically classical.

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: 0982: "Set Theory"

Postby Proginoskes » Sat Nov 26, 2011 7:45 am UTC

lalop wrote:
Proginoskes wrote:It's easy to show that the axiom of choice holds for nonempty finite sets, so all you have to do is to deny the axiom of infinity. ("Infinite sets exist.") Viola!


I think you mean for finite collections.


Probably. Hey, I'm a combinatorialist; all the important sets are finite.

If you deny the axiom of infinity, however, would you be able to prove it happens for any natural number n, rather than just for specific ones? Remember that you wouldn't be able to say "forall n in N ..."


Actually, you can; you just can't group together all the integers and call them a set.

It's just like there is no set consisting of all sets. However, you can say: "Let A be a set."

User avatar
addams
Posts: 10269
Joined: Sun Sep 12, 2010 4:44 am UTC
Location: Oregon Coast: 97444

Re: 0982: "Set Theory"

Postby addams » Sat Nov 26, 2011 3:50 pm UTC

carolineee wrote:Hadn't heard of this method before although there are numerous "proof by ..." jokes among math students.
I found this site for a list of them: http://www.onlinemathlearning.com/math- ... roofs.html
But they're missing the most widely used one, which is proof by coffee break: "We'll prove this after the break." (5 minutes pass) "As shown before the break ..."
It works even better if you say "We'll prove this next time." (2 days) "As shown in the last lecture ..."


http://www.onlinemathlearning.com/math- ... roofs.html

Very funny. Very funny, indeed. That link has amused me for minutes on end.
Thank you.

We see Proof of this one, every day.

"We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the Internet, we know this is not true." -- Professor Robert Silensky





chapel » Fri Nov 25, 2011 1:05 pm UTC

Proginoskes wrote:Actually, I have to ask: Why does it say "x is an element of the empty set" in the comic?

Because that particular element was executed as an example to the others.

So, funny. Humans are horrible. Yet; It is amusing.
Life is, just, an exchange of electrons; It is up to us to give it meaning.

We are all in The Gutter.
Some of us see The Gutter.
Some of us see The Stars.
by mr. Oscar Wilde.

Those that want to Know; Know.
Those that do not Know; Don't tell them.
They do terrible things to people that Tell Them.

superfli
Posts: 1
Joined: Sat Nov 26, 2011 9:08 pm UTC

Re: 0982: "Set Theory"

Postby superfli » Sat Nov 26, 2011 9:14 pm UTC

Let F be the set of all sets which fear being fed into wood chippers.

The postulated proof only applies where S is a member of F.

fffudge
Posts: 13
Joined: Wed Sep 30, 2009 7:16 am UTC

Re: 0982: "Set Theory"

Postby fffudge » Sun Nov 27, 2011 4:03 am UTC

capefeather wrote:In an infinite pile of pairs of socks, it's possible to pick out all of the left socks without invoking AC.


Really? I have a finite pile of pairs of socks and I can't even manage that. :P

User avatar
bmonk
Posts: 662
Joined: Thu Feb 18, 2010 10:14 pm UTC
Location: Schitzoed in the OTT between the 2100s and the late 900s. Hoping for singularity.

Re: 0982: "Set Theory"

Postby bmonk » Sun Nov 27, 2011 4:56 am UTC

alreadytaken4536 wrote:
Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin.


... isn't that obvious? Why is this such a useful and pivotal theorem in mathematics?


It's not so easy when you have an infinite series of bins/sets.

carolineee wrote:Hadn't heard of this method before although there are numerous "proof by ..." jokes among math students.
I found this site for a list of them: http://www.onlinemathlearning.com/math- ... roofs.html
But they're missing the most widely used one, which is proof by coffee break: "We'll prove this after the break." (5 minutes pass) "As shown before the break ..."
It works even better if you say "We'll prove this next time." (2 days) "As shown in the last lecture ..."


And then there's the series of (isomorphic) jokes about the math prof who says, ". . . now, from this it is obvious that . . .

"Is it obvious?"

[several minutes pass, or possibly several hours]

"YES! It IS obvious!"

And he continues with the proof.
Having become a Wizard on n.p. 2183, the Yellow Piggy retroactively appointed his honorable self a Temporal Wizardly Piggy on n.p.1488, not to be effective until n.p. 2183, thereby avoiding a partial temporal paradox. Since he couldn't afford two philosophical PhDs to rule on the title.

User avatar
tomandlu
Posts: 1111
Joined: Fri Sep 21, 2007 10:22 am UTC
Location: London, UK
Contact:

Re: 0982: "Set Theory"

Postby tomandlu » Sun Nov 27, 2011 7:19 am UTC

Could someone explain AC to the maths-challenged?

It seems to be saying "if you've got a collection of things, it's self-evident that you can select and remove one of them."

Why is this useful or interesting? What goes wrong without this axiom? (I'm not dissing it - I just don't understand).
How can I think my way out of the problem when the problem is the way I think?


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: hetas, LHC, Reka and 42 guests