This may seem like an odd question but, if proof is about why
things work, is there a difference between proof and derivation?
Does a derivation from basic principles satisfy as a proof?
Thanks
Ali
I'd have thought a derivation is one form of proof, so yes, it does satisfy as a proof, but there is a difference between the two.
This is an interesting question. In any axiomatic system
(collection of statements derived from stated principles) a
statement is either TRUE or FALSE. Like you say proof can be seen
as nothing more than derivation, it is a method of convincing us
that a statement is TRUE. I think there is quite a lot of
philosophical argument about whether a statement is 'TRUE' or
'FALSE' before it is proved or disproved, also about whether a
statement that is NOT TRUE is necessarily FALSE. I don't know
very much about this but would like to learn more, I've seen one
or two similar posts on the topic, perhaps NRICH could get an
expert to do an article on the subject.
There is also the interesting question of Godel's theorems that
state that in any axiomatic system there exists a statement that
cannot be proved or disproved.
Fascinating...
On a slightly separate note, does this work as a proof?
Let S be the set of all positive integers about which there are
no interesting facts. S then has a least element, x. But then
there is an interesting fact about x, therefore no such set can
exist.
Seems kinda weird to me...
Olof
In other words every number has an interesting property :)
Actually, isn't this a version of Russell's paradox?
No, it's not really the same. Russell's
paradox is based on the axiom of abstraction, formulated by Frege
in 1893. It says:
"Given any property, there exists a set whose members are just
those entities possessing that property."
Now soon it was discovered that this was a nonsensical axiom -
i.e. it was not self-consistent and it was quickly abandoned. Can
you see why? There are two well-known proofs. One of them is
Russell's paradox Here it is:
By the axiom of abstraction we can find a set S which contains
all entities such that
i) each entity in S is a set
ii) each set in S is not a member of itself.
(So the set of all words is in S because the set of words is not
a word itself. But the set of all things apart from words is not
a word so it is a not a member of S.)
Now consider the question is S a member of S? Well if it is then
it isn't and if it isn't then it is. We have our
contradiction.
There is another way of showing the axiom of abstraction is
nonsensical; this one's called Cantor's Paradox.
By the axiom of abstraction, we can find a set S that contains
all entities - i.e. is the universal set. Now by Cantor's theorem
the set of subsets of S (called P(S)) is of higher cardinality
than S, so there is no surjection from S to P(S). But as S is the
universal set P(S) is just a subset of S, so there is obviously a
surjection from S to P(S) contradicting Cantor's Theorem, which
can be proved. We have a paradox.
These prove that the axiom of abstraction is inconsistent. It has
been replaced by the axiom of separation which states that for
any property there exists a set whose members possess just that
property and whose members all belong to some other set X. Can
you see how this gets around these two?
Just for completeness, here are a few more paradoxes.
Liar's Paradox
It is believed to have been put forward by the Cretan philosopher
Epimendies around 500 BC. Suppose someone says:
"I am lying."
This statement contradicts itself. For if it is true, then it is
false and if it is false then it is true. This is an example of a
grammatically correct sentence which is not logically
self-consistent.
Grelling's Paradox
Put forward by K. Grelling in 1808. We call an adjective
autological if it has the property of itself. So for instance,
the word polysyllabic is polysyllabic (as it has > 1
syllables) therefore it is autological. Also English is English,
so English is an autological word too. On the other hand the word
French is not French so it is called heterological. (The
definition of a heterological word is one which is not
autological.) Monosyllabic is another heterological word. Now a
question: is the word "heterological" autological or not? Well if
it is then this implies it is heterological, contradicting the
fact it is autological. But if it is heterological then it is not
heterological so it is autological which is again a
contradiction. We have a paradox.
(Clearly, this is very, very similar to Russell's paradox.)
Richard's Paradox
Put forward by J. Richard in 1905. We are first of all going to
specify an enumeration of the English phrases that denote real
numbers.
First take all one-syllable phrases representing numbers. Order
these in terms of the magnitude of the number. Next write down
the words of two syllables (again ordering these in magnitude)
then three syllables etc. So we now have an enumeration of
phrases denoting real numbers. Call the nth phrase in the list
the nth Richard number.
Now consider the phrase denoting the real number r, such that for
all integers n, the nth decimal place of r is 2 if the nth
decimal place of the nth Richard number is 1. Otherwise the nth
decimal place is 1.
This expression should be a Richard number but if it's the kth
then it differs in the kth decimal place to the kth Richard
number which is a contradiction.
Berry's Paradox
Formulated by G. Berry in 1906. Let f(n) be equal to the least
number of syllables you need to communicate the number n. So f(1)
= 1 because the number 1 can be communicated in one syllable -
namely "one". Now consider the minimal integer n such that f(n)
> 18. If you do a bit of calculation it appears that this
number is one hundred and eleven thousand seven hundred and
seventy seven (i.e. 111777) which is 19 syllables. However notice
that you can also specify the number in eighteen syllables as
follows: it is "the least integer not nameable in fewer than
nineteen syllables". If you look at the expression in quotes it
uniquely names the number in question and yet the quoted
expression is only 18 syllables. So n can be specified in 18
syllables which is a contradiction so we have a paradox.
Going back to the earlier discussion I think Godel's proof says something like in any axiomatic system involving arithmetic there are always undecidable statements. Clearly there are trivial axiomatic systems with no undecidable statements.
Do you happen to know of any mathematical (non-set specific)
statements that have been proven to be unprovable (if that's a
word)?
Nice list of paradoxes by the way.
Olof
Provability (if that is a word) depends
on what axioms you use. For example, it was shown, by Godel in
1938, that the axiom of choice is consistent with the framework
of ZF set theory. Further, in 1963, Cohen proved that the
negation of axiom of choice can also be consistent with ZF. Hence
the Axiom of Choice is undecidable in ZF. I think it was also
proven that the (generalised) continuum hypothesis is independent
of ZF+Choice.
There is a theorem which states that a statement A is provable in
the system N if and only if it is true in all models of N. Godel
and Cohen's work basically consisted of constructing a model of
ZF in which AC is true and false respectively.
Kerwin
What's the continuum hypothesis?
Thanks,
Olof
The continuum hypothesis states that, if
a subset of R, the reals, is infinite, then it either bijects
with N, the naturals, or R itself. Basically this means there are
no intermediate infinities between the size of N and the size of
R.
Kerwin
Sorry I'm not quite sure what bijects means - could you
perhaps give a brief explanation? Thanks.
Olof
Sets A and B biject if there is a
mapping A-> B which takes no two elements of A to the same
element of B and takes some element of A to each element of
B.
If A and B are finite then this says the number of elements in A
is the same as the number of elements in B. We generalise and say
that any two sets have 'the same number of elements'
(cardinality) if and only if they biject.