All Questions
1,459 questions with no upvoted or accepted answers
2
votes
0
answers
220
views
Which is richer Set or Graph Theory?
This theory about structures, defined as abstractions over isomorphic graphs, can interpret Set Theory in a rather creepy manner. Though the theory is largely technical, yet it is not far from being ...
- 11.3k
2
votes
0
answers
116
views
Reference for a coarse complexity notion
Throughout, I'm only interested in structures with domain $\mathbb{N}$, no primitive relations, and at least $0,\mathsf{Succ}$ as primitive functions. The length of $m\in\mathbb{N}$ is $\lfloor 1+\...
- 20.5k
2
votes
0
answers
118
views
Uniformization and functions on Turing degrees
Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ?
$\mathcal{D}_t$ is the set of Turing ...
- 7,545
2
votes
0
answers
80
views
An alternative definition for finitely generated (and principal) ideals in a semigroup
Let $S$ be a semigroup. An ideal (of $S$) is a subset $I$ of $S$ such that $SI$ and $IS$ are both contained in $I$. The non-empty ideals constitute a subsemigroup, $\mathfrak I(S)$, of the power ...
- 10.5k
2
votes
0
answers
91
views
A recursive description of the smallest divisor-closed subsemigroup containing a set
Let $S$ be a semigroup and $\widehat{S}$ be its unitization, i.e., the monoid obtained from $S$ by adjoining an identity element if necessary (so that $\widehat{S} = S$ when $S$ is already a monoid).
...
- 10.5k
2
votes
0
answers
119
views
Adding partitions of one but not the other kind
Say that two partitions $(P_i)_{i\in I}, (Q_j)_{j\in J}$ are isomorphic iff there is a bijection $f: I\rightarrow J$ such that $\vert P_i\vert=\vert Q_{f(i)}\vert$ for all $i\in I$. (Note that in the ...
- 20.5k
2
votes
0
answers
145
views
Is it consistent to have these kinds of acyclic hereditarily size sets?
Working in $\sf ZFC-Reg. {}+ Acyclicity$. Where :
Acyclicity: $\neg \exists x_1, \cdots, \exists x_n: x_1 \in x_2 \in\cdots\in x_n \in x_1$
We add the following kind of weird non-well founded sets.
$\...
- 11.3k
2
votes
0
answers
144
views
The strongest reflection principle that does not violate covering lemmas
#-generated reflection, or Indiscernible-generation, is considered to be the strongest reflection principle that does not violate the covering lemma in L. [1]
Is there a way to extend this success to ...
- 695
2
votes
0
answers
97
views
Which of these non-well founded set theories is synonymous with ZFC?
Lets add a constant $\mathcal A$ to the language of $\sf ZFC$.
Let "Foundation$_{\mathcal A}$" denote the following sentence:
$$ \forall x: \forall y \in x \exists z \in y \cap x \to \exists ...
- 11.3k
2
votes
0
answers
112
views
Existence of trees with height $\kappa$, every level has at most size $\lambda$ and has at least $\lambda^{+}$ maximal branches
Definitions A tree means a set-theoretic tree, that is a poset $(T,<)$ so that for each $x\in T$, the set $\{y\in T\mid y<x\}$ is well-ordered.
A $\kappa$-Kurepa tree is a tree of height $\kappa$...
2
votes
0
answers
81
views
Is monotonicity redundant in this definition of Tarskian logics?
Given a logic over a language $L$, which has a consequence relation $\vdash$. This logic is Tarskian if for every $\Gamma \cup \Delta \cup {\alpha} \subseteq L$:
If $\alpha \in \Gamma$, then $\Gamma \...
- 21
2
votes
0
answers
87
views
Do Fagin's zero-one laws hold on stochastic block model?
Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...
- 131
2
votes
0
answers
342
views
What's the definition of a mouse in Mitchell's handbook article "the covering lemma"?
In the book "handbook of set theory", in the chapter "the covering lemma", definition 3.24, Mitchell defines what is mouse.
However he did not give any definition of $\mathcal{U}_\...
- 1,490
2
votes
0
answers
19
views
Reference request for dinatural transformations arising from free Cartesian closed categories
Let $g_n$ be a discrete graph with $n$ nodes and $\operatorname{F}$ the free functor of the adjunction between the category of graphs and the category of Cartesian closed categories and functors, as ...
2
votes
0
answers
74
views
Relation of top and bottom types given multiple universes
This is something that I haven't seen mentioned in any literature.
In a type theory (extensional, intuitionistic, Martin Lof variant), given two ordered Tarski Universes such that $U_i < U_{i+1}$, ...
- 21
2
votes
0
answers
121
views
Can this theory of classes of ordinals interpret ZFC?
The following theory is a theory of classes of ordinals.
Language: Bi-sorted FOL with identity. First sort in lower case ranging over ordinals. Second sort in upper case ranging over classes of ...
- 11.3k
2
votes
0
answers
178
views
Reference request for a modification of Bi-Intuitionistic Logic
I’ve asked this same question on math.stackexchange.com, but haven’t received any answers. I ask this question in good faith, so I hope it meets this site’s standards.
I have been spending the better ...
- 184
2
votes
0
answers
54
views
Finite (schema) axiomatizability of representable cylindric algebras
If we know that the class of all representable cylindric algebras of dimension $\alpha$ (for any ordinal number $\alpha>2$) is NOT finitely (schema) axiomatizable*, then does it (perhaps trivially) ...
- 63
2
votes
0
answers
75
views
Can all the strongly provable theorems of $\sf PA+\neg Con(PA)$ be captured in an effective manner through alternative kind of provability?
If we extend $\sf PA$ with the following axiom asserting its own inconsistency:
Inconsistency: $\exists x: \operatorname {Proof}_{\sf PA} (x, \ulcorner 0=1 \urcorner)$
For short denote this axiom by $\...
- 11.3k
2
votes
0
answers
176
views
On the origin of power semigroups
Let $S$ be a (multiplicatively written) semigroup. Equipped with the (binary) operation of setwise multiplication $(X, Y) \mapsto \{xy \colon x \in X, \, y \in Y\}$, the family of all non-empty ...
- 10.5k
2
votes
0
answers
192
views
Can PA be acyclically complete?
Any formula $\phi$ in the first order language of arithmetic is to be called acyclic if and only if we can associate with it an acyclic undirected graph whose nodes are the variable symbols occurring ...
- 11.3k
2
votes
0
answers
70
views
A formula which is true in all possibilities for variables in IPL
Let $\mathcal{F}(n, 2^m)$ be an intuitionistic Kripke in Fig. 1, which is formed by the set
$$
\left\{(i, j)\in \omega \times \omega \mid (0 \leq i \leq n-3, 0 \leq j \leq 1) \vee (i= n-2, 0 \leq j \...
- 53
2
votes
1
answer
430
views
Logic which depends on the perspective? (Semantic space of logic / perspectivism)
I am not sure if this question is appropriate for MO, since I have only a basic understanding of Boolean logic, and am maybe not qualified to ask questions beyond that, but still I will try to write ...
- 3,072
2
votes
0
answers
167
views
Which first-order theories have full indiscernible extraction?
Stable theories have the following useful property, which I will state in a sub-optimal way for simplicity's sake:
Fact 1. If $T$ is $\lambda$-stable for some $\lambda \geq |T|^+$, then for any set ...
- 12.5k
2
votes
0
answers
267
views
Is determinacy of (some) very long open games consistent?
For $\varphi$ a first-order sentence in the language of set theory and $\kappa$ an ordinal, let $G_\varphi^{\kappa}$ be the game of length $\kappa$ in which players $1$ and $2$ alternately play ...
- 20.5k
2
votes
0
answers
116
views
Who proved first that the Lindenbaum-Tarski algebra of a theory consisting of the propositional tautologies is a free Boolean algebra?
The title says it all: Who first proved/observed that the Lindenbaum-Tarski algebra of a theory consisting of the propositional tautologies is a free Boolean algebra? (I don't think it was Lindenbaum ...
- 207
2
votes
0
answers
94
views
Counterexamples to the definable (P,Q)-Theorem
Pierre Simon conjectured a model-theoretic definable version of Matoušek’s (p,q) -theorem in NIP theories:
[Conjecture 5.1]: Let T be NIP and M⊨T . Let ϕ(x;d) ∈ L(U) a formula, non-forking over M . ...
- 51
2
votes
0
answers
211
views
Some questions about the Hyperuniverse Program
The Hyperuniverse Program, founded by Sy D. Friedman, intends to produce new second-order axioms of set theory which appropriately formalize "the universe is maximal" in one of a few ways. A ...
- 2,031
2
votes
0
answers
74
views
Question related to number of distinct forcing extensions of a countable model
A bit of context: the below question is motivated by roughly the following scenario: we have some countable model $\mathcal{M}$, and want to “count” the number of functions/sets $f$ such that $\...
- 111
2
votes
0
answers
96
views
Can one extend higher randomness theory to the entire analytical hierarchy under certain large cardinal assumptions?
In the "Recursion Theory" book by C.T Chong, Liang Yu, towards the end of the book they list a few "open" research areas connected to higher computability theory. One such ...
- 893
2
votes
0
answers
61
views
Is $\sf NF(U)$ interpretable in $\sf NF(U)-0$?
It is known that in $\sf ZFC$ related theories one can remove the the empty set axiom and foundation, stipulate that all sets are nonempty, axiomatize replacement and separation in such a manner that ...
- 11.3k
2
votes
0
answers
77
views
Is "strongly unbounded logics are unbounded" equivalent to "no descending sequence of cardinals"?
This question is motivated by Vaananen's paper Generalized quantifiers in models of set theory. Say that a (set-sized, regular) logic $\mathcal{L}$ is
unbounded if there are $\mathcal{L}$-sentences $\...
- 20.5k
2
votes
0
answers
120
views
How to express Kunen's inconsistency, Reinhardt and Wholeness axioms, by single sentences?
Working in $\sf NBG, $ can we express the property of a class being set theoretically definable, by a single sentence? Like for example, the following way:
$$\operatorname {std}(X) \iff \exists x_1 \...
- 11.3k
2
votes
0
answers
68
views
Semigroups related to iterated orthogonal complement
Let $R\subset V\times V$ be a relation on a set $V$. For a subset $S\subset V$, define its orthogonal complement with respect to $R$
as
$$S^l:=\{ x: \forall y\in S\ \ (x,y)\in R\},\ \ S^r:=\{y: \...
- 513
2
votes
0
answers
64
views
A particular generalization of free partially commutative monoids
A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
- 21
2
votes
0
answers
106
views
Enumerating unions of arithmetical sets
In Simpsons's excellent Subsystems of Second-order Arithmetic, we find V.4.10 which tells us the following:
The following is provable in ATR$_0$. Let $(A_n)_{n\in \mathbb{N}}$ be a sequence of ...
- 4,359
2
votes
0
answers
195
views
"Very $L$-like" models, part 2: combinatorics
Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ and having the finite use property and the strong downward Lowenheim-Skolem property together with, for each finite ...
- 20.5k
2
votes
0
answers
198
views
Sets and their characteristic functions
There are some nice connections between properties of sets and properties of their characteristic functions.
For instance:
a set $C\subset \mathbb{R}$ is closed (resp. open) IFF the characteristic ...
- 4,359
2
votes
0
answers
73
views
What should I call a log scheme with free reduced monoids?
This is a terminology question about a class of log varieties.
Given an fs (fine and saturated) log variety $(X, M)$ (for $M$ the defining sheaf of monoids), any geometric point $x\in X$ has a ...
- 7,962
2
votes
0
answers
134
views
Does the consistency of $\sf NF$ enable us to transfer its cardinal comparisons to the inside of $\sf Z$?
I think that stratified comprehension has the potential to breach Cantor's arguments about the relative size of sets and their powers, this has been done to an extent in $\sf NFU$ and the known ...
- 11.3k
2
votes
0
answers
235
views
Is computability theory less cumulative than other areas in mathematics?
I love compatibility theory, degree theory etc and I'm astonished by the advances that have been made in the field but it often seems like computability is less cumulative than other areas of ...
- 3,029
2
votes
0
answers
105
views
Does every ordered-union coideal contain an ordered-union ultrafilter?
$\newcommand{\FU}{\operatorname{FU}}$
$\newcommand{\H}{\mathcal{H}}$
Recall that an ordered-union ultrafilter is an ultrafilter on $\omega$ with a base of sets of the form $\FU(A)$. Here, $A = \{a_0,...
- 1,442
2
votes
0
answers
115
views
Will the least class satisfying Scott set theory interpret AC and CH?
I use ST for the set theory used by Dana Scott in More on the Axiom of Extensionality,
in Y. Bar Hillel et alia, Essays on the Foundations of Mathematics}, Hebrew University, Jerusalem: $115-131$. ...
- 3,574
2
votes
0
answers
161
views
Embedding a monoid into a group via its monoid ring
Suppose I have a monoid $(M,\, \cdot,\, e)$ equipped with a monoid homomorphism $\textrm{length} : M \rightarrow \mathbb{N}_+$ into the monoid of natural numbers under addition where $e$ is the only ...
user491484
2
votes
0
answers
61
views
Can we use forcing to adjoin this set to a model of ZF+j+$\alpha$?
Let $M$ be a countable transitive model of $\sf ZF + j +\alpha$, where $j:V_{\alpha+1} \to V_\alpha$ is an external [not used in separation and replacement] bijection such that for any $S \in V_{\...
- 11.3k
2
votes
0
answers
40
views
Uniformity of splitting for n-REA degrees
In "A SPLITTING THEOREM FOR n−REA DEGREES" Shore and Slaman extend the following result of Sacks
If $C$ is r.e., $D \leq_T C$ and $D, C \not\leq_T 0$ then there are sets $C_0, C_1$ such ...
- 3,029
2
votes
0
answers
140
views
Weakening of open determinacy for uncountably long games
For a cardinal $\kappa$ I'll use the phrase "$(\kappa,\kappa)$-game" to mean "two-player, perfect-information, deterministic game on $\kappa$ of length $\kappa$."
Say that a ...
- 20.5k
2
votes
0
answers
181
views
So many types of subwords! How are they called?
Let $\mathscr F(X)$ be the free monoid on an alphabet $X$, the carrier set of $\mathscr F(X)$ being the union of $X^{\times k}$ (the Cartesian product of $k$ copies of $X$) as $k$ ranges over $\mathbb ...
- 10.5k
2
votes
0
answers
248
views
Universes from sets of logical relations
Consider any set $I$ and any logical structure $L$. Let $R$ denote some set of $I$-relations over $L$, i.e. each element $r\in R$ sends each $I$-tuple $(x_i)_{i\in I}$ of elements $x_i\in L$ to a ...
- 329
2
votes
0
answers
107
views
Empires and the net criterion
Currently, I am struggling to understand the proof of Proposition 2.5 on page 250 (page 22 in the document) of the paper Natural deduction and coherence for weakly distributive categories by Blute, ...
- 764