- Each article can suck you in. Octopus.
- Once you read one article, you have to read another. Dominoes.
- All the articles are linked to each other. Spiderweb.
Therefore, based on everything I've heard from Cold War rhetoric, wikis are communist.
Showing posts with label library. Show all posts
Showing posts with label library. Show all posts
14 April 2011
29 March 2010
Waiting for Gödel
Continued!
This is the part where things start getting complicated, because set theory can, in fact, be defined in terms of itself. You see, any mathematical theory can be defined as a set of statements - some of which are unproven and assumed, and called axioms, and others of which are called theorems because they are implied by the axioms.
For example: The axioms of the basic arithmetic we all learn in school are as follows.
- Every number is equal to itself. If one number is equal to a second number, that number must be equal to the first. If a third number is equal to the second, it must also be equal to the first. But only a number can be equal to a number. (Equality defined!)
- 0 is a "natural" number, and adding one to any natural number yields another natural number. (Addition permitted!)
- If you have two numbers and add one to both of them, and get the same result, the two numbers must themselves be equal. (Subtraction permitted!)
- If you define some set of numbers such that if it contains some natural number then it must also contain that number plus one, and define it to contain 0, then that set contains all natural numbers. (The principle of induction!)
Arithmetic theorems include 1+1=2; 1+2=3; 2+2=4; and so on. It should be clear that there are an infinite number of these, even though there are some distinct limits - this arithmetic system doesn't even allow for multiplication yet, let alone fractions, irrational numbers, negatives, and more complicated ideas! But such concepts can be incorporated, by adding more axioms to get a larger system that still contains arithmetic.
For centuries, mathematicians have held two dreams. On the one hand, that it would be eventually possible to extend arithmetic logic - that is, the logic that underlies how we experience the universe on an everyday basis - to the point that it would contain all possible true statements. The day was dreamed of when two philosophers in a dispute would, instead of saying "let us argue", would say "let us calculate"; and then sit down and work out the equations underlying the properties of the soul, or the top quark, or God - a system both eminently powerful, and eminently practical.
On the other hand, there was the fear that mathematics is itself broken in some way, that one day someone would calculate some grotesque and immense equation, prove it true beyond all possible doubt or inherent limitation, and then realize that you could apply it in such away that 0=1. A waste of millennia of research and imagination and rigor, and the seed of a potential existential crisis among the entirety of the sciences and philosophies, which rely so heavily on the idea that human reason can understand the cosmos to begin with.
The dream and the nightmare are fundamentally in opposition to each other, and either would precipitate a tremendous shift in human understanding.
And Kurt Godel was the man who proved both were impossible.
The First Incompleteness Theorem: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.
In simpler terms, any theory that includes the axioms discussed above - which we know to be true - either contains false statements, or it excludes true statements.
Let me repeat that. If a theory can be made to contain all truth, then it also contains at least one statement that's false. If you can fix it to kick out that one statement, you also have to kick out at least one statement that's true.
This is the strongest argument for agnosticism that could ever possibly be made, and it is provably true based on everything we understand about logic and mathematics. And if you think that's bad, it gets worse.
The Second Incompleteness Theorem: For any formal effectively generated theory T including basic arithmetical truths, and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent.
That is, one of those statements you can never prove is that you're right. And if your theory can prove that all the statements it implies are true, they aren't.
Funny thing is, we can still define the "universal set" of all statements that are true. There's just no theory that can tell us what all those statements are. Sure, we can identify a "Godelian statement" for every theory we come up with, and add an axiom to the theory to account for it. We can splice a couple of mutually-cohesive theories together to cover even more ground. But these just make a bigger theory, and we already proved every consistent theory has a true statement outside it. We can make infinite theories, but the thing about eternity is, there's always more of it.
We can mark off a section of the Library of Babel that contains all the books we can prove to be true, but there's always another secret just beyond the horizon and we'll have to fight through a bunch of lies to get to it - and if you should find a lie in your own head, well, you'll have to throw it out, with all the ones relying on it that you thought you'd already proven.
Sound perilous? If you care about what you think, it's the only choice you've got. The quest for knowledge is an unending struggle against infinite odds. Besides, they say an inconvenience is only an adventure wrongly considered.
Bring me that horizon.
This is the part where things start getting complicated, because set theory can, in fact, be defined in terms of itself. You see, any mathematical theory can be defined as a set of statements - some of which are unproven and assumed, and called axioms, and others of which are called theorems because they are implied by the axioms.
For example: The axioms of the basic arithmetic we all learn in school are as follows.
- Every number is equal to itself. If one number is equal to a second number, that number must be equal to the first. If a third number is equal to the second, it must also be equal to the first. But only a number can be equal to a number. (Equality defined!)
- 0 is a "natural" number, and adding one to any natural number yields another natural number. (Addition permitted!)
- If you have two numbers and add one to both of them, and get the same result, the two numbers must themselves be equal. (Subtraction permitted!)
- If you define some set of numbers such that if it contains some natural number then it must also contain that number plus one, and define it to contain 0, then that set contains all natural numbers. (The principle of induction!)
Arithmetic theorems include 1+1=2; 1+2=3; 2+2=4; and so on. It should be clear that there are an infinite number of these, even though there are some distinct limits - this arithmetic system doesn't even allow for multiplication yet, let alone fractions, irrational numbers, negatives, and more complicated ideas! But such concepts can be incorporated, by adding more axioms to get a larger system that still contains arithmetic.
For centuries, mathematicians have held two dreams. On the one hand, that it would be eventually possible to extend arithmetic logic - that is, the logic that underlies how we experience the universe on an everyday basis - to the point that it would contain all possible true statements. The day was dreamed of when two philosophers in a dispute would, instead of saying "let us argue", would say "let us calculate"; and then sit down and work out the equations underlying the properties of the soul, or the top quark, or God - a system both eminently powerful, and eminently practical.
On the other hand, there was the fear that mathematics is itself broken in some way, that one day someone would calculate some grotesque and immense equation, prove it true beyond all possible doubt or inherent limitation, and then realize that you could apply it in such away that 0=1. A waste of millennia of research and imagination and rigor, and the seed of a potential existential crisis among the entirety of the sciences and philosophies, which rely so heavily on the idea that human reason can understand the cosmos to begin with.
The dream and the nightmare are fundamentally in opposition to each other, and either would precipitate a tremendous shift in human understanding.
And Kurt Godel was the man who proved both were impossible.
The First Incompleteness Theorem: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.
In simpler terms, any theory that includes the axioms discussed above - which we know to be true - either contains false statements, or it excludes true statements.
Let me repeat that. If a theory can be made to contain all truth, then it also contains at least one statement that's false. If you can fix it to kick out that one statement, you also have to kick out at least one statement that's true.
This is the strongest argument for agnosticism that could ever possibly be made, and it is provably true based on everything we understand about logic and mathematics. And if you think that's bad, it gets worse.
The Second Incompleteness Theorem: For any formal effectively generated theory T including basic arithmetical truths, and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent.
That is, one of those statements you can never prove is that you're right. And if your theory can prove that all the statements it implies are true, they aren't.
Funny thing is, we can still define the "universal set" of all statements that are true. There's just no theory that can tell us what all those statements are. Sure, we can identify a "Godelian statement" for every theory we come up with, and add an axiom to the theory to account for it. We can splice a couple of mutually-cohesive theories together to cover even more ground. But these just make a bigger theory, and we already proved every consistent theory has a true statement outside it. We can make infinite theories, but the thing about eternity is, there's always more of it.
We can mark off a section of the Library of Babel that contains all the books we can prove to be true, but there's always another secret just beyond the horizon and we'll have to fight through a bunch of lies to get to it - and if you should find a lie in your own head, well, you'll have to throw it out, with all the ones relying on it that you thought you'd already proven.
Sound perilous? If you care about what you think, it's the only choice you've got. The quest for knowledge is an unending struggle against infinite odds. Besides, they say an inconvenience is only an adventure wrongly considered.
Bring me that horizon.
21 February 2010
Kurt Gödel
I've been really bad about updating this - last week I was sick, but yesterday I was just lazy. Shame on me. But - I'm sworn not to become one of those people who starts a blog and never updates it, so.
Time to start talking about the other half of the title.
The Library of Babel, if you'll remember, is a metaphor for the inherent vagueness of truth and falsehood - you cannot know that a statement is true simply by looking at it. You have to compare it to itself, and to other statements that you know to be true... which you don't necessarily really know to be true, either.
So doubt everything. Test every book you read. Can it describe itself? Or does it rely on another book that can, or another book that relies on another book that relies on an entire series that can? If it can survive your earnest flame - and you must be in earnest to avoid deceiving yourself - you may trust it with your life. If not, it was not worth keeping to begin with, as useful to you as the belief that you can live without breathing.
And if you think that's no way to live... I have a bridge to sell you.
There's this construct called mathematics, which is basically the above taken to extremes. It's not just for numbers - that would be the subject known as arithmetic - but the rigorous calculation of fact. Set theory is probably one of the most general sub-categories, dealing with absolutely anything that can be grouped; but also predicate logic, with begins with tautologies like "if A is true, then A is true" and "either A is true or A is not true", and builds from there. Because of this, mathematical proofs are absolutely reliable... and this leads to problems.
Let's talk set theory. Any group that can be described constitutes a set - the set of all rational numbers, for instance, or its subset that contains only the numbers 4, 18, and 6... or the set of all the books in my library, or the set of everyone who has ever had the name "Julius Caesar". You can even define a set whose elements are {white, 14, Literacy, [you]}, as long as you don't include yourself (or literacy, or white, or 14) more than once.
There are also sets whose elements are other sets - the set of {white, 14, Literacy, the set of all the books in my library}, for instance. This is where a few important distinctions come in:
(1) 14 is not {14}. A set containing a single element is not the same as that element; saying {14} + {7} = {21} is like saying that {apple} + {orange} = {some bizarre sum equal to apple+orange}.
(2) {14} is a subset of {14, white} because all the elements of {14} are also elements of {14, white}. 14 is not a subset of {14, white} because it is not a set. More weirdly, 14 is an element of {14, {14, white}} and {14} is a subset, but {14} is an element of {{14}, {14, white}} but not a subset. The brackets are important!
(3) {14, white} and {white, 14} contain exactly the same elements (i.e. they're subsets of each other), which means they must be the same set. Order doesn't matter.
Confused yet? If you are, ask me and I'll try to explain better.
Time to start talking about the other half of the title.
The Library of Babel, if you'll remember, is a metaphor for the inherent vagueness of truth and falsehood - you cannot know that a statement is true simply by looking at it. You have to compare it to itself, and to other statements that you know to be true... which you don't necessarily really know to be true, either.
So doubt everything. Test every book you read. Can it describe itself? Or does it rely on another book that can, or another book that relies on another book that relies on an entire series that can? If it can survive your earnest flame - and you must be in earnest to avoid deceiving yourself - you may trust it with your life. If not, it was not worth keeping to begin with, as useful to you as the belief that you can live without breathing.
And if you think that's no way to live... I have a bridge to sell you.
There's this construct called mathematics, which is basically the above taken to extremes. It's not just for numbers - that would be the subject known as arithmetic - but the rigorous calculation of fact. Set theory is probably one of the most general sub-categories, dealing with absolutely anything that can be grouped; but also predicate logic, with begins with tautologies like "if A is true, then A is true" and "either A is true or A is not true", and builds from there. Because of this, mathematical proofs are absolutely reliable... and this leads to problems.
Let's talk set theory. Any group that can be described constitutes a set - the set of all rational numbers, for instance, or its subset that contains only the numbers 4, 18, and 6... or the set of all the books in my library, or the set of everyone who has ever had the name "Julius Caesar". You can even define a set whose elements are {white, 14, Literacy, [you]}, as long as you don't include yourself (or literacy, or white, or 14) more than once.
There are also sets whose elements are other sets - the set of {white, 14, Literacy, the set of all the books in my library}, for instance. This is where a few important distinctions come in:
(1) 14 is not {14}. A set containing a single element is not the same as that element; saying {14} + {7} = {21} is like saying that {apple} + {orange} = {some bizarre sum equal to apple+orange}.
(2) {14} is a subset of {14, white} because all the elements of {14} are also elements of {14, white}. 14 is not a subset of {14, white} because it is not a set. More weirdly, 14 is an element of {14, {14, white}} and {14} is a subset, but {14} is an element of {{14}, {14, white}} but not a subset. The brackets are important!
(3) {14, white} and {white, 14} contain exactly the same elements (i.e. they're subsets of each other), which means they must be the same set. Order doesn't matter.
Confused yet? If you are, ask me and I'll try to explain better.
13 February 2010
"The universe, which others call the Library..."
The Library of Babel is a short story by Jorge Luis Borges describing its own title. The Library is an entire world completely filled by hexagonal rooms of bookshelves, containing all the possible permutations of 25 symbols - 22 letters, plus the period, comma, and space - that could be contained in books that are precisely 410 pages long, 40 lines per page, 80 symbols per line. Every possible book that fits these parameters is somewhere in the Library, exactly once. Somewhere, there is a book containing nothing but four hundred and ten pages of MCVMCVMCV, but also the Encyclopedia Britannica, Shakespeare's First Folio, and a book that describes how to construct a perpetual-motion machine.
And, of course, a book whose title page is from the First Folio (by MCV), but the rest of which is from a faulty version of the Britannica that contains a description of a perpetual-motion machine. Thus, the Library contains all truth - but also all falsehood.
Obviously, somewhere, there is an index - a catalogue, explaining where all the books containing truth can be found, and one in every language, no less. But of course there are also a countless number of flawed indices, many of which have simply misplaced a period or substituted a word, but many of which are seemingly flawless except that where they say you should be able to find your own biography there is actually a copy of Finnegan's Wake. How, then, can you tell the true from the false?
You can start by picking an apparent index and looking it up in itself. If it's not there, you obviously can't trust it, because if it is true it should be listed in the book! Moreover, if it gives you a wrong location, you can't trust it, either. This is the easiest thing to begin with - any index which cannot account for itself is not a reliable index.
When you have an index that satisfies this basic condition, you can check the reliability of the rest of the list to make sure that all the books it contains are where it says they are. Then you must test the reliability of those books to make sure that they actually contain what they say they contain in the title; if any of these books are themselves indices (more than likely, for a library of this scope), this means testing a number of their contents for accuracy as well, ad infinitum if it goes that far.
Difficult, you say? Yes. Impossible? Necessary, if you wish to believe you know anything.
I hate hitting people with frying pans, but... if you haven't realized what this entire entry is a metaphor for yet, well, the majority of the rest of this blog is probably not for you.
As for Godel... he can wait until later.
And, of course, a book whose title page is from the First Folio (by MCV), but the rest of which is from a faulty version of the Britannica that contains a description of a perpetual-motion machine. Thus, the Library contains all truth - but also all falsehood.
Obviously, somewhere, there is an index - a catalogue, explaining where all the books containing truth can be found, and one in every language, no less. But of course there are also a countless number of flawed indices, many of which have simply misplaced a period or substituted a word, but many of which are seemingly flawless except that where they say you should be able to find your own biography there is actually a copy of Finnegan's Wake. How, then, can you tell the true from the false?
You can start by picking an apparent index and looking it up in itself. If it's not there, you obviously can't trust it, because if it is true it should be listed in the book! Moreover, if it gives you a wrong location, you can't trust it, either. This is the easiest thing to begin with - any index which cannot account for itself is not a reliable index.
When you have an index that satisfies this basic condition, you can check the reliability of the rest of the list to make sure that all the books it contains are where it says they are. Then you must test the reliability of those books to make sure that they actually contain what they say they contain in the title; if any of these books are themselves indices (more than likely, for a library of this scope), this means testing a number of their contents for accuracy as well, ad infinitum if it goes that far.
Difficult, you say? Yes. Impossible? Necessary, if you wish to believe you know anything.
I hate hitting people with frying pans, but... if you haven't realized what this entire entry is a metaphor for yet, well, the majority of the rest of this blog is probably not for you.
As for Godel... he can wait until later.
Subscribe to:
Posts (Atom)