# Questions tagged [definability]

definability by formulas in first-order logic, e.g. as explained at https://en.wikipedia.org/wiki/Definable_set, or as in J. Robinson's first-order definition of the integers in the field of rationals

42 questions
Filter by
Sorted by
Tagged with
214 views

### Can HCD accommodate all known large cardinal axioms?

HOD has been found to be useful in that it is an inner model that can accommodate essentially all known large cardinals. However, there is a definable well ordering over HOD, so it cannot satisfy ...
389 views

123 views

I will rewrite my question using Matt F. suggestion. Consider the logical structure $L = (\mathbb{R}, +, *, 1, 0, =)$ and a function $f:\mathbb{R}\to\mathbb{R}$. Consider the map $Q:2^\mathbb{R}→2^\... 0 votes 1 answer 106 views ### An infinite Leibnizian structure in a finite language with precisely$n$definable elements This question was inspired by Joel David Hamkins's excellent question on Leibnizian structures with no definable elements. Let$n$be a positive integer. Is there an infinite structure in a finite ... 9 votes 0 answers 263 views ### Definable constructions in o-minimal geometry Recently I've been working with o-minimal expansions of$(\mathbb{R},\times,+)$, and I want to work "internally" to the language of o-minimal sets instead of working with "definable ... 10 votes 0 answers 195 views ### Are the nonnegative rationals diophantine with only two quantifiers? Definition: A subset$D\subseteq \mathbb{Q}$is diophantine if it is the projection of the zero set of a polynomial, i.e. there exists a polynomial$f\in\mathbb{Q}[X,Y_1,\dots,Y_n]$for some$n$such ... 2 votes 0 answers 289 views ### Can we have$\sf V=HTD$? How it relates to$\sf V=HOD$? In my search for some type-set motivated line of thought that might prove axiom of choice, I was thinking of a concept that looks like$\sf V=HOD$, but in terms of types instead of ordinals, that is ... 14 votes 2 answers 522 views ### Definability of Gödel's pairing function on ordinals Given an infinite cardinal$\kappa$, Gödel's function is a well-known bijection$p:\kappa^2\to\kappa$. Is$p$definable in the structure$\langle\kappa;\in\rangle$? Is$p$definable in a bigger 2nd ... 4 votes 1 answer 255 views ### What is the lowest complexity definition of$\mathbb{Z}$in an infinite algebraic extension of$\mathbb{Q}$? In 2009, Jochen Koenigsmann showed that$\mathbb{Z}$is universally definable in the field$\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that$\mathbb{Z}$is$\exists\forall$-... 8 votes 1 answer 225 views ### What is the lowest complexity definition of$\mathbb{Z}$in an infinite extension of$\mathbb{Q}$In 2009, Jochen Koenigsmann showed that$\mathbb{Z}$is universally definable in the field$\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that$\mathbb{Z}$is$\exists\forall$-... 10 votes 1 answer 340 views ### Is$\mathbb{Z}$universally definable in any number fields other than$\mathbb{Q}$? In 2009, Jochen Koenigsmann showed that$\mathbb{Z}$is universally definable in the field$\mathbb{Q}$. My question is, are there any other number fields in which$\mathbb{Z}$is universally ... 10 votes 0 answers 291 views ### Definability up to isomorphism versus definability of an isomorphic copy Question: Is it provable in ZFC that every structure that is ordinal definable up to isomorphism has an ordinal definable isomorphic copy? If not, what are some counterexamples? All structures are ... 4 votes 0 answers 356 views ### A question regarding the "math tea" argument Joel David Hamkins published a paper where he analyzes the "math tea" argument, namely, the argument that some real numbers are undefinable. He constructed a countable model of set theory ... 5 votes 1 answer 296 views ### Is there a complete characterization of ordered fields without definable proper subfields?$\mathbb{Q}$has no proper subfields. As a result, all ordered fields elementarily equivalent to$\mathbb{Q}$have no proper subfields which are first-order definable without parameters. And by the ... 6 votes 1 answer 303 views ### Definability of ordinals in various signatures Recently, I've been studying what the definable subsets of the countable ordinals "look like" from the perspective of bare-bones first order logic (not set theory) equipped with various ways ... 9 votes 0 answers 314 views ### Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable? Assume ZFC. Is there a formula of$\mathcal{L}_\in$(without parameters) defining a model$\mathcal{M}$of PA whose domain is a proper class but the complete theory of that model is not definable by ... 1 vote 1 answer 246 views ### Does choice always hold in a model of ZF with point-wise parameter-free definable sets? If one add to ZF the rule that all sets are parameter free definable. Would that prove the axiom of choice? More specifically. IF we add the following omega rule to inference rules of the language of ... 10 votes 2 answers 378 views ### Definability of the ring of integer in algebraic extensions of$\mathbb Q$J. Robinson has proved that exists a formula$\psi(x)$in the language of rings which,applied to the rational numbers, defines the the ring integers (making the theory of$\mathbb{Q}$undecidable, due ... 8 votes 1 answer 254 views ### Non-normal numbers definable without parameters in the langauge of differential rings with composition Background: It is currently unknown whether$e$is normal. A natural way to approach this question is to find a class to which$e$belongs, and prove all members of that class are normal. For example, ... 5 votes 0 answers 138 views ### Self-additive posets We say that a partially ordered set$(P,<)$is self-additive if the two natural embeddings of$P$in$P\oplus P$(the linear sum of$P$and itself) are elementary. We have the following. ... 4 votes 0 answers 44 views ### Closed and bounded intervals of definably complete ordered groups True or false? All closed and bounded intervals of definably complete ordered groups are definably compact. Let$G$be an ordered abelian group. Then, a definable subset$D ⊆ G$is said to be ... 1 vote 1 answer 195 views ### In NBG (ZFC + classes) if$P$nonempty predicate of classes must$P$have definable solution? Let$A, B, C..X, Y$range over potentially proper classes in NBG set theory (or adding class quantification to ZFC in obvious way) and$x,y,z$range over sets. Since I don't know the proper symbols ... 6 votes 1 answer 367 views ### Problem with definability in the constructible hierarchy This is a rather technical question. I cannot find my mistake in a proof of the (obviously wrong) following sentence: Every countable ordinal is$\Sigma_2$-definable in$J_{\omega_1 + 1}$by a formula ... 8 votes 1 answer 460 views ### Are the definable hyper-reals, using quantifiers only over the standard reals and natural numbers, the same as the algebraic numbers? This question arose today at Yevgeny Gordon's talk, "Will nonstandard analysis be the analysis of the future?" at the CUNY Logic Workshop. Here is my way of asking it. Consider the ordered real field ... 30 votes 2 answers 1k views ### Define$\mathbb{N}$in the ring$\mathbb{Z}$without Lagrange's theorem It is well-known that the set of nonnegative integers$\mathbb{N}$is definable in the ring of integers$\mathbb{Z}$. Indeed, by Lagrange's four squares theorem we have$\mathbb{N} = \{n \in \mathbb{Z}... 338 views

