Proof that there exist no finite axiomatic system with Compactness Theorem
$begingroup$
Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).
Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.
This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.
The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?
logic first-order-logic predicate-logic model-theory
$endgroup$
add a comment |
$begingroup$
Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).
Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.
This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.
The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?
logic first-order-logic predicate-logic model-theory
$endgroup$
add a comment |
$begingroup$
Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).
Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.
This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.
The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?
logic first-order-logic predicate-logic model-theory
$endgroup$
Say we would like to prove that the class of all infinite groups $(G, circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $Phi_{group}$ (the standard FO axiomatic system for groups) and $Phi_{infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n in mathbb{N}$).
Assuming there exist a $Phi_{infGrp} subseteq FO(tau)$ that finitely axiomatizes this class. Therefore, we can find a $psi in FO(tau)$ that axiomatizes this class too, since the axiomatic system is finite.
This implies that $Phi_{infGrp} cup {negpsi}$ is not satisfiable. We then go on to find a arbitrary, finite subset $Phi_0 subseteq Phi_{infGrp} cup {negpsi}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m in mathbb{N}$ in $Phi_0$. We then finally say that since structure $mathbb{A} models Phi_0$, by virtue of compactness theory, $Phi_{infGrp} cup {negpsi}$ is satsifiable.
The question is... how can $Phi_{infGrp} cup {negpsi}$ be satisfiable when $negpsi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $Phi_{infGrp} cup {negpsi}$?
logic first-order-logic predicate-logic model-theory
logic first-order-logic predicate-logic model-theory
edited Jan 26 at 21:06
Taroccoesbrocco
5,64271840
5,64271840
asked Aug 12 '14 at 11:46
mercurialmercurial
5862815
5862815
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
$psi$ is the sentence
$$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
The sentence $lnot psi$ is then the sentence
$$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
This is a disjunction. No group property needs to fail.
$endgroup$
$begingroup$
Ah yea true that didn't occur to me! Thanks!
$endgroup$
– mercurial
Aug 12 '14 at 12:25
$begingroup$
You are welcome. It is natural to think that a group-theoretic axiom is being negated.
$endgroup$
– André Nicolas
Aug 12 '14 at 13:13
add a comment |
$begingroup$
The following may be a more intuitive proof:
Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.
If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f895021%2fproof-that-there-exist-no-finite-axiomatic-system-with-compactness-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
$psi$ is the sentence
$$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
The sentence $lnot psi$ is then the sentence
$$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
This is a disjunction. No group property needs to fail.
$endgroup$
$begingroup$
Ah yea true that didn't occur to me! Thanks!
$endgroup$
– mercurial
Aug 12 '14 at 12:25
$begingroup$
You are welcome. It is natural to think that a group-theoretic axiom is being negated.
$endgroup$
– André Nicolas
Aug 12 '14 at 13:13
add a comment |
$begingroup$
There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
$psi$ is the sentence
$$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
The sentence $lnot psi$ is then the sentence
$$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
This is a disjunction. No group property needs to fail.
$endgroup$
$begingroup$
Ah yea true that didn't occur to me! Thanks!
$endgroup$
– mercurial
Aug 12 '14 at 12:25
$begingroup$
You are welcome. It is natural to think that a group-theoretic axiom is being negated.
$endgroup$
– André Nicolas
Aug 12 '14 at 13:13
add a comment |
$begingroup$
There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
$psi$ is the sentence
$$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
The sentence $lnot psi$ is then the sentence
$$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
This is a disjunction. No group property needs to fail.
$endgroup$
There is nothing in $lnotpsi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $alpha_1,dots,alpha_m$, the usual axioms of group theory, plus additional special axioms $beta_1,dots,beta_n$, which in conjunction with the group axioms force the group to be infinite. Then
$psi$ is the sentence
$$alpha_1landcdotsland alpha_m land beta_1landdotsland beta_n.$$
The sentence $lnot psi$ is then the sentence
$$lnotalpha_1lorcdotslor lnotalpha_m lor lnotbeta_1lordotslor lnotbeta_n.$$
This is a disjunction. No group property needs to fail.
answered Aug 12 '14 at 12:02
André NicolasAndré Nicolas
454k36432819
454k36432819
$begingroup$
Ah yea true that didn't occur to me! Thanks!
$endgroup$
– mercurial
Aug 12 '14 at 12:25
$begingroup$
You are welcome. It is natural to think that a group-theoretic axiom is being negated.
$endgroup$
– André Nicolas
Aug 12 '14 at 13:13
add a comment |
$begingroup$
Ah yea true that didn't occur to me! Thanks!
$endgroup$
– mercurial
Aug 12 '14 at 12:25
$begingroup$
You are welcome. It is natural to think that a group-theoretic axiom is being negated.
$endgroup$
– André Nicolas
Aug 12 '14 at 13:13
$begingroup$
Ah yea true that didn't occur to me! Thanks!
$endgroup$
– mercurial
Aug 12 '14 at 12:25
$begingroup$
Ah yea true that didn't occur to me! Thanks!
$endgroup$
– mercurial
Aug 12 '14 at 12:25
$begingroup$
You are welcome. It is natural to think that a group-theoretic axiom is being negated.
$endgroup$
– André Nicolas
Aug 12 '14 at 13:13
$begingroup$
You are welcome. It is natural to think that a group-theoretic axiom is being negated.
$endgroup$
– André Nicolas
Aug 12 '14 at 13:13
add a comment |
$begingroup$
The following may be a more intuitive proof:
Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.
If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.
$endgroup$
add a comment |
$begingroup$
The following may be a more intuitive proof:
Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.
If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.
$endgroup$
add a comment |
$begingroup$
The following may be a more intuitive proof:
Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.
If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.
$endgroup$
The following may be a more intuitive proof:
Let $mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.
If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $psi$ such that $K$ is the set of the all $mathcal{L}$-structures $M$ such that $M models psi$. Since the group axioms are finite, let $Phi$ be the conjunction of all the group axioms. Then $ Phi wedge neg psi$ axiomatizes the class of all finite groups. Let $mathcal{L}' = mathcal{L} cup {c_i : i < omega}$. $mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = {Phi wedge neg psi} cup {c_i neq c_j : i neq j}$. If $Delta subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $Delta$. Take any group $G$ of size $n$. Make $G$ into a $mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $mathcal{L}'$-structure satisfies $Delta$. So $Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G models T$. Clearly $G$ must be an infinite $mathcal{L}'$-structure which satisfies $Phi wedge neg psi$. The reduct of $G$ back to $mathcal{L}$ is then an infinite group satisfying $Phi wedge neg psi$. This is a contradiction since $Phi wedge neg psi$ was suppose to be an axiomatization of finite groups.
edited Aug 12 '14 at 12:17
answered Aug 12 '14 at 12:08
WilliamWilliam
17.3k22256
17.3k22256
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f895021%2fproof-that-there-exist-no-finite-axiomatic-system-with-compactness-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown