All Questions
1,460 questions with no upvoted or accepted answers
1
vote
0
answers
708
views
What is the consistency strength of this kind of iterating Berkeley cardinals?
[EDIT] After suggestion from Monroe Eskew, and after having an e-mail correspondence with Prof. Joan Bagaria, I'll re-present the older question as the second in a series of 4 questions. I've had an e-...
- 11.3k
1
vote
0
answers
101
views
Questions in proof theory (PRA-provability of EA-theorems, Girards book from '87)
I've been working through a textbook, often encountering difficulties with the exercises.
On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution.
As I understand, ...
- 121
1
vote
0
answers
116
views
n-consistency - provability/truth of $\Sigma^0_n$ and $\Pi^0_{n+1}$ -formulas; n-consistent extensions, etc
I've been working through a textbook, often encountering difficulties with the exercises. On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution.
As I understand, ...
- 121
1
vote
0
answers
82
views
Looking for help in defining a new epistemic logic
I'm looking for some guidance in defining a new epistemic, temporal logic.
I am looking to extend a logic called Sequential Epistemic Logic (SPAL): https://pdfs.semanticscholar.org/dae6/...
- 11
1
vote
0
answers
116
views
A generalized Cauchy type functional equation
Let $(S,+)$ be an abelian semigroup . Let $f:S \to \mathbb C$ be a function such that for some positive integer $n>1$, $f(x+y)^n=(f(x)+f(y))^n,\forall x,y \in S$.
Then is it true that $f(x+y)=f(x)...
- 1,209
1
vote
0
answers
205
views
Lowest Turing degree that allows a Turing machine to tell whether $\operatorname{Con}(PA)$?
Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...
- 6,353
1
vote
0
answers
82
views
What is known about the cohomology of the matrix monoid?
When I say the cohomology of a monoid, I mean that of its classifying space (considering the monoid as a category with a single object).
Let $M_n(R)$ be the monoid of matrices with matrix ...
- 1,726
1
vote
0
answers
51
views
Is there a restriction of Linear Temporal Logic that has a "Markov" property?
I have a problem, that I can formulate as model-finding in Linear Temporal Logic (via Büchi automata). I also have the additional knowledge, that there is always satisfied a Markov-like property, ...
- 283
1
vote
0
answers
255
views
Presentation of amalgamated sum as a quotient of the direct sum
I am currently reading Arthur Ogus' "Lectures on Logarithmic Algebraic Geometry" (https://math.berkeley.edu/~ogus/preprints/log_book/logbook.pdf).
I'm trying to understand why the amalgamated sum of ...
- 65
1
vote
0
answers
40
views
A exemple of a strongly-continuous contraction semigroup : how to prove the contraction?
I am trying to prove that $P_t := e^{\lambda t (P-I)}$ (where $Pf:= \int f(y) P(\cdot , dy)\in \mathcal{C}_0(\mathbb{R}^d)$, for $f\in \mathcal{C}_0(\mathbb{R}^d)$, $P$ being a probability kernel), is ...
- 111
1
vote
0
answers
369
views
Ultraconsistency & Truth
Let $D$ be an effectively generated set of recursive ordinals that contains $0$ and that is closed under an effectively defined ordinal successor function "$+1$" and that have a well defined ...
- 11.3k
1
vote
0
answers
80
views
Compact formal semantics which is incompletable?
I am interested in the relationship between completeness and compactness of formal logical systems. I think it is pretty well known that if an effective proof system can be developed for a formal ...
- 11
1
vote
0
answers
29
views
Generating larger atoms from smaller ones in a simple $\text{C}_0$-monoid
Let $P$ be a finite set, $\mathscr F(P)$ the free abelian monoid with basis $P$ (which I'll write multiplicatively), $H$ a submonoid of $\mathscr F(P)$, and $\mathcal A(H)$ the set of atoms of $H$ (...
- 10.5k
1
vote
0
answers
93
views
Are all normal modal logics isomorphic to this type of algebras?
Consider a Boolean set algebra on a set $\Omega$. Let $\sigma$ be a set function on $\Omega$ such that for all $m\in \Omega$ $\sigma(m)\subset \Omega$. The operator $\square_\sigma$ is defined by $\...
- 53
1
vote
0
answers
92
views
Question Regarding Hierarchies of Functions
The more precise statement of this question is partly inspired by the question Extensions of fast-growing hierarchy. However, I didn't want to derail the original question (since the OP may have ...
- 881
1
vote
0
answers
55
views
Does Sion minimax require choice?
Is the axiom of choice (or equivalent) required to establish Sion's minimax theorem?
H. Komiya's elementary
proof
does not seem not to use any transfinite induction or choice axiom. Is this really ...
- 6,541
1
vote
0
answers
125
views
Can $GPK^{+}_{\infty}$ + $AC_{WF}$ prove "$ZFC$ proves that the class of ordinals is not weakly compact for definable classes?
Consider the topological set theory $GPK^{+}_{\infty}$ +$AC_{WF}$, where $GPK^{+}_{\infty}$ is defined as follows (this from Olivier Esser's papers, "An Interpretation of the Zermelo-Fraenkel Set ...
- 6,132
1
vote
0
answers
113
views
How do I justify these nontheorems in the absence of the Existence Property for $PA$
Let $\Pi$ be the provability predicate for $PA$. I want to conclude that $PA\nvdash\exists x(\alpha(x)\wedge\lnot\Pi\ulcorner \alpha(\overset{.}{x}) \urcorner)$ and $PA\nvdash\exists x(\lnot \alpha(x)\...
- 3,574
1
vote
0
answers
176
views
Does Robinson Arithmetic already entail the Recursion Theorem?
Gödel's incompleteness theorem already holds for $Q$ (Robinson's Arithmetic), by design. Is $Q$ already strong enough to support (entail) Kleene's recursion theorem, or are there some limits to ...
- 3,574
1
vote
0
answers
121
views
How do I express a second order restriction upon a third order comprehension schema?
I want a third order $\Pi^2_1$-comprehension schema so that $\alpha$ in
$$\forall x_1,\ldots,x_k, X_1,\ldots,X_l,\Psi_1,\ldots,\Psi_m\exists \Upsilon\forall Y(\Upsilon Y\Leftrightarrow\forall \Phi\...
- 3,574
1
vote
0
answers
181
views
A question about real closed fields that contain the real numbers as a proper subfield
Let F be such a real closed field and let F(C) be the algebraic closure of F. An important example of F is FSR- the field of SURREAL numbers. Suppose that one has constructed an exponential function f ...
- 6,215
1
vote
0
answers
58
views
A class of finitely generated semigroups
Let $G$ be a finitely generated group with a probability measure $\nu$. Suppose we have a finite first moment function $f:G\to \mathbb{R}$, i.e, such that $\Sigma_{g\in G}f(g)\nu(g)< \infty$. Then, ...
- 49
1
vote
0
answers
177
views
Is there a Carnap-Gödel style account of the undecidability of the Halting Problem?
The proof of Gödel's incompleteness theorem can be streamlined by means of the Carnap-Gödel diagonal lemma and the ensuing fixed point theorem $\vdash_S G\leftrightarrow\lnot\Pi\ulcorner G\urcorner$ ...
- 3,574
1
vote
0
answers
639
views
What is the real name of this relation and operation on a particular set of maps between cancellative monoids?
Let $A,B$ be cancellative monoids and define a transducer as a map $f\colon A \rightarrow B$ such that $f(1)=1$ and for all $a_1 ,a_2 \in A$, there exists a $b \in B$ such that $f(a_1 a_2)=f(a_1) b$. ...
1
vote
0
answers
143
views
eliminating contraction
I'd like to better understand the role of the contraction rule in Gentzen's $\mathsf{LK}$. I would like to have an example of a derivable sequent that is no longer derivable if the contraction rule is ...
- 974
1
vote
0
answers
111
views
Is there any standard name for Provably Decidable Set?
A function $f:\mathbb{N}^k\to\mathbb{N}$ is Provably Total in Arithmetical recursively enumerable Theory $T$ if there exists a $\Sigma_1$ formula $\phi({\bf x},y)$ in language of $T$ such that:
$T\...
- 1,689
1
vote
0
answers
210
views
A (second-order) axiomatic characterization of the integers which rules out surreal/hyperreal versions
I've seen it stated, for example here, that the integers are the unique commutative ordered ring with identity whose positive elements are well-ordered.
I understand why the integers are the smallest ...
- 3,058
1
vote
0
answers
157
views
Full epsilon-induction and bounded epsilon-induction
epsilon-induction is the scheme: $\forall x(\forall y\in x\varphi (y)\rightarrow \varphi (x))\rightarrow \forall x\varphi (x)$.
Let "bounded epsilon-induction" be the above scheme, but only for ...
- 117
1
vote
0
answers
143
views
Can Basic Law $V$ be derived from Leibniz's Law in Second-Order Logic without comprehension principles?
Consider Basic Law $V$:
$\hat x$$F$($x$)=$\hat x$$G$($x$)$\equiv$($\forall$$x$)($F$$x$$\equiv$$G$$x$)
At first glance, it seems to have the same form as Leibniz's law
$x$=$y$$\equiv$($\forall$$F$)($...
- 6,132
1
vote
0
answers
194
views
Reference request: Models of isomorphic languages result into isomorphic categories
This is basically a reference request by someone who has not been educated as a logician and would like to be rigorous about certain preliminary aspects of model theory.
Fix an uncountable universe $\...
- 10.5k
1
vote
0
answers
87
views
models of $I\exists^+_1$
$\phi$ is a $\exists^+_1$ formula iff it is in language of arithmetic and does not have $\forall$,$\neg$ and $\rightarrow$, therefore $I\exists^+_1$ is theory of $Q$+induction axioms for $\exists^+_1$ ...
- 1,689
1
vote
0
answers
219
views
What can be said about a Boolean-valued structure from what the Boolean-valued forcing extension thinks about it?
Suppose that $\phi$ is a formula in the language of set theory such that
there are some $n_{1},...,n_{k}$ such that if $V\models\phi(x)$, then $x=(X,R_{1},...,R_{k})$ and $\mathrm{Eq}:X^{2}\...
1
vote
0
answers
106
views
A question on complexity notation
I am considering writing ''$\Pi^{n}_{i_{0},...,i_{n-1}}$-comprehension'' as abbreviation for ''$\Pi^{0}_{i_{0}}$-comprehension plus ... plus $\Pi^{n-1}_{i_{n-1}}$-comprehension'' in the context of an ...
- 3,574
1
vote
0
answers
99
views
Name for condition on map of cancellative monoids
Let $M,N$ be cancellative monoids with identity $\epsilon$ and suppose that $k\colon M\rightarrow N$ is a function such that
$k(\epsilon)=\epsilon$
for all $a,b\in M$, there exists $v\in N$ such that ...
1
vote
0
answers
210
views
Existence of $\lambda$-transitive linear orders for $\lambda \geq \aleph_0$
A linear order $(L, <)$ is $\lambda$-transitive iff any order-preserving bijection between sets of size $\lambda$ can be extended to an order automorphism of $L$.
For $\lambda < \aleph_0$, $2$-...
- 168
1
vote
0
answers
223
views
This modal logic semantics is not S5, but is it something else well-known?
The short form of the question is this:
Is there a model of modal propositional calculus that gives the modal operators the meanings
...
- 524
1
vote
0
answers
134
views
Reference Request: Category of explicit maps between primitive recursive sets?
[Edited]
Let $\mathsf{PR}$ be the category defined as follows:
Choose a specific presentation of Primitive Recursive Arithmetic, that is, with a specific set of terms for primitive recursive ...
- 437
1
vote
0
answers
173
views
Property theories
Property theory is, as I have understood it, first of all characterized by an attempt to approach naive comprehension type-freely and without committing to extensionality.
There is e.g. the work of ...
- 3,574
1
vote
0
answers
103
views
Lower periodic subsets of groups and semigroups
Suppose that $A$ and $B$ are subsets of a group or semigroup. We call $A$ left
upper [resp. lower] $B$-periodic if $BA\subseteq A$
[resp. $A\subseteq BA$]. If $A$ is both left upper and
lower $B$-...
- 995
1
vote
0
answers
101
views
Real algebraic groups and pseudo-finiteness
What is the relationship between pseudo-finite groups and real algebraic groups?
Could you provide an example of a pseudo-finite real algebraic group and of a non pseudo-finite one, if any?
Thank ...
- 11
1
vote
0
answers
143
views
on reductive monoids which are gorenstein
Let $M$ a reductive monoid, i.e. a integral normal affine scheme, which is a monoid whose group of units is a connected reductive group.
By Rittatore http://www.cmat.edu.uy/cmat/docentes/alvaro/...
- 3,472
1
vote
0
answers
164
views
Interesting fragments of first-order logic induced by sorting?
In first approximation, modal logic (I'm using the term loosely)
can be understood as an interesting fragment of first-order logic
(for simplicity I ignore e.g. how modal logic relates to
...
- 341
1
vote
0
answers
66
views
Is it possible to classify all the inequivalent classes of first order sentence with quantifier rank fixed
It is known that for symbols with finite many relations, the number of inequivalent class of first order sentence with quantifier rank $m$ is finite. But is it possible to list (classify) them? At ...
- 11
1
vote
0
answers
257
views
Is there a non-trivial consistency preserving transformation?
In set theory "equiconsistency" (and not "consistency") of the theories is the main part of researches. So we usually try to construct a new model using a given one. In the ...
user36136
1
vote
0
answers
327
views
Logical and alphabetological variant?
The notion of alphabetical variant is well known, so that a formula $x=x$ is an alphabetical variant of $y=y$ if $x$ and $y$ are distinct variables.
One may want to consider the set term $\{x:x \neq ...
- 3,574
1
vote
0
answers
204
views
A question on definable categories
One way to define a category set-theoretically might be to give four $\in$-formulas (not sets!)
$$\begin{array}{rl}
\mathsf{O}(X)&\text{(“$X$ is an object”)}\\
\mathsf{M}(X,Y,z)&\text{(“$z$ ...
- 9,720
1
vote
0
answers
142
views
A generalization of quasi-identities
In universal algebra, a variety is axiomatized by identities $t \approx s$ between terms $t$ and $s$. More general are quasi-varieties that are axiomatized by quasi-identities of the form $$u_1 \...
- 44.4k
1
vote
0
answers
263
views
axiom schema versus inference rule
wikipedia says "An inference rule containing no premises is called an axiom schema or it if contains no metavariables simply an axiom."
but why can't we trivially make a premise ("A is true") part of ...
- 111
1
vote
0
answers
260
views
A question regarding Koepke' s Ordinal Computability in HOD
Consider the following theorem of Koepke-Koerwien-Siders:
"A set x of ordinals is ordinal computable [either by ordinal Turing machines or ordinal register machines--my comment] if and only if it is ...
- 6,132
1
vote
0
answers
139
views
Intersection of integers and rationals defined by logic
Consider the class of sets of the form $X \cap Y$ where $X \subseteq \mathbb{N}^d$ is defined in FO($\mathbb{N}, +$) and $Y \subseteq \mathbb{Q}^d$ is defined in FO($\mathbb{Q}, +, \leq$). Clearly, ...
- 11