All Questions
1,142 questions
7
votes
1
answer
540
views
Are larger large cardinals less expressible?
First note to the following well known theorems:
Theorem (1): The notion of "$x$ is a strongly inaccessible cardinal" is first order expressible and $\Pi_{1}$.
Theorem (2): ...
user36136
7
votes
0
answers
274
views
Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?
Given a Diophantine equation it is not decidable if it has integer solution.
I. Is there a Diophantine set $\mathcal D_{unique}$ satisfying the properties
every member in $\mathcal D_{unique}$ is a ...
- 13.9k
7
votes
1
answer
500
views
Elementary Embeddings and Relative Constructibility
Suppose $$j:M\prec N$$ is a non-trivial elementary embedding. Under what conditions on the sets (classes?) $M$ and $N$ (or even the critical point of $j$) does $j$ extend to an elementary embedding $$...
- 971
7
votes
5
answers
2k
views
What axioms are stronger than the Axiom of choice?
What other axioms in set theory are stronger than AC ? I mean what are those axioms that will imply AC ?
user30338
7
votes
0
answers
194
views
Factoring a function from a finite set to itself
Let $S$ be a finite set and $f: S \to S$ be a function. Let $k = |f(S)|$ and let $\alpha$ be the partition of $S$ into $f$-fibers, i.e. $\alpha = \{ \alpha_t \}_{t \in f(S)}$ where $\alpha_t = f^{-1}(\...
- 695
7
votes
3
answers
426
views
What are other theories of causality besides graphical models and Bayesian networks?
I am trying to find some data structures/mathemetical theories to represent causal relationships which differ from graphical models or Bayesian Networks. Any ideas?
- 71
7
votes
2
answers
878
views
Are computable models sufficient?
What I mean is this. By downward Lowenheim-Skolem theorem, first-order formula Q is a always true iff it is true in every countable structure. But is there some first-order formula Q which is true in ...
- 1,175
7
votes
1
answer
393
views
Models with fixed cardinality of non-Lebesgue measurable sets
In the usual $\mathsf{ZFC}$, we know that there are $2^\mathfrak{c}$ many subsets of $\mathbb{R}$ that are not (Lebesgue) measurable. On the other hand, the Solovay model also provides us a model of $\...
- 1,442
7
votes
1
answer
1k
views
What are current trends/questions in algebraic logic?
What are current trends/questions in algebraic logic? I mean the research developed by Paul Halmos.
Could anyone give some references for the overview of its history? Any overview of its application ...
- 3,094
7
votes
1
answer
324
views
Inaccessible becomes successor of singular
Is it possible, starting from any large cardinal assumption, to find a countably closed forcing $\mathbb{P}$ such that for some inaccessible $\kappa$, $\Vdash_\mathbb{P} "\kappa = \lambda^+$ and $\...
- 18.6k
7
votes
3
answers
2k
views
Decidable but nonrecursive sets
Until recently, I believed that recursive=decidable,
subscribing to this Wikipedia quote:
"In computability theory, a set is decidable, computable, or recursive if there
is an algorithm that ...
- 151k
7
votes
6
answers
10k
views
A book about model theory
I am looking for a good book about model theory. As this is obviously too vague, let me
explain what I am looking for and why.
First I am interested about the basics and foundations of model theory. ...
7
votes
1
answer
712
views
Equivalence between Lowenheim-Skolem Theorem and Godel Completeness
In papers published 1920 and 1922, Skolem offered two separate proofs of a result due to Lowenheim. On this basis we can distinguish a strong and a weak version of the Lowenheim-Skolem theorem as ...
- 583
7
votes
2
answers
1k
views
Ordinal analysis and proofs of consistency
$\epsilon_0$ is the proof-theoretic ordinal of PA. Gentzen proved the consistency of Peano's first-order axioms for arithmetic using primitive recursive arithmetic and induction up to $\epsilon_0$.
...
- 22.3k
7
votes
1
answer
597
views
Hyperimaginaries and continuous logic
Classical (i.e., discrete) logic is well positioned to study imaginaries in part because the $T^{eq}$ construction allows us to treat imaginary sorts as we would treat any other sort. With ...
user71137
7
votes
2
answers
896
views
Iterated forcing and CH
I need some help with this theorem: if $P_\beta=\langle P_\alpha,\dot{Q}_\alpha:\alpha\leq\beta\rangle$, $\beta<\omega_2$, is a CSI of proper forcings, $P_\alpha\Vdash \lvert \dot{Q}_\alpha\rvert\...
- 71
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
7
votes
1
answer
262
views
Different ways of making $HOD$ far from $V$
There are different criteria for building a model $V$ of $ZFC$ which is far from its
$HOD$, for example:
$(A)$ Cardinality criteria: For this in a joint work with James Cummings and Sy Friedman, we ...
- 32.2k
7
votes
1
answer
491
views
"Robinson arithmetic" for (some) levels of $L$?
I'll write "$\mathcal{L}_\alpha$" for the fragment $\mathcal{L}_{\infty,\omega}\cap L_\alpha$.
Say that a countable admissible $\alpha$ is Robinsonian if there is some sentence $\varphi\in\mathcal{L}...
- 20.5k
7
votes
2
answers
735
views
For a partition of $\mathbb{R}$ into countably infinite sets, must there be an almost-disjoint family of $2^{\frak c}$ many selectors?
My question arises from a construction I gave in my recent
answer to a question of Alexander Pruss concerning large families of independent non-measurable sets of reals. In that argument, using
the ...
- 236k
7
votes
1
answer
2k
views
Least ordinal not in a countable transitive model of ZFC
Frequently it is useful do deal with countable transitive models M of ZFC, for example in forcing constructions.
The notion of being an ordinal is absolute for any transitive model, so certainly if ...
- 884
7
votes
4
answers
572
views
A conservative extension of Peano Arithmetic
Ulrich Kohlenbach makes the following intriguing comment here:
"In the 70s S. Feferman introduced a mathematically strong system S=restricted(PA^omega)+QF-AC+mu for classical mathematics (and in ...
- 16.6k
7
votes
1
answer
181
views
Lachlan on topology for priority arguments
There is a set of notes by Lachlan from 1973 on casting priority arguments in topological language; references to these notes are few and far between, but one source refers to them as "Topology for ...
- 20.5k
7
votes
2
answers
370
views
Wants: Polynomial Time Algorithm for Decomposing a Multiset of Rationals into Two Additive Subsets.
First, allow me to say that this problem was posed to me by a professor in the department. It is related to his research in a way that I do not know. However, since I couldn't come up with anything ...
- 4,842
7
votes
1
answer
621
views
Failure of Shoenfield's Absoluteness
Shoenfield's absoluteness states that if $M \subseteq N$ are models of $ZF$ and $M \supseteq \omega_1^N$, then every $\Sigma^1_2$ formula with parameters in $M$ is absolute between $M$ and $N$. In ...
- 133
7
votes
2
answers
455
views
Ultrafilters preserved by $\mathbb{P}$ but not by products?
Let $U\in V$ be an ultrafilter on $\omega$. We say $U$ is preserved under forcing with $\mathbb{P}$ if $\Vdash \forall x\subset \omega \ \exists Z\in U \ Z\subset x \vee Z\subset x^c$. In other words,...
- 3,038
7
votes
1
answer
291
views
Reducing largeness notions, uniformly
This question is a particular take on the following theme. Suppose $A$ and $B$ are two notions of "large subset of $\omega^\omega$;" when is there a uniform method for turning an element of $...
- 20.5k
7
votes
0
answers
269
views
Something like "o-minimal ordinal analysis"
Below, by "nice structure" I mean "o-minimal expansion of $(\mathbb{R};<)$ by countably many continuous functions and open relations."
Suppose $\mathfrak{A}=(\mathbb{R};<,......
- 20.5k
7
votes
9
answers
7k
views
Ultrainfinitism, or a step beyond the transfinite
Cantor has, in the immortal words of D. Hilbert, given all of us a paradise (or perhaps, I would rather say, a great vacation spot), the TRANSFINITE.
$\aleph_0, \aleph_1,\aleph_2\dots$
the lists ...
- 7,853
7
votes
1
answer
306
views
On the cardinal arithmetic of accessible categories
If $\lambda, \mu$ are regular cardinals, say that $\lambda \trianglelefteq \mu$ if $\lambda \leq \mu$ and
$$\forall X, \, |X| < \mu \implies \mathrm{cf} (P_\lambda(X)) < \mu$$
Here $P_\lambda(X)...
- 64k
7
votes
2
answers
488
views
Is every cancellative semigroup a subdirect product of subdirectly irreducible cancellative semigroups?
By a classical result of Birkhoff (that is, Theorem 2 in [G. Birkhoff, Subdirect unions in universal algebra, Bull. AMS, 1944]) and the trivial fact that the class of semigroups is closed under the ...
- 10.5k
6
votes
1
answer
756
views
Lawvere's 'Categories of space and of quantity" - the projection formula
I'm trying to read bits and pieces of W. Lawvere's Categories of Space and of Quantity, and, as usual have lots of questions. Page numbers will refer to the number printed on the corners of the pages.
...
- 10.5k
6
votes
1
answer
205
views
Preserve validity between the two Kripke frames
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $n \geq 1$, let $\mathcal{C}_n$ denote the frame which is shown in Fig.1. ...
- 53
6
votes
1
answer
727
views
What is the consistency strength of this theory?
Language: first-order logic
Primitives: $=, S, \in $ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation).
Axioms: those of identity ...
- 11.3k
6
votes
2
answers
566
views
Is there a perfect set of ground model reals in the Cohen extension?
This question is motivated by the "interesting tidbit" in Hamkins' response here: https://mathoverflow.net/a/99025/10671, in which he demonstrates that, after Cohen forcing, there is a perfect set ...
- 1,146
6
votes
3
answers
472
views
Spaces with unique endomorphism monoids
If $(X,\tau)$ is a topological space, let $\text{End}(X)$ denote the collection of all continuous maps $f: X\to X$. With composition, this becomes the endomorphism monoid $(\text{End}(X), \circ)$.
We ...
- 48.9k
6
votes
1
answer
541
views
Does Playfair imply Proclus?
I am interested in the interplay between the Playfair and Proclus Axioms in linear spaces.
By a linear space I understand a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of ...
- 42k
6
votes
1
answer
419
views
A special c.c.c forcing notion and adding minimal generic reals
This question is related to my question "Forcing with c.c.c forcing notions, Cohen reals and Random reals".
A natural way to answer Prikry's conjecture is to build a c.c.c. forcing notion which adds ...
- 32.2k
6
votes
1
answer
398
views
Conservativity of multiplicative linear logic over intuitionistic multiplicative linear logic
It is well known that multiplicative linear logic (MLL) is conservative over intuitionistic multiplicative linear logic (IMLL). In other words, if an IMLL formula is provable in MLL then it is already ...
- 2,896
6
votes
0
answers
241
views
ITTMs with higher types
What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set?
...
- 7,545
6
votes
1
answer
604
views
Embedding of classical into intuitionistic linear logic
Following on from this recent question, there is another construction that is well-known, but I don’t know a good primary source for: the Kolmogorov-style double-negation embedding of classical into ...
- 2,896
6
votes
2
answers
522
views
addition of definable numbers decidable?
Define a number generating machine to be a total turing machine running on input alphabet {0,1} (or, any ary), that given input n (in binary) outputs a digit (binary or decimal or whatever).
Given ...
- 119
6
votes
5
answers
3k
views
A meta-mathematical question related to Hilbert tenth problem
I am reading Bjorn Poonen's very nice survey on Hilbert's Tenth problem
(http://www-math.mit.edu/~poonen/papers/uniform.pdf), and while I believe I understand the mathematics well, I have widespread ...
- 26k
6
votes
1
answer
309
views
Failure of Cantor-Bernstein for the Levy Collapse
Related to this question, is it possible to give an example of the failure of Cantor-Bernstein for complete embeddings of forcing notions involving the Levy Collapse $Col(\omega,<\kappa)$? Suppose ...
- 18.6k
6
votes
1
answer
969
views
Is Ackermann's set theory minus class comprehension equal to ZF?
Ackermann in 1956 proposed an axiomatic set theory.
Reinhardt proved that Ackermann's set theory equals ZF
It's clear that Zermelo set theory can be interpreted in Ackermann's set theory minus class ...
- 11.3k
6
votes
1
answer
226
views
Are $G$-limits of a slender group $G$ in the space of marked groups also slender?
A group $G$ is slender if every subgroup $H \leq G$ is finitely generated. This includes polycyclic-by-finite groups. Such groups are also called noetherian.
Suppose that $L$ is a $G$-limit group in ...
- 1,033
6
votes
1
answer
485
views
Show that the positive existential theory is undecidable
To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...
- 309
6
votes
3
answers
537
views
Limits of determinacy on reals
For $X\subseteq\mathbb{R}^\omega$, say that $X$ is determined if the associated game on $\mathbb{R}$ of length $\omega$ (players I and II alternate playing reals, player I wins iff the sequence built ...
- 20.5k
6
votes
1
answer
742
views
Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?
EDIT: Noah Schweber helpfully points out that $\mathsf{ACA}_0$ is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
- 708
6
votes
3
answers
837
views
Is the power set axiom essential for constructing L?
Take ZFC, remove axiom of Power set, and put instead of it the following axiom:
Axiom of Successor Cardinals: $\forall \kappa\, \exists x \, \forall \alpha \, ( \alpha \leq \kappa \to \alpha \in x)$
...
- 11.3k