Mixing
ZFC is inconsistent.
Clash Royale CLAN TAG#URR8PPP
up vote
2
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 33 mins ago
Derek Elkins
15.6k11035
asked 1 hour ago
user313212
223519
add a comment |Â
up vote
2
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 33 mins ago
Derek Elkins
15.6k11035
asked 1 hour ago
user313212
223519
$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
1 hour 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
1 hour 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
1 hour ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
1 hour 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
52 mins ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
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 33 mins ago
Derek Elkins
15.6k11035
asked 1 hour ago
user313212
223519
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 33 mins ago
Derek Elkins
15.6k11035
asked 1 hour ago
user313212
223519
edited 33 mins ago
Derek Elkins
15.6k11035
asked 1 hour ago
user313212
223519
edited 33 mins ago
Derek Elkins
15.6k11035
edited 33 mins ago
Derek Elkins
15.6k11035
edited 33 mins ago
Derek Elkins
15.6k11035
15.6k11035
asked 1 hour ago
user313212
223519
asked 1 hour ago
user313212
223519
asked 1 hour ago
user313212
223519
223519
$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
1 hour 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
1 hour 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
1 hour ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
1 hour 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
52 mins ago
add a comment |Â
$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
1 hour 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
1 hour 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
1 hour ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
1 hour 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
52 mins 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
1 hour 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
1 hour 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
1 hour 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
1 hour 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
1 hour 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
1 hour ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
1 hour ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
1 hour 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
52 mins 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
52 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
5
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 1 hour ago
user122495
712
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
2
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 37 mins 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
5
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 1 hour ago
user122495
712
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
5
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 1 hour ago
user122495
712
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
5
down vote
up vote
5
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 1 hour ago
user122495
712
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 1 hour ago
user122495
712
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 1 hour ago
user122495
712
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 1 hour ago
user122495
712
answered 1 hour ago
user122495
712
712
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
2
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 37 mins ago
spaceisdarkgreen
30.3k21550
add a comment |Â
up vote
2
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 37 mins ago
spaceisdarkgreen
30.3k21550
add a comment |Â
up vote
2
down vote
up vote
2
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 37 mins 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 37 mins ago
spaceisdarkgreen
30.3k21550
answered 37 mins ago
spaceisdarkgreen
30.3k21550
answered 37 mins ago
spaceisdarkgreen
30.3k21550
answered 37 mins 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%2fzfc-is-inconsistent%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
$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
1 hour 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
1 hour 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
1 hour ago
Suppose $varphi$ was a lexicographical enumeration of unary formulas. What would $psi$ look like? How many symbols long would it be?
– DanielV
1 hour 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
52 mins ago