7 ms·
> What does “Undecidable” mean, anyway A big and relatively recent example is to take (1) the axioms of Zermelo-Fraenkel set theory and (2) the axiom of choice
by graycat 1y ago
> What does “Undecidable” mean, anyway
A big and relatively recent example is to
take (1) the axioms of Zermelo-Fraenkel
set theory and (2) the axiom of choice and
ask if (1) can be used to prove or
disprove (2). The surprising answer is
"No", i.e., (1) cannot be used either to
prove or disprove (2). So, can work with
(1) and, whenever convenient, assume (2),
continue on, and never encounter a
problem.
So, given (1), (2) is undecidable.
The work was by Paul J. Cohen as at
https://en.wikipedia.org/wiki/Paul_Cohen https://en.wikipedia.org/wiki/Paul_Cohen
The field of research about what is
undecidable also goes back to Kurt Gödel
as at
https://en.wikipedia.org/wiki/Kurt_G%C3%B6del https://en.wikipedia.org/wiki/Kurt_G%C3%B6del
Another example, starting with (1), of an
undecidable statement is the continuum
hypothesis:
There is no set whose cardinality is
strictly between that of the integers
and the real numbers.
In simple terms, "cardinality" means that
there is no set X that is too large to be
put into 1-1 correspondence with the set
of integers and too small to be put into
1-1 correspondence with the set of real
numbers.