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
0
votes
0answers
87 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 ...
1
vote
1answer
159 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 ...
1
vote
0answers
41 views

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

Julia Robinson proved that the family of all total unary computable functions is the smallest class containing $S$, $\mathrm{Exc}$, and closed under composition, addition and inversion of surjective ...
10
votes
0answers
156 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 ...
4
votes
0answers
109 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?
-2
votes
0answers
27 views

DNF conversion in Propositional Logic: Commutative Property [closed]

I want to deduce the below function to a Distributive normal formula (DNF) and Conjunctive normal formula (CNF) $$ (P \land \neg Q) \lor (\neg Q \lor R) $$ Next I assume Commutative holds. (the ...
6
votes
0answers
169 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 ...
-3
votes
0answers
195 views

Generate distinct integers with OR [closed]

how many distinct numbers can be generated by doing bitwise OR of one or more integers between A and B (inclusive)? for example if A=7 and B=9 then answer=4 because there are four integers that can be ...
3
votes
1answer
227 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?
6
votes
0answers
98 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 (...
2
votes
2answers
210 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 \...
43
votes
4answers
4k views

Category theory and set theory: just a different language, or different foundation of mathematics?

This is a question to research mathematicians, as well as to those concerned with the history and philosophy of mathematics. I am asking for a reference. In order to make the reference request as ...
6
votes
1answer
190 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}(...
14
votes
1answer
317 views

Reverse mathematics of Cousin's lemma

This paper by Normann and Sanders apparently caused a stir in the reverse mathematics community when it came out a couple years ago. It says that Cousin's lemma, which is an extension of the Heine-...
10
votes
0answers
361 views

Does Merkurjev's argument help Voevodsky's program?

In the talk Unimath - its present and its future, July 10, 2017. Video and slides of a talk, Isaac Newton Institute for Mathematical Sciences, Cambridge. (abstract) Voevodsky mentioned that he was ...
0
votes
1answer
280 views

What is the relevant literature –if any– on real-valued functions on sets and their Boolean combinations? [closed]

As part of a project (https://arxiv.org/abs/2004.06745), I've constructed the following table, $\left( \begin{array}{ccc} \hline Constraint Imposed & Probability & Quasirandom Estimate \\ ...
49
votes
1answer
2k 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 ...
15
votes
0answers
410 views
+400

Positive set theory and the “co-Russell” set

This is a more focused version of a question which was asked at MSE a couple years ago, but is still unanswered there. That question asks about a broad range of theories, whereas this version focuses ...
0
votes
0answers
64 views

At which large cardinal property Ackermann set theory + finitization rule would stop?

By the finitization rule I mean a rule that inputs a schema in the $V$ world and outputs a single statement in the $V$ world that serves to capture that schema! So in this sense we'll have for ...
9
votes
1answer
340 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 ...
0
votes
0answers
61 views

Is Separation in $V$ a theorem schema of Ackermann set theory minus subsets?

Working in Ackermann set theory minus axiom of subsets: is $V$- bounded separation a theorem scheme of it? $V$-Bounded Separation: if $\phi^V(y)$ is a formula in which all quantifiers are bounded ...
0
votes
0answers
166 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 ...
1
vote
0answers
86 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 ...
7
votes
1answer
292 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 ...
11
votes
0answers
309 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 ...
10
votes
0answers
205 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 ...
3
votes
1answer
422 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 $...
23
votes
1answer
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 ...
13
votes
3answers
1k 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 ...
6
votes
2answers
226 views

Comparing “axiomatized function spaces”

This was previously asked and bountied at math.stackexchange with no response. Let $C(\mathbb{R}^2,\mathbb{R})$ be the space of all continuous functions $\mathbb{R}^2\rightarrow \mathbb{R}$ with the ...
8
votes
1answer
256 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 ...
7
votes
1answer
196 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 $...
4
votes
1answer
228 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)$....
2
votes
0answers
88 views

Definability in countable nonstandard models of Peano arithmetic

I know that every element of $\mathbb{N}$ is definable the standard model of Peano Arithmetic. Does there exist a countable non-standard model of PA where the same is true?
21
votes
2answers
2k views

Does the “three-set-lemma” imply the Axiom of Choice?

Consider the following curious statement: $(S)$ $\;$ Let $X$ be a non-empty set and let $f:X \to X$ be fixpoint-free (that is $f(x) \neq x$ for all $x\in X$). Then there are subsets $X_1, X_2, X_3 \...
8
votes
0answers
231 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 ...
28
votes
2answers
2k 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 ...
6
votes
1answer
174 views

Complexity of a combinatorial constraint

For two $k$-partitions $X,Y\in k^\omega$ of $\omega$ (seen as functions $\omega\rightarrow k$), we say $X,Y$ are almost disjoint iff $X^{-1}(i)\cap Y^{-1}(i)$ is finite for all $i<k$. Question: ...
54
votes
4answers
5k views

Bourbaki's definition of the number 1

According to a polemical article by Adrian Mathias, Robert Solovay showed that Bourbaki's definition of the number 1, written out using the formalism in the 1970 edition of Théorie des Ensembles, ...
2
votes
0answers
107 views

ITTMs with higher types

What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set? ...
13
votes
1answer
351 views

History of well founded relations

I have changed the title in the hope of attracting the attention of someone who knows about the history of set theory as well as intuitionistic logic: Who was the first to state the definition of ...
11
votes
3answers
576 views

The constancy principle in choiceless constructive foundations

Prove, without any Choice principles or Excluded Middle, that if a pointwise differentiable function has derivative $0$ everywhere, then it is constant. The function in this case maps $\mathbb R$ to $\...
7
votes
0answers
158 views

“Local” compactness properties beyond $\mathcal{L}_{\omega_1,\omega}$?

Below, all languages are finite for simplicity. This question is about generalizations of Barwise compactness for logics more complicated than $\mathcal{L}_{\omega_1,\omega}$: properties of the form "...
9
votes
1answer
429 views

Toposes in which countable choice is true but dependent choice isn't

I'd like examples of toposes in which Countable Choice is true but Dependent Choice isn't. I'd prefer examples without Excluded Middle. It's hard to find a natural example.
0
votes
0answers
112 views

Can inaccessibility be captured in relational flat set theory?

Working in a first order theory of flat sets (axioms given below) , which is a theory with a single non-trivial tier of membership, that is all sets are nonempty sets of Quine atoms, plus having some ...
3
votes
0answers
89 views

Global choice for models of complete theories in $\mathsf{ZFC}$

This is a followup to a previous question of mine. To summarize the result of that question, by a result of Kanovei and Shelah, $\mathsf{ZFC}$ is enough to show that there is a uniform procedure for ...
8
votes
2answers
373 views

Can nonstandard fields contain $\mathbb R$ in different ways?

Suppose $e : \mathbb R \to F$ is an elementary embedding in the language of ordered fields. Can there exist an elementary embedding $e' : \mathbb R \to F$ such that $e \not= e'$? Note that it would ...
5
votes
0answers
161 views

Inner models with all sets generic

Question: Under large cardinal axioms, what is the intersection of all inner models $M$ of ZFC such that every set in $V$ is set-generic over $M$? Every set belongs to a generic extension of HOD, and ...
11
votes
0answers
209 views

Is there a characterization of the class of first-order formulas that are closed in every compact Hausdorff structure?

Fix a relational language $\mathcal{L}$. (I don't think relational really matters that much but I don't want to worry about it.) A topological $\mathcal{L}$-structure is an $\mathcal{L}$-structure $M$ ...
0
votes
0answers
68 views

Lindenbaum lemma and non-monotonic logics

Is it possible to apply Lindenbaum's lemma to non-monotonic propositional logics to prove completeness theorem? To be more specific, for a given non-monotonic deductive system is it always possible to ...

1
2 3 4 5
73