All Questions
1,458 questions with no upvoted or accepted answers
4
votes
0
answers
236
views
Does absoluteness imply a club dichotomy?
My question is about two types of consequence of large cardinals, considered over ZFC on their own.
First, we have statements of the form, "The club filter on $\omega_1$ is an ultrafilter when ...
- 20.5k
4
votes
0
answers
379
views
Forcing without choice: when countable sets yield reals
One natural way to show that a forcing adds no new reals is to show that it is countable closed (EDIT: this is somewhat misleading, see Joel's comment below). However, it turns out that this is ...
- 20.5k
4
votes
0
answers
161
views
Preservation of Baumgartner's I-ultrafilters under various forcings
For $I\subset \mathcal{P}(2^\omega)$, an ultrafilter $U$ on $\omega$ is said to be an I-ultrafilter if for all $f:\omega \to 2^\omega$, there exists $A\in U$ such that $f''[A]\in I$ [Baumgartner]. In ...
- 3,038
4
votes
0
answers
219
views
Construction of model of arithmetic from an arbitrary model
Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that:
$M'\models PA^-$ (or $...
- 1,689
4
votes
0
answers
189
views
Are Braid Groups with Finitely many Generators NIP?
I am curious what braid groups (strings in $\mathbb{R}^3$) are NIP. Consider the following:
Let $B_\mathbb{N}$ be braid group with "braids" indexed by the natural numbers (alternatively, the ...
- 756
4
votes
0
answers
115
views
Ref request: modelling regular theories as an injectivity condition
The background to the following observation is standard material in categorical logic, and I thought this was was too — I don’t remember learning it, but I don’t think it is original — but I can’t now ...
- 21.3k
4
votes
0
answers
205
views
Set theory and forcing from the point of view of a formal system $G^+$ of Gentzen type
There are four papers by Vladimir Alfeevich Kuznetsov, which discuss the above titled topic:
(1) Some problems in set theory from the standpoint of a formal system G+ of Gentzen type. (Russian) Akad. ...
- 32.2k
4
votes
0
answers
233
views
How distributive are the bad Laver tables?
Suppose that $n\in\omega\setminus\{0\}$. Then define $(S_{n},*)$ to be the algebra where $S_{n}=\{1,...,n\}$ and $*$ is the unique operation on $S_{n}$ where
$n*x=x$
$x*1=x+1\,\text{mod}\, n$ and
if $...
4
votes
0
answers
77
views
Catenarity of monoid algebras
Let $R$ be a commutative ring, let $M$ be a commutative monoid, and let $R[M]$ denote the corresponding monoid algebra. Suppose further that $R$ is universally catenary. One may ask for conditions on $...
- 6,700
4
votes
0
answers
126
views
Lascar strong types in fragments of arithmetic
Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.)
Definition Given a saturated model ${\cal M}$ ...
4
votes
0
answers
268
views
Primitive Closure Arithmetic
I am researching a system that was designed by myself and what I call PCA (Primitive Closure Arithmetic), because it looks like PRA.
The differences are:
- PRA uses recursive definition with a ...
- 1,659
4
votes
0
answers
241
views
Is the lowenheim-skolem number of nth order logic larger than the corresponding number for 2nd order logic
According to this paper, by Vaananen, the $LS$ number for $2^{nd}$ order logic is given by "the supremum of $Π_{2}$-definable ordinals", where "The Lowenheim-Skolem number $LS(L)$ of $L$ is the ...
- 95
4
votes
0
answers
220
views
Fixed Points of the Friedman Stanley Jump
Consider the situation of a pair $(X,E)$, where $X$ is a standard Borel space and $E$ is an invariant equivalence relation on $X$*. The Friedman-Stanley jump of this pair is an equivalence relation $...
- 1,979
4
votes
0
answers
276
views
Quasi-disjoint subsets of an infinite set and $\neg \mathsf{AC}$
Is it consistent with $\mathsf{ZF}$ (without $\mathsf{AC}$) that there is an infinite set $X$ and a subset $S\subseteq\mathcal P(X)$ of the same cardinality as $\mathcal P(X)$ with the property that ...
- 48.9k
4
votes
0
answers
152
views
On the computational complexity of the Hilbert polynomial of numerical semigroup rings
Let $(R, \mathfrak{m}) = k[[X^a, X^b, X^c]]$, $a<b<c$, $gcd(a, b, c) = 1$, be a semigroup ring. We have $R$ is a Cohen-Macaulay local ring of dimension one. It is well known that $\ell(R/\...
- 2,773
4
votes
0
answers
108
views
TCAs (total combinatory algebras) with oracles
Is there a natural, non-trivial example of a TCA (total combinatory algebra, cf. pca) with a natural notion of an oracle?
- 354
4
votes
0
answers
225
views
A construction on commutative monoids similar to the semidirect product
Let $M_1$ and $M_2$ be commutative monoids, $M_1$ written additively with identity $0$ and $M_2$ multiplicatively with identity $1$. Furthermore, let $M_2$ act on the left on $M_1$ via monoid ...
- 492
4
votes
0
answers
789
views
Examples of unproven but likely true existential sentence (in the sense of incompleteness)
Some examples of universal statements that are unproven but likely true include the Riemann hypothesis (all non-trivial zeros of the zeta function have real part 1/2) and the Goldbach conjecture (all ...
- 149
4
votes
0
answers
350
views
Is there any research of universal algebras axiomatized by non-Horn clauses?
A Horn clause in the language of a universal algebra is a disjunction of equations and of at most one inequality
("equation" and "inequality" are the terms used by A.Horn in his paper "On sencences ...
- 889
4
votes
0
answers
106
views
$n$th order arithmetic with predicates for orders
Two papers I have looked at lately axiomatize $n$-th order arithmetic in a single sorted language with predicates $Z_1,\dots,Z_n$ and axioms like $\forall x(Z_1(x)\vee\dots\vee Z_n(x))$ to say ...
- 11.1k
4
votes
0
answers
199
views
Correspondence between numerical semigroups and polynomials?
A numerical semigroup $A$ is defined as a subsemigroup of the semigroup $(\mathbb{N},+)$ of the positive integers such that the set $\mathbb{N}\setminus A$ is finite. Equivalently (for a subsemigroup) ...
4
votes
0
answers
269
views
Relation between fundamental theorem of Ehrenfeucht-Fraisse games and notions of bisimulation and simulation
Vijay D alluded to the relation between the fundamental theorem of Ehrenfeucht-Fraisse games and notions of bisimulation and simulation in response to the whats-a-magical-theorem-in-logic question.
...
- 41
4
votes
0
answers
118
views
Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$
Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in $M$....
- 3,038
4
votes
0
answers
568
views
About "natural proof" of Razborov and Rudich
The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...
- 781
4
votes
0
answers
703
views
Is there a notion of "predicative given the real numbers"?
A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
- 4,597
4
votes
0
answers
330
views
determine if a toric variety is Gorenstein
Let $G$ a simply connected group over $k$ and $car(k)=0$.
Let $T_{+}=(T\times T)/Z_{G}$ we consider the closure $\overline{T}_{+}$ of the torus $T_{+}$ in $\prod End(V_{\omega_{i}})\times\prod\...
- 3,472
4
votes
0
answers
321
views
strong order property in continuous logic
I am wondering what is the accepted version of the strong order property in continuous logic.
The definition for classical logic is as follows:
$T$ has SOP$_n$ (for $n\geq 3$) if there is a formula $\...
- 3,274
4
votes
0
answers
372
views
How to get the modern logic formulas in Principia Mathematica
Recently, we have contrived some procedures based on resolution method. So, we want to test these procedures.
I know that many propositions are presented by logic formulas in Principia Mathematica. ...
- 41
4
votes
0
answers
212
views
Alternate proof of van de Wiele's theorem in E-recursion
Hello, all
I'm currently trying to understand $E$-recursion theory, which is a generalization of classical recursion theory to arbitrary sets. One of the difficulties I'm having with understanding $E$...
- 20.5k
4
votes
0
answers
396
views
Is there a homological way to compute quiver presentations?
I have recently been studying with colleagues the representation theory of certain finite monoids that come up in probability theory and combinatorics, see Ken Brown's beautiful survey here.
These ...
- 38.6k
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
4
votes
0
answers
512
views
Homogeneous Structures
Let $M$ be a countable structure that is homogeneous, i.e. every isomorphism between finitely generated substructures of $M$ extends to an automorphism of $M$. Let $\phi_M$ be the Scott sentence of $M$...
- 2,882
4
votes
0
answers
570
views
Is this observation about the Borel Hierarchy trivial?
Hello, consider the following theorem. Is it trivial? Is it interesting? Is it worth including in a paper if I can prove it in 1 line as a corollary?
Theorem: Suppose $n>0$ is a natural. ...
- 121
4
votes
0
answers
577
views
Tropical Properties From Algebraic Geometry
What properties of tropical geometry (Starting from a valued Field) can be proven to be true using their analogue in algebraic geometry? For example, using the valuation on the Puiseux series $\mathbb{...
- 345
4
votes
0
answers
373
views
Sentences Preserved by Direct Products (including the Empty Product)
Consider the class of all structures for a given signature in first-order logic. Let $S_i$ be a family of structures, and $\oplus S_i$ be the direct product of the family. You can extend the notion ...
- 6,870
4
votes
0
answers
939
views
Proofs of Baire category theorem
I would like to have a list of proofs of the fact that the real line is not meager (also very useful would be a reference to such a list, if it already exists somewhere).
My motivation is the ...
- 315
4
votes
0
answers
306
views
To what extent MSO = WS1S, when adding relations?
Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures:
$${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...
- 786
4
votes
0
answers
1k
views
Associative binary operations on natural numbers
Which are all the associative binary operations on natural numbers ?
Certain results in this regard can be found in arxiv:math/0508215.
It appears that such associative operations cannot grow too fast....
3
votes
0
answers
54
views
Does there exist a multi-valued "monotone" and "compact" map from a Boolean algebra to the "free" part of $\mathcal{P}(\kappa)$?
This is a follow-up to my previous question, which has a negative answer. Here is the most general version that I'm interested:
Does there exist a Boolean algebra $A$, an infinite cardinal $\kappa$, ...
- 2,830
3
votes
0
answers
120
views
References on P vs NP under various axiomatic systems
I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem.
This problem has resisted attacks ...
- 31
3
votes
0
answers
90
views
Existence of symmetric total measures
Is it consistent that there is a total finitely additive measure $μ$ on $ℝ$ extending the Lebesgue measure such that for every Borel Lebesgue-measure-preserving bijection $f$ of $ℝ$, $∀α∈Ord \, ∀s∈Ord^...
- 7,545
3
votes
0
answers
153
views
What is known about the word problem on free algebraic models?
Consider the fragment of first-order logic with equality and universal quantification as the only logical symbols; we call this logic the logic of universal algebra. I am interested in languages $\...
3
votes
0
answers
250
views
Action (of a graded monoid) required
Reference request: Did the construction below appear anywhere before? Any mentions of it or especially any links to something commonly known would be really helpful. I feel that it might be related to ...
- 321
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
3
votes
0
answers
97
views
Can the differential field of d.c.e. reals be nicely construed as a field of functions?
This question is basically a special case of this older question of mine, which is still unanswered.
Let $\mathcal{D}$ be the field of d.c.e. reals; these turn out to be exactly the reals $\alpha$ for ...
- 20.5k
3
votes
0
answers
76
views
Why does the following test for protoalgebraicity work?
Remark. Crossposted from Math SE due to lack of responses.
The following text appears in Janusz Czelakowski's "Protoalgebraic Logics":
Suppose there exists a class $\mathbf{K}$ of matrices ...
- 31
3
votes
0
answers
183
views
Can we have a theory that interpret $\sf ZFC$, proves existence of an infinite set, and yet prove all of its sets being Dedekind finite?
If we start with axioms of $\sf ZF$ replace the axiom of Infinity with an axiom stating the existence of a set that doesn't have an injection to a von Neumann natural, and replace the axiom of Power ...
- 11.3k
3
votes
0
answers
89
views
Ordering the elements of a semigroup by $a \le b$ iff $a=b$ or $b=ab=ba$
Let $S$ be a semigroup, written multiplicatively. The binary relation $\le$ on (the underlying set of) $S$, whose graph consists of all pairs $(a,b) \in S \times S$ such that $a = b$ or $b = ab = ba$, ...
- 10.5k
3
votes
0
answers
130
views
Is Quine's Mathematical Logic "ML" consistent with Azcel's Extensionality?
Now that Holmes had proven the consistency of adding Extensionality to Stratified Comprehension (i.e. $\sf NF$), a question along the same vein presents itself:
Is Aczel's Extensionality axiom ...
- 11.3k
3
votes
0
answers
211
views
Intuitionistic set-theoretic geology
Work in ZF, if there are proper class many supercompact cardinals, then all grounds are uniformly definable. Hence under reasonable assumption, we can have choiceless set-theoretic geology.
But can we ...
- 695