Mixing
![Double sum misunderstanding - $sum_n=2^infty frac1n! sum_k=0^infty frac(k+2)cdots(k+n)k! z^n$. [on hold]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Reconstruction of FOL language
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
If we have a FOL language $S$ and we suddenly lost its logical structure $left(rightarrow,wedge,vee,bot,top,forall x,exists xright)$, can we recover it (modulo a logical equivalence) using only the logical consequence relation: $models$ ?
Let's consider $S$ the set of formulas of a first order logic and $bar S$ its quotient set by the logical equivalence relation ($equiv$).
All logical connectives over $bar S$ can be obviously expressed using only $models$, for example: $$bar prightarrowbar q=leftrin S $$
Now, and in order to reconstruct quantifiers, let's consider the following set :
$$ Pi = leftpiinbig(bar S^bar Sbig)^* middlevert beginarrayl
forall pinbar S, (pi pmodels p)wedge(pi pi p=pi p) \
forall p,qinbar S, pi (pi prightarrowpi q)=pi prightarrowpi q\
forall pinbar S,Gammasubseteqbar S,Gammamodels pRightarrow pi Gamma models pi p
endarrayright $$
I think that elements of $Pi_e=leftpiinPi,exists!left(pi_1,pi_2right)inPi^2,pi=pi_1circpi_2right$ are universal quantifiers (i.e.
$ pmapstoforall x, p[aleftarrow x] $ where $x$ doesn't occur in $p$ and $a$ is a variable or a constant) plus circular substitutions conjunctions: $$pmapstobigwedge_i<npleft[x_0leftarrow x_i,...,x_kleftarrow x_(k+i mod n),...,x_n-1leftarrow x_(n-1+i mod n)right]$$
Where $(x_i)_i$ can be variables, functions or relations of the same arity.
Is this claim true in intuitionist FOL and in classic FOL ?
If the hole subject is already discussed, could someone please refer me to appropriate articles, and thanks a lot.
EDIT: To be more clear, I'm asking about recovering the logical signature up to a logical equivalence. So we can determine some relation between formulas equivalence classes like: $overlineforall x, P(x)$ is a result of an application of universal quantifier on $overlineP(x)$ while $overlineP(x)wedge Q(x)$ is not.
EDIT: And since this is not possible in general, is it possible at least when the non logical signature is finite and contains at least one non-zero arity relation and one non-zero arity function ?
logic first-order-logic quantifiers
asked Jul 28 at 18:34
Ahmed Lazhar
618
add a comment |Â
up vote
3
down vote
favorite
If we have a FOL language $S$ and we suddenly lost its logical structure $left(rightarrow,wedge,vee,bot,top,forall x,exists xright)$, can we recover it (modulo a logical equivalence) using only the logical consequence relation: $models$ ?
Let's consider $S$ the set of formulas of a first order logic and $bar S$ its quotient set by the logical equivalence relation ($equiv$).
All logical connectives over $bar S$ can be obviously expressed using only $models$, for example: $$bar prightarrowbar q=leftrin S $$
Now, and in order to reconstruct quantifiers, let's consider the following set :
$$ Pi = leftpiinbig(bar S^bar Sbig)^* middlevert beginarrayl
forall pinbar S, (pi pmodels p)wedge(pi pi p=pi p) \
forall p,qinbar S, pi (pi prightarrowpi q)=pi prightarrowpi q\
forall pinbar S,Gammasubseteqbar S,Gammamodels pRightarrow pi Gamma models pi p
endarrayright $$
I think that elements of $Pi_e=leftpiinPi,exists!left(pi_1,pi_2right)inPi^2,pi=pi_1circpi_2right$ are universal quantifiers (i.e.
$ pmapstoforall x, p[aleftarrow x] $ where $x$ doesn't occur in $p$ and $a$ is a variable or a constant) plus circular substitutions conjunctions: $$pmapstobigwedge_i<npleft[x_0leftarrow x_i,...,x_kleftarrow x_(k+i mod n),...,x_n-1leftarrow x_(n-1+i mod n)right]$$
Where $(x_i)_i$ can be variables, functions or relations of the same arity.
Is this claim true in intuitionist FOL and in classic FOL ?
If the hole subject is already discussed, could someone please refer me to appropriate articles, and thanks a lot.
EDIT: To be more clear, I'm asking about recovering the logical signature up to a logical equivalence. So we can determine some relation between formulas equivalence classes like: $overlineforall x, P(x)$ is a result of an application of universal quantifier on $overlineP(x)$ while $overlineP(x)wedge Q(x)$ is not.
EDIT: And since this is not possible in general, is it possible at least when the non logical signature is finite and contains at least one non-zero arity relation and one non-zero arity function ?
logic first-order-logic quantifiers
asked Jul 28 at 18:34
Ahmed Lazhar
618
Note that you seem to be juggling between sentences and formulas a bit, here; it ultimately makes no difference, but working with sentences only makes things messier (since in general $forall xvarphi(x)$ can be a sentence without $varphi(x)$ being a sentence).
– Noah Schweber
Jul 28 at 19:20
Yes, you have reason, I'm sorry for that mistake.
– Ahmed Lazhar
Jul 28 at 19:31
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
If we have a FOL language $S$ and we suddenly lost its logical structure $left(rightarrow,wedge,vee,bot,top,forall x,exists xright)$, can we recover it (modulo a logical equivalence) using only the logical consequence relation: $models$ ?
Let's consider $S$ the set of formulas of a first order logic and $bar S$ its quotient set by the logical equivalence relation ($equiv$).
All logical connectives over $bar S$ can be obviously expressed using only $models$, for example: $$bar prightarrowbar q=leftrin S $$
Now, and in order to reconstruct quantifiers, let's consider the following set :
$$ Pi = leftpiinbig(bar S^bar Sbig)^* middlevert beginarrayl
forall pinbar S, (pi pmodels p)wedge(pi pi p=pi p) \
forall p,qinbar S, pi (pi prightarrowpi q)=pi prightarrowpi q\
forall pinbar S,Gammasubseteqbar S,Gammamodels pRightarrow pi Gamma models pi p
endarrayright $$
I think that elements of $Pi_e=leftpiinPi,exists!left(pi_1,pi_2right)inPi^2,pi=pi_1circpi_2right$ are universal quantifiers (i.e.
$ pmapstoforall x, p[aleftarrow x] $ where $x$ doesn't occur in $p$ and $a$ is a variable or a constant) plus circular substitutions conjunctions: $$pmapstobigwedge_i<npleft[x_0leftarrow x_i,...,x_kleftarrow x_(k+i mod n),...,x_n-1leftarrow x_(n-1+i mod n)right]$$
Where $(x_i)_i$ can be variables, functions or relations of the same arity.
Is this claim true in intuitionist FOL and in classic FOL ?
If the hole subject is already discussed, could someone please refer me to appropriate articles, and thanks a lot.
EDIT: To be more clear, I'm asking about recovering the logical signature up to a logical equivalence. So we can determine some relation between formulas equivalence classes like: $overlineforall x, P(x)$ is a result of an application of universal quantifier on $overlineP(x)$ while $overlineP(x)wedge Q(x)$ is not.
EDIT: And since this is not possible in general, is it possible at least when the non logical signature is finite and contains at least one non-zero arity relation and one non-zero arity function ?
logic first-order-logic quantifiers
asked Jul 28 at 18:34
Ahmed Lazhar
618
If we have a FOL language $S$ and we suddenly lost its logical structure $left(rightarrow,wedge,vee,bot,top,forall x,exists xright)$, can we recover it (modulo a logical equivalence) using only the logical consequence relation: $models$ ?
Let's consider $S$ the set of formulas of a first order logic and $bar S$ its quotient set by the logical equivalence relation ($equiv$).
All logical connectives over $bar S$ can be obviously expressed using only $models$, for example: $$bar prightarrowbar q=leftrin S $$
Now, and in order to reconstruct quantifiers, let's consider the following set :
$$ Pi = leftpiinbig(bar S^bar Sbig)^* middlevert beginarrayl
forall pinbar S, (pi pmodels p)wedge(pi pi p=pi p) \
forall p,qinbar S, pi (pi prightarrowpi q)=pi prightarrowpi q\
forall pinbar S,Gammasubseteqbar S,Gammamodels pRightarrow pi Gamma models pi p
endarrayright $$
I think that elements of $Pi_e=leftpiinPi,exists!left(pi_1,pi_2right)inPi^2,pi=pi_1circpi_2right$ are universal quantifiers (i.e.
$ pmapstoforall x, p[aleftarrow x] $ where $x$ doesn't occur in $p$ and $a$ is a variable or a constant) plus circular substitutions conjunctions: $$pmapstobigwedge_i<npleft[x_0leftarrow x_i,...,x_kleftarrow x_(k+i mod n),...,x_n-1leftarrow x_(n-1+i mod n)right]$$
Where $(x_i)_i$ can be variables, functions or relations of the same arity.
Is this claim true in intuitionist FOL and in classic FOL ?
If the hole subject is already discussed, could someone please refer me to appropriate articles, and thanks a lot.
EDIT: To be more clear, I'm asking about recovering the logical signature up to a logical equivalence. So we can determine some relation between formulas equivalence classes like: $overlineforall x, P(x)$ is a result of an application of universal quantifier on $overlineP(x)$ while $overlineP(x)wedge Q(x)$ is not.
EDIT: And since this is not possible in general, is it possible at least when the non logical signature is finite and contains at least one non-zero arity relation and one non-zero arity function ?
logic first-order-logic quantifiers
asked Jul 28 at 18:34
Ahmed Lazhar
618
edited Jul 29 at 7:19
asked Jul 28 at 18:34
Ahmed Lazhar
618
asked Jul 28 at 18:34
Ahmed Lazhar
618
asked Jul 28 at 18:34
Ahmed Lazhar
618
618
Note that you seem to be juggling between sentences and formulas a bit, here; it ultimately makes no difference, but working with sentences only makes things messier (since in general $forall xvarphi(x)$ can be a sentence without $varphi(x)$ being a sentence).
– Noah Schweber
Jul 28 at 19:20
Yes, you have reason, I'm sorry for that mistake.
– Ahmed Lazhar
Jul 28 at 19:31
add a comment |Â
Note that you seem to be juggling between sentences and formulas a bit, here; it ultimately makes no difference, but working with sentences only makes things messier (since in general $forall xvarphi(x)$ can be a sentence without $varphi(x)$ being a sentence).
– Noah Schweber
Jul 28 at 19:20
Yes, you have reason, I'm sorry for that mistake.
– Ahmed Lazhar
Jul 28 at 19:31
Note that you seem to be juggling between sentences and formulas a bit, here; it ultimately makes no difference, but working with sentences only makes things messier (since in general $forall xvarphi(x)$ can be a sentence without $varphi(x)$ being a sentence).
– Noah Schweber
Jul 28 at 19:20
Note that you seem to be juggling between sentences and formulas a bit, here; it ultimately makes no difference, but working with sentences only makes things messier (since in general $forall xvarphi(x)$ can be a sentence without $varphi(x)$ being a sentence).
– Noah Schweber
Jul 28 at 19:20
Yes, you have reason, I'm sorry for that mistake.
– Ahmed Lazhar
Jul 28 at 19:31
Yes, you have reason, I'm sorry for that mistake.
– Ahmed Lazhar
Jul 28 at 19:31
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
EDIT: Formulas make the situation even easier: any permutation of the variables induces an automorphism of $mathcalB$. For this reason I've left my answer mostly as is, since the interesting situation is when we restrict attention to sentences.
(The above assumes that we don't identify a formula with its universal closure; if we do, then the situation is the same as for sentences since every formula is equivalent to a sentence, namely its universal closure.)
No, you cannot do this in general: when we look at the Boolean algebra $mathcalB$ of semantic equivalence classes of $S$-sentences (which is what you're left with when you forget everything except "$models$" - incidentally, this is the Lindenbaum algebra of the empty theory over $S$), this algebra has lots of nontrivial automorphisms - these will send sentences to non-equivalent sentences while preserving the $models$-structure.
Under weak hypotheses on $S$ (let's assume $S$ is countable for now) we can prove this quickly. If $S$ contains two distinct symbols of the same type (e.g. two constant symbols, or two $17$-ary relation symbols, or etc.), then swapping them induces a nontrivial automorphism of $mathcalB$. More complicatedly, if $S$ is infinite then $mathcalB$ is a countable atomless Boolean algebra, and these are homogeneous (given any two elements neither of which is $0$ or $1$, there is an automorphism swapping them); this is proved by a back-and-forth argument, similar to that presented in this proof that any two countable atomless Boolean algebras are isomorphic. Similarly, if $S=emptyset$ then any permutation of the sentences of the form "there are exactly $n$ elements" induces an automorphism of $mathcalB$.
I believe in fact that we can never perform the reconstruction you want, but I don't have a proof of that yet. Note in particular that we can produces examples of $S$ where some elements of $mathcalB$ are atoms but other elements don't lie above any atoms, so it's neither atomless nor "atomful;" this complicates the picture a bit.
The picture for intuitionistic logic will be similar, except with Heyting algebras taking the role of Boolean algebras. In general, any logic allowing a significant amount of reconstruction along the lines you're proposing would have to be very "algebraically restrictive" (in the sense of algebraic logic), and I'm not aware of any natural such logics.
answered Jul 28 at 18:58
Noah Schweber
110k9139260
Thank you for your answer. In fact, I have made a mistake, I wrote sentences instead of formulas. Can you please, see it again :)
– Ahmed Lazhar
Jul 28 at 19:29
@AhmedLazhar: That doesn't really change anything, because usually we consider a non-sentence formula and its universal closure to entail each other. So each of the equivalence classes are going to contain some sentences anyway.
– Henning Makholm
Jul 28 at 19:33
@HenningMakholm I'm not sure how usual that is. I think things are almost always more interesting without it. It certainly makes quantification nicer, since $forall xP(x)$ and $forall xP(y)$ are inequivalent even though the universal closures of $P(x)$ and $P(y)$ are equivalent.
– Noah Schweber
Jul 28 at 20:27
@NoahSchweber, And what if the signature is finite ? For example, let's consider our signature with two relations $P(x)$ and $R(x,y)$ then $forall xforall y(P(x)wedge Q(x,y)wedge x=y)$ is an atom. If the logic is not with equality or we required the existence of infinity of elements, then $forall xforall y(P(x)wedge Q(x,y))$ would be an atom. Is that true ? In that case what can be the elements of my $Pi$ ? I have to mention that what I'm looking for is to reconstruct the logical signature. There is no problem if I swap two symbols as long as the hole sentence structure is recovered.
– Ahmed Lazhar
Jul 29 at 6:45
Even if we add $negforall xforall y(P(x)wedge R(x,y))$ as an axiom, can't we take as atom $forall xforall yne a(P(x)wedge R(x,y))$ if the logic is with equality and $forall xforall y(P(x)wedge R(x,f(y)))$ otherwise ?
– Ahmed Lazhar
Jul 29 at 7:12
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
EDIT: Formulas make the situation even easier: any permutation of the variables induces an automorphism of $mathcalB$. For this reason I've left my answer mostly as is, since the interesting situation is when we restrict attention to sentences.
(The above assumes that we don't identify a formula with its universal closure; if we do, then the situation is the same as for sentences since every formula is equivalent to a sentence, namely its universal closure.)
No, you cannot do this in general: when we look at the Boolean algebra $mathcalB$ of semantic equivalence classes of $S$-sentences (which is what you're left with when you forget everything except "$models$" - incidentally, this is the Lindenbaum algebra of the empty theory over $S$), this algebra has lots of nontrivial automorphisms - these will send sentences to non-equivalent sentences while preserving the $models$-structure.
Under weak hypotheses on $S$ (let's assume $S$ is countable for now) we can prove this quickly. If $S$ contains two distinct symbols of the same type (e.g. two constant symbols, or two $17$-ary relation symbols, or etc.), then swapping them induces a nontrivial automorphism of $mathcalB$. More complicatedly, if $S$ is infinite then $mathcalB$ is a countable atomless Boolean algebra, and these are homogeneous (given any two elements neither of which is $0$ or $1$, there is an automorphism swapping them); this is proved by a back-and-forth argument, similar to that presented in this proof that any two countable atomless Boolean algebras are isomorphic. Similarly, if $S=emptyset$ then any permutation of the sentences of the form "there are exactly $n$ elements" induces an automorphism of $mathcalB$.
I believe in fact that we can never perform the reconstruction you want, but I don't have a proof of that yet. Note in particular that we can produces examples of $S$ where some elements of $mathcalB$ are atoms but other elements don't lie above any atoms, so it's neither atomless nor "atomful;" this complicates the picture a bit.
The picture for intuitionistic logic will be similar, except with Heyting algebras taking the role of Boolean algebras. In general, any logic allowing a significant amount of reconstruction along the lines you're proposing would have to be very "algebraically restrictive" (in the sense of algebraic logic), and I'm not aware of any natural such logics.
answered Jul 28 at 18:58
Noah Schweber
110k9139260
Thank you for your answer. In fact, I have made a mistake, I wrote sentences instead of formulas. Can you please, see it again :)
– Ahmed Lazhar
Jul 28 at 19:29
@AhmedLazhar: That doesn't really change anything, because usually we consider a non-sentence formula and its universal closure to entail each other. So each of the equivalence classes are going to contain some sentences anyway.
– Henning Makholm
Jul 28 at 19:33
@HenningMakholm I'm not sure how usual that is. I think things are almost always more interesting without it. It certainly makes quantification nicer, since $forall xP(x)$ and $forall xP(y)$ are inequivalent even though the universal closures of $P(x)$ and $P(y)$ are equivalent.
– Noah Schweber
Jul 28 at 20:27
@NoahSchweber, And what if the signature is finite ? For example, let's consider our signature with two relations $P(x)$ and $R(x,y)$ then $forall xforall y(P(x)wedge Q(x,y)wedge x=y)$ is an atom. If the logic is not with equality or we required the existence of infinity of elements, then $forall xforall y(P(x)wedge Q(x,y))$ would be an atom. Is that true ? In that case what can be the elements of my $Pi$ ? I have to mention that what I'm looking for is to reconstruct the logical signature. There is no problem if I swap two symbols as long as the hole sentence structure is recovered.
– Ahmed Lazhar
Jul 29 at 6:45
Even if we add $negforall xforall y(P(x)wedge R(x,y))$ as an axiom, can't we take as atom $forall xforall yne a(P(x)wedge R(x,y))$ if the logic is with equality and $forall xforall y(P(x)wedge R(x,f(y)))$ otherwise ?
– Ahmed Lazhar
Jul 29 at 7:12
 |Â
show 1 more comment
up vote
3
down vote
accepted
EDIT: Formulas make the situation even easier: any permutation of the variables induces an automorphism of $mathcalB$. For this reason I've left my answer mostly as is, since the interesting situation is when we restrict attention to sentences.
(The above assumes that we don't identify a formula with its universal closure; if we do, then the situation is the same as for sentences since every formula is equivalent to a sentence, namely its universal closure.)
No, you cannot do this in general: when we look at the Boolean algebra $mathcalB$ of semantic equivalence classes of $S$-sentences (which is what you're left with when you forget everything except "$models$" - incidentally, this is the Lindenbaum algebra of the empty theory over $S$), this algebra has lots of nontrivial automorphisms - these will send sentences to non-equivalent sentences while preserving the $models$-structure.
Under weak hypotheses on $S$ (let's assume $S$ is countable for now) we can prove this quickly. If $S$ contains two distinct symbols of the same type (e.g. two constant symbols, or two $17$-ary relation symbols, or etc.), then swapping them induces a nontrivial automorphism of $mathcalB$. More complicatedly, if $S$ is infinite then $mathcalB$ is a countable atomless Boolean algebra, and these are homogeneous (given any two elements neither of which is $0$ or $1$, there is an automorphism swapping them); this is proved by a back-and-forth argument, similar to that presented in this proof that any two countable atomless Boolean algebras are isomorphic. Similarly, if $S=emptyset$ then any permutation of the sentences of the form "there are exactly $n$ elements" induces an automorphism of $mathcalB$.
I believe in fact that we can never perform the reconstruction you want, but I don't have a proof of that yet. Note in particular that we can produces examples of $S$ where some elements of $mathcalB$ are atoms but other elements don't lie above any atoms, so it's neither atomless nor "atomful;" this complicates the picture a bit.
The picture for intuitionistic logic will be similar, except with Heyting algebras taking the role of Boolean algebras. In general, any logic allowing a significant amount of reconstruction along the lines you're proposing would have to be very "algebraically restrictive" (in the sense of algebraic logic), and I'm not aware of any natural such logics.
answered Jul 28 at 18:58
Noah Schweber
110k9139260
Thank you for your answer. In fact, I have made a mistake, I wrote sentences instead of formulas. Can you please, see it again :)
– Ahmed Lazhar
Jul 28 at 19:29
@AhmedLazhar: That doesn't really change anything, because usually we consider a non-sentence formula and its universal closure to entail each other. So each of the equivalence classes are going to contain some sentences anyway.
– Henning Makholm
Jul 28 at 19:33
@HenningMakholm I'm not sure how usual that is. I think things are almost always more interesting without it. It certainly makes quantification nicer, since $forall xP(x)$ and $forall xP(y)$ are inequivalent even though the universal closures of $P(x)$ and $P(y)$ are equivalent.
– Noah Schweber
Jul 28 at 20:27
@NoahSchweber, And what if the signature is finite ? For example, let's consider our signature with two relations $P(x)$ and $R(x,y)$ then $forall xforall y(P(x)wedge Q(x,y)wedge x=y)$ is an atom. If the logic is not with equality or we required the existence of infinity of elements, then $forall xforall y(P(x)wedge Q(x,y))$ would be an atom. Is that true ? In that case what can be the elements of my $Pi$ ? I have to mention that what I'm looking for is to reconstruct the logical signature. There is no problem if I swap two symbols as long as the hole sentence structure is recovered.
– Ahmed Lazhar
Jul 29 at 6:45
Even if we add $negforall xforall y(P(x)wedge R(x,y))$ as an axiom, can't we take as atom $forall xforall yne a(P(x)wedge R(x,y))$ if the logic is with equality and $forall xforall y(P(x)wedge R(x,f(y)))$ otherwise ?
– Ahmed Lazhar
Jul 29 at 7:12
 |Â
show 1 more comment
up vote
3
down vote
accepted
up vote
3
down vote
accepted
EDIT: Formulas make the situation even easier: any permutation of the variables induces an automorphism of $mathcalB$. For this reason I've left my answer mostly as is, since the interesting situation is when we restrict attention to sentences.
(The above assumes that we don't identify a formula with its universal closure; if we do, then the situation is the same as for sentences since every formula is equivalent to a sentence, namely its universal closure.)
No, you cannot do this in general: when we look at the Boolean algebra $mathcalB$ of semantic equivalence classes of $S$-sentences (which is what you're left with when you forget everything except "$models$" - incidentally, this is the Lindenbaum algebra of the empty theory over $S$), this algebra has lots of nontrivial automorphisms - these will send sentences to non-equivalent sentences while preserving the $models$-structure.
Under weak hypotheses on $S$ (let's assume $S$ is countable for now) we can prove this quickly. If $S$ contains two distinct symbols of the same type (e.g. two constant symbols, or two $17$-ary relation symbols, or etc.), then swapping them induces a nontrivial automorphism of $mathcalB$. More complicatedly, if $S$ is infinite then $mathcalB$ is a countable atomless Boolean algebra, and these are homogeneous (given any two elements neither of which is $0$ or $1$, there is an automorphism swapping them); this is proved by a back-and-forth argument, similar to that presented in this proof that any two countable atomless Boolean algebras are isomorphic. Similarly, if $S=emptyset$ then any permutation of the sentences of the form "there are exactly $n$ elements" induces an automorphism of $mathcalB$.
I believe in fact that we can never perform the reconstruction you want, but I don't have a proof of that yet. Note in particular that we can produces examples of $S$ where some elements of $mathcalB$ are atoms but other elements don't lie above any atoms, so it's neither atomless nor "atomful;" this complicates the picture a bit.
The picture for intuitionistic logic will be similar, except with Heyting algebras taking the role of Boolean algebras. In general, any logic allowing a significant amount of reconstruction along the lines you're proposing would have to be very "algebraically restrictive" (in the sense of algebraic logic), and I'm not aware of any natural such logics.
answered Jul 28 at 18:58
Noah Schweber
110k9139260
EDIT: Formulas make the situation even easier: any permutation of the variables induces an automorphism of $mathcalB$. For this reason I've left my answer mostly as is, since the interesting situation is when we restrict attention to sentences.
(The above assumes that we don't identify a formula with its universal closure; if we do, then the situation is the same as for sentences since every formula is equivalent to a sentence, namely its universal closure.)
No, you cannot do this in general: when we look at the Boolean algebra $mathcalB$ of semantic equivalence classes of $S$-sentences (which is what you're left with when you forget everything except "$models$" - incidentally, this is the Lindenbaum algebra of the empty theory over $S$), this algebra has lots of nontrivial automorphisms - these will send sentences to non-equivalent sentences while preserving the $models$-structure.
Under weak hypotheses on $S$ (let's assume $S$ is countable for now) we can prove this quickly. If $S$ contains two distinct symbols of the same type (e.g. two constant symbols, or two $17$-ary relation symbols, or etc.), then swapping them induces a nontrivial automorphism of $mathcalB$. More complicatedly, if $S$ is infinite then $mathcalB$ is a countable atomless Boolean algebra, and these are homogeneous (given any two elements neither of which is $0$ or $1$, there is an automorphism swapping them); this is proved by a back-and-forth argument, similar to that presented in this proof that any two countable atomless Boolean algebras are isomorphic. Similarly, if $S=emptyset$ then any permutation of the sentences of the form "there are exactly $n$ elements" induces an automorphism of $mathcalB$.
I believe in fact that we can never perform the reconstruction you want, but I don't have a proof of that yet. Note in particular that we can produces examples of $S$ where some elements of $mathcalB$ are atoms but other elements don't lie above any atoms, so it's neither atomless nor "atomful;" this complicates the picture a bit.
The picture for intuitionistic logic will be similar, except with Heyting algebras taking the role of Boolean algebras. In general, any logic allowing a significant amount of reconstruction along the lines you're proposing would have to be very "algebraically restrictive" (in the sense of algebraic logic), and I'm not aware of any natural such logics.
answered Jul 28 at 18:58
Noah Schweber
110k9139260
edited Jul 28 at 20:28
answered Jul 28 at 18:58
Noah Schweber
110k9139260
answered Jul 28 at 18:58
Noah Schweber
110k9139260
answered Jul 28 at 18:58
Noah Schweber
110k9139260
110k9139260
Thank you for your answer. In fact, I have made a mistake, I wrote sentences instead of formulas. Can you please, see it again :)
– Ahmed Lazhar
Jul 28 at 19:29
@AhmedLazhar: That doesn't really change anything, because usually we consider a non-sentence formula and its universal closure to entail each other. So each of the equivalence classes are going to contain some sentences anyway.
– Henning Makholm
Jul 28 at 19:33
@HenningMakholm I'm not sure how usual that is. I think things are almost always more interesting without it. It certainly makes quantification nicer, since $forall xP(x)$ and $forall xP(y)$ are inequivalent even though the universal closures of $P(x)$ and $P(y)$ are equivalent.
– Noah Schweber
Jul 28 at 20:27
@NoahSchweber, And what if the signature is finite ? For example, let's consider our signature with two relations $P(x)$ and $R(x,y)$ then $forall xforall y(P(x)wedge Q(x,y)wedge x=y)$ is an atom. If the logic is not with equality or we required the existence of infinity of elements, then $forall xforall y(P(x)wedge Q(x,y))$ would be an atom. Is that true ? In that case what can be the elements of my $Pi$ ? I have to mention that what I'm looking for is to reconstruct the logical signature. There is no problem if I swap two symbols as long as the hole sentence structure is recovered.
– Ahmed Lazhar
Jul 29 at 6:45
Even if we add $negforall xforall y(P(x)wedge R(x,y))$ as an axiom, can't we take as atom $forall xforall yne a(P(x)wedge R(x,y))$ if the logic is with equality and $forall xforall y(P(x)wedge R(x,f(y)))$ otherwise ?
– Ahmed Lazhar
Jul 29 at 7:12
 |Â
show 1 more comment
Thank you for your answer. In fact, I have made a mistake, I wrote sentences instead of formulas. Can you please, see it again :)
– Ahmed Lazhar
Jul 28 at 19:29
@AhmedLazhar: That doesn't really change anything, because usually we consider a non-sentence formula and its universal closure to entail each other. So each of the equivalence classes are going to contain some sentences anyway.
– Henning Makholm
Jul 28 at 19:33
@HenningMakholm I'm not sure how usual that is. I think things are almost always more interesting without it. It certainly makes quantification nicer, since $forall xP(x)$ and $forall xP(y)$ are inequivalent even though the universal closures of $P(x)$ and $P(y)$ are equivalent.
– Noah Schweber
Jul 28 at 20:27
@NoahSchweber, And what if the signature is finite ? For example, let's consider our signature with two relations $P(x)$ and $R(x,y)$ then $forall xforall y(P(x)wedge Q(x,y)wedge x=y)$ is an atom. If the logic is not with equality or we required the existence of infinity of elements, then $forall xforall y(P(x)wedge Q(x,y))$ would be an atom. Is that true ? In that case what can be the elements of my $Pi$ ? I have to mention that what I'm looking for is to reconstruct the logical signature. There is no problem if I swap two symbols as long as the hole sentence structure is recovered.
– Ahmed Lazhar
Jul 29 at 6:45
Even if we add $negforall xforall y(P(x)wedge R(x,y))$ as an axiom, can't we take as atom $forall xforall yne a(P(x)wedge R(x,y))$ if the logic is with equality and $forall xforall y(P(x)wedge R(x,f(y)))$ otherwise ?
– Ahmed Lazhar
Jul 29 at 7:12
Thank you for your answer. In fact, I have made a mistake, I wrote sentences instead of formulas. Can you please, see it again :)
– Ahmed Lazhar
Jul 28 at 19:29
Thank you for your answer. In fact, I have made a mistake, I wrote sentences instead of formulas. Can you please, see it again :)
– Ahmed Lazhar
Jul 28 at 19:29
@AhmedLazhar: That doesn't really change anything, because usually we consider a non-sentence formula and its universal closure to entail each other. So each of the equivalence classes are going to contain some sentences anyway.
– Henning Makholm
Jul 28 at 19:33
@AhmedLazhar: That doesn't really change anything, because usually we consider a non-sentence formula and its universal closure to entail each other. So each of the equivalence classes are going to contain some sentences anyway.
– Henning Makholm
Jul 28 at 19:33
@HenningMakholm I'm not sure how usual that is. I think things are almost always more interesting without it. It certainly makes quantification nicer, since $forall xP(x)$ and $forall xP(y)$ are inequivalent even though the universal closures of $P(x)$ and $P(y)$ are equivalent.
– Noah Schweber
Jul 28 at 20:27
@HenningMakholm I'm not sure how usual that is. I think things are almost always more interesting without it. It certainly makes quantification nicer, since $forall xP(x)$ and $forall xP(y)$ are inequivalent even though the universal closures of $P(x)$ and $P(y)$ are equivalent.
– Noah Schweber
Jul 28 at 20:27
@NoahSchweber, And what if the signature is finite ? For example, let's consider our signature with two relations $P(x)$ and $R(x,y)$ then $forall xforall y(P(x)wedge Q(x,y)wedge x=y)$ is an atom. If the logic is not with equality or we required the existence of infinity of elements, then $forall xforall y(P(x)wedge Q(x,y))$ would be an atom. Is that true ? In that case what can be the elements of my $Pi$ ? I have to mention that what I'm looking for is to reconstruct the logical signature. There is no problem if I swap two symbols as long as the hole sentence structure is recovered.
– Ahmed Lazhar
Jul 29 at 6:45
@NoahSchweber, And what if the signature is finite ? For example, let's consider our signature with two relations $P(x)$ and $R(x,y)$ then $forall xforall y(P(x)wedge Q(x,y)wedge x=y)$ is an atom. If the logic is not with equality or we required the existence of infinity of elements, then $forall xforall y(P(x)wedge Q(x,y))$ would be an atom. Is that true ? In that case what can be the elements of my $Pi$ ? I have to mention that what I'm looking for is to reconstruct the logical signature. There is no problem if I swap two symbols as long as the hole sentence structure is recovered.
– Ahmed Lazhar
Jul 29 at 6:45
Even if we add $negforall xforall y(P(x)wedge R(x,y))$ as an axiom, can't we take as atom $forall xforall yne a(P(x)wedge R(x,y))$ if the logic is with equality and $forall xforall y(P(x)wedge R(x,f(y)))$ otherwise ?
– Ahmed Lazhar
Jul 29 at 7:12
Even if we add $negforall xforall y(P(x)wedge R(x,y))$ as an axiom, can't we take as atom $forall xforall yne a(P(x)wedge R(x,y))$ if the logic is with equality and $forall xforall y(P(x)wedge R(x,f(y)))$ otherwise ?
– Ahmed Lazhar
Jul 29 at 7:12
 |Â
show 1 more 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%2f2865485%2freconstruction-of-fol-language%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
Note that you seem to be juggling between sentences and formulas a bit, here; it ultimately makes no difference, but working with sentences only makes things messier (since in general $forall xvarphi(x)$ can be a sentence without $varphi(x)$ being a sentence).
– Noah Schweber
Jul 28 at 19:20
Yes, you have reason, I'm sorry for that mistake.
– Ahmed Lazhar
Jul 28 at 19:31