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
1 answer
198 views

Is every extension of ZFC interpretable in a finite extension of ZC + rank?

Let's speak of the theory $\sf ZC + rank$ as the first order set theory with axioms of Extensionality, Separation, infinity, and choice (written as usual), plus iterative powers and foundation, those ...
26 votes
3 answers
2k views

Does Con(ZF + Reinhardt) really imply Con(ZFC + I0)?

The question is: if I assert in ZF that there exists a Reinhardt cardinal, do I really get a theory of higher consistency strength than when I assert in ZFC that there exists an I0 cardinal (the ...
1 vote
0 answers
129 views

Completeness of certain formal deduction system

Consider a certain formal system with only axiom Excluded Middle -$EM$ and 18 inference rules: 9 implicative ruules (clearly not independent) and 9 tautological rules: If we have substitution at ...
2 votes
1 answer
348 views

Relation of $\omega_{\omega_1+1}^{CK}$ to some other ordinals

This was posted as a side question in Formal definition of this ordinal? and was split as a separate question based upon suggestion in comments there. Assume an ordinary ORM model (call it $C_1$). ...
4 votes
0 answers
152 views

An analogue to Robinson's theorem for Kalmar-elementary functions

Julia Robinson proved that the family of all unary computable total functions is the smallest class containing $S$, $\mathrm{Exc}$, and closed under composition, addition and inversion of surjective ...
2 votes
1 answer
315 views

Physics applications of quantum logic

Are there any examples of quantum logic being applied to solve actual physical questions, in particular to predict the physical properties (spectrum etc.) of some quantum-mechanical system? (Note that ...
-2 votes
1 answer
245 views

why do the Computability theory choose the natural number as the object of study? [closed]

I am wondering why the computable function is defined in the natural number set. Can people give me the answer or some resources that can solve my puzzle.
1 vote
0 answers
147 views

Is there difference in notion of measurability in classical versus constructive?

Are there notions of measure and examples of sets measurable in that measure in classical logic but not in constructive logic (I think there cannot be counterexamples in other direction)? Are there ...
11 votes
0 answers
249 views

Quantifier swap in Banach space theory

The uniform boundedness principle and its corollaries from a logical point of view are statements of when one can swap quantifiers in Banach spaces. Take for instance the principle of condensation of ...
6 votes
0 answers
160 views

Undecidable statements of second-order arithmetic

What are examples of statements of second order arithmetic (SOA) that are undecided by that theory? How do they relate to the existence of large cardinals?
8 votes
0 answers
252 views

Are there analogues of real-valued measurability for larger powersets?

Apologies if the question is somewhat naïve - I'm not a set theorist, just an enthusiast. One possible intuition we could have about the generalized continuum hypothesis is that power sets are so ...
37 votes
15 answers
8k views

Essential reads in the philosophy of mathematics and set theory

I am graduate student and have a decent understanding of logic and set theory. Recently I have got interested in the philosophy of mathematics and set theory. I have read a number of papers by ...
2 votes
2 answers
413 views

Is there any reasonable non-regular Gödel numbering of the language of arithmetic?

Let $\mathcal{L}$ be the language of arithmetic given as follows: $x::= {\sf v} \mid x'$ $t ::= x \mid 0 \mid {\sf S}t \mid (t+t) \mid (t\times t)$ $A ::= \bot \mid \top \mid t=t \mid \neg A \mid (A \...
1 vote
1 answer
398 views

NF and incompleteness

Are there any well-known statements independent of NF? And also, are there prerequisites suggesting that NF in any way, to one extent or another, are not covered by the incompleteness theorem?
8 votes
0 answers
177 views

Topological Vaught's conjecture for special theories

As is know, Vaught's conjecture is a special case of topological Vaught's conjecture. On the other hand, the Vaught's conjecture is true for the following theories: 1- $\omega$-stable theories (...
7 votes
1 answer
658 views

Generalizations of Birkhoff's HSP Theorem

Let $\mathbf{C}$ be the class of algebraic structures of some fixed type satisfying some sentence $\phi$. Birkhoff's HSP theorem says that $\mathbf{C}$ is closed under homomorphisms, subalgebras and ...
6 votes
1 answer
225 views

Can we recover an inner model of CH after forgetting some generic information?

Suppose $\kappa$ is an inaccessible cardinal. Let $G \times H$ be $\mathrm{Col}(\omega_1,{<}\kappa) \times \mathrm{Add}(\omega,\kappa)$-generic over $V$. Let $X \subseteq \kappa$ be $\mathrm{Add}(...
11 votes
1 answer
985 views

Kolmogorov-Arnold theorem for (just-)functions

There is famous Kolmogorov-Arnold theorem for continuous functions composition - continuous function of several variables can be composed of continuous functions of two variables. Specialization of ...
7 votes
0 answers
390 views

Universal anti-Horn classes?

Is there published work about universal anti-Horn classes? Anti-Horn formulas are also sometimes known as dual Horn. See also related question Is there any research of universal algebras axiomatized ...
2 votes
1 answer
514 views

Can rules of set theory be founded by paralleling parts of atomic Mereology?

If we work in General Extensional Atomic Mereology [without bottom], so the primitives of the language are $P$ standing for "is a part of", and equality, now we add to it membership $\in$ relation ...
54 votes
1 answer
3k views

In the two-person Killing the Hydra game, what is the winning strategy?

My question is which player has a winning strategy in the two-player version of the Killing the Hydra game? In their amazing paper, Kirby, Laurie; Paris, Jeff, Accessible independence results for ...
8 votes
2 answers
743 views

weakening naive comprehension to avoid the paradoxes

Weakening the axiom of naive comprehension has not been a popular way of escaping from the set-theoretic paradoxes because no consistent weakenings seem to be particularly well motivated or even to ...
9 votes
1 answer
578 views

Does every cofinal branch through Kleene's O compute true arithmetic?

My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides ordinal denotations for any ...
6 votes
1 answer
339 views

Semigroup product of the left-invariant completion of a Polish group (restatement of Question 71389)

This is a re-statement, of sorts, of the question Is there a relational countable ultra-homogeneous structure whose countable substructures do not have the amalgamation property?, so far unanswered. ...
8 votes
1 answer
445 views

Natural $\Pi_1$ sentence independent of PA

Order invariant graphs and finite incompleteness by Harvey Friedman gives an example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of ZFC. Is there a simpler example of ...
8 votes
4 answers
866 views

Self-defining structures

The relations $R$ in abstract graphs (with genuinely propertyless vertices) cannot be defined because there is nothing the relations can base on: they have to be presupposed. But consider derived ...
4 votes
1 answer
563 views

Is ZFC interpretable in a kind of an extended form of second order arithmetic?

Informally the following theory is a kind of extension of second order arithmetic, where numbers are not limited to naturals, instead here we have formation of further numbers by setting limits on ...
15 votes
3 answers
1k views

A rigid type of structure that can be put on every set?

Call a type of structure rigid if any automorphism of such a structure is an identity. (This is a bit different from some other uses of the word, but hopefully I'll be forgiven.) For example, well-...
2 votes
2 answers
884 views

Who first discovered the concept corresponding to the symbol of class comprehension?

Who first discovered the concept corresponding to the symbol of class comprehension $\{x/\varphi\}$ used today in set theory ?
0 votes
0 answers
195 views

Is there a formula with one free variable in NBG that defines a class that does not exist?

This question concerns Godel's Theorem on existence of classes in Set Theory of von Neumann–Bernays–Gödel. This theorem implies that for any formula $\varphi(x)$ with one free variable $x$ whose ...
5 votes
0 answers
301 views

When does $\operatorname{Aut}(M)$ preserve a linear order?

I have a general-type question: Let $M$ be a countable structure that is ultrahomogeneous, i.e. every (partial) isomorphism between finitely generated substructures of $M$ extends to an automorphism ...
2 votes
0 answers
403 views

A decision problem from sheaf set theory?

Let $V^{X}$ be a sheaf model of ZF set theory, where $X$ is a topological space as it is defined in [1]. Let $T(y_1,\ldots,y_n)$ be an $B(T)$-free algebra as it is defined in [2], where $B(T)$ is the ...
1 vote
0 answers
219 views

What can be said about a Boolean-valued structure from what the Boolean-valued forcing extension thinks about it?

Suppose that $\phi$ is a formula in the language of set theory such that there are some $n_{1},...,n_{k}$ such that if $V\models\phi(x)$, then $x=(X,R_{1},...,R_{k})$ and $\mathrm{Eq}:X^{2}\...
3 votes
1 answer
682 views

Turing machines with all runs decidable

$\DeclareMathOperator\Comp{\mathit{Comp}} \DeclareMathOperator\succ{\mathit{succ}}$Let $(\Phi_e)_{e\in\omega}$ be your favorite enumeration of Turing machines. For $e,n\in\omega$ there is a structure $...
10 votes
2 answers
590 views

Normal subgroups of automorphism group of relational structure

Let $S$ be the set of all finite permutations of $\mathbb{N}$, i.e. they fix all but a finite set, and $A\subset S$ the set of all even permutations. Theorem. The normal subgroups of $S_\infty$ are ...
1 vote
0 answers
110 views

"The" axiom of induction up to recursive ordinal $\alpha$ in $\mbox{PRA}$

As far as I understand, Kriesel proved that there exists a recursive relation $R$ of order type $\omega$ such that $\mbox{PRA}+TI(R)$ proves $\mbox{Con}(PA)$, and Beklemishev proved that for any ...
11 votes
0 answers
516 views

Isomorphic free groups have bijective generating sets

Let $F(X)$ be the free group on a set $X$. Classically, we can prove the statement: $F(X) \cong F(Y)$ if and only if $|X|=|Y|$. The proofs (that I have seen) consist of turning the group ...
8 votes
1 answer
345 views

The lattice of analogues of Robinson's $Q$

This question was asked and bountied at MSE without response. Call a sentence $\varphi$ in the language of arithmetic $Q$-like iff $\mathbb{N}\models\varphi$ and $\{\varphi\}$ is essentially ...
11 votes
2 answers
596 views

Eliminating constant in Rado graph

Let $R$ denote the Rado graph, and let $c$ be a fixed vertex. Question 1. Is the structure obtained by extending $R$ by the constant $c$ interpretable in $R$ without parameters? By interpretable I ...
13 votes
3 answers
2k views

Tarski's truth theorem — semantic or syntactic?

I was reading the sketch of the proof of Tarski's theorem in Jech's "Set Theory", which appears as Theorem 12.7, thinking that it would be an interesting result to really understand. As stated in the ...
27 votes
1 answer
2k views

Are Conway's combinatorial games the "monster model" of any familiar theory?

This is related to this question about a "mother of all" groups, and so seemed like it'd fit in better at MO than MSE. If I understand the answer to that question correctly, the surreal numbers have ...
10 votes
0 answers
273 views

How wealthy are canonical inner models?

One of the way a person shows their wealth is by having many diamonds. The same can be said about models of $\sf ZFC$. We can add generic diamond sequences, while preserving the old ones, so in some ...
5 votes
1 answer
302 views

Is Axiom of Choice equivalent to its version for families of sets, indexed by ordinals? [duplicate]

Is Axiom of Choice equivalent to the following statement? Axiom of Ordinal Choice: For any ordinal $\lambda$ and any indexed family of sets $(X_\alpha)_{\alpha\in\lambda}$ there exists a function $...
2 votes
1 answer
194 views

Determinacy and polynomial time degrees

Is there a function $f:2^{<ℕ}→\{0,1\}$ such that for all $X∈{2^ℕ}$ with $X_{2i+1}=f(X_0,...,X_i)$ all hyperarithmetical properties of the polynomial time degree of $X$ are independent of $X$? The ...
21 votes
3 answers
4k views

Categories of recursive functions

I have a couple of conjectures on recursive functions, that I feel must have been proved or refuted by someone else, but I don't know where to look. In short: 1. The primitive recursive functions ...
7 votes
2 answers
1k views

Primitive recursive arithmetic via universal algebra

From the Wikipedia article on Primitive recursive arithmetic: "Primitive recursive arithmetic, or PRA, is a quantifier-free formalization of the natural numbers. It was first proposed by Skolem[1] ...
5 votes
1 answer
427 views

How can we know the well-foundedness of $\epsilon_0$?

I think the question can be quite philosophical, but I see that $WF(\epsilon_0)$ is widely accepted as one of the attributes of the natural numbers. Gentzen proved $Con(PA)$ with $PRA+WF(\epsilon_0)$....
113 votes
11 answers
17k views

On mathematical arguments against Quantum computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
28 votes
2 answers
3k views

Who introduced direct limits?

The general notion of a direct limit of a commuting system of embeddings, indexed by pairs in a directed set, has seen heavy use in set theory. It is the same notion as in category theory. I was ...
8 votes
0 answers
428 views

Does any 'logical' theory have a bounded ∞-pretopos as syntactic category?

Stone duality may be understood as providing a duality between syntax and semantics for propositional logic, so that a theory may be recovered from its models. In order to do likewise for first-order ...

1
39 40
41
42 43
103