Mixing
Describing all models of the theory of $(mathbbZ, =, S, 0)$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Consider the theory of integers with equality, a constant 0 and the successor operation. In other words, that's a theory with axioms
- axioms of equality ,
- $forall x forall y (S(x) = S(y) rightarrow x = y)$,
- $forall x exists y (S(y) = x)$,
- $forall x lnot (x = S(x))$,
- $forall x lnot (x = S(S(x)))$,
- $forall x lnot (x = S(S(S(x))))$,
- and countably infinite number of similar axioms each stating that $k$ applications of $S$ don't cycle.
What would be the models of this theory?
Clearly, one example is $mathbbR$ with the natural interpretation. It just decomposes to $mathbbZ times mathbbR$, so we have $mathfrakc$ copies of $mathbbZ$ that don't care about each other. This suggests that for every uncountable cardinality $alpha$ we can do something similar and decompose that into $mathbbZ times alpha$ (and similarly for countable models of the form $mathbbZ times k$, where $k$ is finite or countably infinite). But is there anything else?
If there is, how does it look? If there isn't, does it mean that this theory is uncountably categorical? The latter would be interesting, since this theory clearly isn't countably categorical.
logic model-theory
asked Jul 15 at 17:45
0xd34df00d
387212
 |Â
show 3 more comments
up vote
1
down vote
favorite
Consider the theory of integers with equality, a constant 0 and the successor operation. In other words, that's a theory with axioms
- axioms of equality ,
- $forall x forall y (S(x) = S(y) rightarrow x = y)$,
- $forall x exists y (S(y) = x)$,
- $forall x lnot (x = S(x))$,
- $forall x lnot (x = S(S(x)))$,
- $forall x lnot (x = S(S(S(x))))$,
- and countably infinite number of similar axioms each stating that $k$ applications of $S$ don't cycle.
What would be the models of this theory?
Clearly, one example is $mathbbR$ with the natural interpretation. It just decomposes to $mathbbZ times mathbbR$, so we have $mathfrakc$ copies of $mathbbZ$ that don't care about each other. This suggests that for every uncountable cardinality $alpha$ we can do something similar and decompose that into $mathbbZ times alpha$ (and similarly for countable models of the form $mathbbZ times k$, where $k$ is finite or countably infinite). But is there anything else?
If there is, how does it look? If there isn't, does it mean that this theory is uncountably categorical? The latter would be interesting, since this theory clearly isn't countably categorical.
logic model-theory
asked Jul 15 at 17:45
0xd34df00d
387212
1
@coffeemath nope, as I'm considering all integers, not just non-negative ones. On the second thought, $0$ probably isn't necessary at all.
– 0xd34df00d
Jul 15 at 17:57
Also, do you require $=$ to be interpreted as actual equality? (If not, then there are loads more models you can get because any element of a model can be replaced by some arbitrary equivalence class.)
– Eric Wofsey
Jul 15 at 17:58
@EricWofsey yep, I'm only considering normal models.
– 0xd34df00d
Jul 15 at 18:03
2
Why only consider $alpha$ uncountable? I daresay that any number of disjoint copies of $Bbb Z $ and/or disjoint copies of (backwards) $Bbb N$ works
– Hagen von Eitzen
Jul 15 at 18:10
@HagenvonEitzen right, good catch! For instance, $mathbbZ + mathbbZ$ is also a model for this, which is $mathbbZ times 2$, and so is $mathbbZ times mathbbN$, for instance. I'll update the question.
– 0xd34df00d
Jul 15 at 18:13
 |Â
