Questions tagged [lo.logic]

first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.

Filter by
Sorted by
Tagged with
-2
votes
0answers
42 views

Computable bound on the minimum number of negations to make a statement provable

Suppose we are working in an intuitionistic logic. A statement $T$ is called $k$-verifiable for an integer $k\geq 0$ if the $k$-fold negation of $T$ has a proof. A statement $T$ is verifiable if it is ...
4
votes
0answers
91 views

Is ZF + “all sets of reals have the Ramsey property” + “there is a set without the Baire property” consistent?

Are there models of set theory where all sets of reals have the Ramsey property but there is a set of reals without the Baire property? A set $A \subseteq [\omega]^\omega$ has the Ramsey property iff ...
4
votes
0answers
79 views

Chains of length $2^\kappa$ in ${\cal P}(\kappa)$ [duplicate]

It is a fact that continues to boggle my mind: There is a set ${\cal C}\subseteq {\cal P}(\omega)$ such that $|{\cal C}|=\frak{c}=2^{\aleph_0}$ and for all $A,B\in{\cal C}$ we have $A\subseteq B$ or $...
4
votes
0answers
310 views

Can we separate the almost-disjointness sunflower numbers?

This question concerns a new cardinal characteristic of the continuum that arose out of issues in my answer to the question, Sunflowers in maximal almost disjoint families. A family $\cal A$ of ...
0
votes
0answers
67 views

How does “spreading-with-determinacy” compare with Cichon's diagram?

For $\mathbb{A},\mathbb{B}\subseteq\mathcal{P}(\omega^\omega)$, say that $\mathbb{A}$ spreads onto $\mathbb{B}$ iff there is some $F:\omega^\omega\rightarrow\omega^\omega$ such that $F[A]\in\mathbb{B}$...
12
votes
3answers
356 views

For ideals, does normal imply countably complete?

