Mixing
Where is the mistake in this “proof†of the inconsistency of ZFC?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
This is a "proof" that ZFC is inconsistent, but I haven't found the mistake yet.
Let $varphi_n colon n <omega$ be an enumeration of all formulas in $L_in$ with exactly one free variable. Consider the formula
$$psi(x) equiv x in omega land lnot varphi_x(x) , .$$
Since $psi$ is a formula with one free variable, then $psi$ is $varphi_k$ for some $k$. But then,
$$mathrmZFC vdash varphi_k(k) leftrightarrow psi(k) leftrightarrow lnot varphi_k(k)$$
I have been giving this a lot of time, but I still cannot figure out the error on the fake proof here. Can anyone give me a clue?
logic set-theory fake-proofs
edited 30 mins ago
Derek Elkins
15.6k11035
asked 3 hours ago
user313212
221519
 |Â
show 1 more comment
up vote
1
down vote
favorite
This is a "proof" that ZFC is inconsistent, but I haven't found the mistake yet.
Let $varphi_n colon n <omega$ be an enumeration of all formulas in $L_in$ with exactly one free variable. Consider the formula
$$psi(x) equiv x in omega land lnot varphi_x(x) , .$$
Since $psi$ is a formula with one free variable, then $psi$ is $varphi_k$ for some $k$. But then,
$$mathrmZFC vdash varphi_k(k) leftrightarrow psi(k) leftrightarrow lnot varphi_k(k)$$
I have been giving this a lot of time, but I still cannot figure out the error on the fake proof here. Can anyone give me a clue?
logic set-theory fake-proofs
edited 30 mins ago
Derek Elkins
15.6k11035
asked 3 hours ago
user313212
221519
1
$psi$ is not a single formula. The term $neg phi_x(x)$ is effectively a different formula for every $x$. I suspect this has something to do with it - in particular I think some form of diagonalization-like reasoning will show that $psi(x)$ is not such a $phi_k$.
– The_Sympathizer
3 hours ago
What is your definition of 'formula'? Since you're talking about a formal logical result, a naive definition that a formula is just a string of symbols isn't sufficient here...
– Steven Stadnicki
3 hours ago
1
There's a language/metalanguage mixup going on here. The you're using a variable of your metalanguage (the $x$ that ranges over natural numbers) as a variable of your object language, which is just plain mischief.
– Malice Vidrine
2 hours ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
2 hours ago
1
This is pretty close to Richard's paradox -- in fact arguably it is Richard's paradox, given the usual set-theoretic convention that identifies "real number" with "subset of $omega$" -- at least as long as you're not giving a specific argument for how "$varphi_x(y)$" is supposed to be a concrete formula in the language of set theory with free variables $x$ and $y$.
– Henning Makholm
2 hours ago
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This is a "proof" that ZFC is inconsistent, but I haven't found the mistake yet.
Let $varphi_n colon n <omega$ be an enumeration of all formulas in $L_in$ with exactly one free variable. Consider the formula
$$psi(x) equiv x in omega land lnot varphi_x(x) , .$$
Since $psi$ is a formula with one free variable, then $psi$ is $varphi_k$ for some $k$. But then,
$$mathrmZFC vdash varphi_k(k) leftrightarrow psi(k) leftrightarrow lnot varphi_k(k)$$
I have been giving this a lot of time, but I still cannot figure out the error on the fake proof here. Can anyone give me a clue?
logic set-theory fake-proofs
edited 30 mins ago
Derek Elkins
15.6k11035
asked 3 hours ago
user313212
221519
This is a "proof" that ZFC is inconsistent, but I haven't found the mistake yet.
Let $varphi_n colon n <omega$ be an enumeration of all formulas in $L_in$ with exactly one free variable. Consider the formula
$$psi(x) equiv x in omega land lnot varphi_x(x) , .$$
Since $psi$ is a formula with one free variable, then $psi$ is $varphi_k$ for some $k$. But then,
$$mathrmZFC vdash varphi_k(k) leftrightarrow psi(k) leftrightarrow lnot varphi_k(k)$$
I have been giving this a lot of time, but I still cannot figure out the error on the fake proof here. Can anyone give me a clue?
logic set-theory fake-proofs
logic set-theory fake-proofs
edited 30 mins ago
Derek Elkins
15.6k11035
asked 3 hours ago
user313212
221519
edited 30 mins ago
Derek Elkins
15.6k11035
asked 3 hours ago
user313212
221519
edited 30 mins ago
Derek Elkins
15.6k11035
edited 30 mins ago
Derek Elkins
15.6k11035
edited 30 mins ago
Derek Elkins
15.6k11035
15.6k11035
asked 3 hours ago
user313212
221519
asked 3 hours ago
user313212
221519
asked 3 hours ago
user313212
221519
221519
1
$psi$ is not a single formula. The term $neg phi_x(x)$ is effectively a different formula for every $x$. I suspect this has something to do with it - in particular I think some form of diagonalization-like reasoning will show that $psi(x)$ is not such a $phi_k$.
– The_Sympathizer
3 hours ago
What is your definition of 'formula'? Since you're talking about a formal logical result, a naive definition that a formula is just a string of symbols isn't sufficient here...
– Steven Stadnicki
3 hours ago
1
There's a language/metalanguage mixup going on here. The you're using a variable of your metalanguage (the $x$ that ranges over natural numbers) as a variable of your object language, which is just plain mischief.
– Malice Vidrine
2 hours ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
2 hours ago
1
This is pretty close to Richard's paradox -- in fact arguably it is Richard's paradox, given the usual set-theoretic convention that identifies "real number" with "subset of $omega$" -- at least as long as you're not giving a specific argument for how "$varphi_x(y)$" is supposed to be a concrete formula in the language of set theory with free variables $x$ and $y$.
– Henning Makholm
2 hours ago
 |Â