show 3 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider the theory of integers with equality, a constant 0 and the successor operation. In other words, that's a theory with axioms
- axioms of equality ,
- $forall x forall y (S(x) = S(y) rightarrow x = y)$,
- $forall x exists y (S(y) = x)$,
- $forall x lnot (x = S(x))$,
- $forall x lnot (x = S(S(x)))$,
- $forall x lnot (x = S(S(S(x))))$,
- and countably infinite number of similar axioms each stating that $k$ applications of $S$ don't cycle.
What would be the models of this theory?
Clearly, one example is $mathbbR$ with the natural interpretation. It just decomposes to $mathbbZ times mathbbR$, so we have $mathfrakc$ copies of $mathbbZ$ that don't care about each other. This suggests that for every uncountable cardinality $alpha$ we can do something similar and decompose that into $mathbbZ times alpha$ (and similarly for countable models of the form $mathbbZ times k$, where $k$ is finite or countably infinite). But is there anything else?
If there is, how does it look? If there isn't, does it mean that this theory is uncountably categorical? The latter would be interesting, since this theory clearly isn't countably categorical.
logic model-theory
asked Jul 15 at 17:45
0xd34df00d
387212
Consider the theory of integers with equality, a constant 0 and the successor operation. In other words, that's a theory with axioms
- axioms of equality ,
- $forall x forall y (S(x) = S(y) rightarrow x = y)$,
- $forall x exists y (S(y) = x)$,
- $forall x lnot (x = S(x))$,
- $forall x lnot (x = S(S(x)))$,
- $forall x lnot (x = S(S(S(x))))$,
- and countably infinite number of similar axioms each stating that $k$ applications of $S$ don't cycle.
What would be the models of this theory?
Clearly, one example is $mathbbR$ with the natural interpretation. It just decomposes to $mathbbZ times mathbbR$, so we have $mathfrakc$ copies of $mathbbZ$ that don't care about each other. This suggests that for every uncountable cardinality $alpha$ we can do something similar and decompose that into $mathbbZ times alpha$ (and similarly for countable models of the form $mathbbZ times k$, where $k$ is finite or countably infinite). But is there anything else?
If there is, how does it look? If there isn't, does it mean that this theory is uncountably categorical? The latter would be interesting, since this theory clearly isn't countably categorical.
logic model-theory
asked Jul 15 at 17:45
0xd34df00d
387212
edited Jul 15 at 18:14
asked Jul 15 at 17:45
0xd34df00d
387212
asked Jul 15 at 17:45
0xd34df00d
387212
asked Jul 15 at 17:45
0xd34df00d
387212
387212
1
@coffeemath nope, as I'm considering all integers, not just non-negative ones. On the second thought, $0$ probably isn't necessary at all.
– 0xd34df00d
Jul 15 at 17:57
Also, do you require $=$ to be interpreted as actual equality? (If not, then there are loads more models you can get because any element of a model can be replaced by some arbitrary equivalence class.)
– Eric Wofsey
Jul 15 at 17:58
@EricWofsey yep, I'm only considering normal models.
– 0xd34df00d
Jul 15 at 18:03
2
Why only consider $alpha$ uncountable? I daresay that any number of disjoint copies of $Bbb Z $ and/or disjoint copies of (backwards) $Bbb N$ works
– Hagen von Eitzen
Jul 15 at 18:10
@HagenvonEitzen right, good catch! For instance, $mathbbZ + mathbbZ$ is also a model for this, which is $mathbbZ times 2$, and so is $mathbbZ times mathbbN$, for instance. I'll update the question.
– 0xd34df00d
Jul 15 at 18:13
 |Â
