All Questions
1,135 questions
5
votes
1
answer
627
views
Can there be no "surprisingly averageable" second-order sentences?
Say that a second-order sentence $\varphi$ is averageable iff there exists some infinite cardinal $\kappa$ and some nonprincipal ultrafilter $\mathcal{U}$ on $\kappa$ such that for every $\kappa$-...
- 20.5k
5
votes
3
answers
884
views
"name" for the ground model
I am a beginner of forcing, often I read from some articles something like "$p \Vdash \dot{G}$ is $P$-generic over $\check{M}$" (where $M$ is a countable transitive model, for instance).
Q1. I ...
- 53
5
votes
1
answer
421
views
Large cardinal axioms and the perfect set property
It is known that if there is a measurable cardinal then every $\Pi_1^1$ set has the perfect set property (i.e it is either countable or contains a copy of $2^{\omega}$). Also if we have $\Pi_1^1$-...
- 3,804
5
votes
2
answers
407
views
What's the consistency strength of this form of reflection?
Working in mono-sorted first order logic with equality $``="$ and membership $``\in"$:
Define: $set(x) \equiv_{df} \exists y \, (x \in y)$
Axiomatize:
Extensionality: $( a \subseteq b \land b \...
- 11.3k
5
votes
2
answers
2k
views
How many models of Peano arithmetic are isomorphic to the standard model and how many models of Peano arithmetic are non-standard?
I am currently writing a paper on non-standard models of Peano arithmetic and I am having trouble finding references or information that discuss the relative sizes of how many models of Peano ...
- 1,441
5
votes
0
answers
449
views
How many Dedekind-finite sets can $\mathbb{R}$ be partitioned into?
Building off Asaf Karagila's answer to my previous question (Can $\mathbb{R}$ be partitioned into dedekind-finite sets?) on partitioning $\mathbb{R}$ into strictly Dedekind-finite sets:
(1) What ...
- 20.5k
5
votes
1
answer
271
views
Can a nonstandard model of $\mathsf{PA}$ be "$\Delta^1_1$-well-ordered?"
This was asked and bountied at MSE with no response:
My question is the following:
Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-...
- 20.5k
5
votes
1
answer
466
views
Computational complexity of proof verification
Let $\mathcal{L}$ be a recursive first-order theory, with a deductive system $\Xi$ (for instance, Hilbert-Ackerman proof system). Let $\phi$ be a formula and let $l=(\psi_1, \ldots, \psi_n=\phi)$ be a ...
- 3,318
5
votes
2
answers
2k
views
Are all models of ZF + DC + "All set of reals are lebesgue measurable" also models of CH? [duplicate]
Possible Duplicate:
Lebesgue Measurability and Weak CH
I have studied a little set theory and I found that Solovay constructed a model of ZF+DC+"All set of reals are Lebesgue measurable" and I ...
5
votes
1
answer
512
views
Translating first order statements about symmetric groups into the language of numbers and back
A question I was asked recently lead me to the following question. For every closed first order formula $\theta$ in the group signature consider the set $N_\theta$ of natural numbers $n$ such that the ...
user6976
5
votes
1
answer
421
views
First order consequence of a combinatorial principle
(Base theory $RCA_0$)The principle says there exists a function g such that g dominates any X-recursive function for any X in the model.
i.e. For any $f\le_T X$, $\exists b\in M$ such that $g(a)>f(...
- 3,038
5
votes
1
answer
367
views
"Intersection number" of a cardinal
Let $\kappa$ be an infinite cardinal. We call a cardinal $\lambda \leq 2^\kappa$ intersecting if there is ${\cal C}\subseteq {\cal P}(\kappa)$ such that
for every $A\in {\cal C}$ we have $|A|=\kappa$,...
- 48.9k
5
votes
0
answers
276
views
Absoluteness and the scale property for $Π^2_2$ or $Σ^2_2$
Under the diamond principle $◊$ and large cardinal axioms, which of the two pointclasses $Π^2_2$ or $Σ^2_2$ is expected to have the scale property?
Because conditional $Σ^2_2$ absoluteness under $◊$ ...
- 7,545
5
votes
1
answer
667
views
What are key $\Sigma^0_2$ or $\Pi^0_3$ theorems?
I am researching a logical system that is limited to $\Pi^0_2$ sentences and I am busy to prove that FOL + PA is a conservative extension of that system. Meaning that with $\Sigma^0_n$ sentences (that ...
- 1,659
5
votes
1
answer
277
views
Infinite products of forcings
Suppose $M \subseteq N$ are models of ZFC such that $(ORD^\omega)^M = (ORD^\omega)^N$. Let $\langle P_n : n \in \omega \rangle$ be a sequence of countably closed partial orders in $M$, and let $\...
- 18.6k
5
votes
1
answer
316
views
Is this set theory used by Gandy first-order with signature $(\in, \lambda)$?
In On the Axiom of Extensionality, Part II, The Journal of Symbolic Logic, Vol. 24, No. 4 (Dec., 1959), https://doi.org/10.2307/2963897, pp. 287-300, R. O. Gandy shows that a class theory X ...
- 3,574
5
votes
2
answers
1k
views
Large cardinals without the ambient set theory?
In an attempt to understand a bit better large cardinals, I have been thinking along the following lines, which could be summarized under the slogan
Talk about cardinals without the
(ambient) ...
- 7,853
5
votes
4
answers
866
views
A Fraïssé class without the strong amalgamation property.
I am trying to find some examples of Fraïssé classes that do not have the strong amalgamation property. Anyone?
5
votes
3
answers
897
views
Did Gödel prove that the Ramified Theory of Types collapses at $\omega_1$?
Second-Order Arithmetic is considered impredicative, because the comprehension scheme allows formulas with bound second-order variables that range over all sets of natural numbers, including the set ...
- 4,597
5
votes
1
answer
558
views
Why is this set stationary?
Hi
I really need a proof for the following statement by Baumgartner:
There exists a stationary subset of $[\omega_2]^{\omega}$ of size $\aleph_2$.
This is Exercise 38.15. in Jechs Book (2003) and ...
- 2,180
5
votes
0
answers
99
views
Zappa-Szép products of the monoid of integers with itself
Question
What are all the functions $\alpha , \beta : \mathbb{N} \to \mathbb{N}$ satisfying the following functional equations?
$\bullet ~~~~ \alpha(0)=0, \quad \beta(0)=0\\
\bullet ~~~ \...
- 5,482
5
votes
1
answer
1k
views
Can the Knaster-Tarski theorem be proved using the Schroeder-Bernstein theorem?
The reverse can be done easily and the proof is well known I am wondering if the exact same argument can be used to prove reverse as well.
- 51
5
votes
0
answers
153
views
What is known about propositional realizability for the second Kleene algebra and related PCAs?
Short version: Various things are known about realizability of propositional formulas for Kleene's “first algebra” (i.e., $\mathbb{N}$), like examples of realizable but unprovable formulas, and some ...
- 32.5k
5
votes
0
answers
120
views
Is an equilateral triangle constructible in a Tarski plane?
By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
- 41.9k
5
votes
1
answer
694
views
What are examples of non-equivalent virtualizations of a large cardinal?
This is a follow up to my previous question concerning virtual large cardinals, that are generally weaker axioms of infinity obtained from ordinary large cardinals through the so-called virtualization ...
5
votes
1
answer
158
views
(Weakly) minimal subcovers of linear covers
Motivation. The starting point of this question is the trivial observation that if we cover $\mathbb{N}$ with $$\big\{\{0,\ldots n\}: n\in \mathbb{N}\big\},$$ then this cover doesn't have a minimal ...
- 48.9k
5
votes
2
answers
922
views
What is the status of the extreme value theorem in forms of constructive mathematics, such as Smooth Infinitesimal Analysis?
In certain intuitionistic frameworks the extreme value theorem cannot be proved. Depending on the exact framework, counterexamples can be constructed as well; see for example pp. 294-295 in
Troelstra,...
- 16.6k
5
votes
0
answers
193
views
"Very $L$-like" models, part 1: large cardinals
(The original version of this question was much narrower and less natural; but see the edit history if interested.)
Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ ...
- 20.5k
5
votes
0
answers
187
views
Isbell duality for monoids and groups
Isbell Duality
$\newcommand{\IsbellSpec}{\mathsf{Spec}}\newcommand{\IsbellO}{\mathsf{O}}\newcommand{\Sets}{\mathsf{Sets}}\newcommand{\rmL}{\mathrm{L}}\newcommand{\rmR}{\mathrm{R}}\newcommand{\B}{\...
- 11.8k
5
votes
1
answer
310
views
Is there a statement in Presburger arithmetic about primes this simple heuristic fails for?
I came up with the following conjecture while thinking about ways to formulate some heuristics about primes:
Conjecture: Given a statement $s$ in Presburger arithmetic, using an additional unary ...
- 3,319
5
votes
1
answer
564
views
Hilbert's and Gödel's expanded definition of "Recursive Function"
There is a very interesting comment in this post:
I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the ...
- 4,907
5
votes
2
answers
402
views
Maximal commuting subsets of $\text{End}(X)$
Let $X$ be a set and let $\text{End}(X)$ be the set of all functions $f:X\to X$. We say that $f, g\in \text{End}(X)$ commute if $g\circ f = f\circ g$, and $S\subseteq \text{End}(X)$ is a commuting ...
- 48.9k
5
votes
4
answers
2k
views
Subsystems of Peano arithmetic and incompleteness theorem
I think everyone is familiar with Goedel's incompleteness theorems. In particular they imply that PA (Peano arithmetic) can not prove its own consistency. Now my question is what is the largest ...
- 741
5
votes
2
answers
332
views
Questions on weakly symmetric algebras
A finite dimensional algebra $A$ over a field $K$ is called weakly symmetric in case $soc(P)=top(P)$ for every indecomposable projective module $P$ and it is called symmetric in case $D(A) \cong A$ as ...
- 26.5k
5
votes
1
answer
231
views
Spreading sets - especially without choice
For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.
Suppose I have a set $X\subseteq \mathbb{R}$. ...
- 20.5k
5
votes
2
answers
768
views
Are the types of nonstandard natural numbers within a Z-chain identical?
Hi,
I was wondering how much (if anything) $\mathcal{L}_{PA}$ can express about individual nonstandard elements in a nonstandard model of PA. For instance, presumably it can say that each has $k$-...
- 145
5
votes
0
answers
484
views
How to study formal logic without formally using the notion of a set?
I have recently begun curious in set theory, and when I researched this subject I saw that all axiomatizations of set theory, such as ZFC and NBG, are expressed in the language of first order logic. ...
- 331
5
votes
2
answers
236
views
Descent of flatness from algebras to monoids
Consider a morphism of commutative monoids $u\colon M\rightarrow N$. We say that $u$ is flat, if the tensor product functor $\bullet\otimes_MN$ from the category of $M$-modules to the category of $N$-...
- 6,700
5
votes
2
answers
496
views
How is compactness related to countable saturation?
By Cantor's intersection theorem every decreasing nested sequence of nonempty compact sets has a common point.
A superficially similar result holds that every decreasing nested sequence of nonempty ...
- 16.6k
5
votes
1
answer
427
views
Computable rings similar to Z
(This is related to my question at Computable nonstandard models for weak systems of arithemtic )
Is there a nontrivial computable discrete ordered ring with Euclidean division that is not isomorphic ...
user5810
5
votes
1
answer
432
views
Is there a class choice principle over MK that is equivalent to class well ordering over MK?
$\sf MKCWO$ is the theory obtained by adding a new primitive binary relation $\prec$ to the signature of $\sf MK$ and axiomatize that $\prec$ is a well order on classes, that is:
$\textbf{Transitive:}...
- 11.3k
5
votes
2
answers
734
views
What are the definable sets in Skolem arithmetic?
Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities ...
- 13.9k
5
votes
1
answer
187
views
Persistent finite axiomatizability, relational edition
Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is ...
- 20.5k
5
votes
1
answer
327
views
$\Sigma_n$ version of HOD
Fix a natural number, $n \geq 1$. Consider the class, M, of all sets hereditarily ordinal-definable using some $\Sigma_n$ formula. Since there is a universal $\Sigma_n$ formula, M is definable. Is M ...
- 1,174
5
votes
0
answers
81
views
Which pseudovarieties have (Eilenberg/Schutzenberger) minimal descriptions?
Suppose $\mathscr{V}$ is a pseudovariety in a countable language $\Sigma$. Say that a minimal description of $\mathscr{V}$ (in the sense of Eilenberg/Schutzenberger rather than Reiterman) is a pair $(...
- 20.5k
5
votes
7
answers
6k
views
Ask for recommendations for textbook on mathematical logic
I studied mathematical logic using a book not written in English. I would now like to study it again using a textbook in English. But I hope I can read a text that is similar to the one I used before, ...
- 764
5
votes
2
answers
655
views
$C^n$ And Forcing: Reading a Recent Paper By Kunen
While reading a recent paper by Kunen arxiv.org/abs/0912.3733, which deals with PFA and the existence of certain differentiable functions, (defined on all of $\mathbb{R}$) which map certain $\aleph_1$-...
- 1,615
5
votes
1
answer
180
views
Can a stage of the cumulative hierarchy violate the partition principle?
If we violate the partition principle and add to $\sf ZF$ the axiom that there exists a set $X$ that has a partition on it that is greater in cardinality than the set of singleton subsets of $X$.
Can ...
- 11.3k
5
votes
1
answer
150
views
Does there exist a section of $\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ that is "nearly Boolean"?
The following might be a somewhat esoteric question:
Does there exist an infinite cardinal $\kappa$ and a section $f$ of the quotient map $\pi:\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ (...
- 2,830
5
votes
1
answer
422
views
What is the relationship between non-existence of those kinds of singular sets and AC?
Let's say a set $A$ is super-singular, if and only if, there exists a set $x$ such that $|A|=|\bigcup x|$ and $| A| > |x|$, and for each $y \in x$ we have: $ |y| \not > |x|$ .
A set $A$ is ...
- 11.3k