Mixing
What is the truth predicate of ZFC?
Clash Royale CLAN TAG#URR8PPP
up vote
-2
down vote
favorite
Tarksi's theorem states that for any sufficiently strong formal language L, the truth predicate for L cannot be defined in L. For instance the truth predicate for the language of first-order arithmetic cannot be defined in the language of first-order arithmetic. It can be defined in the language of second-order arithmetic though.
My question is, what is the truth predicate for the language of ZFC, i.e. the language of first-order set theory? And what is the language needed to define this truth predicate. Is it second-order set theory, i.e. the language of NBG and MK involving sets and classes?
logic set-theory
edited Jul 27 at 21:08
Andrés E. Caicedo
63.1k7151235
asked Jul 27 at 14:11
Keshav Srinivasan
1,75611338
 |Â
show 8 more comments
up vote
-2
down vote
favorite
Tarksi's theorem states that for any sufficiently strong formal language L, the truth predicate for L cannot be defined in L. For instance the truth predicate for the language of first-order arithmetic cannot be defined in the language of first-order arithmetic. It can be defined in the language of second-order arithmetic though.
My question is, what is the truth predicate for the language of ZFC, i.e. the language of first-order set theory? And what is the language needed to define this truth predicate. Is it second-order set theory, i.e. the language of NBG and MK involving sets and classes?
logic set-theory
edited Jul 27 at 21:08
Andrés E. Caicedo
63.1k7151235
asked Jul 27 at 14:11
Keshav Srinivasan
1,75611338
1
That's an odd question. The truth predicate is... a truth predicate. it tells you which sentences are true.
– Asaf Karagila
Jul 27 at 14:38
1
You're not aware of how you code logic into set theory? You don't understand what does it mean for something to be true? What is it that you think you're missing?
– Asaf Karagila
Jul 27 at 14:57
1
@AsafKaragila I think the OP is talking about Traski's undefinability theorem and that by truth predicate he means the predicate $mathrmtruth(x)$ that holds only for the encodings of arithmetic formulas that hold in $mathbb N$, or to be exact an analogous predicate for ZFC.
– Giorgio Mossa
Jul 27 at 16:24
2
@Giorgio: Yes, I am very clear about that. I'm just confused as to what exactly confuses the OP.
– Asaf Karagila
Jul 27 at 16:25
2
Yes, that is a different question than the one in your previous comment (and it makes less sense).
– Andrés E. Caicedo
Jul 27 at 21:46
 |Â
show 8 more comments
up vote
-2
down vote
favorite
up vote
-2
down vote
favorite
Tarksi's theorem states that for any sufficiently strong formal language L, the truth predicate for L cannot be defined in L. For instance the truth predicate for the language of first-order arithmetic cannot be defined in the language of first-order arithmetic. It can be defined in the language of second-order arithmetic though.
My question is, what is the truth predicate for the language of ZFC, i.e. the language of first-order set theory? And what is the language needed to define this truth predicate. Is it second-order set theory, i.e. the language of NBG and MK involving sets and classes?
logic set-theory
edited Jul 27 at 21:08
Andrés E. Caicedo
63.1k7151235
asked Jul 27 at 14:11
Keshav Srinivasan
1,75611338
Tarksi's theorem states that for any sufficiently strong formal language L, the truth predicate for L cannot be defined in L. For instance the truth predicate for the language of first-order arithmetic cannot be defined in the language of first-order arithmetic. It can be defined in the language of second-order arithmetic though.
My question is, what is the truth predicate for the language of ZFC, i.e. the language of first-order set theory? And what is the language needed to define this truth predicate. Is it second-order set theory, i.e. the language of NBG and MK involving sets and classes?
logic set-theory
edited Jul 27 at 21:08
Andrés E. Caicedo
63.1k7151235
asked Jul 27 at 14:11
Keshav Srinivasan
1,75611338
edited Jul 27 at 21:08
Andrés E. Caicedo
63.1k7151235
edited Jul 27 at 21:08
Andrés E. Caicedo
63.1k7151235
edited Jul 27 at 21:08
Andrés E. Caicedo
63.1k7151235
63.1k7151235
asked Jul 27 at 14:11
Keshav Srinivasan
1,75611338
asked Jul 27 at 14:11
Keshav Srinivasan
1,75611338
asked Jul 27 at 14:11
Keshav Srinivasan
1,75611338
1,75611338
1
That's an odd question. The truth predicate is... a truth predicate. it tells you which sentences are true.
– Asaf Karagila
Jul 27 at 14:38
1
You're not aware of how you code logic into set theory? You don't understand what does it mean for something to be true? What is it that you think you're missing?
– Asaf Karagila
Jul 27 at 14:57
1
@AsafKaragila I think the OP is talking about Traski's undefinability theorem and that by truth predicate he means the predicate $mathrmtruth(x)$ that holds only for the encodings of arithmetic formulas that hold in $mathbb N$, or to be exact an analogous predicate for ZFC.
– Giorgio Mossa
Jul 27 at 16:24
2
@Giorgio: Yes, I am very clear about that. I'm just confused as to what exactly confuses the OP.
– Asaf Karagila
Jul 27 at 16:25
2
Yes, that is a different question than the one in your previous comment (and it makes less sense).
– Andrés E. Caicedo
Jul 27 at 21:46
 |Â
