Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with definability
Search options answers only
not deleted
user 12705
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
25
votes
Accepted
Is factorial definable using a $\Delta_0$ formula?
Yes, the graph of factorial is $\Delta_0$.
As mentioned above by Ali Enayat, a direct $\Delta_0$ definition of factorial was constructed by D’Aquino [4]. It is based on collecting contributions of all …
- 47.1k
11
votes
Definability of Gödel's pairing function on ordinals
For $\langle\kappa,{\in}\rangle$, James Hanson has already answered the question as stated. However, let me mention a generalization: it’s not just Gödel’s pairing function that’s not definable in $\l …
- 47.1k
9
votes
Accepted
Methods for proving non FO definability
One method is to use quantifier elimination. Note that 0 and $S(x)=x+1$ are definable in $M=(\mathbb N,<)$. The expanded structure $M'=(\mathbb N,<,0,S)$ is a model of the theory $T$ of a discrete lin …
- 47.1k
8
votes
Accepted
Existence property for ordered fields
The answer is negative.
For any model $M$, let $M_d$ denote the submodel of its parameter-free definable elements. We have the following characterization for classical theories.
Lemma: $T$ has EP if …
- 47.1k
6
votes
Ways to define "definability"
What I wrote above is true, but useless by itself, because definability of sets by formulas allowing arbitrary parameters is not an interesting notion (every set is trivially definable from itself as a … For example, one can define an injection $\mathrm{Ord}\times\mathrm{Ord}\to\mathrm{Ord}$, which allows us to take $X=\mathrm{Ord}$, so this generalizes ordinal definability. …
- 47.1k