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
8
votes
1answer
114 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 ...
11
votes
0answers
152 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).$$ ...
8
votes
1answer
232 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 ...
6
votes
1answer
149 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
211 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 ...
5
votes
1answer
140 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/...
8
votes
0answers
174 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 ...
5
votes
1answer
93 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
126 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
84 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
244 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
215 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
81 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
148 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
200 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
160 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
162 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]$-...
29
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
141 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
202 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
176 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
306 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
160 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
149 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
217 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
166 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 ...
1
vote
1answer
199 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
85 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
65 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'\...
6
votes
1answer
111 views

Empty preimage under homomorphism of finitely presented groups with decidable word problems

Let $f:G\to H$ be a homomorphism of finitely presented groups with decidable word problems. Assume you are given explicit finite presentations for both $G$ and $H$ and you are given the words to which ...
13
votes
1answer
411 views

Is the diagonal of finitely presented groups computable?

Let $f:G\to H$ be a surjective homomorphism of finitely presented groups. If the kernel of $f$ is finitely generated then is $G\times_H G$ is a finitely presented group? Can one compute an explicit ...
16
votes
2answers
805 views

Element being trivial in a finitely presented group independent of ZFC

Is there an explicit finitely presented group $G$ and an element $g\in G$ such that the statement "$g$ is equal to the identity" is independent of ZFC?
6
votes
1answer
130 views

Empty preimage under homomorphism of finitely presented groups independent of ZFC

Is there a homomorphism of finitely presented groups $f:G\to H$ and an element $h\in H$ such that the statement "$f^{-1}(h)$ is empty" is independent of ZFC?
0
votes
0answers
34 views

Can all unions of sets above some level be constructible before the sets in some relative constructible universe?

Can we have some relative constructible universe $ L(A) \ (or \ L[A])$ such that for some infinite ordinal $\gamma \leq |A|$ we have: for every subset $u$ of $A$, if $u$ is the union of a set $\sf U$ ...
3
votes
0answers
62 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?...
9
votes
1answer
269 views

Do saturated models require choice?

Let $T$ be a first-order theory, and suppose we want to build a saturated model $\mathbb U$ of $T$. That is, we want a model $\mathbb U$ of cardinality bigger than $|T|$, saturated in its own ...
6
votes
0answers
61 views

How similar can a model of $I\Delta_0$ be to the intersection of all of its definable cuts?

Let $M$ be a model of $I\Delta_0$. Recall that a definable cut is a definable (possibly with parameters) subset $I$ of $M$ that is non-empty, downwards closed, and closed under successor. If we ...
0
votes
1answer
251 views

Can we choose a sequence of Hilbert spaces?

Let $n$ be a fixed natural number. Let $H$ be a complex Hilbert space and $H_1,\dotsc,H_n$ be closed subspaces of $H$. Set $H_0\mathrel{:=}H_1\cap H_2\cap\dotsb\cap H_n$ and let $P_i$ be the ...
11
votes
1answer
520 views

Does every countable set of Turing degrees have an upper bound, without AC?

It is easy to see that every countable collection of sets $A_n\subseteq\mathbb{N}$ has an upper bound in the Turing degrees, since we can just take a copy of their disjoint sum $\oplus_n A_n=\{\langle ...
4
votes
1answer
170 views

Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?

Given a Diophantine equation it is not decidable if it has integer solution. I. Is there a Diophantine set $\mathcal D_{unique}$ satisfying the properties every member in $\mathcal D_{unique}$ is a ...
27
votes
1answer
726 views

Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?

Zorn’s Lemma applies to posets in which every chain has an upper bound. However, in all applications I know, the poset is also evidently chain-complete — chains have least upper bounds. A few ...
8
votes
5answers
2k views

Can you do math without knowing how to count?

Are there mathematical theories that do not use intuitive integers? [That is, do not use integers to write statements.] Can you propose a theory that describes natural integers, without using ...
1
vote
1answer
230 views

Is existence of this set consistent with Zermelo set theory minus choice?

Define a pre-ordinal as a transitive set of transitive sets. Is it consistent with Zermelo set theory (without choice) to have a nonempty set $S$ such that: for every element $s \in S$ there exists a ...
0
votes
0answers
83 views

Where does intuitionistic predicate logic live in the arithmetical hierarchy?

I started reading Plisko's papers on arithmetic complexity on the arithmetic complexity of constructive logic (see for example here or here). In this context, I started wondering about the following ...
4
votes
1answer
115 views

Universal property of the codomain fibration

Let $\mathcal{C}$ a category with pullbacks. Does $\mathsf{cod}: \mathcal{C}^{\to}\to\mathcal{C}$ have any kind of universal property in the category of (co)fibrations over $\mathcal{C}$? I'd want it ...
1
vote
0answers
91 views

What is the proof theoretic strength of PCF?

Godel's system $T$ means different, although equivalent, things to different people. To people working in the traditon of mathematical logic, $T$ is a quantifier-free equational theory of arithmetic ...
3
votes
0answers
119 views

Is anything known about $\Delta_n$ bounding?

For a class $\Gamma \in \{ \Sigma_n, \Pi_n, \Delta_n \}$ in the arithmetical hierarchy, we can consider the induction, bounding, and least number principles for $\Gamma$: $\mathsf{I}\Gamma$ is $\big[ ...
0
votes
3answers
125 views

value (element of an algebra), constant, variable, ground and non-ground terms, free algebras : there is a need for clarification

I have been developing an algorithm to compute the congruence defined by a finite set of "generators" and a finite set of equations (in the sense of equational theories). The algorithm ...

1
2 3 4 5
80