Mixing
For any pair of definable sets of the same cardinality, is there a definable bijection between them?
6
$begingroup$
The answer is no. My question actually is, what are the sufficient and necessary conditions so that an arbitrary $mathcal{L}$-structure $mathcal{M}$ is rich enough to be able to define bijections between any two definable sets of the same cardinality?
I use these terms in this sense:
$mathcal{L}$-structure $mathcal{M}$: It is an structure with domain $M$, with an associated set of named constants and another associated set of named relations.
Definable set: It is a subset of $M^n$, for any natural number $n$, that can be defined using logical formulas and the associated sets of constants and relations.
Definable function: A definable set, which contains only ordered pairs and $(x,y)in f$ and $(x,z) in f$ imply $y=z$.
Let's call the property of being able to define a bijection for any two definable sets of the same cardinality as bijection-complete. Here are some examples:
- The $mathcal{L}$-structure $mathcal{N}$ that has as domain $mathbb{N}$, no constants, and only a one-placed relation $R(x)$ that holds if $x$ is even, is not bijection-complete, since we can define the sets of even numbers ${x:R(x)}$ and odd numbers ${x: lnot R(x)}$ and the only definable function is the identity (be it ranging through all the naturals, just the evens or just the odds) ${(x,x): x=x}$
- If we add to the structure $mathcal{N}$ of the previous point, the functions $S(x, y)=x+y$ and $M(x,y)=x*y$, the structure becomes bijection-complete. Given that we can define $0$ as the ${x: forall y[S(x, y)=y] }$, and $1$ in a similar maner, we can start defining all the naturals and hence, be able to define any finite set and any bijection between finite sets. Furthermore, for any infinite definable sets $A$ and $B$ we can well order them ($x<y$ iff $exists z [z not = 0 land S(x, z)=y]$), define their associated successor functions $S_A$ and $S_B$, and define the bijection by recursion.
- For the $mathcal{L}$-structure $mathcal{Q}$ that has as domain $mathbb{Q}$, all it's elements named by a constant (the decimal expansion) and all the usual relations (if it's in a math textbook, we'll count it as included), it is not clear at all (to me) if it is bijection-complete. The definition by recursion of the previous point can no longer apply here given that a successor function can't be defined (because $mathbb{Q}$ is dense), and I see no straightforward way of (dis)proving bijection-completeness. Consider the difficulty of defining a bijection between ${x: text{the first three numbers of its decimal expansion sum 12} }$ and ${x: text{in it's continued fraction form, the third element is a prime} }$.
So again, what is needed for $mathcal{M}$ to be bijection complete? How can it be proved that a certain $mathcal{M}$ is or isn't bijection complete? (exhaustion or recursion as in $mathcal{N}$ is not, in general, possible)
Edited: point 2 of examples and the definition of definable set
logic model-theory
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
$endgroup$
|
show 13 more comments
6
$begingroup$
The answer is no. My question actually is, what are the sufficient and necessary conditions so that an arbitrary $mathcal{L}$-structure $mathcal{M}$ is rich enough to be able to define bijections between any two definable sets of the same cardinality?
I use these terms in this sense:
$mathcal{L}$-structure $mathcal{M}$: It is an structure with domain $M$, with an associated set of named constants and another associated set of named relations.
Definable set: It is a subset of $M^n$, for any natural number $n$, that can be defined using logical formulas and the associated sets of constants and relations.
Definable function: A definable set, which contains only ordered pairs and $(x,y)in f$ and $(x,z) in f$ imply $y=z$.
Let's call the property of being able to define a bijection for any two definable sets of the same cardinality as bijection-complete. Here are some examples:
- The $mathcal{L}$-structure $mathcal{N}$ that has as domain $mathbb{N}$, no constants, and only a one-placed relation $R(x)$ that holds if $x$ is even, is not bijection-complete, since we can define the sets of even numbers ${x:R(x)}$ and odd numbers ${x: lnot R(x)}$ and the only definable function is the identity (be it ranging through all the naturals, just the evens or just the odds) ${(x,x): x=x}$
- If we add to the structure $mathcal{N}$ of the previous point, the functions $S(x, y)=x+y$ and $M(x,y)=x*y$, the structure becomes bijection-complete. Given that we can define $0$ as the ${x: forall y[S(x, y)=y] }$, and $1$ in a similar maner, we can start defining all the naturals and hence, be able to define any finite set and any bijection between finite sets. Furthermore, for any infinite definable sets $A$ and $B$ we can well order them ($x<y$ iff $exists z [z not = 0 land S(x, z)=y]$), define their associated successor functions $S_A$ and $S_B$, and define the bijection by recursion.
- For the $mathcal{L}$-structure $mathcal{Q}$ that has as domain $mathbb{Q}$, all it's elements named by a constant (the decimal expansion) and all the usual relations (if it's in a math textbook, we'll count it as included), it is not clear at all (to me) if it is bijection-complete. The definition by recursion of the previous point can no longer apply here given that a successor function can't be defined (because $mathbb{Q}$ is dense), and I see no straightforward way of (dis)proving bijection-completeness. Consider the difficulty of defining a bijection between ${x: text{the first three numbers of its decimal expansion sum 12} }$ and ${x: text{in it's continued fraction form, the third element is a prime} }$.
So again, what is needed for $mathcal{M}$ to be bijection complete? How can it be proved that a certain $mathcal{M}$ is or isn't bijection complete? (exhaustion or recursion as in $mathcal{N}$ is not, in general, possible)
Edited: point 2 of examples and the definition of definable set
logic model-theory
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
$endgroup$
2
$begingroup$
Note that bijection-completeness doesn't have to be a notion of richness: sufficiently vacuous structures may be bijection-complete by virtue of having very few definable sets. E.g. in $(mathbb{Q};<)$, the only definable sets are $emptyset$ and $mathbb{Q}$. (Incidentally, it may be more natural to consider definability with parameters, but the point still applies.)
$endgroup$
– Noah Schweber
Sep 13 '18 at 18:00
2
$begingroup$
Unfortunately there are some imprecisions in your question. 1. By "logical formula", do you mean formula of first-order logic? Do you allow formulas with parameters from $mathcal{M}$ (as in Noah's comment)? Do you only consider definable subsets of $mathcal{M}$ (corresponding to formulas in one free variable) or definable subsets of $mathcal{M}^n$ for all $n$ (corresponding to arbitrary formulas)? 2. The argument in your second example is not right. Assuming that "logical formula" means first-order logic, (continued...)
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:10
2
$begingroup$
... the structure $(mathbb{N},R,S)$ does not define $<$, and can't carry out definitions by recursion in general. It's possible that this structure is bijection-complete, just because there are very few definable sets (I haven't thought about this carefully, but they should basically be Boolean combinations of finite translates of the even numbers, plus or minus finitely many elements). But not for the reason you gave.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
3. When you say $mathbb{Q}$ with "the usual constants and the usual relations", what are these? It's common to consider $mathbb{Q}$ as a linear order, an abelian group, a field, etc. In the rational field, you can define $mathbb{N}$ and carry out definitions by recursion.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
What are "the usual constants and the usual relations" on $mathbb Q$? In particular, is "is an integer" a usual relation?
$endgroup$
– Henning Makholm
Sep 13 '18 at 18:19
|
show 13 more comments
6
6
6
$begingroup$
The answer is no. My question actually is, what are the sufficient and necessary conditions so that an arbitrary $mathcal{L}$-structure $mathcal{M}$ is rich enough to be able to define bijections between any two definable sets of the same cardinality?
I use these terms in this sense:
$mathcal{L}$-structure $mathcal{M}$: It is an structure with domain $M$, with an associated set of named constants and another associated set of named relations.
Definable set: It is a subset of $M^n$, for any natural number $n$, that can be defined using logical formulas and the associated sets of constants and relations.
Definable function: A definable set, which contains only ordered pairs and $(x,y)in f$ and $(x,z) in f$ imply $y=z$.
Let's call the property of being able to define a bijection for any two definable sets of the same cardinality as bijection-complete. Here are some examples:
- The $mathcal{L}$-structure $mathcal{N}$ that has as domain $mathbb{N}$, no constants, and only a one-placed relation $R(x)$ that holds if $x$ is even, is not bijection-complete, since we can define the sets of even numbers ${x:R(x)}$ and odd numbers ${x: lnot R(x)}$ and the only definable function is the identity (be it ranging through all the naturals, just the evens or just the odds) ${(x,x): x=x}$
- If we add to the structure $mathcal{N}$ of the previous point, the functions $S(x, y)=x+y$ and $M(x,y)=x*y$, the structure becomes bijection-complete. Given that we can define $0$ as the ${x: forall y[S(x, y)=y] }$, and $1$ in a similar maner, we can start defining all the naturals and hence, be able to define any finite set and any bijection between finite sets. Furthermore, for any infinite definable sets $A$ and $B$ we can well order them ($x<y$ iff $exists z [z not = 0 land S(x, z)=y]$), define their associated successor functions $S_A$ and $S_B$, and define the bijection by recursion.
- For the $mathcal{L}$-structure $mathcal{Q}$ that has as domain $mathbb{Q}$, all it's elements named by a constant (the decimal expansion) and all the usual relations (if it's in a math textbook, we'll count it as included), it is not clear at all (to me) if it is bijection-complete. The definition by recursion of the previous point can no longer apply here given that a successor function can't be defined (because $mathbb{Q}$ is dense), and I see no straightforward way of (dis)proving bijection-completeness. Consider the difficulty of defining a bijection between ${x: text{the first three numbers of its decimal expansion sum 12} }$ and ${x: text{in it's continued fraction form, the third element is a prime} }$.
So again, what is needed for $mathcal{M}$ to be bijection complete? How can it be proved that a certain $mathcal{M}$ is or isn't bijection complete? (exhaustion or recursion as in $mathcal{N}$ is not, in general, possible)
Edited: point 2 of examples and the definition of definable set
logic model-theory
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
$endgroup$
The answer is no. My question actually is, what are the sufficient and necessary conditions so that an arbitrary $mathcal{L}$-structure $mathcal{M}$ is rich enough to be able to define bijections between any two definable sets of the same cardinality?
I use these terms in this sense:
$mathcal{L}$-structure $mathcal{M}$: It is an structure with domain $M$, with an associated set of named constants and another associated set of named relations.
Definable set: It is a subset of $M^n$, for any natural number $n$, that can be defined using logical formulas and the associated sets of constants and relations.
Definable function: A definable set, which contains only ordered pairs and $(x,y)in f$ and $(x,z) in f$ imply $y=z$.
Let's call the property of being able to define a bijection for any two definable sets of the same cardinality as bijection-complete. Here are some examples:
- The $mathcal{L}$-structure $mathcal{N}$ that has as domain $mathbb{N}$, no constants, and only a one-placed relation $R(x)$ that holds if $x$ is even, is not bijection-complete, since we can define the sets of even numbers ${x:R(x)}$ and odd numbers ${x: lnot R(x)}$ and the only definable function is the identity (be it ranging through all the naturals, just the evens or just the odds) ${(x,x): x=x}$
- If we add to the structure $mathcal{N}$ of the previous point, the functions $S(x, y)=x+y$ and $M(x,y)=x*y$, the structure becomes bijection-complete. Given that we can define $0$ as the ${x: forall y[S(x, y)=y] }$, and $1$ in a similar maner, we can start defining all the naturals and hence, be able to define any finite set and any bijection between finite sets. Furthermore, for any infinite definable sets $A$ and $B$ we can well order them ($x<y$ iff $exists z [z not = 0 land S(x, z)=y]$), define their associated successor functions $S_A$ and $S_B$, and define the bijection by recursion.
- For the $mathcal{L}$-structure $mathcal{Q}$ that has as domain $mathbb{Q}$, all it's elements named by a constant (the decimal expansion) and all the usual relations (if it's in a math textbook, we'll count it as included), it is not clear at all (to me) if it is bijection-complete. The definition by recursion of the previous point can no longer apply here given that a successor function can't be defined (because $mathbb{Q}$ is dense), and I see no straightforward way of (dis)proving bijection-completeness. Consider the difficulty of defining a bijection between ${x: text{the first three numbers of its decimal expansion sum 12} }$ and ${x: text{in it's continued fraction form, the third element is a prime} }$.
So again, what is needed for $mathcal{M}$ to be bijection complete? How can it be proved that a certain $mathcal{M}$ is or isn't bijection complete? (exhaustion or recursion as in $mathcal{N}$ is not, in general, possible)
Edited: point 2 of examples and the definition of definable set
logic model-theory
logic model-theory
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
edited Sep 14 '18 at 1:25
Ryunaq
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
asked Sep 13 '18 at 17:38
RyunaqRyunaq
1057
1057
2
$begingroup$
Note that bijection-completeness doesn't have to be a notion of richness: sufficiently vacuous structures may be bijection-complete by virtue of having very few definable sets. E.g. in $(mathbb{Q};<)$, the only definable sets are $emptyset$ and $mathbb{Q}$. (Incidentally, it may be more natural to consider definability with parameters, but the point still applies.)
$endgroup$
– Noah Schweber
Sep 13 '18 at 18:00
2
$begingroup$
Unfortunately there are some imprecisions in your question. 1. By "logical formula", do you mean formula of first-order logic? Do you allow formulas with parameters from $mathcal{M}$ (as in Noah's comment)? Do you only consider definable subsets of $mathcal{M}$ (corresponding to formulas in one free variable) or definable subsets of $mathcal{M}^n$ for all $n$ (corresponding to arbitrary formulas)? 2. The argument in your second example is not right. Assuming that "logical formula" means first-order logic, (continued...)
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:10
2
$begingroup$
... the structure $(mathbb{N},R,S)$ does not define $<$, and can't carry out definitions by recursion in general. It's possible that this structure is bijection-complete, just because there are very few definable sets (I haven't thought about this carefully, but they should basically be Boolean combinations of finite translates of the even numbers, plus or minus finitely many elements). But not for the reason you gave.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
3. When you say $mathbb{Q}$ with "the usual constants and the usual relations", what are these? It's common to consider $mathbb{Q}$ as a linear order, an abelian group, a field, etc. In the rational field, you can define $mathbb{N}$ and carry out definitions by recursion.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
What are "the usual constants and the usual relations" on $mathbb Q$? In particular, is "is an integer" a usual relation?
$endgroup$
– Henning Makholm
Sep 13 '18 at 18:19
|
show 13 more comments
2
$begingroup$
Note that bijection-completeness doesn't have to be a notion of richness: sufficiently vacuous structures may be bijection-complete by virtue of having very few definable sets. E.g. in $(mathbb{Q};<)$, the only definable sets are $emptyset$ and $mathbb{Q}$. (Incidentally, it may be more natural to consider definability with parameters, but the point still applies.)
$endgroup$
– Noah Schweber
Sep 13 '18 at 18:00
2
$begingroup$
Unfortunately there are some imprecisions in your question. 1. By "logical formula", do you mean formula of first-order logic? Do you allow formulas with parameters from $mathcal{M}$ (as in Noah's comment)? Do you only consider definable subsets of $mathcal{M}$ (corresponding to formulas in one free variable) or definable subsets of $mathcal{M}^n$ for all $n$ (corresponding to arbitrary formulas)? 2. The argument in your second example is not right. Assuming that "logical formula" means first-order logic, (continued...)
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:10
2
$begingroup$
... the structure $(mathbb{N},R,S)$ does not define $<$, and can't carry out definitions by recursion in general. It's possible that this structure is bijection-complete, just because there are very few definable sets (I haven't thought about this carefully, but they should basically be Boolean combinations of finite translates of the even numbers, plus or minus finitely many elements). But not for the reason you gave.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
3. When you say $mathbb{Q}$ with "the usual constants and the usual relations", what are these? It's common to consider $mathbb{Q}$ as a linear order, an abelian group, a field, etc. In the rational field, you can define $mathbb{N}$ and carry out definitions by recursion.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
What are "the usual constants and the usual relations" on $mathbb Q$? In particular, is "is an integer" a usual relation?
$endgroup$
– Henning Makholm
Sep 13 '18 at 18:19
2
2
$begingroup$
Note that bijection-completeness doesn't have to be a notion of richness: sufficiently vacuous structures may be bijection-complete by virtue of having very few definable sets. E.g. in $(mathbb{Q};<)$, the only definable sets are $emptyset$ and $mathbb{Q}$. (Incidentally, it may be more natural to consider definability with parameters, but the point still applies.)
$endgroup$
– Noah Schweber
Sep 13 '18 at 18:00
$begingroup$
Note that bijection-completeness doesn't have to be a notion of richness: sufficiently vacuous structures may be bijection-complete by virtue of having very few definable sets. E.g. in $(mathbb{Q};<)$, the only definable sets are $emptyset$ and $mathbb{Q}$. (Incidentally, it may be more natural to consider definability with parameters, but the point still applies.)
$endgroup$
– Noah Schweber
Sep 13 '18 at 18:00
2
2
$begingroup$
Unfortunately there are some imprecisions in your question. 1. By "logical formula", do you mean formula of first-order logic? Do you allow formulas with parameters from $mathcal{M}$ (as in Noah's comment)? Do you only consider definable subsets of $mathcal{M}$ (corresponding to formulas in one free variable) or definable subsets of $mathcal{M}^n$ for all $n$ (corresponding to arbitrary formulas)? 2. The argument in your second example is not right. Assuming that "logical formula" means first-order logic, (continued...)
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:10
$begingroup$
Unfortunately there are some imprecisions in your question. 1. By "logical formula", do you mean formula of first-order logic? Do you allow formulas with parameters from $mathcal{M}$ (as in Noah's comment)? Do you only consider definable subsets of $mathcal{M}$ (corresponding to formulas in one free variable) or definable subsets of $mathcal{M}^n$ for all $n$ (corresponding to arbitrary formulas)? 2. The argument in your second example is not right. Assuming that "logical formula" means first-order logic, (continued...)
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:10
2
2
$begingroup$
... the structure $(mathbb{N},R,S)$ does not define $<$, and can't carry out definitions by recursion in general. It's possible that this structure is bijection-complete, just because there are very few definable sets (I haven't thought about this carefully, but they should basically be Boolean combinations of finite translates of the even numbers, plus or minus finitely many elements). But not for the reason you gave.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
$begingroup$
... the structure $(mathbb{N},R,S)$ does not define $<$, and can't carry out definitions by recursion in general. It's possible that this structure is bijection-complete, just because there are very few definable sets (I haven't thought about this carefully, but they should basically be Boolean combinations of finite translates of the even numbers, plus or minus finitely many elements). But not for the reason you gave.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
2
$begingroup$
3. When you say $mathbb{Q}$ with "the usual constants and the usual relations", what are these? It's common to consider $mathbb{Q}$ as a linear order, an abelian group, a field, etc. In the rational field, you can define $mathbb{N}$ and carry out definitions by recursion.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
$begingroup$
3. When you say $mathbb{Q}$ with "the usual constants and the usual relations", what are these? It's common to consider $mathbb{Q}$ as a linear order, an abelian group, a field, etc. In the rational field, you can define $mathbb{N}$ and carry out definitions by recursion.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
2
$begingroup$
What are "the usual constants and the usual relations" on $mathbb Q$? In particular, is "is an integer" a usual relation?
$endgroup$
– Henning Makholm
Sep 13 '18 at 18:19
$begingroup$
What are "the usual constants and the usual relations" on $mathbb Q$? In particular, is "is an integer" a usual relation?
$endgroup$
– Henning Makholm
Sep 13 '18 at 18:19
|
show 13 more comments
0
active
oldest
votes
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
});
}
});
draft saved
draft discarded
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%2f2915895%2ffor-any-pair-of-definable-sets-of-the-same-cardinality-is-there-a-definable-bij%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f2915895%2ffor-any-pair-of-definable-sets-of-the-same-cardinality-is-there-a-definable-bij%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
2
$begingroup$
Note that bijection-completeness doesn't have to be a notion of richness: sufficiently vacuous structures may be bijection-complete by virtue of having very few definable sets. E.g. in $(mathbb{Q};<)$, the only definable sets are $emptyset$ and $mathbb{Q}$. (Incidentally, it may be more natural to consider definability with parameters, but the point still applies.)
$endgroup$
– Noah Schweber
Sep 13 '18 at 18:00
2
$begingroup$
Unfortunately there are some imprecisions in your question. 1. By "logical formula", do you mean formula of first-order logic? Do you allow formulas with parameters from $mathcal{M}$ (as in Noah's comment)? Do you only consider definable subsets of $mathcal{M}$ (corresponding to formulas in one free variable) or definable subsets of $mathcal{M}^n$ for all $n$ (corresponding to arbitrary formulas)? 2. The argument in your second example is not right. Assuming that "logical formula" means first-order logic, (continued...)
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:10
2
$begingroup$
... the structure $(mathbb{N},R,S)$ does not define $<$, and can't carry out definitions by recursion in general. It's possible that this structure is bijection-complete, just because there are very few definable sets (I haven't thought about this carefully, but they should basically be Boolean combinations of finite translates of the even numbers, plus or minus finitely many elements). But not for the reason you gave.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
3. When you say $mathbb{Q}$ with "the usual constants and the usual relations", what are these? It's common to consider $mathbb{Q}$ as a linear order, an abelian group, a field, etc. In the rational field, you can define $mathbb{N}$ and carry out definitions by recursion.
$endgroup$
– Alex Kruckman
Sep 13 '18 at 18:13
2
$begingroup$
What are "the usual constants and the usual relations" on $mathbb Q$? In particular, is "is an integer" a usual relation?
$endgroup$
– Henning Makholm
Sep 13 '18 at 18:19