View previous topic | View next topic

proof

Page 1 of 2
Goto page 1, 2  Next

Zziggy
1135655.  Tue Jun 02, 2015 5:28 am Reply with quote

suze wrote:
Husband is muttering something about the "axiom of choice". I'm not a mathmo, so I'm hoping that Zziggy or someone can come by and help me out if I screw this up, but here goes ...

The axiom of choice states that if we have any number of boxes, all of which contain at least one item, then it is possible to select precisely one item from every box.

If the number of boxes is finite then that statement is obviously true, and there is a simple mathematical proof using the method of induction. (Oh good. A term from hard sums which I understand!)

But it is apparently not obvious that it is true if the number of boxes is infinite, and there is no proof of the axiom of choice as regards an infinite number of boxes.

However, there is a proof that the axiom of choice cannot be proved false. It's something to do with Gödel, but I wouldn't understand the math even if husband tried to explain it to me and so I won't make him do it.

That doesn't make the axiom of choice true for an infinite number of boxes, but the proof that it can't be proved false is good enough for most mathmos, and one is in general "allowed" to assume it to be true.

Or something like that ...

Formal logic is not my forté* but I'll give it a shot.

Conventional mathematics is based on ZFC. This is the Zermelo-Fraenkel axioms (ZF) plus the Axiom of Choice (AC) (which is as you stated it). Other axiom systems exist - for instance, Von Neumann–Bernays–Gödel set theory is a conservative extension which only requires finitely many axioms rather than the infinite number of axioms required by ZFC (the axiom of replacement is technically an infinite number of axioms I believe).

But I digress. ZFC uses AC as an axiom, and most mathematicians accept that it is true, partly because a lot of very nice lemmas and theorems rely on it. There are also important proofs that haven't been found yet which we know exist independently of AC if and only if they exist within ZFC.

However, AC is not without controversy. It leads to proving statements such as the Banarch-Tarski paradox, which states that you can take a solid sphere, decompose it into finitley many pieces, and reconstruct those pieces into two solid spheres with the same volume as the original. Some people reject AC simply because it conflicts with their choice of mathematical philosophy.

Suze is right in saying that Gödel showed that, assuming ZF, ZFC is consistent. He did this by constructing the constructible universe - in layman's terms, just a particular choice of sets which satisfy AC. Thus, "AC is false" is inconsistent within ZF.

Unfortunately, and to the surprise of many, in 1963 Paul Cohen also showed that, assuming ZF, ZF¬C is consistent - that is, "AC is true" is also inconsistent within ZF. This means the Axiom of Choice is actually logically independent of ZF.


Now, to an easier example of something which cannot be proven. Consider Euclidean geometry - this is just the standard geometry you learned at school. Euclidean geometry is described by the following axioms:
    1. A straight line segment can be drawn joining any two points.
    2. Any straight line segment can be extended indefinitely in a straight line.
    3. Given any straight line segment, a circle can be drawn having the segment as radius and one endpoint as centre.
    4. All right angles are congruent.
However, consider the following fact: given any straight line, and a point somewhere not on that line, it is possible to draw exactly one new line which goes through the point, but never crosses the first line. This is called the parallel postulate, and it is impossible to prove using only the first four axioms, despite being true. To get round this, it was added as a fifth axiom, with which nobody was ever really happy, leading to all sorts of sketchy (and completely incorrect) proofs of the postulate over the years. It took the conceptual leap of non-Euclidean geometries by Bolyai and Lobachevsky to realise that in fact the parallel postulate describes only this one geometry.


Which leads me to Gödel's Incompleteness Theorems, the first of which says that, in any consistent formal system involving (enough) theory of natural numbers, there will be statements which are true but cannot be proved.** The crucial word here is any: unlike in Euclidean geometry or AC, you cannot get around this one by simply adding in the statement as an axiom and hoping nobody notices - there will simply be another statement, equally true, equally unprovable.

Gödel's Second Incompleteness Theorem says informally that
Quote:
... any formal system that is interesting enough to formulate its own consistency can prove its own consistency iff [if and only if] it is inconsistent.

