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
3 votes
0 answers
171 views

In constructive set theory, is it consistent for there to be a ring that models smooth infinitesimal analysis?

In a constructive set theory such as CZF, it is consistent to assume that every function $f : \mathbb R \to \mathbb R$ is continuous. However, it is not consistent to assume that every such function ...
Christopher King's user avatar
4 votes
0 answers
141 views

Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?

(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.) Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
user21820's user avatar
  • 2,734
1 vote
1 answer
296 views

What is the set theory synonymous with this order-set theory?

Let $ T$ be a theory written in Mono-sorted first order logic with equality, with extralogical primitives: $<, \in$. Define: $x \leq y \iff x < y \lor x=y$ Axioms: $\textbf{Well ordering: }\\\...
Zuhair Al-Johar's user avatar
3 votes
0 answers
47 views

A new(?) kind of 2-adjunction for relating cartesian closed functors using dinatural hexagons

$\newcommand{\A}{\operatorname{A}} \newcommand{\B}{\operatorname{B}} \newcommand{\Cat}{\mathcal{Cat}} \newcommand{\Cart}{\mathcal{Cart}} \newcommand{\C}{\mathbf{C}} \newcommand{\F}{\operatorname{F}} \...
Johan Thiborg-Ericson's user avatar
5 votes
1 answer
155 views

Electronic copy of Glivenko, ‘Sur quelque points de la logique de M. Brouwer’

Glivenko is cited i.a. in the SEP: Glivenko, V., 1929, “Sur quelques points de la logique de M. Brouwer,” Académie Royale de Belgique, Bulletins de la classe des sciences, 5 (15): 183–188. I’m ...
wolvercote's user avatar
1 vote
0 answers
80 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 \...
Zuhair Al-Johar's user avatar
10 votes
4 answers
1k views

Is this theory synonymous with PA?

Language: Mono-sorted first order logic with equality. Extralogical Primitives: $<, \in$ Define: $x \leq y \iff x < y \lor x=y$ $\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
Zuhair Al-Johar's user avatar
7 votes
0 answers
129 views

Logical properties of realizability (topoi or McCarty models) defined by alpha-recursion on admissible ordinals

Setup: Let $\alpha$ be an admissible ordinal (viꝫ., one such that $L_\alpha$ is a model of Kripke-Platek set theory), identified as usual with the set of ordinals $<\alpha$. Then there is a ...
Gro-Tsen's user avatar
  • 29.8k
33 votes
3 answers
4k views

Using Busy Beavers to prove conjectures

I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
schnitzi's user avatar
  • 463
4 votes
1 answer
255 views

Bounded alternatives to powerset that interpret ZFC

In set theory, many properties/relations of interest can be expressed as $\Delta_0$ formulas (formulas with only bounded quantifiers): \begin{align} \text{empty}(a) &\equiv \forall x \in a . \...
user76284's user avatar
  • 1,793
14 votes
2 answers
1k views

Church–Turing thesis for higher order functions

The Church–Turing thesis states that, simply speaking, any reasonable definition of "effectively computable functions" $\mathbb{N} \to \mathbb N$ agrees with the definition using Turing ...
Trebor's user avatar
  • 971
2 votes
2 answers
238 views

Erdős–Sierpiński duality in locally compact Polish groups (e.g. $\mathbb{R}^n$)

Erdős–Sierpiński mapping for a locally compact Polish group $G$ is a bijection $f$ from $G$ to $G$ such that $A$ is a null set in $G$ with respect to the Haar measure if and only if $f(A)$ is a meager ...
Nugi's user avatar
  • 131
1 vote
0 answers
272 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 ...
Zuhair Al-Johar's user avatar
6 votes
1 answer
277 views

A variation on pinned equivalence relations

Recall (see e.g. Zapletal, Pinned equivalence relations) that a Borel equivalence relation $E$ on $\omega^\omega$ is pinned iff for every forcing $\mathbb{P}$ and every $\mathbb{P}$-name $\nu$ we have ...
Noah Schweber's user avatar
1 vote
1 answer
209 views

Seeking clarification of ultrapower nonstandard model of arithmetic

I've read that one nonstandard model of arithmetic is: take $\mathbb{N}^\mathbb{N}$, the set of countably infinite sequences of natural numbers take a quotent that gives the ultrapower: identify ...
Dave Pritchard's user avatar
6 votes
0 answers
205 views

What are these non-classical versions of ZFC defined by realizability?

See Kleene realizability in Peano arithmetic for a similar question, but about PA instead of ZFC. In the context of constructive set theory, consider two ways of defining realizability. The first is $\...
Christopher King's user avatar
6 votes
1 answer
274 views

