All Questions
6,027 questions
22
votes
2
answers
1k
views
Toposes (topoi) as classifying toposes of groupoids
A famous theorem of Joyal and Tierney says that each Grothendieck topos is equivalent to the classifying topos of a localic groupoid. I believe that Butz and Moerdijk have shown that if the topos has ...
- 38.6k
30
votes
1
answer
2k
views
Do the algebraic integers form a free abelian group?
It is a well-known fact, proved in every introductory textbook on algebraic number theory, that if $K$ is an algebraic number field, i.e. a finite extension of $\mathbb{Q}$, then its ring $\mathcal{O}...
- 1,298
25
votes
6
answers
4k
views
undecidable sentences of first-order arithmetic whose truth values are unknown
Godel's undecidable sentences in first-order arithmetic were guaranteed to be true, by construction. But are there examples of specific sentences known to be undecidable in first-order arithmetic ...
- 1,189
4
votes
0
answers
331
views
What is the pro-algebraic completion of the free semigroup on one generator?
This question is motivated by an attempt to understand what is going on in Tom's post from a certain point of view.
Let $\mathbb N^+$ be the free semigroup on one generator (so the positive natural ...
- 38.6k
5
votes
4
answers
3k
views
Explicit expression for recursively defined functions
Consider a function $w(i)$, $i \in \mathbb{N}$, defined recursively by:
$w(0)=w(1)=1$, and
$w(i)={i}^{n}-\sum_{j=1}^{i-1}{i \choose j}w(j)$ for $i>1$.
Is it possible to write $w(i)$ out ...
- 2,619
5
votes
1
answer
233
views
Permutation models with a class-sized group
I'm working on building a model of ZF where a very weak choice principle fails, in so much as in any permutation model with a set of atoms it is inconsistent that this principle fails.
To get a feel ...
- 35.5k
12
votes
1
answer
621
views
2-colorings of the reals
It's easy to prove that, if $\mathbb{R}$ is well-orderable, then there is a 2-coloring of pairs of reals with no uncountable homogeneous set, i.e., there is an $m: [\mathbb{R}]^2\rightarrow 2$ such ...
- 20.5k
8
votes
1
answer
2k
views
decidable fragments of first-order logic without the finite countermodel property
Say a set of sentences in first-order logic has the finite countermodel property if any sentence in the set that is falsifiable is falsifiable on a finite domain. (Two examples: the set of sentences ...
- 1,189
6
votes
0
answers
300
views
What are these sets in Freyd's model?
Recall Freyd's model of $ZF +\neg AC$ (as recounted in MacLane and Moerdijk's book Sheaves in Geometry and Logic): it arises as the Fourman interpretation of the topos of sheaves on a particular ...
- 35.5k
26
votes
1
answer
1k
views
Can we find strong fixed-points in the fixed-point lemma of Gödel's incompleteness theorem, that is, where the fixed point is syntactically identical to its substitution instance rather than merely provably equivalent to it?
At Graham Priest's talk for the CUNY set theory seminar yesterday, an issue arose concerning the possibility (or impossibility) of a stronger-than usual form of the arithmetic fixed-point lemma often ...
- 236k
2
votes
1
answer
301
views
Is there existing terminology for this technical condition on semilattices?
Given a semilattice $S$, a subset $E$, and a positive integer $n$, let $E^{[n]}$ be the set of all products of $n$-tuples in $E$. Thus $\bigcup_{n\geq 1} E^{[n]}$ is nothing but the subsemigroup of $S$...
- 25.8k
15
votes
2
answers
1k
views
Exact sequence of monoids
What is the right definition of an exact sequence of monoid homomorphisms?
I can't seem to find a consistent in my searches; indeed Balmer (Remark 2.6,
http://www.math.ucla.edu/~balmer/Pubfile/...
- 3,009
17
votes
0
answers
694
views
Antichains of Cardinals in ZF Without Choice...
With the Axiom of Choice, the cardinals form a nice linearly ordered "set". In the absence of the Axiom of Choice, the cardinals form a partially ordered "set". Broadly, I am wondering what ...
- 596
6
votes
1
answer
315
views
Acceptability and Soundness of J-structures.
I would like an example of a J-structure $(J^A,B)$ which is not acceptable and one that is not 1-sound.
Edit:Let us recall that a structure $J^A_\alpha$ is acceptable if for every limit ordinal $ \xi&...
- 163
3
votes
1
answer
468
views
Forcing and divisibility
A version of this question got a couple of comments but no answer on stackexchange.
I learned the concept of forcing in logic from Boolos & Jeffrey's book Computability and Logic (second edition, ...
6
votes
3
answers
822
views
Is it consistent with ZFC that for all ordinals $\alpha, \beta < \omega$ it holds that $2^{\aleph_\alpha} = 2^{\aleph_\beta}$?
Let $\gamma=\omega$ (the first transfinite ordinal). Is it consistent with ZFC that for all ordinals $\alpha, \beta < \gamma$ it holds that $2^{\aleph_\alpha} = 2^{\aleph_\beta}$?
If yes, can the ...
- 6,819
1
vote
1
answer
1k
views
Shortest formal statement equivalent to the continuum hypothesis
What is the shortest formal statement you can write that is provably equivalent to the Continuum Hypothesis in ZFC?
Please use only variables and the following symbols: $\forall, \exists,\lor,\land,\...
- 6,819
2
votes
3
answers
674
views
Notion of internality in model theory
Good evening,
Can someone explain to me the notion of internality in model theory (what it is,
where it comes from...) ?
Thank you
8
votes
2
answers
599
views
Categorical Brouwer-Heyting-Kolmogorov interpretation
Let $\mathcal{L}$ be the language of intuitionistic propositional logic generated by some atomic propositions $t_1, t_2, \ldots$. The Lindenbaum–Tarski algebra of $\mathcal{L}$ can be regarded as a ...
- 15.9k
6
votes
4
answers
1k
views
Example of two structures
This is probably a very trivial question, still I don't seem to find an answer.
I'd like to see an example (in some language) of two countable structures $\mathcal{M}_1 $ and $ \mathcal{M}_2 $ with $...
- 392
14
votes
3
answers
2k
views
Is the Axiom of Union independent of the rest of ZF?
Short version: Is the axiom of union independent of the rest of axioms of ZF?
NO) Tourlakis (2003) says in p. 177 that the axiom of union can be derived from the rest of ZF if an appropriate version ...
- 243
6
votes
0
answers
516
views
Are advanced number-theoretic techniques related to undecidability?
Is there any evidence for or against the idea that some of the important statements of number theory that have only been proved using infinite sets, are in fact undecidable in Peano arithmetic?
Most ...
- 149k
7
votes
2
answers
955
views
Distribution of the computable numbers on the real number line
If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
- 71
12
votes
1
answer
3k
views
Up-to-date version of Principia Mathematica?
Background: I found this interesting translation of Godel's On formally undecidable propositions of Principia Mathematica and related systems I that, along with translating it into English, uses more ...
- 1,052
2
votes
3
answers
299
views
Can the 'linkages' between equivalent extensions of modules of an algebraic group be taken to have bounded length?
I have a conjecture concerning how "tightly" two equivalent $n$-fold extensions of modules over an algebraic group over a field might
be "linked". I suspect that the
question has been already ...
- 511
5
votes
0
answers
2k
views
Is the radical of a homogeneous ideal homogeneous?
Let $S$ be an $M$-graded $R$-algebra, where $M$ is some monoid, and $I\subset S$ an homogeneous ideal. The original, naïve, question, was: is it true that $\sqrt{I}$ is homogeneous? In this generality,...
- 1,811
12
votes
1
answer
744
views
Is the following construction of the 0-Hecke monoid (well) known?
Let W be a Coxeter group with Coxeter generators S. The corresponding 0-Hecke monoid H(W) has generating set S, the braid relations of W and the relations that each element of S is an idempotent. If ...
- 38.6k
0
votes
0
answers
592
views
About a weakening of "union axiom" on ZF set theory
About the axiom of union, from the naive set theory is very natural understand the concept of union (as well others Boolean operation) between the subset os a fixed base set X, this is because $X$ is ...
- 4,165
5
votes
5
answers
1k
views
Union of a object (a set) in the Elementary Theory of the Category of Sets
I see the Todd Trimble article "Elementary Theory of the Category of Sets" on catlab.
I ask: how make (in the categorical setting) the usual union of a set $\cup X=${$y |\exists x\in X: y\in x$}?
...
- 4,165
9
votes
3
answers
1k
views
Is the set of undecidable problems decidable?
I would like to know if the set of undecidable problems (within ZFC or other standard system of axioms) is decidable (in the same sense of decidable). Thanks in advance, and I apologize if the ...
- 193
3
votes
1
answer
383
views
Universe-sized groups with only set-sized normal subgroups, their cardinality in a certain range
Let $\kappa$ be an inaccessible cardinal, and let $G$ be a group with $|G| \geq \kappa$. For any cardinal $\lambda \le \kappa$ (regular, say, but not necessary), say $G$ is $\lambda$-simple if for all ...
9
votes
2
answers
3k
views
Topological proof of the Compactness Theorem in propositional logic without the Axiom of Choice
There is a well-known proof of the Compactness Theorem in propositional logic which uses the compactness of the space $\{0,1\}^P$, where $P$ is the set of propositional variables in consideration. In ...
- 63.1k
3
votes
0
answers
175
views
Intersecting the algebraic closure of independent elements
$G$ is a group with a simple first order theory $T$ as defined by Shelah, hence equiped with a "nice" notion of independence. $G$ also has generic elements. I write $acl^n(A)$ for the set of elements ...
- 1,555
53
votes
1
answer
6k
views
Does $2^X=2^Y\Rightarrow |X|=|Y|$ imply the axiom of choice?
The Generalized Continuum Hypothesis can be stated as $2^{\aleph_\alpha}=\aleph_{\alpha+1}$. We know that GCH implies AC (Jech, The Axiom of Choice, Theorem 9.1 p.133).
In fact, a relatively weak ...
- 39.8k
8
votes
3
answers
746
views
Natural statements independent from true $\Pi^0_2$ sentences
I am looking for sentences in the language of first order arithmetic ($0,1,+,\cdot,\leq$) which are independent from $\Pi^0_2$ consequences of true arithmetic $\Pi^0_2\text{-}\mathsf{Th}(\mathbb{N})$. ...
- 5,502
7
votes
1
answer
722
views
How is called a semigroup...
Does anyone know, how is called a semigroup in which every equation $ax=b$ has only a finite set (maybe empty) of solutions?
- 3,110
9
votes
2
answers
887
views
Are there standard examples of stable theories that are undecidable?
What is known about decidability of various first order theories studied in stable model theory, geometric model theory, o-minimality? For example, is there a natural example of an undecidable first ...
- 1,299
31
votes
8
answers
3k
views
Unique existence and the axiom of choice
The axiom of choice states that arbitrary products of nonempty sets are nonempty.
Clearly, we only need the axiom of choice to show the non-emptiness of the product if
there are infinitely many ...
13
votes
2
answers
1k
views
Two questions about vector spaces absent AC.
My questions are motivated by
this question
which asks, in the absence of AC, whether a subspace of a vector space with a basis must have a basis.
Does every real vector space embed isomorphically ...
- 31.5k
1
vote
1
answer
782
views
Partial subsets of a given set: reference request
Given a set or space X, a characteristic function on X is a function whose domain is X and whose value is either 0 or 1. The subsets of X may be taken as defined by characteristic functions on X.
It ...
- 327
2
votes
1
answer
362
views
quantifier order in monadic first-order logic
In (polyadic) first-order logic, for any sentence $\psi(x,y)$ with variables $x$ and $y$ free, we have $(\exists y)(\forall x)\psi(x,y)\vDash (\forall x)(\exists y)\psi(x,y)$ but not the reverse ...
- 1,189
13
votes
1
answer
1k
views
Large cardinal axiom: everything that happen once must happen an unbounded number of times
I remember reading something about a large cardinal axiom saying something like
If some cardinal $\kappa$ has some property $P$, then there should be a proper class of cardinals with the property $...
- 3,033
12
votes
2
answers
969
views
A Model-Theoretic Helly's Theorem
There is a combinatorial question posed to me (or rather, posed near me) by my adviser. I am having quite a lot of difficulty proving it. It goes:
For any NIP theory $T$ (complete with infinite ...
- 1,979
0
votes
2
answers
963
views
For the symmetric group on an infinite set, is there a generating set of strictly smaller cardinality? [closed]
Let $S_{\kappa}$ denote the symmetric group on some set of cardinality $\kappa$. Does there exist a generating set $X \subset S_{\kappa}$ such that $|X| < |S_{\kappa}|$ ($\stackrel{?}{=} 2^{\kappa}$...
- 19
10
votes
0
answers
317
views
full support iteration of semiproper forcings
Suppose $\langle P_\alpha,\dot{Q}_\alpha:\alpha\leq\omega_1\rangle$ is a full support iteration of (semi)proper forcings. Is the full limit $P_{\omega_1}$ (semi)proper or at least stationary set ...
- 489
2
votes
0
answers
434
views
Showing that every satisfiable sentence with at most two variables has a finite model
I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. My attempts were unsuccessful.
This is an ...
- 21
4
votes
2
answers
420
views
End extensions of models which do not preserve axioms
Assuming the axiom of choice there is a neat way defining inaccessible cardinals as uncountable, regular, strong limit cardinals.
Without the axiom of choice we have several notions of ...
- 39.8k
65
votes
7
answers
23k
views
Can the Riemann hypothesis be undecidable?
The question is contained in the title; I mean the standard axioms ZFC. The wiki link: Riemann hypothesis. There are finite algorithms allowing one to decide if there are non-trivial zeroes of the $\...
- 659
5
votes
0
answers
301
views
When does $\operatorname{Aut}(M)$ preserve a linear order?
I have a general-type question:
Let $M$ be a countable structure that is ultrahomogeneous, i.e. every (partial) isomorphism between finitely generated substructures of $M$ extends to an automorphism ...
- 2,882
3
votes
1
answer
483
views
Examples of Graphs with Trivial Definable Closure
If I'm giving a lecture on trivial definable closure (as a property of graphs), what is a good example of a graph that I can easily draw to depict the concept of trivial dcl?
- 31