So to answer the original question (assuming I haven't forgotten it by now) - something can indeed be true and unprovable.


*more's the pity because I genuinely find it fascinating - apparently I am in a tiny minority among mathematicians though, and it's bloody hard to find anybody willing to teach it or let you research it for money!

** Or as he rather snappily put it,
Quote:
"To every omega-consistent recursive class kappa of formulas, there correspond recursive class-signs r such that neither (v Gen r) nor Neg(v Gen r) belongs to Flg(kappa), where v is the free variable of r"

 
crissdee
1135658.  Tue Jun 02, 2015 5:49 am Reply with quote

oocephalous wrote:
oocephalous wrote:
If you can prove that something can't be proved, then does that mean that it is wrong or doesn't exist?

When I said about this, I was referring to time, but I am not sure that whether or not it has been proved to be improvable. I wanted to see what sort of reply I would get, because this was one of the facts on QI (time cannot be proved).


Can you (or someone else) either explain this or state it more coherently? I didn't see the episode where this was mentioned and I don't know what you're getting at. What aspect of time are you saying cannot be proved?

 
PDR
1135669.  Tue Jun 02, 2015 6:27 am Reply with quote

crissdee wrote:
What aspect of time are you saying cannot be proved?


Promised completion times from car repair/servicing organisations.

PDR

 
RLDavies
1135690.  Tue Jun 02, 2015 7:55 am Reply with quote

A good book for the layman on this topic is Forever Undecided by Raymond Smullyan, which approaches Godel by way of logic puzzles and a beginner's course in symbolic logic.

It helps if you work up to it through at least one or two of Smullyan's earlier logic-puzzle books:
What is the Name of This Book?
The Lady or the Tiger
Alice in Puzzle-Land
To Mock a Mockingbird


I see that he's come out with other logic puzzles since then, so I'll have to go out and get them. I adore Smullyan.

 
barbados
1135691.  Tue Jun 02, 2015 7:56 am Reply with quote

PDR wrote:
crissdee wrote:
What aspect of time are you saying cannot be proved?


Promised completion times from car repair/servicing organisations.

PDR


We even struggle for a thirty minute Chinese delivery.
Tesco even struggle sometimes - although they are usually the opposite (they get there the hour before my chosen time slot)

 
crissdee
1135740.  Tue Jun 02, 2015 1:23 pm Reply with quote

PDR wrote:
crissdee wrote:
What aspect of time are you saying cannot be proved?


Promised completion times from car repair/servicing organisations.

PDR


In fairness they haven't promised me anything at all, least of all completion times. They haven't even deigned to talk to me off their own bat.

 
WordLover
1135745.  Tue Jun 02, 2015 1:47 pm Reply with quote

RLDavies wrote:
A good book for the layman on this topic is Forever Undecided by Raymond Smullyan, which approaches Godel by way of logic puzzles and a beginner's course in symbolic logic.

It helps if you work up to it through at least one or two of Smullyan's earlier logic-puzzle books:
What is the Name of This Book?
The Lady or the Tiger
Alice in Puzzle-Land
To Mock a Mockingbird


I see that he's come out with other logic puzzles since then, so I'll have to go out and get them. I adore Smullyan.
Another book with useful info on this topic, and more besides, is Gödel, Escher, Bach by Douglas Hofstadter.

In that book he constructs a mathematical system. This system contains, among other things, second-order logic, and an operation that behaves like multiplication and thus is commutative. But the system is not rich enough for it to be provable in that system that multiplication is commutative.

 
Zziggy
1135787.  Tue Jun 02, 2015 6:06 pm Reply with quote

WordLover wrote:
Another book with useful info on this topic, and more besides, is Gödel, Escher, Bach by Douglas Hofstadter.

I was given this, as well as a book of sort stories by Chekhov, for my birthday by my supervisor. It looks good, but I haven't yet made an attempt to get through it, since it is intimidatingly large (& the font is rather small).

 
Leith
1135788.  Tue Jun 02, 2015 6:27 pm Reply with quote

I'll second WordLover's recommendation. I found it a fascinating and enjoyably playful meander through a whole range of QI topics.

 
RLDavies
1135884.  Wed Jun 03, 2015 8:09 am Reply with quote

I've always intended to get hold of Godel, Escher, Bach but haven't yet.

I do have Hofstadter's other opus, Metamagical Themas, which I'll eagerly recommend to everyone on this forum. It's a compilation of articles he wrote for Scientific American in the 1980s. It covers an enormous range of thought, including letterform design, self-reference, analogies, the Prisoner's Dilemma and related problems, and a lot more. It's the book I'd want to take with me to a desert island because you can always find something in it to read and ponder, and often be inspired to do something creative yourself.

 
gruff5
1135898.  Wed Jun 03, 2015 9:14 am Reply with quote

Zziggy wrote:
I was given this, as well as a book of sort stories by Chekhov...

Chekhov was such a polymath - I particularly liked his binary sort yarn.

 
Zziggy
1135904.  Wed Jun 03, 2015 10:32 am Reply with quote

It's not very nice to make fun of people you know. I'm actually very self-conscious of my visual anti-lisp :(

 
PDR
1135920.  Wed Jun 03, 2015 11:31 am Reply with quote

Well you've certainly been bubbled now...

PDR

 
crissdee
1135967.  Wed Jun 03, 2015 2:46 pm Reply with quote

Still waiting for someone to explain to me what aspect of "time" can/cannot be proved.

 
CharliesDragon
1135969.  Wed Jun 03, 2015 2:59 pm Reply with quote

Well, we can certainly observe the effects of time, which in my simple mind means it must exist. To define it in any way that doesn't rely on minutes, hours, years, etc? Not that easy.

 

Page 1 of 2
Goto page 1, 2  Next

All times are GMT - 5 Hours


Display posts from previous:   

Search Search Forums

Powered by phpBB © 2001, 2002 phpBB Group