New answers tagged model-theory
12
votes
Are integers conservatively embedded in the field of complex numbers?
I don't know a reference, but here's a (slightly overkill) proof:
It's known that $(\mathbb{Z};+,\times)$ interprets an algebraically closed field $K$ of infinite transcendence degree and ...
- 21.1k
8
votes
Accepted
Are PA and Counting Theory synonymous\bi-interpretable?
For bi-interpretability, it seems like you’ve mostly answered the question yourself. You’ve described interpretations $\newcommand{\PA}{\mathsf{PA}}\newcommand{\CT}{\mathsf{CT}}\newcommand{\S}{\mathsf{...
- 21.3k
14
votes
Accepted
Does synonymy seep down to the fragments of theories?
It's a very nice question!
The answer is negative. For a counterexample, consider:
Let $T$ be the theory of a partial order $\leq$, that is, a reflexive, transitive, antisymmetric relation.
Let $H$ ...
- 236k
2
votes
Distinguishing finite families of sets by algebras of bounded size
Here is a simple argument (simpler than other answers so far) that the answer to Q2 is negative — specifically, that for any $\newcommand{\l}{\ell}\l \geq 2$ and any $N\!$, there are disjoint families ...
- 21.3k
2
votes
Distinguishing finite families of sets by algebras of bounded size
Here's a messier but more elementary negative response to Question 2. First note that instead of taking $K$ to be an algebra of sets in the question, we can take $K$ to be a partition of $X = \bigcup(...
- 2,555
7
votes
Distinguishing finite families of sets by algebras of bounded size
The answer to Question 2 is also negative. I can show this using the Hales-Jewett Theorem. I am certain there must be a (much) nicer way to do this, but at the moment this is the only way I can think ...
- 18.5k
5
votes
Distinguishing finite families of sets by algebras of bounded size
The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in ...
- 32.1k
6
votes
Stably embedded clone
As was pointed out in the comments, the question as stated is a little bit ambiguous (specifically is the formula in the language of set theory allowed to be an $L_{\infty,\infty}$-formula or just an ...
- 12.4k
Top 50 recent answers are included