what is actually a âdefinableâ real number? [duplicate]
![Creative The name of the picture](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgO9GURib1T8z7lCwjOGLQaGtrueEthgQ8LO42ZX8cOfTqDK4jvDDpKkLFwf2J49kYCMNW7d4ABih_XCb_2UXdq5fPJDkoyg7-8g_YfRUot-XnaXkNYycsNp7lA5_TW9td0FFpLQ2APzKcZ/s1600/1.jpg)
![Creative The name of the picture](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYQ0N5W1qAOxLP7t7iOM6O6AzbZnkXUy16s7P_CWfOb5UbTQY_aDsc727chyphenhyphen5W4IppVNernMMQeaUFTB_rFzAd95_CDt-tnwN-nBx6JyUp2duGjPaL5-VgNO41AVsA_vu30EJcipdDG409/s400/Clash+Royale+CLAN+TAG%2523URR8PPP.png)
up vote
9
down vote
favorite
This question already has an answer here:
Definable real numbers
1 answer
Wikipedia states that a definable (real) number is a number "that can be uniquely specified by its description". I naïvely thought that this was the same as "a number which may be computed", but elsewhere in math.SE I found out that it is not the case, because for example numbers related to Chaitin's $Omega$ are definable but not computable. Could someone explain me what a specification is, then? I always thought that $Omega$ was a probability value, which was not a real specification.
computability
marked as duplicate by Asaf Karagila, Xander Henderson, Taroccoesbrocco, Community⦠19 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
9
down vote
favorite
This question already has an answer here:
Definable real numbers
1 answer
Wikipedia states that a definable (real) number is a number "that can be uniquely specified by its description". I naïvely thought that this was the same as "a number which may be computed", but elsewhere in math.SE I found out that it is not the case, because for example numbers related to Chaitin's $Omega$ are definable but not computable. Could someone explain me what a specification is, then? I always thought that $Omega$ was a probability value, which was not a real specification.
computability
marked as duplicate by Asaf Karagila, Xander Henderson, Taroccoesbrocco, Community⦠19 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
This question has some valuable insight into the subtleties of the notion of a "definable" real number.
â Hayden
yesterday
As they say in that article, that's just an informal definition. In particular, as you point out, "specification" requires definition. The article goes on to give some concrete instances.
â lulu
yesterday
add a comment |Â
up vote
9
down vote
favorite
up vote
9
down vote
favorite
This question already has an answer here:
Definable real numbers
1 answer
Wikipedia states that a definable (real) number is a number "that can be uniquely specified by its description". I naïvely thought that this was the same as "a number which may be computed", but elsewhere in math.SE I found out that it is not the case, because for example numbers related to Chaitin's $Omega$ are definable but not computable. Could someone explain me what a specification is, then? I always thought that $Omega$ was a probability value, which was not a real specification.
computability
This question already has an answer here:
Definable real numbers
1 answer
Wikipedia states that a definable (real) number is a number "that can be uniquely specified by its description". I naïvely thought that this was the same as "a number which may be computed", but elsewhere in math.SE I found out that it is not the case, because for example numbers related to Chaitin's $Omega$ are definable but not computable. Could someone explain me what a specification is, then? I always thought that $Omega$ was a probability value, which was not a real specification.
This question already has an answer here:
Definable real numbers
1 answer
computability
asked yesterday
mau
6,75323162
6,75323162
marked as duplicate by Asaf Karagila, Xander Henderson, Taroccoesbrocco, Community⦠19 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Asaf Karagila, Xander Henderson, Taroccoesbrocco, Community⦠19 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
This question has some valuable insight into the subtleties of the notion of a "definable" real number.
â Hayden
yesterday
As they say in that article, that's just an informal definition. In particular, as you point out, "specification" requires definition. The article goes on to give some concrete instances.
â lulu
yesterday
add a comment |Â
1
This question has some valuable insight into the subtleties of the notion of a "definable" real number.
â Hayden
yesterday
As they say in that article, that's just an informal definition. In particular, as you point out, "specification" requires definition. The article goes on to give some concrete instances.
â lulu
yesterday
1
1
This question has some valuable insight into the subtleties of the notion of a "definable" real number.
â Hayden
yesterday
This question has some valuable insight into the subtleties of the notion of a "definable" real number.
â Hayden
yesterday
As they say in that article, that's just an informal definition. In particular, as you point out, "specification" requires definition. The article goes on to give some concrete instances.
â lulu
yesterday
As they say in that article, that's just an informal definition. In particular, as you point out, "specification" requires definition. The article goes on to give some concrete instances.
â lulu
yesterday
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
"Definable" is always relative to some particular language the definition is expressed in.
A number is definable if there is a property expressed in that language that is satisfied for that number but by no other numbers.
There is no particular expectation that the language we use for the definition is "executable" enough to pinpoint the number with any particular precision. As one example, we can consider definitions in the full first-order language of set theory, where
$$ (x=1landtextthe Riemann Hypothesis is true)lor(x=-1landtextthe Riemann Hypothesis is false)$$
can be expressed as a perfectly good property that defines a nonzero integer $x$ -- but we don't even know the sign of the number that is defined.
Chaitin's constant is actually not a single constant but depends on selecting a representation of Turing machines first. Slightly simplified, once we have selected an enumeration $T_n$ of Turing machines, we get a Chaitin constant
$$ Omega = sum_n=1^infty begincases 2^-n & textif T_ntext terminates \ 0 & textotherwise endcases $$
which again is a perfectly good definition (whether a given Turing machine terminates is a well-defined property), but we cannot compute the constant because whether a given Turing machine terminates is not computable.
(This can also be interpreted as a probability: Go through all of the Turing machines in sequence, flipping a coin for each and select the first machine where you get tails; what is the probability that this randomly chosen machine will terminate? But being a probability has, in itself, no bearing on whether the number is well-defined and/or computable).
add a comment |Â
up vote
2
down vote
The definable numbers depend on how one defines them. Since "the least positive integer not specifiable in fewer than twelve words" is an eleven-word phrase, we get something called Berry's paradox unless we recognise that the specification standard must preclude reference to itself. Formally, this separation relies on an object language and a metalanguage for talking about it, so "the least positive integer not specificable in fewer than sixteen words of that object language" can exist as a description in the metalanguage, but not in the object language; but this forces definability to be relative.
The important point is this: no matter what specification you formalise, if you're only allowed finite-length descriptions in a language with a countable alphabet, you'll only be able to define countably many things. (Roughly speaking, this is because $sum_n=0^inftyaleph_0^n=aleph_0$.) Since $mathbbR$ is uncountable, you'll definitely leave out something.
Don't you mean "$mathbb R$ is uncountable" ?
â Pece
yesterday
@Pece Thanks; fixed.
â J.G.
yesterday
2
Be careful of the last paragraph; it's easy to infer too much; I think the potential problem is basically another form of Skolem's paradox where you conflate internal and external properties. See this MSE question for references on how it is possible that you can specify not just every individual real number, but in fact every set!
â Hurkyl
yesterday
I know of Berry's paradox, but since it deals with a metalanguage I did not think that it was a bona fide definition of a number. Indeed I was interested in computable numbers exactly because they are countable and so there must exist (many...) uncomputable real numbers.
â mau
yesterday
1
@mau As I mentioned, it's only valid if you make succinct definability relative to a non-self-referential choice of specification. The point was to show that definability is relative, but will apply only to countably many numbers, just like computability does.
â J.G.
yesterday
add a comment |Â
up vote
2
down vote
"Definable" as a very precise meaning. Given a structure $M$ on a first-order language $mathcal L$, an element $ain M$ is definable if and only if there exists a formula $varphi(x)$ in one variable such that
$$ M models forall x, varphi(x) leftrightarrow (x=a)$$
In particular "definable" is always relative to the language of specification. For example, given $M$ as before, an element $ain M$ is always definable in (the induced structure on) $M$ over the language $mathcal L sqcup c_a$ where the new constant $c_a$ is interpreted as $a$ (the wanted $varphi(x)$ is just "$x=c_a$"). Even if $a$ was not definable over $mathcal L$.
When saying "Is the real number $a$ definable?", it is probable that people mean: given a model $mathcal S$ of ZFC, is (the set corresponding to) the real number $a$ (in the usual encoding of reals in ZFC) definable over the language $in$?
As nobody know an explicit model of ZFC, there is a good chance that "the real number $a$" is actually already a shortcut for the formula $varphi(x)$. To go back to your question, when people say "Chaitin's constant", they do not refer to a specific element of a God-given model of ZFC, they refer to the construction you probably know: enumerates the countably infinite Turing's machines as $m_1,dots$ and affect the value $t_i=0$ if $m_i$ terminates or $t_i=1$ otherwise then creates the number $sum_i=1^infty t_i10^-i$. All of that is completely expressable in the language $in$ under the axioms of ZFC. In particular, what is bothering you is the "if $m_i$ terminates", but termination of a Turing machine is a property that can be encoded into ZFC once the notion of Turing machine is encoded into ZFC. (ZFC would be making a poor job as a foundation of mathematics if such things was not expressable.)
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
"Definable" is always relative to some particular language the definition is expressed in.
A number is definable if there is a property expressed in that language that is satisfied for that number but by no other numbers.
There is no particular expectation that the language we use for the definition is "executable" enough to pinpoint the number with any particular precision. As one example, we can consider definitions in the full first-order language of set theory, where
$$ (x=1landtextthe Riemann Hypothesis is true)lor(x=-1landtextthe Riemann Hypothesis is false)$$
can be expressed as a perfectly good property that defines a nonzero integer $x$ -- but we don't even know the sign of the number that is defined.
Chaitin's constant is actually not a single constant but depends on selecting a representation of Turing machines first. Slightly simplified, once we have selected an enumeration $T_n$ of Turing machines, we get a Chaitin constant
$$ Omega = sum_n=1^infty begincases 2^-n & textif T_ntext terminates \ 0 & textotherwise endcases $$
which again is a perfectly good definition (whether a given Turing machine terminates is a well-defined property), but we cannot compute the constant because whether a given Turing machine terminates is not computable.
(This can also be interpreted as a probability: Go through all of the Turing machines in sequence, flipping a coin for each and select the first machine where you get tails; what is the probability that this randomly chosen machine will terminate? But being a probability has, in itself, no bearing on whether the number is well-defined and/or computable).
add a comment |Â
up vote
3
down vote
"Definable" is always relative to some particular language the definition is expressed in.
A number is definable if there is a property expressed in that language that is satisfied for that number but by no other numbers.
There is no particular expectation that the language we use for the definition is "executable" enough to pinpoint the number with any particular precision. As one example, we can consider definitions in the full first-order language of set theory, where
$$ (x=1landtextthe Riemann Hypothesis is true)lor(x=-1landtextthe Riemann Hypothesis is false)$$
can be expressed as a perfectly good property that defines a nonzero integer $x$ -- but we don't even know the sign of the number that is defined.
Chaitin's constant is actually not a single constant but depends on selecting a representation of Turing machines first. Slightly simplified, once we have selected an enumeration $T_n$ of Turing machines, we get a Chaitin constant
$$ Omega = sum_n=1^infty begincases 2^-n & textif T_ntext terminates \ 0 & textotherwise endcases $$
which again is a perfectly good definition (whether a given Turing machine terminates is a well-defined property), but we cannot compute the constant because whether a given Turing machine terminates is not computable.
(This can also be interpreted as a probability: Go through all of the Turing machines in sequence, flipping a coin for each and select the first machine where you get tails; what is the probability that this randomly chosen machine will terminate? But being a probability has, in itself, no bearing on whether the number is well-defined and/or computable).
add a comment |Â
up vote
3
down vote
up vote
3
down vote
"Definable" is always relative to some particular language the definition is expressed in.
A number is definable if there is a property expressed in that language that is satisfied for that number but by no other numbers.
There is no particular expectation that the language we use for the definition is "executable" enough to pinpoint the number with any particular precision. As one example, we can consider definitions in the full first-order language of set theory, where
$$ (x=1landtextthe Riemann Hypothesis is true)lor(x=-1landtextthe Riemann Hypothesis is false)$$
can be expressed as a perfectly good property that defines a nonzero integer $x$ -- but we don't even know the sign of the number that is defined.
Chaitin's constant is actually not a single constant but depends on selecting a representation of Turing machines first. Slightly simplified, once we have selected an enumeration $T_n$ of Turing machines, we get a Chaitin constant
$$ Omega = sum_n=1^infty begincases 2^-n & textif T_ntext terminates \ 0 & textotherwise endcases $$
which again is a perfectly good definition (whether a given Turing machine terminates is a well-defined property), but we cannot compute the constant because whether a given Turing machine terminates is not computable.
(This can also be interpreted as a probability: Go through all of the Turing machines in sequence, flipping a coin for each and select the first machine where you get tails; what is the probability that this randomly chosen machine will terminate? But being a probability has, in itself, no bearing on whether the number is well-defined and/or computable).
"Definable" is always relative to some particular language the definition is expressed in.
A number is definable if there is a property expressed in that language that is satisfied for that number but by no other numbers.
There is no particular expectation that the language we use for the definition is "executable" enough to pinpoint the number with any particular precision. As one example, we can consider definitions in the full first-order language of set theory, where
$$ (x=1landtextthe Riemann Hypothesis is true)lor(x=-1landtextthe Riemann Hypothesis is false)$$
can be expressed as a perfectly good property that defines a nonzero integer $x$ -- but we don't even know the sign of the number that is defined.
Chaitin's constant is actually not a single constant but depends on selecting a representation of Turing machines first. Slightly simplified, once we have selected an enumeration $T_n$ of Turing machines, we get a Chaitin constant
$$ Omega = sum_n=1^infty begincases 2^-n & textif T_ntext terminates \ 0 & textotherwise endcases $$
which again is a perfectly good definition (whether a given Turing machine terminates is a well-defined property), but we cannot compute the constant because whether a given Turing machine terminates is not computable.
(This can also be interpreted as a probability: Go through all of the Turing machines in sequence, flipping a coin for each and select the first machine where you get tails; what is the probability that this randomly chosen machine will terminate? But being a probability has, in itself, no bearing on whether the number is well-defined and/or computable).
edited yesterday
answered yesterday
Henning Makholm
225k16289515
225k16289515
add a comment |Â
add a comment |Â
up vote
2
down vote
The definable numbers depend on how one defines them. Since "the least positive integer not specifiable in fewer than twelve words" is an eleven-word phrase, we get something called Berry's paradox unless we recognise that the specification standard must preclude reference to itself. Formally, this separation relies on an object language and a metalanguage for talking about it, so "the least positive integer not specificable in fewer than sixteen words of that object language" can exist as a description in the metalanguage, but not in the object language; but this forces definability to be relative.
The important point is this: no matter what specification you formalise, if you're only allowed finite-length descriptions in a language with a countable alphabet, you'll only be able to define countably many things. (Roughly speaking, this is because $sum_n=0^inftyaleph_0^n=aleph_0$.) Since $mathbbR$ is uncountable, you'll definitely leave out something.
Don't you mean "$mathbb R$ is uncountable" ?
â Pece
yesterday
@Pece Thanks; fixed.
â J.G.
yesterday
2
Be careful of the last paragraph; it's easy to infer too much; I think the potential problem is basically another form of Skolem's paradox where you conflate internal and external properties. See this MSE question for references on how it is possible that you can specify not just every individual real number, but in fact every set!
â Hurkyl
yesterday
I know of Berry's paradox, but since it deals with a metalanguage I did not think that it was a bona fide definition of a number. Indeed I was interested in computable numbers exactly because they are countable and so there must exist (many...) uncomputable real numbers.
â mau
yesterday
1
@mau As I mentioned, it's only valid if you make succinct definability relative to a non-self-referential choice of specification. The point was to show that definability is relative, but will apply only to countably many numbers, just like computability does.
â J.G.
yesterday
add a comment |Â
up vote
2
down vote
The definable numbers depend on how one defines them. Since "the least positive integer not specifiable in fewer than twelve words" is an eleven-word phrase, we get something called Berry's paradox unless we recognise that the specification standard must preclude reference to itself. Formally, this separation relies on an object language and a metalanguage for talking about it, so "the least positive integer not specificable in fewer than sixteen words of that object language" can exist as a description in the metalanguage, but not in the object language; but this forces definability to be relative.
The important point is this: no matter what specification you formalise, if you're only allowed finite-length descriptions in a language with a countable alphabet, you'll only be able to define countably many things. (Roughly speaking, this is because $sum_n=0^inftyaleph_0^n=aleph_0$.) Since $mathbbR$ is uncountable, you'll definitely leave out something.
Don't you mean "$mathbb R$ is uncountable" ?
â Pece
yesterday
@Pece Thanks; fixed.
â J.G.
yesterday
2
Be careful of the last paragraph; it's easy to infer too much; I think the potential problem is basically another form of Skolem's paradox where you conflate internal and external properties. See this MSE question for references on how it is possible that you can specify not just every individual real number, but in fact every set!
â Hurkyl
yesterday
I know of Berry's paradox, but since it deals with a metalanguage I did not think that it was a bona fide definition of a number. Indeed I was interested in computable numbers exactly because they are countable and so there must exist (many...) uncomputable real numbers.
â mau
yesterday
1
@mau As I mentioned, it's only valid if you make succinct definability relative to a non-self-referential choice of specification. The point was to show that definability is relative, but will apply only to countably many numbers, just like computability does.
â J.G.
yesterday
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The definable numbers depend on how one defines them. Since "the least positive integer not specifiable in fewer than twelve words" is an eleven-word phrase, we get something called Berry's paradox unless we recognise that the specification standard must preclude reference to itself. Formally, this separation relies on an object language and a metalanguage for talking about it, so "the least positive integer not specificable in fewer than sixteen words of that object language" can exist as a description in the metalanguage, but not in the object language; but this forces definability to be relative.
The important point is this: no matter what specification you formalise, if you're only allowed finite-length descriptions in a language with a countable alphabet, you'll only be able to define countably many things. (Roughly speaking, this is because $sum_n=0^inftyaleph_0^n=aleph_0$.) Since $mathbbR$ is uncountable, you'll definitely leave out something.
The definable numbers depend on how one defines them. Since "the least positive integer not specifiable in fewer than twelve words" is an eleven-word phrase, we get something called Berry's paradox unless we recognise that the specification standard must preclude reference to itself. Formally, this separation relies on an object language and a metalanguage for talking about it, so "the least positive integer not specificable in fewer than sixteen words of that object language" can exist as a description in the metalanguage, but not in the object language; but this forces definability to be relative.
The important point is this: no matter what specification you formalise, if you're only allowed finite-length descriptions in a language with a countable alphabet, you'll only be able to define countably many things. (Roughly speaking, this is because $sum_n=0^inftyaleph_0^n=aleph_0$.) Since $mathbbR$ is uncountable, you'll definitely leave out something.
edited yesterday
answered yesterday
J.G.
12.8k11323
12.8k11323
Don't you mean "$mathbb R$ is uncountable" ?
â Pece
yesterday
@Pece Thanks; fixed.
â J.G.
yesterday
2
Be careful of the last paragraph; it's easy to infer too much; I think the potential problem is basically another form of Skolem's paradox where you conflate internal and external properties. See this MSE question for references on how it is possible that you can specify not just every individual real number, but in fact every set!
â Hurkyl
yesterday
I know of Berry's paradox, but since it deals with a metalanguage I did not think that it was a bona fide definition of a number. Indeed I was interested in computable numbers exactly because they are countable and so there must exist (many...) uncomputable real numbers.
â mau
yesterday
1
@mau As I mentioned, it's only valid if you make succinct definability relative to a non-self-referential choice of specification. The point was to show that definability is relative, but will apply only to countably many numbers, just like computability does.
â J.G.
yesterday
add a comment |Â
Don't you mean "$mathbb R$ is uncountable" ?
â Pece
yesterday
@Pece Thanks; fixed.
â J.G.
yesterday
2
Be careful of the last paragraph; it's easy to infer too much; I think the potential problem is basically another form of Skolem's paradox where you conflate internal and external properties. See this MSE question for references on how it is possible that you can specify not just every individual real number, but in fact every set!
â Hurkyl
yesterday
I know of Berry's paradox, but since it deals with a metalanguage I did not think that it was a bona fide definition of a number. Indeed I was interested in computable numbers exactly because they are countable and so there must exist (many...) uncomputable real numbers.
â mau
yesterday
1
@mau As I mentioned, it's only valid if you make succinct definability relative to a non-self-referential choice of specification. The point was to show that definability is relative, but will apply only to countably many numbers, just like computability does.
â J.G.
yesterday
Don't you mean "$mathbb R$ is uncountable" ?
â Pece
yesterday
Don't you mean "$mathbb R$ is uncountable" ?
â Pece
yesterday
@Pece Thanks; fixed.
â J.G.
yesterday
@Pece Thanks; fixed.
â J.G.
yesterday
2
2
Be careful of the last paragraph; it's easy to infer too much; I think the potential problem is basically another form of Skolem's paradox where you conflate internal and external properties. See this MSE question for references on how it is possible that you can specify not just every individual real number, but in fact every set!
â Hurkyl
yesterday
Be careful of the last paragraph; it's easy to infer too much; I think the potential problem is basically another form of Skolem's paradox where you conflate internal and external properties. See this MSE question for references on how it is possible that you can specify not just every individual real number, but in fact every set!
â Hurkyl
yesterday
I know of Berry's paradox, but since it deals with a metalanguage I did not think that it was a bona fide definition of a number. Indeed I was interested in computable numbers exactly because they are countable and so there must exist (many...) uncomputable real numbers.
â mau
yesterday
I know of Berry's paradox, but since it deals with a metalanguage I did not think that it was a bona fide definition of a number. Indeed I was interested in computable numbers exactly because they are countable and so there must exist (many...) uncomputable real numbers.
â mau
yesterday
1
1
@mau As I mentioned, it's only valid if you make succinct definability relative to a non-self-referential choice of specification. The point was to show that definability is relative, but will apply only to countably many numbers, just like computability does.
â J.G.
yesterday
@mau As I mentioned, it's only valid if you make succinct definability relative to a non-self-referential choice of specification. The point was to show that definability is relative, but will apply only to countably many numbers, just like computability does.
â J.G.
yesterday
add a comment |Â
up vote
2
down vote
"Definable" as a very precise meaning. Given a structure $M$ on a first-order language $mathcal L$, an element $ain M$ is definable if and only if there exists a formula $varphi(x)$ in one variable such that
$$ M models forall x, varphi(x) leftrightarrow (x=a)$$
In particular "definable" is always relative to the language of specification. For example, given $M$ as before, an element $ain M$ is always definable in (the induced structure on) $M$ over the language $mathcal L sqcup c_a$ where the new constant $c_a$ is interpreted as $a$ (the wanted $varphi(x)$ is just "$x=c_a$"). Even if $a$ was not definable over $mathcal L$.
When saying "Is the real number $a$ definable?", it is probable that people mean: given a model $mathcal S$ of ZFC, is (the set corresponding to) the real number $a$ (in the usual encoding of reals in ZFC) definable over the language $in$?
As nobody know an explicit model of ZFC, there is a good chance that "the real number $a$" is actually already a shortcut for the formula $varphi(x)$. To go back to your question, when people say "Chaitin's constant", they do not refer to a specific element of a God-given model of ZFC, they refer to the construction you probably know: enumerates the countably infinite Turing's machines as $m_1,dots$ and affect the value $t_i=0$ if $m_i$ terminates or $t_i=1$ otherwise then creates the number $sum_i=1^infty t_i10^-i$. All of that is completely expressable in the language $in$ under the axioms of ZFC. In particular, what is bothering you is the "if $m_i$ terminates", but termination of a Turing machine is a property that can be encoded into ZFC once the notion of Turing machine is encoded into ZFC. (ZFC would be making a poor job as a foundation of mathematics if such things was not expressable.)
add a comment |Â
up vote
2
down vote
"Definable" as a very precise meaning. Given a structure $M$ on a first-order language $mathcal L$, an element $ain M$ is definable if and only if there exists a formula $varphi(x)$ in one variable such that
$$ M models forall x, varphi(x) leftrightarrow (x=a)$$
In particular "definable" is always relative to the language of specification. For example, given $M$ as before, an element $ain M$ is always definable in (the induced structure on) $M$ over the language $mathcal L sqcup c_a$ where the new constant $c_a$ is interpreted as $a$ (the wanted $varphi(x)$ is just "$x=c_a$"). Even if $a$ was not definable over $mathcal L$.
When saying "Is the real number $a$ definable?", it is probable that people mean: given a model $mathcal S$ of ZFC, is (the set corresponding to) the real number $a$ (in the usual encoding of reals in ZFC) definable over the language $in$?
As nobody know an explicit model of ZFC, there is a good chance that "the real number $a$" is actually already a shortcut for the formula $varphi(x)$. To go back to your question, when people say "Chaitin's constant", they do not refer to a specific element of a God-given model of ZFC, they refer to the construction you probably know: enumerates the countably infinite Turing's machines as $m_1,dots$ and affect the value $t_i=0$ if $m_i$ terminates or $t_i=1$ otherwise then creates the number $sum_i=1^infty t_i10^-i$. All of that is completely expressable in the language $in$ under the axioms of ZFC. In particular, what is bothering you is the "if $m_i$ terminates", but termination of a Turing machine is a property that can be encoded into ZFC once the notion of Turing machine is encoded into ZFC. (ZFC would be making a poor job as a foundation of mathematics if such things was not expressable.)
add a comment |Â
up vote
2
down vote
up vote
2
down vote
"Definable" as a very precise meaning. Given a structure $M$ on a first-order language $mathcal L$, an element $ain M$ is definable if and only if there exists a formula $varphi(x)$ in one variable such that
$$ M models forall x, varphi(x) leftrightarrow (x=a)$$
In particular "definable" is always relative to the language of specification. For example, given $M$ as before, an element $ain M$ is always definable in (the induced structure on) $M$ over the language $mathcal L sqcup c_a$ where the new constant $c_a$ is interpreted as $a$ (the wanted $varphi(x)$ is just "$x=c_a$"). Even if $a$ was not definable over $mathcal L$.
When saying "Is the real number $a$ definable?", it is probable that people mean: given a model $mathcal S$ of ZFC, is (the set corresponding to) the real number $a$ (in the usual encoding of reals in ZFC) definable over the language $in$?
As nobody know an explicit model of ZFC, there is a good chance that "the real number $a$" is actually already a shortcut for the formula $varphi(x)$. To go back to your question, when people say "Chaitin's constant", they do not refer to a specific element of a God-given model of ZFC, they refer to the construction you probably know: enumerates the countably infinite Turing's machines as $m_1,dots$ and affect the value $t_i=0$ if $m_i$ terminates or $t_i=1$ otherwise then creates the number $sum_i=1^infty t_i10^-i$. All of that is completely expressable in the language $in$ under the axioms of ZFC. In particular, what is bothering you is the "if $m_i$ terminates", but termination of a Turing machine is a property that can be encoded into ZFC once the notion of Turing machine is encoded into ZFC. (ZFC would be making a poor job as a foundation of mathematics if such things was not expressable.)
"Definable" as a very precise meaning. Given a structure $M$ on a first-order language $mathcal L$, an element $ain M$ is definable if and only if there exists a formula $varphi(x)$ in one variable such that
$$ M models forall x, varphi(x) leftrightarrow (x=a)$$
In particular "definable" is always relative to the language of specification. For example, given $M$ as before, an element $ain M$ is always definable in (the induced structure on) $M$ over the language $mathcal L sqcup c_a$ where the new constant $c_a$ is interpreted as $a$ (the wanted $varphi(x)$ is just "$x=c_a$"). Even if $a$ was not definable over $mathcal L$.
When saying "Is the real number $a$ definable?", it is probable that people mean: given a model $mathcal S$ of ZFC, is (the set corresponding to) the real number $a$ (in the usual encoding of reals in ZFC) definable over the language $in$?
As nobody know an explicit model of ZFC, there is a good chance that "the real number $a$" is actually already a shortcut for the formula $varphi(x)$. To go back to your question, when people say "Chaitin's constant", they do not refer to a specific element of a God-given model of ZFC, they refer to the construction you probably know: enumerates the countably infinite Turing's machines as $m_1,dots$ and affect the value $t_i=0$ if $m_i$ terminates or $t_i=1$ otherwise then creates the number $sum_i=1^infty t_i10^-i$. All of that is completely expressable in the language $in$ under the axioms of ZFC. In particular, what is bothering you is the "if $m_i$ terminates", but termination of a Turing machine is a property that can be encoded into ZFC once the notion of Turing machine is encoded into ZFC. (ZFC would be making a poor job as a foundation of mathematics if such things was not expressable.)
answered yesterday
Pece
7,88211038
7,88211038
add a comment |Â
add a comment |Â
1
This question has some valuable insight into the subtleties of the notion of a "definable" real number.
â Hayden
yesterday
As they say in that article, that's just an informal definition. In particular, as you point out, "specification" requires definition. The article goes on to give some concrete instances.
â lulu
yesterday