All Questions
1,460 questions with no upvoted or accepted answers
1
vote
0
answers
177
views
About the sum $\sum_{n=1}^\infty \frac{1}{\mathrm{BB}(n)}$
Let $\mathrm{BB}:\mathbb{N}\to\mathbb{N}$ be the busy beaver function. Eventually $\mathrm{BB}(n)>n^2$ so the sum$$S=\sum_{n=1}^\infty \frac{1}{\mathrm{BB}(n)}$$converges.
Question. What is the ...
- 21
1
vote
0
answers
139
views
Free monoids on posets
I've suddenly found myself working with some free monoids $F(S)$ in which the set $S$ is a poset, and the order extends to an order $F(S)$, satisfying
if (but not only if) $s_1, s_2, \ldots, s_r, t_1, ...
- 12.5k
1
vote
0
answers
219
views
What is the proof theoretic strength of PCF?
Godel's system $T$ means different, although equivalent, things to different people. To people working in the traditon of mathematical logic, $T$ is a quantifier-free equational theory of arithmetic ...
- 482
1
vote
0
answers
339
views
What a good alternative for Mendelson's math logic can I read?
I am a programmer and I am master of computer science. I remember we studied mathematical logic with Mendelson's book "Introduction to mathematical logic" and I barely understood this book ...
- 119
1
vote
0
answers
66
views
Is existence of external rank shifting automorphism proves moving of infinitely ranked stratified power stages of this theory?
In this posting, I've define stratified power sets $\mathcal P^\equiv$ operator.
Now we define $V^\equiv_\alpha$ as the iterative stratified power sets of $V_\omega$ as:
$$V^\equiv_0 = V_\omega \\ V^\...
- 11.3k
1
vote
0
answers
148
views
Why doesn't $\mathsf{B}\Sigma_2$ hold in $\mathsf{RCA}_0$?
For a formula $\varphi(i,u)$ of arithmetic, the bounding principle for $\varphi$ is the statement
$$\forall m \, \Big( \big( \forall i<m\ \exists u\ \varphi(i,u) \big) \to \big( \exists v\ \forall ...
- 788
1
vote
0
answers
126
views
Minimizing all aspects of the definition of Boolean algebra
There are many equivalent ways to describe Boolean algebras. There are a number of different ways to "minimize" the description. We can:
Minimize the number of function symbols.
Minimize ...
- 18.7k
1
vote
0
answers
330
views
Is stratified acyclic ZF consistent with non-trivial automorphisms over $V$?
The folloing is an Edit of the previous question.
By stratified acyclic ZF, it is meant acylic ZF but with restricting Separation and Replacement to stratified instances of them and forbid the use of ...
- 11.3k
1
vote
0
answers
78
views
$\mathsf{NP}$ complete version of 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
1
vote
0
answers
84
views
Hyperarithmetical analysis and finite types
The notion of 'hyperarithmetical set' is well-known (see e.g. [1,p. 18]). In the language of second-order arithmetic, this notion is used to define the notion of 'system of hyperarithmetical analysis'...
- 4,359
1
vote
0
answers
83
views
What is known about the algebraic completion of a monoid?
It is the monoid obtained by adjoining all solutions of polynomial equations. I'll demonstrate how to adjoin a single solution to a polynomial equation to a monoid:
Let $W$ be a monoid and let $p(x)=q(...
1
vote
0
answers
231
views
Has an "algebraic manifold" been defined before? Are there any non-trivial examples?
Let $S$ be a set and $\cdot$ a partial binary operation on $S$. A subset $F\subseteq S$ is $\cdot$-closed if the following condition holds:
for all $f,g\in F$, if $(f,g)\in\mathrm{dom}(\cdot)$, then $...
1
vote
0
answers
102
views
What is the real name for the initial object in the category of "monoid-valued measures of intervals" on transitive relations?
(I'm not asking for a true/false answer; I have a true algebraic fact and I'm looking for a reference in the literature. By the way, there is a version of this theorem that replaces monoid with $R$-...
1
vote
0
answers
52
views
Is every cyclic right action of a cancellative invertible-free monoid on a set isomorphic to the set of shifts of some homography?
The terms are defined in a related question. [1]
Conjecture 1. Let $A$ be a set, $W$ a cancellative invertible-free monoid, and $\cdot\colon A\times W\rightarrow A$ a cyclic right $W$-action generated ...
1
vote
0
answers
71
views
terminology for a kind of two-sided module over a monoid
If $M$ is a monoid object in a pointed category $\mathcal{C}$, then a right $M$-module is an object $X$ equipped with a morphism $\alpha: X\times M\to X$ that satisfies the usual rules. There are ...
- 12.5k
1
vote
0
answers
355
views
On logarithmic schemes
I have two questions on logarithmic schemes
Can we explicitly construct a chart for any coherent logarithmic scheme? By definition of coherence it must have a chart but given a coherent sheaf of ...
- 494
1
vote
0
answers
158
views
Infinite recursive graphs and different ways to build them
I asked this question one week ago on MSE and has received no answer.
Infinite directed graphs (graphs with countably many nodes and edges) have a number of different applications.
They can be ...
- 161
1
vote
0
answers
107
views
Formalization in PA in the Kritchman-Raz proof
In their paper Kritchman and Raz present a proof of Gödel's second theorem using Kolmogorov complexity. To make it work, they operate in some (weak) formal theory $T$ that incorporates some arithmetic,...
- 189
1
vote
0
answers
236
views
Weakly berkeley cardinal
Define $\kappa$ as $\Sigma_n$-weakly berkeley cardinal if for any transitive set $M$ that includes $\kappa$ exist elementary embedding $j:M\rightarrow M$ save only $\Sigma_n$ formulas and critical ...
- 51
1
vote
0
answers
115
views
Disjunction in weakened Robinson arithmetic
Let $ T $ denote the theory obtained by removing the axiom $ \forall x ( x = 0 \lor \exists y \, S y = x ) $ and restricting double negation elimination to disjunction-free formulas of Robinson ...
- 346
1
vote
0
answers
65
views
Algebraization of arithmetic and stronger theories?
Intuitionistic and classical propositional logic, and even classical first-order logic with identity, have algebraic counterparts. Algebraizable logics, 1989, by Willem J. Blok and Don Pigozzi, is a ...
- 3,574
1
vote
0
answers
144
views
Checking existence of proofs of fixed length
This question is a continuation of a related previous question (check here).
Let $\mathcal{L}$ be a recursive first-order theory with the Hilbert-Ackerman's proof calculus, and such that the ...
- 3,318
1
vote
0
answers
87
views
Does a finite procedure for demonstrating truth-functional unsatisfiability count as a deduction method?
Question: Does a semi-effective procedure for demonstrating that a formula is truth-functionally unsatisfiable count as a ``deduction method''?
Background: According to Warren Goldfarb, in his 1928 ``...
- 583
1
vote
0
answers
90
views
Does this hereditary size based definition of cardinality work under grounds weaker than regularity and choice?
To $\sf ZF - Regularity$ add the following axiom:
Hereditary size: $\forall x \ \exists H_x \ \exists f (f: x \rightarrowtail H_x)$
Where: $H_x= \{y: \forall z \in TC(\{y\})\exists f (f: z \...
- 11.3k
1
vote
0
answers
130
views
Completeness of certain formal deduction system
Consider a certain formal system with only axiom Excluded Middle -$EM$
and 18 inference rules:
9 implicative ruules (clearly not independent)
and 9 tautological rules:
If we have substitution at ...
- 774
1
vote
0
answers
150
views
Is there difference in notion of measurability in classical versus constructive?
Are there notions of measure and examples of sets measurable in that measure in classical logic but not in constructive logic (I think there cannot be counterexamples in other direction)? Are there ...
- 1,826
1
vote
0
answers
112
views
"The" axiom of induction up to recursive ordinal $\alpha$ in $\mbox{PRA}$
As far as I understand, Kriesel proved that there exists a recursive relation $R$ of order type $\omega$ such that $\mbox{PRA}+TI(R)$ proves $\mbox{Con}(PA)$, and Beklemishev proved that for any ...
- 1,307
1
vote
0
answers
150
views
Satisfying systems in Gödel's original proof of completeness
Gödel's original proof of completeness shows that a formula of the form $\forall \exists A$ is either satisfiable or refutable. The quantifier-free formula $A$ is composed of individual variables $v_i$...
- 583
1
vote
0
answers
313
views
Is there a second-order expression of '$\kappa$ is Reinhardt' in $NGB$, where $\kappa$ is a cardinal?
In their paper, "Generalizations of the Kunen inconsistency", (Annals of Pure and Applied Logic 163 (2012) 1872-1890, doi:10.1016/j.apal.2012.06.001, arXiv:1106.1951), Hamkins, Kirmayer, and ...
- 6,132
1
vote
0
answers
105
views
Can small class choice be weaker than global choice and stronger than set choice + collection?
In this posting what was termed as "Proper Class Choice" principle turned to be equivalent to Global Choice over the base theory of "MK-Foundation -Limitation of size + Set Replacement*&...
- 11.3k
1
vote
0
answers
278
views
A countable set theory providing choice?
Instead of Zermelo set theory $Z$ take $Y$ = $Z$ minus the power set axiom plus
Enumerability: $\forall x(x\neq \emptyset \to\exists f[f:\mathbb{N}\overset{onto}{\frown}x ])$
$\imath$ is the ...
- 3,574
1
vote
0
answers
61
views
Is there a restrain on the total number of proper classes strictly smaller than the universe in variants of MK?
In an old discussion thread at sci.math, Herman Rubin said:
"
There exist models where all proper classes have the same cardinality;
i.e., the universe is equinumerous with the class of ordinal ...
- 11.3k
1
vote
0
answers
163
views
Can "description" of models revive formalism?
A model of a theory is a structure (e.g. an interpretation) that satisfies the sentences of that theory. Wikipedia
Let $A$ be a set of sentences in some language that has only one extra-logical ...
- 11.3k
1
vote
0
answers
326
views
Can Ackerman set theory without class construction scheme plus a limitation of size axiom prove consistency of ZF?
Take all axioms of Ackermann's set theory, remove the class construction axiom schema.
Add the limitation of size axiom:
$\forall X \forall Y [X \in V \land Y \subseteq V \land |Y|\leq |X| \to Y \...
- 11.3k
1
vote
0
answers
246
views
Skolem's proof of Konig's infinity lemma
I am trying to understand the following passage from Skolem’s (1922) proof of the Lowenheim-Skolem theorem by reference to the contemporary proof of Konig’s infinity lemma:
Let $L_{1,n},L_{2,n},...,...
- 583
1
vote
0
answers
209
views
Uncountable chain of nested sets without choice
Let $\kappa$ be an uncountable cardinal.
Given a set of S of cardinality $\kappa$, I want to construct a chain {$S_\lambda : \lambda \in \kappa$ } such that:
1) Each $S_\lambda$ is a proper subset of ...
- 675
1
vote
0
answers
219
views
Completeness or soundness? Understanding a claim by Gödel
My question concerns a statement by Gödel in 1967. Commenting on Skolem’s failure to infer completeness from his (1922) proof of the Lowenheim-Skolem theorem, Gödel observes that Skolem
did not ...
- 583
1
vote
0
answers
194
views
Induction on open formulas vs. Induction on $\Pi_1$ formulas
There are infinitely many extension to Robinson's $Q$ arithmetic many of which are defined by adding an axiom schema of induction for particular set of formulas.
I am confused about the theory $\text{...
- 173
1
vote
0
answers
250
views
topological properties of $G_{\delta}$ sets in a compact Hausdorff space
I am trying to understand a family of types $\mathcal{F}$ in the set $S(A)$,the set of complete types over $A$ (in the sense of types in model theory) which is a compact and Haurdorff space equipped ...
- 195
1
vote
0
answers
144
views
Which of the known alternative set theories is near in structure to this theory with a universal set and the complement of Russell set?
Before I'll present the exposition of this theory, I'll speak a little bit about the Mereological concept it is meant to catpure.
The idea is to work in Atomic General Extensional Mereology "AGEM", ...
- 11.3k
1
vote
0
answers
106
views
Sentential, first order and higher logics from a categorical perspective
Is there a standard reference for understanding sentential, first and higher order logics from a categorical perspective?
I'm close to knowing enough $1$/$2$/internal category theory to tackle the ...
- 10.1k
1
vote
0
answers
149
views
Relative strength and propositional indistinguishability of non-distributive lattices
Consider the class of bounded non-distributive lattices $\mathbf{Mn}$ ($n\geqslant 3$).
(from left to right: M3, M4, Mn)
Now consider a propositional language over $\{\wedge,\vee,\neg\}$ with the ...
1
vote
0
answers
69
views
How exactly to adapt Brown's collapse from monoids to algebras?
In The Geometry of Rewriting Systems (Springerlink behind paywall), Kenneth Brown describes a method to collapse the bar resolution of a monoid. Roughly:
Given a simplicial set $X$ equipped with a ...
1
vote
0
answers
202
views
What is the normalized complex of a simplicial set with a monoid action?
This question is a follow up to this question I posted on Math.SE. I will make this question self-contained, though.
In a certain point on the paper The Geometry of Rewriting Systems, Kenneth Brown ...
1
vote
0
answers
88
views
Approximating $3SAT$ by polynomials
Given $3SAT$ formula $\phi$ in $n$ variables and a $\mu\in(0,1/2)$ what is the smallest degree of polynomial $f\in\mathbb Z[x_1,\dots,x_n]$ such that for an $(a_1,\dots,a_n)\in\{0,1\}^n$ if $\phi(a_1,\...
- 1,826
1
vote
0
answers
132
views
Is the Upper Banach density always zero with respect to some sequence of Finite subset
The following question came to me while reading the paper 'Density in Arbitrary Semigroups' by Hindman and Strauss.
Question: Given an infinite subset $A$ of $\mathbb{N}$ such that $A^c$ is also ...
- 73
1
vote
0
answers
55
views
Schemes for conditional distributions (monads)
(Note: This is a heuristic question. I'm trying to work out if this idea makes sense. I don't have much background in this area, so apologies if I'm wide of the mark.)
Suppose you have a monad ...
- 121
1
vote
0
answers
111
views
When a semigroup ideal is a determinantal ideal?
Let $S=\langle n_1,...,n_r \rangle$ be a commutative semigroup, and let $I_S \subset k[x_1,...,x_r]$ the associated ideal of $S$, defined as the kernel of the polinomial map $\varphi:k[x_1,...x_n] \...
- 113
1
vote
0
answers
206
views
Is it possible to construct a formal language that allows to refer to specific real numbers that encode ordinals accidentally writable by an ITTM?
Let $A$ denote a particular (fixed) algorithm to encode ordinals as real numbers. The exact technical description of $A$ is irrelevant for this question: it can be any algorithm that is mathematically ...
- 959
1
vote
0
answers
115
views
Consistency of reflective sequences
Is it consistent that there is a measurable cardinal $κ$, a $κ$-complete normal nonprincipal ultrafilter $U$ on $κ$, and $S∈U$ such that for every $T⊂S$ with $T∈U$ and $T$ ordinal definable from $S$ ...
- 7,545