show 3 more comments
1
@coffeemath nope, as I'm considering all integers, not just non-negative ones. On the second thought, $0$ probably isn't necessary at all.
– 0xd34df00d
Jul 15 at 17:57
Also, do you require $=$ to be interpreted as actual equality? (If not, then there are loads more models you can get because any element of a model can be replaced by some arbitrary equivalence class.)
– Eric Wofsey
Jul 15 at 17:58
@EricWofsey yep, I'm only considering normal models.
– 0xd34df00d
Jul 15 at 18:03
2
Why only consider $alpha$ uncountable? I daresay that any number of disjoint copies of $Bbb Z $ and/or disjoint copies of (backwards) $Bbb N$ works
– Hagen von Eitzen
Jul 15 at 18:10
@HagenvonEitzen right, good catch! For instance, $mathbbZ + mathbbZ$ is also a model for this, which is $mathbbZ times 2$, and so is $mathbbZ times mathbbN$, for instance. I'll update the question.
– 0xd34df00d
Jul 15 at 18:13
1
1
@coffeemath nope, as I'm considering all integers, not just non-negative ones. On the second thought, $0$ probably isn't necessary at all.
– 0xd34df00d
Jul 15 at 17:57
@coffeemath nope, as I'm considering all integers, not just non-negative ones. On the second thought, $0$ probably isn't necessary at all.
– 0xd34df00d
Jul 15 at 17:57
Also, do you require $=$ to be interpreted as actual equality? (If not, then there are loads more models you can get because any element of a model can be replaced by some arbitrary equivalence class.)
– Eric Wofsey
Jul 15 at 17:58
Also, do you require $=$ to be interpreted as actual equality? (If not, then there are loads more models you can get because any element of a model can be replaced by some arbitrary equivalence class.)
– Eric Wofsey
Jul 15 at 17:58
@EricWofsey yep, I'm only considering normal models.
– 0xd34df00d
Jul 15 at 18:03
@EricWofsey yep, I'm only considering normal models.
– 0xd34df00d
Jul 15 at 18:03
2
2
Why only consider $alpha$ uncountable? I daresay that any number of disjoint copies of $Bbb Z $ and/or disjoint copies of (backwards) $Bbb N$ works
– Hagen von Eitzen
Jul 15 at 18:10
Why only consider $alpha$ uncountable? I daresay that any number of disjoint copies of $Bbb Z $ and/or disjoint copies of (backwards) $Bbb N$ works
– Hagen von Eitzen
Jul 15 at 18:10
@HagenvonEitzen right, good catch! For instance, $mathbbZ + mathbbZ$ is also a model for this, which is $mathbbZ times 2$, and so is $mathbbZ times mathbbN$, for instance. I'll update the question.
– 0xd34df00d
Jul 15 at 18:13
@HagenvonEitzen right, good catch! For instance, $mathbbZ + mathbbZ$ is also a model for this, which is $mathbbZ times 2$, and so is $mathbbZ times mathbbN$, for instance. I'll update the question.
– 0xd34df00d
Jul 15 at 18:13
 |Â