show 1 more comment
1
$psi$ is not a single formula. The term $neg phi_x(x)$ is effectively a different formula for every $x$. I suspect this has something to do with it - in particular I think some form of diagonalization-like reasoning will show that $psi(x)$ is not such a $phi_k$.
– The_Sympathizer
3 hours ago
What is your definition of 'formula'? Since you're talking about a formal logical result, a naive definition that a formula is just a string of symbols isn't sufficient here...
– Steven Stadnicki
3 hours ago
1
There's a language/metalanguage mixup going on here. The you're using a variable of your metalanguage (the $x$ that ranges over natural numbers) as a variable of your object language, which is just plain mischief.
– Malice Vidrine
2 hours ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
2 hours ago
1
This is pretty close to Richard's paradox -- in fact arguably it is Richard's paradox, given the usual set-theoretic convention that identifies "real number" with "subset of $omega$" -- at least as long as you're not giving a specific argument for how "$varphi_x(y)$" is supposed to be a concrete formula in the language of set theory with free variables $x$ and $y$.
– Henning Makholm
2 hours ago
1
1
$psi$ is not a single formula. The term $neg phi_x(x)$ is effectively a different formula for every $x$. I suspect this has something to do with it - in particular I think some form of diagonalization-like reasoning will show that $psi(x)$ is not such a $phi_k$.
– The_Sympathizer
3 hours ago
$psi$ is not a single formula. The term $neg phi_x(x)$ is effectively a different formula for every $x$. I suspect this has something to do with it - in particular I think some form of diagonalization-like reasoning will show that $psi(x)$ is not such a $phi_k$.
– The_Sympathizer
3 hours ago
What is your definition of 'formula'? Since you're talking about a formal logical result, a naive definition that a formula is just a string of symbols isn't sufficient here...
– Steven Stadnicki
3 hours ago
What is your definition of 'formula'? Since you're talking about a formal logical result, a naive definition that a formula is just a string of symbols isn't sufficient here...
– Steven Stadnicki
3 hours ago
1
1
There's a language/metalanguage mixup going on here. The you're using a variable of your metalanguage (the $x$ that ranges over natural numbers) as a variable of your object language, which is just plain mischief.
– Malice Vidrine
2 hours ago
There's a language/metalanguage mixup going on here. The you're using a variable of your metalanguage (the $x$ that ranges over natural numbers) as a variable of your object language, which is just plain mischief.
– Malice Vidrine
2 hours ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
2 hours ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
2 hours ago
1
1
This is pretty close to Richard's paradox -- in fact arguably it is Richard's paradox, given the usual set-theoretic convention that identifies "real number" with "subset of $omega$" -- at least as long as you're not giving a specific argument for how "$varphi_x(y)$" is supposed to be a concrete formula in the language of set theory with free variables $x$ and $y$.
– Henning Makholm
2 hours ago
This is pretty close to Richard's paradox -- in fact arguably it is Richard's paradox, given the usual set-theoretic convention that identifies "real number" with "subset of $omega$" -- at least as long as you're not giving a specific argument for how "$varphi_x(y)$" is supposed to be a concrete formula in the language of set theory with free variables $x$ and $y$.
– Henning Makholm
2 hours ago
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
up vote
8
down vote
The issue is there's no way to write $varphi_n(x)$ uniformly in ZFC via a single formula $phi(n,x)$. If you wanted a way to enumerate the unary formulas of $L_in$ in ZFC then they won't be in the representation you want here, rather they'd be in the form of Godel numbering. Then if ZFC could prove the schema $mathsfProv(lceilvarphi_nrceil)tovarphi_n$ for each $n$ then it would be indeed be inconsistent. This all holds for far weaker than ZFC as well.
answered 2 hours ago
user122495
1012
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
4
down vote
As others have suggested, the key is to think about how we would actually go about writing down the predicate $psi(x)$ in the language of set theory. The "$n$" in $varphi_n$ is in the metatheory, so on its face, you really can't.
The best you could hope for is to write something equivalent to this, through formalization of syntax. You can certainly formalize and enumerate the one-variable formulas of $L_in$ in set theory, and formalize the substitution of a set parameter for a variable. Then you want to write something like "$kinomega$ and $varphi_k(k) $ holds."
It's the "$varphi_k(k)$ holds" part that is problematic. It requires we have a truth predicate that expresses the notion of a sentence holding. So another way of looking at what you've written is as a proof that a truth predicate does not exist. This is Tarski's theorem.
answered 2 hours ago
spaceisdarkgreen
30.3k21550
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
The issue is there's no way to write $varphi_n(x)$ uniformly in ZFC via a single formula $phi(n,x)$. If you wanted a way to enumerate the unary formulas of $L_in$ in ZFC then they won't be in the representation you want here, rather they'd be in the form of Godel numbering. Then if ZFC could prove the schema $mathsfProv(lceilvarphi_nrceil)tovarphi_n$ for each $n$ then it would be indeed be inconsistent. This all holds for far weaker than ZFC as well.
answered 2 hours ago
user122495
1012
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
8
down vote
The issue is there's no way to write $varphi_n(x)$ uniformly in ZFC via a single formula $phi(n,x)$. If you wanted a way to enumerate the unary formulas of $L_in$ in ZFC then they won't be in the representation you want here, rather they'd be in the form of Godel numbering. Then if ZFC could prove the schema $mathsfProv(lceilvarphi_nrceil)tovarphi_n$ for each $n$ then it would be indeed be inconsistent. This all holds for far weaker than ZFC as well.
answered 2 hours ago
user122495
1012
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
8
down vote
up vote
8
down vote
The issue is there's no way to write $varphi_n(x)$ uniformly in ZFC via a single formula $phi(n,x)$. If you wanted a way to enumerate the unary formulas of $L_in$ in ZFC then they won't be in the representation you want here, rather they'd be in the form of Godel numbering. Then if ZFC could prove the schema $mathsfProv(lceilvarphi_nrceil)tovarphi_n$ for each $n$ then it would be indeed be inconsistent. This all holds for far weaker than ZFC as well.
answered 2 hours ago
user122495
1012
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
The issue is there's no way to write $varphi_n(x)$ uniformly in ZFC via a single formula $phi(n,x)$. If you wanted a way to enumerate the unary formulas of $L_in$ in ZFC then they won't be in the representation you want here, rather they'd be in the form of Godel numbering. Then if ZFC could prove the schema $mathsfProv(lceilvarphi_nrceil)tovarphi_n$ for each $n$ then it would be indeed be inconsistent. This all holds for far weaker than ZFC as well.
answered 2 hours ago
user122495
1012
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 hours ago
user122495
1012
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 hours ago
user122495
1012
answered 2 hours ago
user122495
1012
1012
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
user122495 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
up vote
4
down vote
As others have suggested, the key is to think about how we would actually go about writing down the predicate $psi(x)$ in the language of set theory. The "$n$" in $varphi_n$ is in the metatheory, so on its face, you really can't.
The best you could hope for is to write something equivalent to this, through formalization of syntax. You can certainly formalize and enumerate the one-variable formulas of $L_in$ in set theory, and formalize the substitution of a set parameter for a variable. Then you want to write something like "$kinomega$ and $varphi_k(k) $ holds."
It's the "$varphi_k(k)$ holds" part that is problematic. It requires we have a truth predicate that expresses the notion of a sentence holding. So another way of looking at what you've written is as a proof that a truth predicate does not exist. This is Tarski's theorem.
answered 2 hours ago
spaceisdarkgreen
30.3k21550
add a comment |Â
up vote
4
down vote
As others have suggested, the key is to think about how we would actually go about writing down the predicate $psi(x)$ in the language of set theory. The "$n$" in $varphi_n$ is in the metatheory, so on its face, you really can't.
The best you could hope for is to write something equivalent to this, through formalization of syntax. You can certainly formalize and enumerate the one-variable formulas of $L_in$ in set theory, and formalize the substitution of a set parameter for a variable. Then you want to write something like "$kinomega$ and $varphi_k(k) $ holds."
It's the "$varphi_k(k)$ holds" part that is problematic. It requires we have a truth predicate that expresses the notion of a sentence holding. So another way of looking at what you've written is as a proof that a truth predicate does not exist. This is Tarski's theorem.
answered 2 hours ago
spaceisdarkgreen
30.3k21550
add a comment |Â
up vote
4
down vote
up vote
4
down vote
As others have suggested, the key is to think about how we would actually go about writing down the predicate $psi(x)$ in the language of set theory. The "$n$" in $varphi_n$ is in the metatheory, so on its face, you really can't.
The best you could hope for is to write something equivalent to this, through formalization of syntax. You can certainly formalize and enumerate the one-variable formulas of $L_in$ in set theory, and formalize the substitution of a set parameter for a variable. Then you want to write something like "$kinomega$ and $varphi_k(k) $ holds."
It's the "$varphi_k(k)$ holds" part that is problematic. It requires we have a truth predicate that expresses the notion of a sentence holding. So another way of looking at what you've written is as a proof that a truth predicate does not exist. This is Tarski's theorem.
answered 2 hours ago
spaceisdarkgreen
30.3k21550
As others have suggested, the key is to think about how we would actually go about writing down the predicate $psi(x)$ in the language of set theory. The "$n$" in $varphi_n$ is in the metatheory, so on its face, you really can't.
The best you could hope for is to write something equivalent to this, through formalization of syntax. You can certainly formalize and enumerate the one-variable formulas of $L_in$ in set theory, and formalize the substitution of a set parameter for a variable. Then you want to write something like "$kinomega$ and $varphi_k(k) $ holds."
It's the "$varphi_k(k)$ holds" part that is problematic. It requires we have a truth predicate that expresses the notion of a sentence holding. So another way of looking at what you've written is as a proof that a truth predicate does not exist. This is Tarski's theorem.
answered 2 hours ago
spaceisdarkgreen
30.3k21550
answered 2 hours ago
spaceisdarkgreen
30.3k21550
answered 2 hours ago
spaceisdarkgreen
30.3k21550
answered 2 hours ago
spaceisdarkgreen
30.3k21550
30.3k21550
add a comment |Â
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%2f2976937%2fwhere-is-the-mistake-in-this-proof-of-the-inconsistency-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
$psi$ is not a single formula. The term $neg phi_x(x)$ is effectively a different formula for every $x$. I suspect this has something to do with it - in particular I think some form of diagonalization-like reasoning will show that $psi(x)$ is not such a $phi_k$.
– The_Sympathizer
3 hours ago
What is your definition of 'formula'? Since you're talking about a formal logical result, a naive definition that a formula is just a string of symbols isn't sufficient here...
– Steven Stadnicki
3 hours ago
1
There's a language/metalanguage mixup going on here. The you're using a variable of your metalanguage (the $x$ that ranges over natural numbers) as a variable of your object language, which is just plain mischief.
– Malice Vidrine
2 hours ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
2 hours ago
1
This is pretty close to Richard's paradox -- in fact arguably it is Richard's paradox, given the usual set-theoretic convention that identifies "real number" with "subset of $omega$" -- at least as long as you're not giving a specific argument for how "$varphi_x(y)$" is supposed to be a concrete formula in the language of set theory with free variables $x$ and $y$.
– Henning Makholm
2 hours ago