show 8 more comments
1
That's an odd question. The truth predicate is... a truth predicate. it tells you which sentences are true.
– Asaf Karagila
Jul 27 at 14:38
1
You're not aware of how you code logic into set theory? You don't understand what does it mean for something to be true? What is it that you think you're missing?
– Asaf Karagila
Jul 27 at 14:57
1
@AsafKaragila I think the OP is talking about Traski's undefinability theorem and that by truth predicate he means the predicate $mathrmtruth(x)$ that holds only for the encodings of arithmetic formulas that hold in $mathbb N$, or to be exact an analogous predicate for ZFC.
– Giorgio Mossa
Jul 27 at 16:24
2
@Giorgio: Yes, I am very clear about that. I'm just confused as to what exactly confuses the OP.
– Asaf Karagila
Jul 27 at 16:25
2
Yes, that is a different question than the one in your previous comment (and it makes less sense).
– Andrés E. Caicedo
Jul 27 at 21:46
1
1
That's an odd question. The truth predicate is... a truth predicate. it tells you which sentences are true.
– Asaf Karagila
Jul 27 at 14:38
That's an odd question. The truth predicate is... a truth predicate. it tells you which sentences are true.
– Asaf Karagila
Jul 27 at 14:38
1
1
You're not aware of how you code logic into set theory? You don't understand what does it mean for something to be true? What is it that you think you're missing?
– Asaf Karagila
Jul 27 at 14:57
You're not aware of how you code logic into set theory? You don't understand what does it mean for something to be true? What is it that you think you're missing?
– Asaf Karagila
Jul 27 at 14:57
1
1
@AsafKaragila I think the OP is talking about Traski's undefinability theorem and that by truth predicate he means the predicate $mathrmtruth(x)$ that holds only for the encodings of arithmetic formulas that hold in $mathbb N$, or to be exact an analogous predicate for ZFC.
– Giorgio Mossa
Jul 27 at 16:24
@AsafKaragila I think the OP is talking about Traski's undefinability theorem and that by truth predicate he means the predicate $mathrmtruth(x)$ that holds only for the encodings of arithmetic formulas that hold in $mathbb N$, or to be exact an analogous predicate for ZFC.
– Giorgio Mossa
Jul 27 at 16:24
2
2
@Giorgio: Yes, I am very clear about that. I'm just confused as to what exactly confuses the OP.
– Asaf Karagila
Jul 27 at 16:25
@Giorgio: Yes, I am very clear about that. I'm just confused as to what exactly confuses the OP.
– Asaf Karagila
Jul 27 at 16:25
2
2
Yes, that is a different question than the one in your previous comment (and it makes less sense).
– Andrés E. Caicedo
Jul 27 at 21:46
Yes, that is a different question than the one in your previous comment (and it makes less sense).
– Andrés E. Caicedo
Jul 27 at 21:46
 |Â