show 3 more comments
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Yes, a decomposition like this is always possible. Just look at the equivalence classes under the relation $xsim y$ iff there is an $n$ such that $S^n(x) = y$ or vice versa. So all models can be expressed as disjoint copies of $mathbb Z.$ It follows that the theory is $kappa$-categorical for any uncountable $kappa,$ but not $aleph_0$-categorical (since the models with finitely many copies will not be isomorphic to each other or to models with countably infinite numbers of copies).
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
add a comment |Â
up vote
1
down vote
Partial answer: Let's say $M=(Bbb Z,=, S, 0)$ to save typing. Note first it seems likely that you don't actually mean to include "$=$" in the signature, it seems more likely that you''re talking about the theory of $(Bbb Z, S, 0)$ in first-order logic with equality. Assuming that:
It's not at all clear to me that the theory of $M$ is in fact characterized by those axioms, although it seems right. In any case, the models of those axioms are exactly $Bbb Ztimes A$ for some set $A$, with the obvious interpretation of $S$ (and with $0$ any element of the structure; note $0$ is never mentioned in the axioms).
This is clear. In any model $M'$ the interpretation of $S$ is a bijection such that no $S^k$ has a fixed point. Say $$O(x)=S^k(x):kinBbb Z.$$Then the sets $O(x)$ give a partition of $M'$, and each $O(x)$ is isomorphic to $Bbb Z$.
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
2
I think these axioms do give the theory of M, since we can show the models have this structure from just the fact that $S$ is bijective and acyclic, and then completeness follows from the categoricity via Vaught's test.
– spaceisdarkgreen
Jul 15 at 18:37
The intuition I used (briefly outlined in a now-deleted comment) is that we can do quantifier elimination on $(mathbbZ, =, S, 0)$ using just these properties of $S$ (being bijective and acyclic). So, for every formula $phi$ of this theory there exists an equivalent quantifier-free formula $psi$, which, for a closed $phi$, means $psi$ is either constantly true or false, meaning it (or its negation) has a derivation in this theory, which means the theory is complete. Though the reference to the Vaught's test is surely more rigorous, I should have used that.
– 0xd34df00d
Jul 15 at 18:43
@spaceisdarkgreen Vaught's test, cool. Sure enough, for example any two moodels of cardinality $c$ are isomorphic.
– David C. Ullrich
Jul 15 at 19:13
1
@0xd34df00d Yes, it's overkill, but you can use QE to get to completeness here. But remember that QE doesn't always imply completeness. For instance, here you have a constant symbol (though as David notes, it's largely irrelevant). So there are quantifier-free sentences besides $top$ and $bot,$ and one would have to show they are all equivalent to $top$ or $bot.$ (But that's not hard here.) Another way to see it follows from QE here is that $mathbb Z$ embeds in every model, so it follows from the fact that QF statements are absolute upwards.
– spaceisdarkgreen
Jul 16 at 0:02
@0xd34df00d If you say so. Given that you thought QE proved the original incomplete set of axioms was complete you might want to write it out carefully. I'm happy with the argument from Vaught's test. Very simple - I'd never heard of Vaught but it didn't take me long to realize it was more or less obvious from Lowenheim-Skolem...
– David C. Ullrich
Jul 16 at 0:19
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Yes, a decomposition like this is always possible. Just look at the equivalence classes under the relation $xsim y$ iff there is an $n$ such that $S^n(x) = y$ or vice versa. So all models can be expressed as disjoint copies of $mathbb Z.$ It follows that the theory is $kappa$-categorical for any uncountable $kappa,$ but not $aleph_0$-categorical (since the models with finitely many copies will not be isomorphic to each other or to models with countably infinite numbers of copies).
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
add a comment |Â
up vote
2
down vote
accepted
Yes, a decomposition like this is always possible. Just look at the equivalence classes under the relation $xsim y$ iff there is an $n$ such that $S^n(x) = y$ or vice versa. So all models can be expressed as disjoint copies of $mathbb Z.$ It follows that the theory is $kappa$-categorical for any uncountable $kappa,$ but not $aleph_0$-categorical (since the models with finitely many copies will not be isomorphic to each other or to models with countably infinite numbers of copies).
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Yes, a decomposition like this is always possible. Just look at the equivalence classes under the relation $xsim y$ iff there is an $n$ such that $S^n(x) = y$ or vice versa. So all models can be expressed as disjoint copies of $mathbb Z.$ It follows that the theory is $kappa$-categorical for any uncountable $kappa,$ but not $aleph_0$-categorical (since the models with finitely many copies will not be isomorphic to each other or to models with countably infinite numbers of copies).
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
Yes, a decomposition like this is always possible. Just look at the equivalence classes under the relation $xsim y$ iff there is an $n$ such that $S^n(x) = y$ or vice versa. So all models can be expressed as disjoint copies of $mathbb Z.$ It follows that the theory is $kappa$-categorical for any uncountable $kappa,$ but not $aleph_0$-categorical (since the models with finitely many copies will not be isomorphic to each other or to models with countably infinite numbers of copies).
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
answered Jul 15 at 18:22
spaceisdarkgreen
27.6k21547
27.6k21547
add a comment |Â
add a comment |Â
up vote
1
down vote
Partial answer: Let's say $M=(Bbb Z,=, S, 0)$ to save typing. Note first it seems likely that you don't actually mean to include "$=$" in the signature, it seems more likely that you''re talking about the theory of $(Bbb Z, S, 0)$ in first-order logic with equality. Assuming that:
It's not at all clear to me that the theory of $M$ is in fact characterized by those axioms, although it seems right. In any case, the models of those axioms are exactly $Bbb Ztimes A$ for some set $A$, with the obvious interpretation of $S$ (and with $0$ any element of the structure; note $0$ is never mentioned in the axioms).
This is clear. In any model $M'$ the interpretation of $S$ is a bijection such that no $S^k$ has a fixed point. Say $$O(x)=S^k(x):kinBbb Z.$$Then the sets $O(x)$ give a partition of $M'$, and each $O(x)$ is isomorphic to $Bbb Z$.
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
2
I think these axioms do give the theory of M, since we can show the models have this structure from just the fact that $S$ is bijective and acyclic, and then completeness follows from the categoricity via Vaught's test.
– spaceisdarkgreen
Jul 15 at 18:37
The intuition I used (briefly outlined in a now-deleted comment) is that we can do quantifier elimination on $(mathbbZ, =, S, 0)$ using just these properties of $S$ (being bijective and acyclic). So, for every formula $phi$ of this theory there exists an equivalent quantifier-free formula $psi$, which, for a closed $phi$, means $psi$ is either constantly true or false, meaning it (or its negation) has a derivation in this theory, which means the theory is complete. Though the reference to the Vaught's test is surely more rigorous, I should have used that.
– 0xd34df00d
Jul 15 at 18:43
@spaceisdarkgreen Vaught's test, cool. Sure enough, for example any two moodels of cardinality $c$ are isomorphic.
– David C. Ullrich
Jul 15 at 19:13
1
@0xd34df00d Yes, it's overkill, but you can use QE to get to completeness here. But remember that QE doesn't always imply completeness. For instance, here you have a constant symbol (though as David notes, it's largely irrelevant). So there are quantifier-free sentences besides $top$ and $bot,$ and one would have to show they are all equivalent to $top$ or $bot.$ (But that's not hard here.) Another way to see it follows from QE here is that $mathbb Z$ embeds in every model, so it follows from the fact that QF statements are absolute upwards.
– spaceisdarkgreen
Jul 16 at 0:02
@0xd34df00d If you say so. Given that you thought QE proved the original incomplete set of axioms was complete you might want to write it out carefully. I'm happy with the argument from Vaught's test. Very simple - I'd never heard of Vaught but it didn't take me long to realize it was more or less obvious from Lowenheim-Skolem...
– David C. Ullrich
Jul 16 at 0:19
add a comment |Â
up vote
1
down vote
Partial answer: Let's say $M=(Bbb Z,=, S, 0)$ to save typing. Note first it seems likely that you don't actually mean to include "$=$" in the signature, it seems more likely that you''re talking about the theory of $(Bbb Z, S, 0)$ in first-order logic with equality. Assuming that:
It's not at all clear to me that the theory of $M$ is in fact characterized by those axioms, although it seems right. In any case, the models of those axioms are exactly $Bbb Ztimes A$ for some set $A$, with the obvious interpretation of $S$ (and with $0$ any element of the structure; note $0$ is never mentioned in the axioms).
This is clear. In any model $M'$ the interpretation of $S$ is a bijection such that no $S^k$ has a fixed point. Say $$O(x)=S^k(x):kinBbb Z.$$Then the sets $O(x)$ give a partition of $M'$, and each $O(x)$ is isomorphic to $Bbb Z$.
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
2
I think these axioms do give the theory of M, since we can show the models have this structure from just the fact that $S$ is bijective and acyclic, and then completeness follows from the categoricity via Vaught's test.
– spaceisdarkgreen
Jul 15 at 18:37
The intuition I used (briefly outlined in a now-deleted comment) is that we can do quantifier elimination on $(mathbbZ, =, S, 0)$ using just these properties of $S$ (being bijective and acyclic). So, for every formula $phi$ of this theory there exists an equivalent quantifier-free formula $psi$, which, for a closed $phi$, means $psi$ is either constantly true or false, meaning it (or its negation) has a derivation in this theory, which means the theory is complete. Though the reference to the Vaught's test is surely more rigorous, I should have used that.
– 0xd34df00d
Jul 15 at 18:43
@spaceisdarkgreen Vaught's test, cool. Sure enough, for example any two moodels of cardinality $c$ are isomorphic.
– David C. Ullrich
Jul 15 at 19:13
1
@0xd34df00d Yes, it's overkill, but you can use QE to get to completeness here. But remember that QE doesn't always imply completeness. For instance, here you have a constant symbol (though as David notes, it's largely irrelevant). So there are quantifier-free sentences besides $top$ and $bot,$ and one would have to show they are all equivalent to $top$ or $bot.$ (But that's not hard here.) Another way to see it follows from QE here is that $mathbb Z$ embeds in every model, so it follows from the fact that QF statements are absolute upwards.
– spaceisdarkgreen
Jul 16 at 0:02
@0xd34df00d If you say so. Given that you thought QE proved the original incomplete set of axioms was complete you might want to write it out carefully. I'm happy with the argument from Vaught's test. Very simple - I'd never heard of Vaught but it didn't take me long to realize it was more or less obvious from Lowenheim-Skolem...
– David C. Ullrich
Jul 16 at 0:19
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Partial answer: Let's say $M=(Bbb Z,=, S, 0)$ to save typing. Note first it seems likely that you don't actually mean to include "$=$" in the signature, it seems more likely that you''re talking about the theory of $(Bbb Z, S, 0)$ in first-order logic with equality. Assuming that:
It's not at all clear to me that the theory of $M$ is in fact characterized by those axioms, although it seems right. In any case, the models of those axioms are exactly $Bbb Ztimes A$ for some set $A$, with the obvious interpretation of $S$ (and with $0$ any element of the structure; note $0$ is never mentioned in the axioms).
This is clear. In any model $M'$ the interpretation of $S$ is a bijection such that no $S^k$ has a fixed point. Say $$O(x)=S^k(x):kinBbb Z.$$Then the sets $O(x)$ give a partition of $M'$, and each $O(x)$ is isomorphic to $Bbb Z$.
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
Partial answer: Let's say $M=(Bbb Z,=, S, 0)$ to save typing. Note first it seems likely that you don't actually mean to include "$=$" in the signature, it seems more likely that you''re talking about the theory of $(Bbb Z, S, 0)$ in first-order logic with equality. Assuming that:
It's not at all clear to me that the theory of $M$ is in fact characterized by those axioms, although it seems right. In any case, the models of those axioms are exactly $Bbb Ztimes A$ for some set $A$, with the obvious interpretation of $S$ (and with $0$ any element of the structure; note $0$ is never mentioned in the axioms).
This is clear. In any model $M'$ the interpretation of $S$ is a bijection such that no $S^k$ has a fixed point. Say $$O(x)=S^k(x):kinBbb Z.$$Then the sets $O(x)$ give a partition of $M'$, and each $O(x)$ is isomorphic to $Bbb Z$.
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
answered Jul 15 at 18:25
David C. Ullrich
54.3k33583
54.3k33583
2
I think these axioms do give the theory of M, since we can show the models have this structure from just the fact that $S$ is bijective and acyclic, and then completeness follows from the categoricity via Vaught's test.
– spaceisdarkgreen
Jul 15 at 18:37
The intuition I used (briefly outlined in a now-deleted comment) is that we can do quantifier elimination on $(mathbbZ, =, S, 0)$ using just these properties of $S$ (being bijective and acyclic). So, for every formula $phi$ of this theory there exists an equivalent quantifier-free formula $psi$, which, for a closed $phi$, means $psi$ is either constantly true or false, meaning it (or its negation) has a derivation in this theory, which means the theory is complete. Though the reference to the Vaught's test is surely more rigorous, I should have used that.
– 0xd34df00d
Jul 15 at 18:43
@spaceisdarkgreen Vaught's test, cool. Sure enough, for example any two moodels of cardinality $c$ are isomorphic.
– David C. Ullrich
Jul 15 at 19:13
1
@0xd34df00d Yes, it's overkill, but you can use QE to get to completeness here. But remember that QE doesn't always imply completeness. For instance, here you have a constant symbol (though as David notes, it's largely irrelevant). So there are quantifier-free sentences besides $top$ and $bot,$ and one would have to show they are all equivalent to $top$ or $bot.$ (But that's not hard here.) Another way to see it follows from QE here is that $mathbb Z$ embeds in every model, so it follows from the fact that QF statements are absolute upwards.
– spaceisdarkgreen
Jul 16 at 0:02
@0xd34df00d If you say so. Given that you thought QE proved the original incomplete set of axioms was complete you might want to write it out carefully. I'm happy with the argument from Vaught's test. Very simple - I'd never heard of Vaught but it didn't take me long to realize it was more or less obvious from Lowenheim-Skolem...
– David C. Ullrich
Jul 16 at 0:19
add a comment |Â
2
I think these axioms do give the theory of M, since we can show the models have this structure from just the fact that $S$ is bijective and acyclic, and then completeness follows from the categoricity via Vaught's test.
– spaceisdarkgreen
Jul 15 at 18:37
The intuition I used (briefly outlined in a now-deleted comment) is that we can do quantifier elimination on $(mathbbZ, =, S, 0)$ using just these properties of $S$ (being bijective and acyclic). So, for every formula $phi$ of this theory there exists an equivalent quantifier-free formula $psi$, which, for a closed $phi$, means $psi$ is either constantly true or false, meaning it (or its negation) has a derivation in this theory, which means the theory is complete. Though the reference to the Vaught's test is surely more rigorous, I should have used that.
– 0xd34df00d
Jul 15 at 18:43
@spaceisdarkgreen Vaught's test, cool. Sure enough, for example any two moodels of cardinality $c$ are isomorphic.
– David C. Ullrich
Jul 15 at 19:13
1
@0xd34df00d Yes, it's overkill, but you can use QE to get to completeness here. But remember that QE doesn't always imply completeness. For instance, here you have a constant symbol (though as David notes, it's largely irrelevant). So there are quantifier-free sentences besides $top$ and $bot,$ and one would have to show they are all equivalent to $top$ or $bot.$ (But that's not hard here.) Another way to see it follows from QE here is that $mathbb Z$ embeds in every model, so it follows from the fact that QF statements are absolute upwards.
– spaceisdarkgreen
Jul 16 at 0:02
@0xd34df00d If you say so. Given that you thought QE proved the original incomplete set of axioms was complete you might want to write it out carefully. I'm happy with the argument from Vaught's test. Very simple - I'd never heard of Vaught but it didn't take me long to realize it was more or less obvious from Lowenheim-Skolem...
– David C. Ullrich
Jul 16 at 0:19
2
2
I think these axioms do give the theory of M, since we can show the models have this structure from just the fact that $S$ is bijective and acyclic, and then completeness follows from the categoricity via Vaught's test.
– spaceisdarkgreen
Jul 15 at 18:37
I think these axioms do give the theory of M, since we can show the models have this structure from just the fact that $S$ is bijective and acyclic, and then completeness follows from the categoricity via Vaught's test.
– spaceisdarkgreen
Jul 15 at 18:37
The intuition I used (briefly outlined in a now-deleted comment) is that we can do quantifier elimination on $(mathbbZ, =, S, 0)$ using just these properties of $S$ (being bijective and acyclic). So, for every formula $phi$ of this theory there exists an equivalent quantifier-free formula $psi$, which, for a closed $phi$, means $psi$ is either constantly true or false, meaning it (or its negation) has a derivation in this theory, which means the theory is complete. Though the reference to the Vaught's test is surely more rigorous, I should have used that.
– 0xd34df00d
Jul 15 at 18:43
The intuition I used (briefly outlined in a now-deleted comment) is that we can do quantifier elimination on $(mathbbZ, =, S, 0)$ using just these properties of $S$ (being bijective and acyclic). So, for every formula $phi$ of this theory there exists an equivalent quantifier-free formula $psi$, which, for a closed $phi$, means $psi$ is either constantly true or false, meaning it (or its negation) has a derivation in this theory, which means the theory is complete. Though the reference to the Vaught's test is surely more rigorous, I should have used that.
– 0xd34df00d
Jul 15 at 18:43
@spaceisdarkgreen Vaught's test, cool. Sure enough, for example any two moodels of cardinality $c$ are isomorphic.
– David C. Ullrich
Jul 15 at 19:13
@spaceisdarkgreen Vaught's test, cool. Sure enough, for example any two moodels of cardinality $c$ are isomorphic.
– David C. Ullrich
Jul 15 at 19:13
1
1
@0xd34df00d Yes, it's overkill, but you can use QE to get to completeness here. But remember that QE doesn't always imply completeness. For instance, here you have a constant symbol (though as David notes, it's largely irrelevant). So there are quantifier-free sentences besides $top$ and $bot,$ and one would have to show they are all equivalent to $top$ or $bot.$ (But that's not hard here.) Another way to see it follows from QE here is that $mathbb Z$ embeds in every model, so it follows from the fact that QF statements are absolute upwards.
– spaceisdarkgreen
Jul 16 at 0:02
@0xd34df00d Yes, it's overkill, but you can use QE to get to completeness here. But remember that QE doesn't always imply completeness. For instance, here you have a constant symbol (though as David notes, it's largely irrelevant). So there are quantifier-free sentences besides $top$ and $bot,$ and one would have to show they are all equivalent to $top$ or $bot.$ (But that's not hard here.) Another way to see it follows from QE here is that $mathbb Z$ embeds in every model, so it follows from the fact that QF statements are absolute upwards.
– spaceisdarkgreen
Jul 16 at 0:02
@0xd34df00d If you say so. Given that you thought QE proved the original incomplete set of axioms was complete you might want to write it out carefully. I'm happy with the argument from Vaught's test. Very simple - I'd never heard of Vaught but it didn't take me long to realize it was more or less obvious from Lowenheim-Skolem...
– David C. Ullrich
Jul 16 at 0:19
@0xd34df00d If you say so. Given that you thought QE proved the original incomplete set of axioms was complete you might want to write it out carefully. I'm happy with the argument from Vaught's test. Very simple - I'd never heard of Vaught but it didn't take me long to realize it was more or less obvious from Lowenheim-Skolem...
– David C. Ullrich
Jul 16 at 0:19
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%2f2852722%2fdescribing-all-models-of-the-theory-of-mathbbz-s-0%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
@coffeemath nope, as I'm considering all integers, not just non-negative ones. On the second thought, $0$ probably isn't necessary at all.
– 0xd34df00d
Jul 15 at 17:57
Also, do you require $=$ to be interpreted as actual equality? (If not, then there are loads more models you can get because any element of a model can be replaced by some arbitrary equivalence class.)
– Eric Wofsey
Jul 15 at 17:58
@EricWofsey yep, I'm only considering normal models.
– 0xd34df00d
Jul 15 at 18:03
2
Why only consider $alpha$ uncountable? I daresay that any number of disjoint copies of $Bbb Z $ and/or disjoint copies of (backwards) $Bbb N$ works
– Hagen von Eitzen
Jul 15 at 18:10
@HagenvonEitzen right, good catch! For instance, $mathbbZ + mathbbZ$ is also a model for this, which is $mathbbZ times 2$, and so is $mathbbZ times mathbbN$, for instance. I'll update the question.
– 0xd34df00d
Jul 15 at 18:13