All Questions
1,135 questions
2
votes
1
answer
200
views
Some very weak statements on choice
This is a follow-up question to Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?
Consider the statements
$(\text{S}1)$ For any infinite set $X$ there is ...
- 48.9k
2
votes
2
answers
382
views
Embedding of consistent subset in first order logic (finitely many variables)
I am looking at FOL with no equality, no constant, no function symbol and the unique binary predicate $\in$ with variables in arbitrary sets $V$ or $W$. Specifically we define ${\bf P}(V)$ as the free ...
- 178
2
votes
1
answer
652
views
On the Actual Potential of Virtual Large Cardinals
Virtual large cardinals belong to a relatively new breed of strong axioms of infinity. They often appear as statements of the following form:
Definition. Suppose $A$ is a large cardinal property ...
2
votes
0
answers
309
views
Set theory for category theory
Let $SC$ (sets and classes) denote the modification of Ackermann set theory laid out in F. A. Muller's Sets, Classes and Categories (denoted there by ARC -- a brief summary of the theory is given ...
- 10.1k
2
votes
1
answer
2k
views
Suggestions on the best introductory Model Theory texts [closed]
Any recommendations on the best texts for introducing Model Theory?
2
votes
3
answers
994
views
Predicative definition
Hi, I met several times the expressions "predicative definition" and "unpredicative definiton" in texts about logic. What these expressions do mean ? I precise I'm a french student, thanks for your ...
user2664
2
votes
2
answers
1k
views
Downgrading from ZFC with universes to ZFC
Is the following correct?
If something is provable for small sets in ZFC with Axiom of Universes ("For any set x, there exists a universe U such that x∈U.") then it is provable for any sets in ZFC (...
- 765
2
votes
0
answers
122
views
First-countable topological monoids without local absorbing elements whose topology is induced by a semimetric
This is a follow up of Question 163246. For the reader's convenience, let me first copy&paste some basic definitions.
We let a semimetric on a set $X$ be a function $d: X \times X \to [0,\infty]$ ...
- 10.5k
2
votes
1
answer
173
views
Chromatic number and taking duals of hypergraphs
If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, then a map $c:V\to \kappa$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e:...
- 48.9k
2
votes
0
answers
106
views
Descent of flatness from algebras to monoids II
This is a follow-up question to this one. There, Benjamin Steinberg showed that a morphism of commutative monoids $u$ need not be flat if the induced morphism of $R$-algebras $R[u]$ is flat for some ...
- 6,700
2
votes
0
answers
71
views
Empty preimage under homomorphism of finitely presented groups with decidable word problems
Let $G, H$ be finitely presented groups with decidable word problems.
Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?...
user178109
2
votes
1
answer
302
views
Name for this algebraic structure?
I've found myself looking at a structure $\mathbb{M}$ whose important properties are:
$\mathbb{M}$ is a discretely ordered additive monoid.
$\mathbb{M}$ has a least element, and this least element is ...
- 10.1k
2
votes
1
answer
142
views
Does $WKL_0$ plus CON(PA+X) give a binary tree model of PA+X?
In the context of reverse mathematics $WKL_0$ is considered equivalent to Gödel's completeness theorem over $RCA_0$. Does this mean that e.g. $WKL_0$ plus the consistency statement CON(PA+X) gives a ...
- 3,574
2
votes
3
answers
393
views
Infinite play with tape, or covering the integers with prime arithmetic progressions
It is possible that a more technical version of this question has been
asked and answered in the literature. If so, then a reference is much
appreciated. I will phrase it in terms of colored tapes ...
- 13k
2
votes
1
answer
267
views
Maximality statements that cannot be proved using $\mathsf{ZL}$ [closed]
What are examples for maximality statements that cannot be proved using Zorn's Lemma?
user62017
2
votes
0
answers
80
views
Are the roots of an infinitely divisible probability infinitely divisible themselves?
Let $\mu$ be an infinitely divisible probability on a topological group $G$. If $\nu ^{* n} = \mu$ for some $n$, is $\nu$ an infinitely divisible probability too?
A sufficient criterion would be to ...
- 5,407
2
votes
3
answers
680
views
Another adjoint pair: Definable sets and set-builder formulas
I see adjointness between the two concepts of "being a definable set" and "being a set-builder formula":
A set $X$ is definable when there is a formula $\phi(x)$ such that $X = \lbrace x : \phi(x)\...
- 9,720
2
votes
1
answer
587
views
Is there a strict limit on choice principles in $\sf ZFC$?
Is there a principle $\sf P$ that $\sf ZFC$ [or some suitable extension of it] proves to be a strict limit on choice principles?
By a choice principle I mean a sentence (or scheme) that is equivalent ...
- 11.3k
2
votes
1
answer
425
views
Is full Replacement provable in Z + Ordinal Replacement?
$\text{Ordinal Replacement:}$ if $\phi(x,y)$ is a formula in two free variables $x,y$, then:
$\forall x \ [ordinal(x) \to \exists! y \ (ordinal (y) \wedge \phi(x,y)) ]
\to
\forall A \ (\forall x \...
- 11.3k
2
votes
1
answer
271
views
Is Extensionality needed for the incompleteness of very weak set theories?
$ST$ is the weak set theory built upon identity theory and containing
the axiom for empty set,
the axiom for adjunction and
the axiom for extensionality.
It is known that $ST$ interprets ...
- 3,574
2
votes
1
answer
118
views
Can a Boolean Set Algebra be Restricted in the Analytical hierarchy?
I want a comprehension principle to capture $\Pi^1_1$-sets from a domain as well as sets that are relative complements of or finite unions of sets already defined by comprehension. I want to use as ...
- 3,574
2
votes
1
answer
223
views
Possible symmetry groups of power terms
Previously asked and bountied at MSE:
Let $\mathfrak{E}=(\mathbb{N};\mathit{exp})$ be the algebra in the sense of universal algebra consisting of the natural numbers with just exponentiation. To each ...
- 20.5k
2
votes
2
answers
292
views
Substructure Argument for Chain Conditions
Once, someone showed me a nice argument using elementary substructures for proving chain conditions about forcings. It was a basic example, maybe that Cohen forcing is ccc. I've been trying to look up ...
- 23
2
votes
2
answers
241
views
If $(\mathbb M, \tau)$ is a topological monoid, is $\tau$ always induced by a [left] subinvariant semimetric?
Let me start by recalling some basic definitions (just for the sake of avoiding misunderstandings due to the vocabulary of the post).
Basically following some ideas of W. Lawvere (but not his ...
- 10.5k
2
votes
3
answers
1k
views
on the set of numbers generated by integer linear combination of two real numbers.
Let $b > a > 0$ be two real numbers. I am interested in the set of numbers
$X(p,q) = p a + q b$ with $p,q$ positive integers. Basically this is the set $a \mathbb{N} + b \mathbb{N}$.
What ...
- 29
2
votes
1
answer
173
views
Is the union of a chain of $\kappa$-colorable subgraphs $\kappa$-colorable?
Motivation. I was trying to prove that whenever $G$ is a simple, undirected graph and $\kappa< \chi(G)$ is a cardinal, then there is an induced subgraph with chromatic number exactly $\kappa$. This ...
- 48.9k
2
votes
0
answers
237
views
Representing iteration of a function in PA
Let $\mathscr{L}$ be a (recursive) FOL language, with numeral symbols $\underline{0},\underline{1},\ldots$. Let $T$ be a recursive, consistent theory, containing PA (or even just Robinson arithmetic)....
- 18.7k
2
votes
1
answer
144
views
Is there a lower bound on the size of a supertransitive model of ZFC?
In a posting to mathstackexchange I've alluded to the concept of supertransitive model. Now $M$ is a supertransitive model of a set $Q$ of first order sentences, denoted by $M \models^{sptr} Q$, is ...
- 11.3k
2
votes
1
answer
307
views
Sigma-complete Lindenbaum algebras? [closed]
Is there any calculus whose algebraization is a sigma-complete Lindenbaum algebra, i.e., a sigma-complete Boolean algebra after identification of equivalent formulas?
- 21
1
vote
1
answer
612
views
Can this kind of Mereology be synonymous with Set Theory?
This question is about synonymy of Morse-Kelley set theory "$\sf MK$" with the following Mereological theory:
Language: first order logic with equality. Extra-logical primitives: $\subseteq$ ...
- 11.3k
1
vote
0
answers
59
views
Construction of the smallest nucleus above a prenucleus: what does this proof tell us?
While reading Hyland's paper on the effective topos [retyped version here] in the L. E. J. Brouwer Centenary Symposium, specifically prop. 16.3, I realized that the following proposition is implicit:
...
- 32.5k
1
vote
1
answer
365
views
Naturally definable sets of natural numbers (3)
[This shall be the last of a series of questions, see Naturally definable sets of natural numbers (2)]
I cannot explain why I have been so stubborn not to see the most straight-forward definition for ...
- 9,720
1
vote
1
answer
174
views
Can we state $\sf V=HOD$ using a single ordinal parameter(other than the formula code)?
$\sf V=HOD$ is stated as:
$\forall X \, \exists \theta \, \exists \alpha < \theta \, \exists \varphi : X=\{y \in V_\theta\mid V_\theta\models\varphi(y,\alpha)\}$
This use two ordinal parameters (...
- 11.3k
1
vote
2
answers
230
views
Does strong provability imply syntactical provability?
This posting is related to the answer to this question.
Lets extend the language of $\sf PA$ with a monadic symbol "$\vdash$", add to the formula formation rules, the rule:
if $(\phi)$ is a ...
- 11.3k
1
vote
1
answer
276
views
About having one axiom schema for ZFC motivated after the iterative conception of sets?
This posting is related to this posting, and builds its motivation from this answer to it.
Define: $\operatorname {History}(x) \iff \\\forall y \in x: y=\{c \mid \exists z : z \in y \cap x \land (c \...
- 11.3k
1
vote
1
answer
347
views
Is the following theory countably axiomatizable?
Let $L$ be the language of set theory, and for each countable ordinal $\kappa$, define $L_\kappa$ as follows: $L_0 = L$, and $L_{\alpha+1}$ is obtained by adding countably many new class constants $c_\...
1
vote
1
answer
383
views
Is there a consistent theory for each instance of the halting problem?
I got a bit confused by a discussion about the provability of the Goldbach conjecture and the seemingly different opinions about this subject. Since I understand computer science better, I will ask my ...
- 67
1
vote
2
answers
109
views
Is every formula of LΩ equivalent to a formula of L1 modulo T1?
Q: Is every formula of $L_\Omega$ equivalent to a formula of $L_1$ modulo $T_1$?
The notation comes from the following question: Is the following theory countably axiomatizable?
Edit: I mean $T_\...
1
vote
1
answer
213
views
Self-embeddings of uncountable total orders
A nice theorem of Dushnik and Miller (from 1940) states that if $(\Omega,\leq)$ is a countable total order, then either
there is an element $\omega \in \Omega$ such that $(\Omega \setminus \{\omega\}...
- 4,547
1
vote
1
answer
231
views
Continuous semigroup homomorphism of composition to additive structure
Let $G$ be the topological semigroup whose underlying space is $C(\mathbb{R}^d,\mathbb{R}^d)$ equipped with composition as semigroup operation and let $H$ be the topological group whose underlying ...
- 5,405
1
vote
2
answers
293
views
Compactness for countable models?
How and where is it proved that WKL$_0$ proves the compactness theorem for countable models? (This is a follow-up to a comment of F. Dorais.)
- 16.6k
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
1
answer
68
views
Computable in $\omega$-REA degree but not double jump of finitely many columns
Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well-known result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can ...
- 3,029
1
vote
1
answer
529
views
A question on the provability predicate of Q
I am not familiar with Robinson's construction as I do not have access to his text or to precise accounts of this, but I have come to understand that the proof predicate of Robinson arithmetic is non-...
- 3,574
1
vote
1
answer
123
views
On asymptotic classes of finite structures
I have a question about the following paper:
One-dimensional asymptotic classes of finite structures
by Macpherson and Steinhorn (link at Trans. AMS website).
Let $\mathbf{K}$ be a one-dimensional ...
- 37
1
vote
1
answer
90
views
Injecting premises into two implicational premises connected by a tensor (multiplicative conjunction) in linear logic
I have another question regarding linear logic: I want to get to the proof E, using the premises in (1-4). Is this at all possible?
1: $A$
2: $C$
3: $(A\multimap B)\otimes(C\multimap D)$
4: $B\...
- 21
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
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
1
answer
96
views
If $H$ is commutative and unit-cancellative, then so is the monoid of non-empty ideals of $H$
Let $H$ be a (multiplicatively written) commutative monoid with identity $1_H$. Given $X, Y \subseteq H$, we take
$$XY := \{xy: x \in X,\, y \in Y\}.$$
We call a set $I \subseteq H$ an ideal of $H$ ...
- 10.5k
1
vote
2
answers
311
views
Does Regularity schema imply $\in$-induction when added to first order Zermelo set theory?
That $\in$-induction fails to be a theorem schema of first order Zermelo + Foundation (see here), then it appears that it is more eligible to replace axiom of Regularity (Foundation) by a Regularity ...
- 11.3k