Need help in trying to understand an argument by V. A. Yankov on the nonrealizability of Scott's axiom

(This is really long because I give a lot of context, but you can skip right to the end where the excerpt I'm trying to make sense of is copied and translated.) Background: I'm trying to understand ...
Gro-Tsen's user avatar
  • 29.8k
2 votes
1 answer
565 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 ...
Zuhair Al-Johar's user avatar
2 votes
0 answers
74 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 \...
NJay's user avatar
  • 21
3 votes
2 answers
507 views

Is the Ordering Principle equivalent to a selection principle?

Working in the context of set theory $\sf ZF$, selection may be defined as a function from nonempty sets to their elements. Formally: $\operatorname {selective}(c) \iff \operatorname {function}(c) \...
Zuhair Al-Johar's user avatar
7 votes
1 answer
856 views

Logical strength of a statement about vector spaces

[Apologies if this is a really trivial question, I know virtually nothing about set theory, and the following came up while preparing undergraduate linear algebra lectures.] I'm asking about the ...
David Loeffler's user avatar
-2 votes
1 answer
358 views

Defining the set of natural numbers in the first order Peano arithmetic [closed]

The question seems simple, but I'm not sure: let's consider a first order Peano Arithmetic and its standard model $N = \{ 0,1,2,3,... \}$ of natural numbers. A question: how can we define the whole ...
Viipuri's user avatar
  • 19
3 votes
1 answer
106 views

Kleene normal form theorem for r.e. relations proven in arithmetical theories

After reading the relevant chapters of Classical Recursion Theory (freely available from here), I have the following questions concerning Theorem II.1.10 (Normal form theorem) and Theorem IV.1.9 (...
CBuch's user avatar
  • 31
4 votes
1 answer
198 views

If a theory has many mutually non-embeddable countable models can it have a countable $\omega$-saturated model?

A theory can have $2^\omega$-many non-isomorphic countable models but has a countable $\omega$-saturated model. (https://math.stackexchange.com/questions/305602/if-a-theory-has-a-countable-omega-...
LYS's user avatar
  • 105
3 votes
1 answer
264 views

When is an upper bound on the longest irreducible program outputting something computable?

Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program is irreducible if no subsequence of it has the ...
Command Master's user avatar
11 votes
1 answer
417 views

Projective well-ordered sets, higher up

Background: It has long been known that it is relatively consistent with $\mathrm{ZFC + CH}$ that there is no linear ordering $\vartriangleleft $ on a subset $A$ of $\mathbb{R}$ of order-type $\...
Ali Enayat's user avatar
3 votes
2 answers
307 views

Ultrafilter projections and critical points of factor maps

Suppose $j : V \to M$ is $\lambda$-supercompactness embedding derived from an $\kappa$-complete normal ultrafilter $U$ on $P_\kappa(\lambda)$, $\lambda$ regular. Suppose $\eta$ is an ordinal such ...
Monroe Eskew's user avatar
  • 18.1k
3 votes
1 answer
242 views

Is the Class Well Ordering principle "CWO" the maximal choice principle?

In a prior posting, the Class Well-Ordering principle "$\sf CWO$" was presented, which simply states that there is a well-ordering over all classes of $\sf MK$. On the other hand, it is ...
Zuhair Al-Johar's user avatar
12 votes
1 answer
3k views

Is there a "halting machine" which halts on itself?

The crux of the halting problem is that there can be no Turing machine $M$ such that $\text{Halt}(M(N))=\neg \text{Halt}(N(N))$ for all Turing machines $N$, since $\text{Halt}(M(M))=\neg \text{Halt}(M(...
Milo Moses's user avatar
  • 2,799
4 votes
0 answers
188 views

Computational complexity of zeros of an analytic function

The work of Friedman and Ko, page 342, Corollary 4.3.1 states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
poeaqnwgo's user avatar
3 votes
0 answers
176 views

Reverse-mathematical strength of Banach-Tarski

What is the reverse mathematical strength of the Banach-Tarski paradox? The usual proof of Banach-Tarski should carry out in $\mathrm{ZF}+\mathrm{AC}_\kappa$, where $\kappa$ is the supremum of the ...
C7X's user avatar
  • 1,176
12 votes
0 answers
236 views

Intuitionistic proofs of propositional formulae versus natural transformations between finite sets

The setup: Given a formula $\varphi$ of intuitionistic propositional logic (i.e., made from the connectors $\Rightarrow$, $\land$, $\lor$, $\top$ and $\bot$ from propositional variables $A,B,C,\ldots$)...
Gro-Tsen's user avatar
  • 29.8k
2 votes
0 answers
80 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 ...
SagarM's user avatar
  • 131
7 votes
2 answers
409 views

On the existence of a real which is not set-generic over $L$

Recall that a real $r$ is set-generic over $L$ if there is a constructible forcing notion $\mathbb{P}$ and some $L$-generic filter $G\subset\mathbb{P}$ such that $r \in L[G]$. I know that Jensen's ...
Lorenzo's user avatar
  • 2,134
5 votes
1 answer
410 views

Is there a class choice principle over MK that is equivalent to class well ordering over MK?

$\sf MKCWO$ is the theory obtained by adding a new primitive binary relation $\prec$ to the signature of $\sf MK$ and axiomatize that $\prec$ is a well order on classes, that is: $\textbf{Transitive:}...
Zuhair Al-Johar's user avatar
3 votes
2 answers
195 views

Existence of trees with height $\omega$, size $\aleph_1$ and $\aleph_2$ maximal branches

Definition 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. Question: I would like to know if it is consistent ...
George Marangelis's user avatar
8 votes
1 answer
384 views

Precipitous ideal and inner model

Assume $\kappa$ is measurable, $U$ is its unique normal measure, $V=L[U]$. We levy collapse $\kappa$ to make it become $\omega_1$. If we don't have the inner model condition, then we only know that $\...
Reflecting_Ordinal's user avatar
5 votes
0 answers
131 views

When does an iteration not add functions $\eta\to V$ at the final stage?

I am interested in better understanding the following property: Let us say that an iteration of forcings $\langle\mathbb{P}_\alpha,\dot{\mathbb{Q}}_\beta\mid\alpha\leq\gamma,\beta<\gamma\rangle$ is ...
Calliope Ryan-Smith's user avatar
14 votes
1 answer
473 views

How exactly are realizability and the Curry-Howard correspondence related?

Consider, on the one hand: the Curry-Howard correspondence between, on the one hand, types and terms (programs) in various flavors of typed $\lambda$-calculus, and on the other, propositions and ...
Gro-Tsen's user avatar
  • 29.8k
-2 votes
1 answer
102 views

How to prove that increasing the number of constant symbols of a first-order logic by the number of formulas keeps the number of formulas the same [closed]

Let $S$ be a set of theory symbols for a first-order logic, and let $C$ be a set of constant symbols in $S$ such that $|C| = |L(S)|$, where $L(S)$ is the set of all formulas generated by $S$ in the ...
Andrew's user avatar
  • 1
3 votes
0 answers
163 views

Can the set of parafinite congruences be descriptive-set-theoretically complicated?

Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...
Noah Schweber's user avatar
1 vote
1 answer
139 views

Congruences that aren't "finite from above," take 2: semigroups

This is a hopefully less trivial version of this question. Briefly, say that a congruence is parafinite if it is the largest congruence contained in some equivalence relation with finitely many ...
Noah Schweber's user avatar
5 votes
3 answers
526 views

Congruences that aren't "finite from above"

Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with ...
Noah Schweber's user avatar
8 votes
1 answer
563 views

Con(PA) via non-well-foundedness?

Lumsdaine made the following interesting comment: if Con(PA) fails in a non-standard model, it means it contains a “proof of non-standard length” of a contradiction from PA. With a little work, one ...
Mikhail Katz's user avatar
  • 15.1k
8 votes
0 answers
123 views

Locally presentable and accessible categories without the axiom of choice?

Is there a good reference for the study of locally presentable and accessible categories without the axiom of choice? For instance, it seems one will need to understand: What is a good notion of $\...
Tim Campion's user avatar
  • 60.5k
2 votes
0 answers
324 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}_\...
Reflecting_Ordinal's user avatar
11 votes
2 answers
2k views

Is GCH useful in proving theorems?

By GCH I mean the Generalized Continuum Hypothesis. Let me give some context before presenting my question. When the axiom of choice was introduced by Zermelo in his 1904 proof of Well-Ordering ...
jg1896's user avatar
  • 2,683
2 votes
0 answers
17 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 ...
Johan Thiborg-Ericson's user avatar
7 votes
1 answer
230 views

Is the Rado graph the unique countable graph that has all finite graphs as induced subgraphs?

I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado ...
Vilhelm Agdur's user avatar
6 votes
0 answers
146 views

Elementary equivalence for rings

Let $\mathcal{L}$ be a first-order language, and $M$ and $N$ be two $\mathcal{L}$-structures. We say that $M$ and $N$ are elementarily equivalent (write $M \approx N$) if they satisfy the same first-...
jg1896's user avatar
  • 2,683