All Questions
1,459 questions with no upvoted or accepted answers
1
vote
0
answers
106
views
The proposition associated with a set
Given a set $U$ and a set $A \subseteq U$, is there an accepted symbol for the proposition $p$ over the universe $U$ such that for each $x \in U$, $p(x)$ is the assertion that $x \in A$? (The symbol $...
- 19.7k
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
1
vote
0
answers
75
views
How many constant symbols can a set of intuitionistic formulas have for completeness to hold?
Fitting proves a version of the completeness theorem for intuitionistic FOL in his book on intuitionistic model theory and forcing.
Let $U$ be any set of formulas without parameters (i.e. constant ...
- 139
1
vote
0
answers
71
views
Can we have partitions on powersets of infinite cardinals that preserve natural arithmetical operators?
There exists an infinite cardinal $\zeta$ such that there exists a set $P$ such that $P$ is a partition on $\mathcal P(\zeta) \setminus \{\varnothing\}$ such that each element $h$ of $P$ is an ...
- 11.3k
1
vote
0
answers
244
views
Christoph Benzmüller and Gödel's ontological proof?
Are there any notable mathematical or logical issues within Christoph Benzmüller and Bruno Woltzenlogel-Paleo formalized Gödel's ontological proof (pdf) that has been identified by the community?
1
vote
0
answers
165
views
Can this formalism prove the consistency of ZFC?
Working in bi-sorted first order logic with equality and membership. First sort variables written in lower case range over sets. Second sort variables written in upper case range over classes. Lets ...
- 11.3k
1
vote
0
answers
119
views
What is the minimal length of an undecidable sentence in those ZFC related theories?
If we measure the length of a sentence by the number of occurrences of atomic subformulas in it. So, for example in set theory written in $\sf FOL(\in)$, the length of a sentence is the number of ...
- 11.3k
1
vote
0
answers
67
views
How $n$-set -like functions are constructed?
if for every $f$ we define a relation $R_f$ as follows: $$ x \ R_f \ y \iff \exists z \in x : y=f(z)$$
So, the binary relation $R_f$ sends a set to each image under $f$ of an element of it.
Define $R \...
- 11.3k
1
vote
0
answers
62
views
Can this theory interpret TG? Would its Reinhardt's extension be equivalent to the usual one?
Language: FOL
Primitives: $=, \in$
Axioms:
Extensionality: as in Z
Define: $\operatorname {set}(y) \iff \exists x: y \in x$
Comprehension: $$n=0,1,2, \ldots \\ \forall \operatorname {set} x_1, \cdots, ...
- 11.3k
1
vote
0
answers
53
views
Can MLU prove symmetric comprehension?
Working in $\sf ML$$\sf U$:
Define: $x \in^f y \iff f(x) \in y$
by $\varphi^f$ we mean the formula obtained by merely replacing each "$\in$" symbol in formula $\varphi$ by the symbol "...
- 11.3k
1
vote
0
answers
139
views
Monads for proof relevance in type theory
I am just getting started with homotopy type theory. After watching an introductory lecture, I was attracted to the concept of proof relevance. In my understanding, the core idea here is to elevate ...
- 1,313
1
vote
0
answers
132
views
Are gaps and loopy games interchangeable in the Surreal Numbers?
The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...
1
vote
0
answers
150
views
What is the strength of adding this de-schematizing inference rule to Ackermann's set theory?
Language: first order logic with equality, membership, and a constant symbol $W$.
Axioms:
Extensionality: $\forall z \, (z \in x \leftrightarrow z \in y) \to x=y$
Comprehension: $\exists x \forall y \,...
- 11.3k
1
vote
0
answers
121
views
Is this modified H. Friedman theory bi-interpretable with ZFC + ORD is Mahlo?
The following theory is a modification of Harvey Friedman $\sf K(W)$ theory.
Language: first order logic with equality, membership, and a constant symbol $W$.
Axioms:
Extensionality: $\forall z \, (z ...
- 11.3k
1
vote
0
answers
174
views
How does the cardinality of a set and its powerset compare in the hereditarily rank-concordant constructible world?
Working in the constructible universe "$L$", if we define two kinds of ranks for any constructible set $x$, one being the ordinal index of the first $L_\alpha$ where $x$ appears as a subset ...
- 11.3k
1
vote
0
answers
63
views
Can the proper/whole domain relationship in bi-interpretations be reversed for non-synonymous theories?
Suppose we have theories $T$ and $H$ that are bi-interpretable, now suppose that the relevant interpretations achieving that bi-interpretability are: $\tau: T \to H$, and $\pi: H \to T$. Now suppose ...
- 11.3k
1
vote
0
answers
73
views
EF-games with scrambling
This question is motivated both by the notion of zero-knowledge proofs and by general curiosity about versions of the infinitely-long Ehrenfeucht-Fraisse game which don't trivialize (= Duplicator win ...
- 20.5k
1
vote
0
answers
182
views
Can this Mereological system be synonymous with $\sf ZF(C)$?
This question is about synonymy of $\sf ZFC$ set theory with the following Mereological theory:
Language: first order logic with equality. Extra-logical primitives: $\subseteq$ standing for the binary ...
- 11.3k
1
vote
0
answers
81
views
Is every set equinumerous to a well founded set in acyclic ZF?
If we replace the axiom of Regularity in $\sf ZF$ by the scheme of Acyclicity, which is:
$$\begin{align} n=2,3,\dots;\ & \neg \exists x_1,\dots , \exists x_n: \\ &x_1 \in x_2 \land \dots \...
- 11.3k
1
vote
0
answers
274
views
Can the following definition of choice principle salvage the prior attempts?
In prior postings 1 , 2, I've presented a definition of choice principle as what is equivalent to a selection principle. However, it was proved that it is inadequate in the sense that it admits ...
- 11.3k
1
vote
0
answers
64
views
Is $\sf MK$ bi-interpretable with this modification of it posing an Ur-proper class for every set?
Let's take $\sf MK$ set theory.
Adopt the notation of upper case ranging over all objects, lower case only range over sets (i.e.; elements of classes), and $\frak A,B,C,..$ to range only over proper ...
- 11.3k
1
vote
0
answers
163
views
Can the Constructible Universe be built in absence of Unions and Power?
Can $L$ be built in
$\sf ZF$ $\sf-Regularity-Union-Power+ Boolean \ Union$?
We know that $L$ can be built in $\sf KP$, but here we don't have Set Union.
If the answer is to the negative, then would ...
- 11.3k
1
vote
0
answers
162
views
Solution of an equation over free group
Let $F_n$ be a free group on $n$ generators. Let $w \in F_n$ be a word such that there does not exist any solution in $F_n$ for the equation $w.w(t_1, \ldots, t_n) = 1$, where $t_1, \ldots, t_n$ are ...
- 355
1
vote
0
answers
110
views
Need help unpacking the interdependence of axiomatic set theory and first-order logic
I'm currently self-studying both Von Neumann Set Theory (not ZFC but rather axiomatic set theory with the undefined notion of class) and First-Order Logic.
I've been self-studying the following ...
- 119
1
vote
0
answers
68
views
On known links between convexity and fuzzy logic
The following are thoughts I had during a joint work with P. Olver on maps from spheres to the convex hull of finitely many points in some finite-dimensional vector space. I do not wish to discuss the ...
- 5,215
1
vote
0
answers
176
views
Theorem constructing a mathematical structure from a set of internal isomorphisms
I am searching for information about a specific theorem mentioned in the book "Discriminator-algebras: algebraic representation and model theoretic properties" by Heinrich Werner. The ...
- 119
1
vote
0
answers
142
views
Must models of the following theory satisfying opposing infinitary sentences, satisfy opposing finitary sentences?
This is a follow-up to posting titled "Is this theory finitary first order complete?"
Recall the theory presented at that posting. Replace the size axiom by the following:
$\textbf{...
- 11.3k
1
vote
0
answers
161
views
Can ordinal definability be defined using no more than one ordinal parameter?
This answer shows that one can indeed define ordinal definable this way:
$\begin{align} \textbf{Define: } & \operatorname {OD} (X) \iff \\& \exists \theta \, \exists \varphi: X= \{y \in V_\...
- 11.3k
1
vote
0
answers
140
views
Infinite Steiner systems
Let $\kappa<\lambda$ be cardinals where $\lambda \geq \aleph_0$ and $\kappa>1$. Is there necessarily a set ${\cal S}\subseteq {\cal P}(\lambda)$ with the following properties?
${|\cal S}| > ...
- 48.9k
1
vote
0
answers
135
views
Can every set be ordinal definable?
From Wikipedia:
OD is not necessarily transitive, and need not be a model of ZFC.
This obviously means that, assuming ZFC is consistent, there is a model $M \models \mathrm{ZFC}$ so that $\mathrm{OD}...
- 704
1
vote
0
answers
100
views
What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?
The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive ...
- 4,597
1
vote
0
answers
99
views
a formal framework for reasoning about infinite sets of formulas
Consider a formula
$\forall n. \varphi $
where $\varphi$ is a 1st-order formula, over a set of $n$ variables. That is, the set of variables is determined by $n$ itself,e.g.,
$\forall n. \forall i. i \...
1
vote
0
answers
38
views
Single parameter programs and halting supremums
Let's first define a function $H:\mathrm{Ord} \rightarrow \mathrm{Ord}$. Suppose we are given some ordinal $\alpha$ and we want to find $H(\alpha)$. We define $H(\alpha)$ as the supremum of halting ...
- 881
1
vote
0
answers
48
views
Is $0^{\omega}$ a minimal cover of a minimal arithmetic degree?
Is there a minimal arithmetic degree $d <_a 0^{\omega}$ such that $0^{\omega}$ is a minimal cover of $d$ in the arithmetic degrees? [1]
While whether or not $0^{\omega}$ is a minimal cover at all (...
- 3,029
1
vote
0
answers
37
views
Are the $\omega$-generic arithmetic degrees downward closed
A degree is $\alpha$-generic if it has representative that is $\alpha$-generic. Are the $\omega$-generic arithmetic degrees (i.e. the degree structure induced by arithmetic reproducibility) downward ...
- 3,029
1
vote
0
answers
154
views
Let us assume that NP is not equal to P. Are there decision problems such that it is known that they can only be answered by brute force?
For example, in principle, it seems possible that that there is a class H
of graphs (perhaps satisfying some specific conditions) such that, for any
G in H, the existence of a Hamiltonian cycle in G ...
- 199
1
vote
0
answers
122
views
Is there an error in W. Buchholz's paper "A simplified version of local predicativity"?
I want to self-learn proof theory. It seems that the operator controlled derivation method is important in this field, and the paper in the title is the first paper that uses this method.
So I'm ...
- 1,490
1
vote
0
answers
266
views
Is Jensen's covering lemma meaningful in a platonist's view?
The typical applications of fine structure theory are finding out the lower bounds of consistency strength of axiom systems. In such a proccess, we also constructs many combinatorial objects in core ...
- 1,490
1
vote
0
answers
44
views
Base of cone of arithmetic minimal covers
By Borel determinacy (exercisce XIII.1.7 in Odifreddi) there is a cone of minimal covers in the arithmetic degrees. Is the base of such a cone known? A minimal such base?
For that matter, is it even ...
- 3,029
1
vote
0
answers
43
views
No arithmetic degree that always joins to arithmetic minimal cover
Is there (I strongly presume not but not seeing how to show it) a (non-zero) arithmetic degree $a$ such that for all arithmetic degrees $e \not\geq_a a$ we have $e \oplus a$ is a minimal cover of $e$ ...
- 3,029
1
vote
0
answers
48
views
Neighborhoods of idempotents in topological inverse semigroups
In a topological group, for any neighborhood $U$ of the origin, there is another such neighborhood with the property that $V.V\subseteq U.$ I conjecture a similar property for topological inverse ...
- 1,093
1
vote
0
answers
76
views
Is this version of Nested Selection equivalent to AC?
This is an endeavor to salvage "Nested Selection" principle presented in a prior posting.
Define
$ \begin{align} Y \text { is } \Phi \text{-image of } X \iff &\forall a \in X \exists b \...
- 11.3k
1
vote
0
answers
95
views
Eventual stabilization for repeatedly adding multiplayer games
This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.
To keep things readable, I'...
- 20.5k
1
vote
0
answers
130
views
How much choice we can get from this partition principle?
For every set $X$ there cannot be a partition on $X$ of a larger size than the set $\iota``X$ of all singleton subsets of $X$. Formally: $$\begin{align} \forall X \forall P: P \text { is a partition ...
- 11.3k
1
vote
0
answers
143
views
Is this approximation to infinitary equivalence coarse on countable structures?
This question is a kind of dual to this earlier one. Note that if we replace $\mathsf{FOL}$ with $\mathcal{L}_{\omega_1,\omega}$, things trivialize since we can use the theory $\{\varphi^A\...
- 20.5k
1
vote
0
answers
74
views
Reference request: Has those type-level tuples working in presence of Ur-elements, been defined before?
Working in $\sf ZFA$, or in $\sf NFU$:
We split the universe $V$ into two disjoint subclasses $\mathcal V_1, \mathcal V_2$ that are equinumerous with $V$
Now we take two bijections:
$F_1: V \to P^+(\...
- 11.3k
1
vote
0
answers
79
views
Can this method let choiceless large cardinals be smaller than cardinals compatible with choice?
Recall question "Can we have this sequence where choice fails and returns?"
Can that theory be extended with requiring the $\mathcal V_n$'s to fulfill a choiceless large cardinal extension ...
- 11.3k
1
vote
0
answers
91
views
A term for a submonoid of a free abelian monoid?
Are there multiple ways of characterising which monoids are submonoids of free abelian monoids?
What free abelian monoids are:
A free abelian monoid $\mathbb N^d$ with $d$ generators (where $d$ is an ...
- 4,943
1
vote
0
answers
57
views
Is stratified sorted rendering of naive set theory equivalent to tangled type theory?
I think the most important point in stratification is to have what may be called a fixed membership type distance per variable.
What I mean is that if a variable $x_i$ occurs in a stratified formula $\...
- 11.3k
1
vote
0
answers
138
views
Category whose morphisms are commutative monoids but not enriched
In a recent investigation, I constructed a category $\mathcal{C}$ with the following property. For objects $X,Y \in \mathcal{C}$, the morphism set $\text{Mor}(X,Y)$ is a commutative monoid with ...
- 161