The following little question has bugged me for a while. Suppose $Z \subseteq \mathcal P(X)$. We say an ideal $I$ on $Z$ is normal when it is closed under diagonal unions, which means that if $\{ A_x ...
6
votes
1answer
364 views

Is this compactness property for “satisfiability on $\mathbb{R}$” consistent?

This was originally part of this older question of mine, but in retrospect that question should have been broken into two parts - this is the still-unanswered part. Let $\Sigma$ be the language of ...
3
votes
1answer
204 views

Do escaping sets “uniformly” cover dominating sets under determinacy?

For $\mathbb{A},\mathbb{B}\subseteq\mathcal{P}(\omega^\omega)$, say $\mathbb{A}$ spreads onto $\mathbb{B}$ iff there is some $F:\omega^\omega\rightarrow\omega^\omega$ such that for all $X\in\mathbb{A}$...
0
votes
1answer
198 views

What is the smallest countable limit ordinal in which 'lost melodies' occur

The question is in the title. This question is in response to the following paragraph found at the end of Prof. Hamkins' answer to my MathOverflow question, Are ITTM's necessary to compute Turing's &...
6
votes
1answer
305 views

Is the supremum of L-definable cardinals silver-indiscernible

Let $\kappa$ be the supremum of ordinals first order definable in L without parameters. Assume $0^\sharp$ exists. Is $\kappa$ the least silver indiscernible ordinal?
6
votes
0answers
154 views

Can this weakish system of arithmetic express multiplication for second-sort numbers?

Consider a 2-sorted first-order logic with equality (for first-sort entities). The first sort consists of numbers, the second sort (which will be capitalized) of unary functions. There is one constant,...
6
votes
1answer
374 views

Practical Benefits of HTT/univalent foundations for assisted proofs

I'm trying to understand what the claimed practical benefits of HTT/univalent foundations are for doing computer assisted proofs and while I've seen a lot of claims of benefits they all seem to be ...
7
votes
0answers
73 views

Can superstability of a countable theory be characterized in terms of not 'weakly trace interpreting' a particular structure?

The concept that I want to think about in this question is very similar to trace definability, introduced here and also independently by Guingona, but is somewhat different from it. There's a very ...
2
votes
0answers
154 views

What is the strength of the single Replacement sentence?

What's the consistency strength of adding the following single sentence replacement like statement to $\sf Z + \forall x \exists \alpha: x \in V_\alpha$ ? $$\forall \varphi \forall A \ [\forall x \in ...
4
votes
0answers
178 views

generate all possible theories compatible with axioms [migrated]

I am currently trying to learn about the fundations of mathematical logic, and the incompleteness theorem. I was curious to know if there's a way, given some given axioms, to analyze all the possible ...
6
votes
0answers
143 views

Curry-Howard isomorphism: What is the logical counterpart of closure conversion?

Continuation-Passing Style (CPS) translation in programming languages corresponds to double-negation translation in logic (and the Yoneda lemma in category theory). Then what in logic corresponds to ...
0
votes
1answer
166 views

What's wrong with this argument for CON(ZFC)? [closed]

If a $\Pi_1$ sentence is independent from PA, then it is true. CON(ZFC) is a $\Pi_1$ sentence and independent from PA. Therefore, CON(ZFC). If this is a valid argument in ZFC, it would violate Gödel'...
4
votes
0answers
272 views

Is the set of approximating sequences for irrationals dominating?

Let $r\in [0,1]\setminus\mathbb{Q}$, let $\mathbb{N}$ denote the set of non-negative integers and let $\mathbb{N}_+=\mathbb{N}\setminus\{0\}$. For $n\in\mathbb{N}_+$ let $$\alpha_r(n)=\min\{|r-\frac{...
12
votes
2answers
642 views

Is “There exists an unbounded non-measurable set but no bounded non-measurable set” consistent with $\mathsf{ZF}$?

This is a follow-up to this question. We say that a set $A \subseteq \mathbb{R}$ is bounded if there exists a finite interval $(a,b)$ such that $A \subseteq (a,b)$. Working in $\mathsf{ZFC}$, the ...
14
votes
1answer
667 views

What is the “Prikry–Silver collapse” when CH fails?

We all know and love Cohen reals, and we can (and often do) define the Cohen forcing as partial functions $p\colon\omega\to 2$ with finite domain. The Prikry–Silver forcing is defined as partial ...
14
votes
1answer
293 views

What are internal complete atomic boolean algebras, intuitively?

The category of complete atomic boolean algebras $\mathbf{CABA}$ is equivalent to $\mathbf{Set}^{\mathrm{op}}$ via $$\mathbf{Set}^{\mathrm{op}} \to \mathbf{CABA}, ~ X \mapsto (P(X),\bigcup,\bigcap).$$ ...
11
votes
1answer
297 views

What is meant by a computational interpretation of univalence?

In homotopy type theory the univalence axiom implies function extensionality. Suppose we have a recursive set we are not sure is empty (e.g. the set of even integers$\geq 4$ that are not a sum of two ...
7
votes
1answer
210 views

Models with fixed cardinality of non-Lebesgue measurable sets

In the usual $\mathsf{ZFC}$, we know that there are $2^\mathfrak{c}$ many subsets of $\mathbb{R}$ that are not (Lebesgue) measurable. On the other hand, the Solovay model also provides us a model of $\...
1
vote
0answers
235 views

Is this theory using defined notions of classes, sets, and membership interpretable in ZFC?

The main difference with this formal theory is that it depends in an essential manner on a defined notion of class, set, and set membership $\in$, rather than the usual appraoch of leaving them ...
6
votes
1answer
186 views

How similar are the c.e. degrees and the CEA(Cohen) degrees?

Given reals $A,B,X$, let $A\le_{T/X}B$ iff $A\oplus X\le_TB\oplus X$. For each real $X$ we can define a version of the c.e. degrees over $X$: we look at the preorder on $X$-c.e. reals given by $\le_{T/...
10
votes
0answers
207 views

Definable constructions in o-minimal geometry

Recently I've been working with o-minimal expansions of $(\mathbb{R},\times,+)$, and I want to work "internally" to the language of o-minimal sets instead of working with "definable ...
6
votes
1answer
106 views

2-REA PA degrees

Remember that an n-REA set is a set of the form $A_0 \oplus A_1 \oplus \cdots \oplus A_n$ with $A_n$ relatively r.e. in $A_m, m<n$ (so $A_0$ is r.e.) and that a degree is PA just if it computes a ...
2
votes
0answers
133 views

A question on entailments in sequents

Suppose $\Gamma\vdash A\vee \Delta$, where as usual $\Gamma$ and $\Delta$ are thought of as sets of propositions and the turnstyle is for logical consequence, or entailment. Given the assumption, may ...
0
votes
1answer
85 views

Detecting non-negativity of a single constraint by polyhedral constraints - $I$

We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
5
votes
2answers
256 views

Extending contents

Suppose $\mu$ is a finitely additive measure on $X$ (aka “content”) with $\mu(X) < \infty$, defined on an algebra of sets $\mathcal A$. Let $$\mu^*(Y) = \inf \{ \mu(E) : E \in \mathcal A \wedge E \...
4
votes
1answer
229 views

Coloring almost-disjointness

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. Let $$E = \big\{\{A,B\}: A,B \in [\omega]^\omega \text{ and } |A\cap B| \text{ is finite}\big\}.$$ We consider the graph $G=...
0
votes
0answers
85 views

What is the exact consistency strength of this type-set theory?

Language: bi-sorted first order logic with equality and its axiom and additionally the extra-logical primitives: $ ``\tau, < , \in"$, the first is a total unary function on sets denoting is the ...
6
votes
0answers
156 views

Are initial segments of coherent measure sequences coherent?

This question is about the "old-fashioned" coherent sequences, in the style of Mitchell Mitchell, W. (1974). Sets constructible from sequences of ultrafilters. Journal of Symbolic Logic, 39(...
5
votes
2answers
211 views

Assuming decidable equality but not LEM in HoTT

The law of excluded middle in homotopy type theory is a term of $$\prod_{A:\mathcal{U}}\Big(\mathrm{isProp}(A)\to(A+\neg A)\Big).$$What if we assume a term of$$\prod_{A:\mathcal{U}}\Big(\mathrm{isSet}(...
1
vote
0answers
166 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 ...
4
votes
1answer
177 views

How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?

This question implies that we have fixed: (i) a particular enumeration of Ordinal Turing machines; (ii) a particular way to encode an ordinal by an infinite binary sequence. The class of $[1]$-...
31
votes
3answers
3k views

Alternatives to the law of the excluded middle

As a sentential logic, intuitionistic logic plus the law of the excluded middle gives classical logic. Is there a logical law that is consistent with intuitionistic logic but inconsistent with ...
8
votes
0answers
147 views

Bounded Diophantine sets

A set $S\subset \mathbb{Z}$ is Diophantine if there is an integer polynomial $P(n, \bar{m})$ such that$$n\in S \iff (\exists \bar{m} \in \mathbb{Z}^{k})(P(n,\bar{m})=0).$$A set $S\subset \mathbb{Z}$ ...
2
votes
0answers
227 views

Can we have $\sf V=HTD$? How it relates to $\sf V=HOD$?

In my search for some type-set motivated line of thought that might prove axiom of choice, I was thinking of a concept that looks like $\sf V=HOD$, but in terms of types instead of ordinals, that is ...
7
votes
1answer
183 views

Categorical semantics of universe levels in dependent type theory

I know that locally closed cartesian categories provide categorical semantics for type theories with dependent products. What kind of categories model type theories with infinite universe hierarchies (...
3
votes
2answers
326 views

Can Z + Ranks + Successor cardinals + Ordinal inaccessibility be equal to ZF?

[EDIT: The axiom of successor cardinals was found by an answer by Greg Kirmayer, not to be capturing the intended meaning of it, which is simply reflected by its name, i.e. the existence of a ...
7
votes
0answers
166 views

How much is known about the consistency strength of toposes and topos-like categories?

It's a well-known fact that the theory of a well-pointed topos with a natural numbers object (NNO) has the same consistency strength as MacLane set theory (also known as bounded Zermelo). There are ...
6
votes
3answers
158 views

Relationship between provable in $RCA_0$ and effectively true

Question: What is the relationship between provability in $RCA_0$ and effectively true? In other words: Given a problem, if a statement asserting the existence of a solution of the problem is provable ...
3
votes
0answers
218 views

Intuitive (topological) explanation of a proof from the HoTT book [closed]

My friends and I are struggling with understanding intuitively the proof of equivalence between based and free path inductions (HoTT book 1.12.2) The first major problem is understanding the meaning ...
4
votes
1answer
91 views

Computable change in minimum word length of subgroup elements

Let $G$ be an infinite finitely generated group. Fix a finite generating set for $G$. Define $\mathrm{len}_G:G\to\mathbb{Z}_{\geq 0}$ by sending $g$ to the minimum length of a word in the generators ...
9
votes
0answers
98 views

Decidable membership for subgroup generated by three elements in $F_2\times F_2$

Let $F_2$ be the non-abelian free group on two generators. Let $G\subset F_2\times F_2$ be a subgroup generated by three elements. Is there an algorithm deciding if a given element of $F_2\times F_2$ ...
1
vote
1answer
176 views

Russell's definite description and vacuous truth: a puzzle? [closed]

According to Russell's definite description theory, "The present King of France is bald" is a false statement. However, since for any property $P$, $P$ is true for the elements of the empty ...
0
votes
1answer
242 views

What does the Concordant constructible universe model?

Define a ranking function $\cal R$ as: $\mathcal{R}: V \to ON; \,\mathcal {R}(x)= \min \alpha \, \forall y \in x: \alpha > \mathcal {R}(y) $ Now the constructible rank $\mathcal R^c$ of a set $X$ ...
7
votes
0answers
87 views

Reduced power of an ordered field

Suppose $K$ is an ordered field, $X$ is any set, and $F$ is a filter over $X$. Let $G$ be the reduced power of $K$ by $F$. That is, we take all functions from $X$ to $K$, then take equivalence ...
5
votes
1answer
67 views

Equality to a power of a given word undecidable in finitely presented group with decidable word problem

Let $G$ be a group with an explicit finite presentation. Assume $G$ has a decidable word problem. Can there exist an explicit word $w\in G$ such that there is no algorithm deciding if a given word $w'\...

1
2 3 4 5
81