show 8 more comments
1 Answer
1
active
oldest
votes
up vote
7
down vote
This is all very standard - here is an attempt to write something about it.
If we are talking about truth, we really want to talk about models, rather than about languages, because until we specify a model we don't have a notion of "true" at hand. We should avoid talking about the "truth predicate for a language".
For any model $M$ in a first-order language, the definition of the truth predicate of $M$ is the same - we define the elementary diagram of $M$ as the set of all sentences with parameters from $M$ that are true in $M$, using Tarski's recursive definition of truth, using the T schema. This is the same for a model of ZFC as for any other model in first-order logic.
A key aspect of the T schema is that it is recursive - it gives an inductive definition of the set of true sentences, but not an explicit definition.
Tarski's theorem on the undefinability of truth shows that, for many theories, there is no formula $textTrue(x)$ in the language of the theory so that, for every model $M$ of the theory and every formula $phi$, $textTrue(phi)$ holds in $M$ if and only if $phi$ holds in $M$. In particular, we could let the theory by PA or ZFC.
But there is a standard way to make an explicit definition of the truth, which works over every model of a given theory like ZFC of PA, by using a higher kind of quantifier. To do so, we first notice that the overall truth predicate of a model is stratified into a hierarchy by the number of alternations of quantifiers that the formula has in prenex normal form. This is analogous to the arithmetical hierarchy, but the formulas may now have parameters. In the case of ZFC these will be set parameters.
The base layer of this hierarchy consists of quantifier-free formulas with parameters. The next level consists of formulas that have one block of a single kind of leading quantifier, the third consists of formulas with two blocks of quantifiers at the front, etc. Call these levels $H_0$, $H_1$, etc.
For example, a formula $(exists x)phi(x)$ is true in a model $M$ if and only if $phi(a)$ is true for some $a in M$, in other words if and only if $phi(a) in H_0$ for some $a in M$. Similarly $(forall x)(exists y)psi(x,y)$ is true in $M$ if and only if $(exists y)psi(a,y)$ is in $H_1$ for every $a in M$.
There is a single second-order formula $tau$ that defines the sequence $(H_0, H_1, ldots)$ over a model $M$. This formula first defines $H_0$ explicitly, then says that for all $n$, an existential formula $(exists x)phi(x)$ is in $H_n+1$ if and only if there is some $a in M$ so that $phi(a)$ is in $H_n$. There are additional clauses for all the logical connectives, etc.
Using the formula $tau$, we can write an explicit second-order definition of the truth predicate: a formula with $n$ alternations of quantifiers is true if and only if, for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$, $phi$ is in $A_n$.
The reason that this does not give an explicit definition of the truth predicate in the original language is the parameters in the formulas. For example, if we work over any model $M$ of ZFC, $H_0$ is already a proper class of $M$ (among other things, it includes the formula $a = a$ for every $a in M$).
Thus, for ZFC, saying "for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$" requires quantifying over proper classes. This is exactly what the new quantifiers in second-order ZFC can do, so we can write an explicit definition of the truth predicate in second-order ZFC. If we call this definition $textTrue'(phi)$ we have this result: for every model $M$ of ZFC, if $M'$ is the expansion of $M$ to a full second-order model, and $phi$ is any sentence of ZFC, then $M$ satisfies $phi$ if and only if $M'$ satisfies $textTrue'(phi)$. Here the full expansion of $M$ is the second-order model whose classes are all the possible subsets of the domain of $M$.
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
What is the purpose of the parameters?
– Keshav Srinivasan
Jul 28 at 13:32
2
In order to ask whether a sentence such as $(exists x)phi(x)$ is true, we need to know whether $phi(a)$ is true for some $a in M$. So, even if we were only interested in the truth values of sentences without parameters, we are immediately led to look at the truth values of formulas with parameters. This is completely due to the meaning that the quantifiers $forall$ and $exists$ have.
– Carl Mummert
Jul 28 at 13:34
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
This is all very standard - here is an attempt to write something about it.
If we are talking about truth, we really want to talk about models, rather than about languages, because until we specify a model we don't have a notion of "true" at hand. We should avoid talking about the "truth predicate for a language".
For any model $M$ in a first-order language, the definition of the truth predicate of $M$ is the same - we define the elementary diagram of $M$ as the set of all sentences with parameters from $M$ that are true in $M$, using Tarski's recursive definition of truth, using the T schema. This is the same for a model of ZFC as for any other model in first-order logic.
A key aspect of the T schema is that it is recursive - it gives an inductive definition of the set of true sentences, but not an explicit definition.
Tarski's theorem on the undefinability of truth shows that, for many theories, there is no formula $textTrue(x)$ in the language of the theory so that, for every model $M$ of the theory and every formula $phi$, $textTrue(phi)$ holds in $M$ if and only if $phi$ holds in $M$. In particular, we could let the theory by PA or ZFC.
But there is a standard way to make an explicit definition of the truth, which works over every model of a given theory like ZFC of PA, by using a higher kind of quantifier. To do so, we first notice that the overall truth predicate of a model is stratified into a hierarchy by the number of alternations of quantifiers that the formula has in prenex normal form. This is analogous to the arithmetical hierarchy, but the formulas may now have parameters. In the case of ZFC these will be set parameters.
The base layer of this hierarchy consists of quantifier-free formulas with parameters. The next level consists of formulas that have one block of a single kind of leading quantifier, the third consists of formulas with two blocks of quantifiers at the front, etc. Call these levels $H_0$, $H_1$, etc.
For example, a formula $(exists x)phi(x)$ is true in a model $M$ if and only if $phi(a)$ is true for some $a in M$, in other words if and only if $phi(a) in H_0$ for some $a in M$. Similarly $(forall x)(exists y)psi(x,y)$ is true in $M$ if and only if $(exists y)psi(a,y)$ is in $H_1$ for every $a in M$.
There is a single second-order formula $tau$ that defines the sequence $(H_0, H_1, ldots)$ over a model $M$. This formula first defines $H_0$ explicitly, then says that for all $n$, an existential formula $(exists x)phi(x)$ is in $H_n+1$ if and only if there is some $a in M$ so that $phi(a)$ is in $H_n$. There are additional clauses for all the logical connectives, etc.
Using the formula $tau$, we can write an explicit second-order definition of the truth predicate: a formula with $n$ alternations of quantifiers is true if and only if, for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$, $phi$ is in $A_n$.
The reason that this does not give an explicit definition of the truth predicate in the original language is the parameters in the formulas. For example, if we work over any model $M$ of ZFC, $H_0$ is already a proper class of $M$ (among other things, it includes the formula $a = a$ for every $a in M$).
Thus, for ZFC, saying "for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$" requires quantifying over proper classes. This is exactly what the new quantifiers in second-order ZFC can do, so we can write an explicit definition of the truth predicate in second-order ZFC. If we call this definition $textTrue'(phi)$ we have this result: for every model $M$ of ZFC, if $M'$ is the expansion of $M$ to a full second-order model, and $phi$ is any sentence of ZFC, then $M$ satisfies $phi$ if and only if $M'$ satisfies $textTrue'(phi)$. Here the full expansion of $M$ is the second-order model whose classes are all the possible subsets of the domain of $M$.
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
What is the purpose of the parameters?
– Keshav Srinivasan
Jul 28 at 13:32
2
In order to ask whether a sentence such as $(exists x)phi(x)$ is true, we need to know whether $phi(a)$ is true for some $a in M$. So, even if we were only interested in the truth values of sentences without parameters, we are immediately led to look at the truth values of formulas with parameters. This is completely due to the meaning that the quantifiers $forall$ and $exists$ have.
– Carl Mummert
Jul 28 at 13:34
add a comment |Â
up vote
7
down vote
This is all very standard - here is an attempt to write something about it.
If we are talking about truth, we really want to talk about models, rather than about languages, because until we specify a model we don't have a notion of "true" at hand. We should avoid talking about the "truth predicate for a language".
For any model $M$ in a first-order language, the definition of the truth predicate of $M$ is the same - we define the elementary diagram of $M$ as the set of all sentences with parameters from $M$ that are true in $M$, using Tarski's recursive definition of truth, using the T schema. This is the same for a model of ZFC as for any other model in first-order logic.
A key aspect of the T schema is that it is recursive - it gives an inductive definition of the set of true sentences, but not an explicit definition.
Tarski's theorem on the undefinability of truth shows that, for many theories, there is no formula $textTrue(x)$ in the language of the theory so that, for every model $M$ of the theory and every formula $phi$, $textTrue(phi)$ holds in $M$ if and only if $phi$ holds in $M$. In particular, we could let the theory by PA or ZFC.
But there is a standard way to make an explicit definition of the truth, which works over every model of a given theory like ZFC of PA, by using a higher kind of quantifier. To do so, we first notice that the overall truth predicate of a model is stratified into a hierarchy by the number of alternations of quantifiers that the formula has in prenex normal form. This is analogous to the arithmetical hierarchy, but the formulas may now have parameters. In the case of ZFC these will be set parameters.
The base layer of this hierarchy consists of quantifier-free formulas with parameters. The next level consists of formulas that have one block of a single kind of leading quantifier, the third consists of formulas with two blocks of quantifiers at the front, etc. Call these levels $H_0$, $H_1$, etc.
For example, a formula $(exists x)phi(x)$ is true in a model $M$ if and only if $phi(a)$ is true for some $a in M$, in other words if and only if $phi(a) in H_0$ for some $a in M$. Similarly $(forall x)(exists y)psi(x,y)$ is true in $M$ if and only if $(exists y)psi(a,y)$ is in $H_1$ for every $a in M$.
There is a single second-order formula $tau$ that defines the sequence $(H_0, H_1, ldots)$ over a model $M$. This formula first defines $H_0$ explicitly, then says that for all $n$, an existential formula $(exists x)phi(x)$ is in $H_n+1$ if and only if there is some $a in M$ so that $phi(a)$ is in $H_n$. There are additional clauses for all the logical connectives, etc.
Using the formula $tau$, we can write an explicit second-order definition of the truth predicate: a formula with $n$ alternations of quantifiers is true if and only if, for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$, $phi$ is in $A_n$.
The reason that this does not give an explicit definition of the truth predicate in the original language is the parameters in the formulas. For example, if we work over any model $M$ of ZFC, $H_0$ is already a proper class of $M$ (among other things, it includes the formula $a = a$ for every $a in M$).
Thus, for ZFC, saying "for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$" requires quantifying over proper classes. This is exactly what the new quantifiers in second-order ZFC can do, so we can write an explicit definition of the truth predicate in second-order ZFC. If we call this definition $textTrue'(phi)$ we have this result: for every model $M$ of ZFC, if $M'$ is the expansion of $M$ to a full second-order model, and $phi$ is any sentence of ZFC, then $M$ satisfies $phi$ if and only if $M'$ satisfies $textTrue'(phi)$. Here the full expansion of $M$ is the second-order model whose classes are all the possible subsets of the domain of $M$.
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
What is the purpose of the parameters?
– Keshav Srinivasan
Jul 28 at 13:32
2
In order to ask whether a sentence such as $(exists x)phi(x)$ is true, we need to know whether $phi(a)$ is true for some $a in M$. So, even if we were only interested in the truth values of sentences without parameters, we are immediately led to look at the truth values of formulas with parameters. This is completely due to the meaning that the quantifiers $forall$ and $exists$ have.
– Carl Mummert
Jul 28 at 13:34
add a comment |Â
up vote
7
down vote
up vote
7
down vote
This is all very standard - here is an attempt to write something about it.
If we are talking about truth, we really want to talk about models, rather than about languages, because until we specify a model we don't have a notion of "true" at hand. We should avoid talking about the "truth predicate for a language".
For any model $M$ in a first-order language, the definition of the truth predicate of $M$ is the same - we define the elementary diagram of $M$ as the set of all sentences with parameters from $M$ that are true in $M$, using Tarski's recursive definition of truth, using the T schema. This is the same for a model of ZFC as for any other model in first-order logic.
A key aspect of the T schema is that it is recursive - it gives an inductive definition of the set of true sentences, but not an explicit definition.
Tarski's theorem on the undefinability of truth shows that, for many theories, there is no formula $textTrue(x)$ in the language of the theory so that, for every model $M$ of the theory and every formula $phi$, $textTrue(phi)$ holds in $M$ if and only if $phi$ holds in $M$. In particular, we could let the theory by PA or ZFC.
But there is a standard way to make an explicit definition of the truth, which works over every model of a given theory like ZFC of PA, by using a higher kind of quantifier. To do so, we first notice that the overall truth predicate of a model is stratified into a hierarchy by the number of alternations of quantifiers that the formula has in prenex normal form. This is analogous to the arithmetical hierarchy, but the formulas may now have parameters. In the case of ZFC these will be set parameters.
The base layer of this hierarchy consists of quantifier-free formulas with parameters. The next level consists of formulas that have one block of a single kind of leading quantifier, the third consists of formulas with two blocks of quantifiers at the front, etc. Call these levels $H_0$, $H_1$, etc.
For example, a formula $(exists x)phi(x)$ is true in a model $M$ if and only if $phi(a)$ is true for some $a in M$, in other words if and only if $phi(a) in H_0$ for some $a in M$. Similarly $(forall x)(exists y)psi(x,y)$ is true in $M$ if and only if $(exists y)psi(a,y)$ is in $H_1$ for every $a in M$.
There is a single second-order formula $tau$ that defines the sequence $(H_0, H_1, ldots)$ over a model $M$. This formula first defines $H_0$ explicitly, then says that for all $n$, an existential formula $(exists x)phi(x)$ is in $H_n+1$ if and only if there is some $a in M$ so that $phi(a)$ is in $H_n$. There are additional clauses for all the logical connectives, etc.
Using the formula $tau$, we can write an explicit second-order definition of the truth predicate: a formula with $n$ alternations of quantifiers is true if and only if, for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$, $phi$ is in $A_n$.
The reason that this does not give an explicit definition of the truth predicate in the original language is the parameters in the formulas. For example, if we work over any model $M$ of ZFC, $H_0$ is already a proper class of $M$ (among other things, it includes the formula $a = a$ for every $a in M$).
Thus, for ZFC, saying "for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$" requires quantifying over proper classes. This is exactly what the new quantifiers in second-order ZFC can do, so we can write an explicit definition of the truth predicate in second-order ZFC. If we call this definition $textTrue'(phi)$ we have this result: for every model $M$ of ZFC, if $M'$ is the expansion of $M$ to a full second-order model, and $phi$ is any sentence of ZFC, then $M$ satisfies $phi$ if and only if $M'$ satisfies $textTrue'(phi)$. Here the full expansion of $M$ is the second-order model whose classes are all the possible subsets of the domain of $M$.
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
This is all very standard - here is an attempt to write something about it.
If we are talking about truth, we really want to talk about models, rather than about languages, because until we specify a model we don't have a notion of "true" at hand. We should avoid talking about the "truth predicate for a language".
For any model $M$ in a first-order language, the definition of the truth predicate of $M$ is the same - we define the elementary diagram of $M$ as the set of all sentences with parameters from $M$ that are true in $M$, using Tarski's recursive definition of truth, using the T schema. This is the same for a model of ZFC as for any other model in first-order logic.
A key aspect of the T schema is that it is recursive - it gives an inductive definition of the set of true sentences, but not an explicit definition.
Tarski's theorem on the undefinability of truth shows that, for many theories, there is no formula $textTrue(x)$ in the language of the theory so that, for every model $M$ of the theory and every formula $phi$, $textTrue(phi)$ holds in $M$ if and only if $phi$ holds in $M$. In particular, we could let the theory by PA or ZFC.
But there is a standard way to make an explicit definition of the truth, which works over every model of a given theory like ZFC of PA, by using a higher kind of quantifier. To do so, we first notice that the overall truth predicate of a model is stratified into a hierarchy by the number of alternations of quantifiers that the formula has in prenex normal form. This is analogous to the arithmetical hierarchy, but the formulas may now have parameters. In the case of ZFC these will be set parameters.
The base layer of this hierarchy consists of quantifier-free formulas with parameters. The next level consists of formulas that have one block of a single kind of leading quantifier, the third consists of formulas with two blocks of quantifiers at the front, etc. Call these levels $H_0$, $H_1$, etc.
For example, a formula $(exists x)phi(x)$ is true in a model $M$ if and only if $phi(a)$ is true for some $a in M$, in other words if and only if $phi(a) in H_0$ for some $a in M$. Similarly $(forall x)(exists y)psi(x,y)$ is true in $M$ if and only if $(exists y)psi(a,y)$ is in $H_1$ for every $a in M$.
There is a single second-order formula $tau$ that defines the sequence $(H_0, H_1, ldots)$ over a model $M$. This formula first defines $H_0$ explicitly, then says that for all $n$, an existential formula $(exists x)phi(x)$ is in $H_n+1$ if and only if there is some $a in M$ so that $phi(a)$ is in $H_n$. There are additional clauses for all the logical connectives, etc.
Using the formula $tau$, we can write an explicit second-order definition of the truth predicate: a formula with $n$ alternations of quantifiers is true if and only if, for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$, $phi$ is in $A_n$.
The reason that this does not give an explicit definition of the truth predicate in the original language is the parameters in the formulas. For example, if we work over any model $M$ of ZFC, $H_0$ is already a proper class of $M$ (among other things, it includes the formula $a = a$ for every $a in M$).
Thus, for ZFC, saying "for every sequence $(A_0, A_1, ldots)$ that satisfies $tau$" requires quantifying over proper classes. This is exactly what the new quantifiers in second-order ZFC can do, so we can write an explicit definition of the truth predicate in second-order ZFC. If we call this definition $textTrue'(phi)$ we have this result: for every model $M$ of ZFC, if $M'$ is the expansion of $M$ to a full second-order model, and $phi$ is any sentence of ZFC, then $M$ satisfies $phi$ if and only if $M'$ satisfies $textTrue'(phi)$. Here the full expansion of $M$ is the second-order model whose classes are all the possible subsets of the domain of $M$.
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
edited Jul 27 at 19:26
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
answered Jul 27 at 19:15
Carl Mummert
63.6k7128236
63.6k7128236
What is the purpose of the parameters?
– Keshav Srinivasan
Jul 28 at 13:32
2
In order to ask whether a sentence such as $(exists x)phi(x)$ is true, we need to know whether $phi(a)$ is true for some $a in M$. So, even if we were only interested in the truth values of sentences without parameters, we are immediately led to look at the truth values of formulas with parameters. This is completely due to the meaning that the quantifiers $forall$ and $exists$ have.
– Carl Mummert
Jul 28 at 13:34
add a comment |Â
What is the purpose of the parameters?
– Keshav Srinivasan
Jul 28 at 13:32
2
In order to ask whether a sentence such as $(exists x)phi(x)$ is true, we need to know whether $phi(a)$ is true for some $a in M$. So, even if we were only interested in the truth values of sentences without parameters, we are immediately led to look at the truth values of formulas with parameters. This is completely due to the meaning that the quantifiers $forall$ and $exists$ have.
– Carl Mummert
Jul 28 at 13:34
What is the purpose of the parameters?
– Keshav Srinivasan
Jul 28 at 13:32
What is the purpose of the parameters?
– Keshav Srinivasan
Jul 28 at 13:32
2
2
In order to ask whether a sentence such as $(exists x)phi(x)$ is true, we need to know whether $phi(a)$ is true for some $a in M$. So, even if we were only interested in the truth values of sentences without parameters, we are immediately led to look at the truth values of formulas with parameters. This is completely due to the meaning that the quantifiers $forall$ and $exists$ have.
– Carl Mummert
Jul 28 at 13:34
In order to ask whether a sentence such as $(exists x)phi(x)$ is true, we need to know whether $phi(a)$ is true for some $a in M$. So, even if we were only interested in the truth values of sentences without parameters, we are immediately led to look at the truth values of formulas with parameters. This is completely due to the meaning that the quantifiers $forall$ and $exists$ have.
– Carl Mummert
Jul 28 at 13:34
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864423%2fwhat-is-the-truth-predicate-of-zfc%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
That's an odd question. The truth predicate is... a truth predicate. it tells you which sentences are true.
– Asaf Karagila
Jul 27 at 14:38
1
You're not aware of how you code logic into set theory? You don't understand what does it mean for something to be true? What is it that you think you're missing?
– Asaf Karagila
Jul 27 at 14:57
1
@AsafKaragila I think the OP is talking about Traski's undefinability theorem and that by truth predicate he means the predicate $mathrmtruth(x)$ that holds only for the encodings of arithmetic formulas that hold in $mathbb N$, or to be exact an analogous predicate for ZFC.
– Giorgio Mossa
Jul 27 at 16:24
2
@Giorgio: Yes, I am very clear about that. I'm just confused as to what exactly confuses the OP.
– Asaf Karagila
Jul 27 at 16:25
2
Yes, that is a different question than the one in your previous comment (and it makes less sense).
– Andrés E. Caicedo
Jul 27 at 21:46