### Cohen's model yet again

It has been discussed already whether a countable OD set necessarily contains an OD element. See e.g. A question about ordinal definable real numbers . A negative answer was obtained in Archive for ...
205 views

### What are the minimal requirements for the definable hyperreal field plus transfer?

It is interesting that to prove the transfer principle for the definable hyperreal field, one requires no more choice than for proving, for instance, the countable additivity of the Lebesgue measure. ...
1k views

### Is factorial definable using a $\Delta_0$ formula?

The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula. Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)? If not, why?
369 views

### Are there known ways to posit definable global choice in ZF without positing V=L?

I need a global choice function defined by a formula in (a fragment of) ZF. There is no harm in assuming V=L for my purposes. But I wonder if there are any familiar alternative ways to get this? ...
657 views

### Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?

This question arises from an issue arising in user38200's recent question concerning models of set theory in which every definable set has a definable element. In my answer to that question, with ...
273 views

### Definability of arithmetic functions and relations

Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand (...
272 views

### Ordinal definable sets of reals in the Solovay

To be precise, let $\Omega$ be an inaccessible cardinal in $L$ and let N be the Solovay model defined by the Levy-collapse in this case. Then $\Omega$ is $\aleph_1$ in $N$. How many different OD (=...
162 views

### Outer Definability of a Class

Definition: Let $C$ be a class of sets and $\mathcal{L}$ a first order relational language. We say $C$ is "outer definable" by $\mathcal{L}$ if there is a first order theory $T$ and for each $n_{R}$ - ... 282 views

904 views

316 views

### What ordinals are definable relations in Peano Arithmetic?

I am not asking which order types PA proves are well ordered. That would be all up to $\epsilon_0$. Rather I mean, assuming a stronger ambient theory such as Zermelo set theory, which ordinals have ...
I'm having difficulties to prove that the subset of even numbers is not first-order definable in $(\mathbb{N},<)$. Any hint is welcomed! More generally, what are usual techniques in order to prove ...
### Defining $\mathbb{Z}$ in $\mathbb{Q}$
It was proved by Poonen that $\mathbb{Z}$ is definable in the structure $(\mathbb{Q}, +, \cdot, 0, 1)$ using $\forall \exists$ formula. Koenigsmann has shown that $\mathbb{Z}$ is in fact definable by ... 