Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-1
votes
2answers
84 views

On OR condition in Linear Programming with exponentially many constraints [closed]

Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
37
votes
4answers
2k views

The symmetric group theory of natural numbers

Sometimes it is not easy to formulate a correct question. Here is a better version of this question (I still do not know if it is optimal, but it is better than the previous one). We say that a set $...
9
votes
2answers
287 views

Does Easton forcing preserve measurable cardinals?

The question is in the title. For Easton's theorem see Wikipedia. Loosely speaking we can use forcing to manipulate the powerset function on regular cardinals as much as we like given we satisfy the ...
6
votes
1answer
156 views

Correspondence between proof-theoretic ordinals and fast growing functions?

For theories with well known proof-theoretic-ordinals, (what) is there a correspondence between their proof-theoretic-ordinal and (ordinal indexed families of?) fast growing functions provable total ...
17
votes
4answers
1k views

Constructively, is the unit of the “free abelian group” monad on sets injective?

Classically, we can explicitly construct the free Abelian group $\newcommand{\Z}{\mathbb{Z}}\Z[X]$ on a set $X$ as the set of finitely-supported functions $X \to \Z$, and so easily see that the unit ...
93
votes
9answers
12k 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 ...
21
votes
1answer
789 views

When will the real numbers be Borel?

In set theory Borel sets are important, but we don't actually care about the sets. We can about the Borel codes. Namely, the algorithm to generate a given Borel set starting with the basic open sets (...
5
votes
1answer
421 views

Translating first order statements about symmetric groups into the language of numbers and back

A question I was asked recently lead me to the following question. For every closed first order formula $\theta$ in the group signature consider the set $N_\theta$ of natural numbers $n$ such that the ...
19
votes
0answers
817 views

Is Feferman's unlimited category theory dead?

In The prospects of unlimited category theory: doing what remains to be done, 2014 (The Review of Symbolic Logic, 8 (2015) pp 306-327, link), Ernst discusses Feferman's program, described in ...
3
votes
1answer
368 views

Does cut elimination fail here?

Proving $\lnot\lnot(A\lor\lnot A)$ in intuitionistic sequent calculus with cut seems to be easy: We use cut to prove $\lnot(A\lor\lnot A)\vdash \bot$ from $\lnot(A\lor\lnot A)\vdash \lnot A \land\lnot\...
4
votes
2answers
270 views

Categorification of spaces and models for set theory

One aspect of topos theory is that it provides an enlarged view of the classical concept of space. Indeed, one may thought that the notion of topos is a sort of categorification of the notion of space....
2
votes
0answers
122 views

How to construct “inaccessible hypernatural”?

Consider that, take a sufficient large natural number $a_1$, then take a natural number $a_2$ sufficient large to $a_1$, then take $a_3$,... Now we have a function $n \mapsto a_n$ which grows very ...
5
votes
1answer
222 views

Isn't a Shapiro-Wilk normality test assuming its conclusion?

I am currently thinking about formalization of some statistics (in Coq). One thing I don't understand is the logic of e.g. the Shapiro-Wilk test for normality. To explain my problem, let's first look ...
2
votes
0answers
76 views

Is the quantifier-free fragment of Robinson arithmetic essentially undecidable?

It is well known that Robinson arithmetic (Q) is undecidable, and in fact essentially undecidable. Matiyasevich's theorem implies that the quantifier-free fragment of Q is also undecidable. However, I'...
50
votes
5answers
5k views

The Logic of Buddha: A Formal Approach

Buddhist logic is a branch of Indian logic (see also Nyaya), one of the three original traditions of logic, alongside the Greek and the Chinese logic. It seems Buddha himself used some of the features ...
4
votes
1answer
250 views

A weak fragment of analysis?

Question: Is there a decidable theory sufficient to formulate and prove (many) theorems of classical analysis? What I have in mind is a theory with two kinds of objects, reals (which are introduced ...
19
votes
4answers
887 views

Mathematics without the principle of unique choice

The principle of unique choice (PUC), also called the principle of function comprehension, says that if $R$ is a relation between two sets $A,B$, and for every $x\in A$ there exists a unique $y\in B$ ...
11
votes
0answers
253 views

Does Foundation increase the strength of second-order logic?

Thinking about the recent threads on structural consequences of the Axiom of Foundation (AF) over ZF-AF, I've been trying to find some conservativity result which explains why AF doesn't seem to have ...
5
votes
1answer
338 views

Can an uncountable model of Peano Arithmetic be recursive?

Can an uncountable model of Peano Arithmetic be recursive? What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...
5
votes
1answer
327 views

What is the consistency strength of this theory?

Language: first-order logic Primitives: $=, S, \in $ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation). Axioms: those of identity ...
10
votes
2answers
352 views

Consequences of foundation/regularity in ordinary mathematics (over ZF–AF)?

This is a followup question to Does foundation/regularity have any categorical/structural consequences, in ZF? As shown in answers to that question, the axiom of foundation (AF, aka regularity) has ...
4
votes
3answers
143 views

Closed free subgroups of the automorphism group of the countable atomless boolean algebra

Let $\mathcal{B}$ be the (unique up to isomorphism) countable atomless boolean algebra, and $\mathrm{Aut}(\mathcal{B})$ its automorphism group, with pointwise convergence topology. My question: Does $...
13
votes
2answers
657 views

What kind of category is generated by Cubical type theory?

What kind of ‘category’ is Cubical type theory the internal language of? Its known that Martin-Löf type theories are the internal language of Locally cartesian closed categories, adding higher ...
3
votes
2answers
200 views

Stability and complete types (in Model Theory)

I read the following statement in these slides of Saharon Shelah: "$K$ is stable iff for every $M \in K$ there are only "few" complete types over $M$." About the notation: here $K$ consists of all ...
8
votes
1answer
267 views

Automated geometry theorem provers

What is the state of the art concerning automated geometry theorem provers (AGTP)? I can see that a few computer algebra softwares and dynamic geometry softwares (e.g. geogebra) have embedded provers ...
1
vote
1answer
134 views

Can we have a nearily unrestricted class comprehension over predicates that do not mention the class membership symbol

Suppose that $T$ is a consistent first order theory. Now let the language of $T$ be $L_T$. Question: is it always consistent to add a new primitive constant $D$, and a new primitive binary relation $...
-3
votes
1answer
258 views

What is the intuitive notion that ZF-Extensionality-Foundation+Collection can be said to capture? [closed]

This question has been moved to philosophy.stackexchange.com I'll try to abbreviate it here: the question asks about the "informal notion" that the fragment of $\text{ZFC}$ that is axiomatized by ...
0
votes
0answers
81 views

Decidability of mate-in-n for infinite chess with huygens piece

Consider a game like chess on an infinite board, where we have the usual chess piece types and an additional piece which moves a prime number of square horizontally or vertically. If we assume a ...
11
votes
2answers
226 views

Are all generalized Scott sets realized as generalized standard systems?

Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so. The standard system of a nonstandard ...
8
votes
9answers
3k views

Circular, or missing, definition in set theory?

Revision in response to early comments. Users of set theory need an implementation (in case "model" means something different) of the axioms. I would expect something like this: An implementation ...
2
votes
1answer
186 views

Concrete mathematical statements in relation to Choice versus Reinhardt cardinals?

Harvey Friedman is well known for investigating concrete mathematical statements that requires strong assumptions, i.e. those that can only be interpreted in a strong extension of $\text{ZF(C)}$. My ...
3
votes
0answers
92 views

Singular compactness for stationary reflection?

Let $\lambda\geq \omega_2$ be a regular cardinal. The weak reflection principle for $[\lambda]^\omega$ ($WRP([\lambda]^\omega)$) asserts that for any stationary $S\subset [\lambda]^\omega$ there ...
28
votes
2answers
2k views

On the probability of the truth of the continuum hypothesis

First note that there exists a natural measure $\mu$ on $P(\omega \times \omega)$, inherited from the Lebesgue measure on the reals (by identifying the reals with $P(\omega)$ and $\omega$ with $\omega ...
-4
votes
1answer
391 views

Are there paradoxes in ZF + (the Axiom of Choice for finite sets)? [closed]

The good intuitive reasons that the Axiom of Choice (AC) for arbitrary sets-- that a function f with f(i) in S(i) for each i in {i}, for any non-empty sets {i} and all S(i), exists-- doesn't follow ...
7
votes
2answers
164 views

On models of $Th_{\Pi_2}(PA)$

Let $M$ be a nonstandard model of $PA$. Q1. Is there any way to get a submodel $N\subset M$ such that $N\models Th_{\Pi_2}(PA)$, but $N\not\models PA$? Q2. Especially, what combinatorial ...
4
votes
1answer
138 views

How is this HA unprovable formula recursive realizable?

In Realizability: A Historical Essay [Jaap van Oosten, 2002], it is said that recursive realizability and HA provability do not concur, because although every HA provable closed formula is realizable, ...
6
votes
1answer
104 views

Join Density in R.E. Degrees: Are there r.e. B, C with all r.e. X below B computable or C join X computes B

Are there r.e. sets $B >_T 0$ and $C >_T 0$, $C \not\geq_T B$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$. The explanation for the title is because one can ...
14
votes
1answer
521 views

Does every model of ZF-foundation have an extension, with no new well-founded sets, where every set is bijective with a well-founded set?

This question follows up on an issue arising in Peter LeFanu Lumsdaine's nice question: Does foundation/regularity have any categorical/structural consequences, in ZF? Let me mention first that my ...
13
votes
2answers
605 views

Does foundation/regularity have any categorical/structural consequences, in ZF?

(Prompted by reflection on this old answer, and its suggestion of the “harmlessness” of the axiom of regularity.) In ZFC, one may justify the axiom of foundation (AF, aka the axiom of regularity) as ...
0
votes
0answers
164 views

How are incompleteness and independence proofs related?

(1) Some typical inclompleteness proofs use a kind of fixed point argument - for certain $\Phi$ you find a $\varphi$ with $\Phi(\mathrm{code}(\varphi))\leftrightarrow\varphi$. (2) Some independence ...
-3
votes
2answers
346 views

Can there be an upper bound on definability of cardinal numbers in ZF? [closed]

Is there a known result to the effect that it cannot be the case that for some natural $n$, there is a formula of length $n$ such that all cardinals can be defined by a formula whose length is shorter ...
2
votes
1answer
201 views

Is $Z_3+{\rm AD}$ equiconsistent with $\text{ZFC+AD}^{L(\mathbb{R})}$

Let $Z_2$ and $Z_3$ be second and third order arithmetics respectively. In $Z_2$'s language, $\text{AD}$ (the axiom of determinacy) and $\text{PD}$ (projective determinacy) are stated the same way (...
4
votes
0answers
367 views

What is the shortest expression of finiteness? [closed]

What is the shortest definition of "$x$ is a finite class" that can be formulated in the class theory presented at: Is it possible to derive the rules of set theory as transfers from the pure finite ...
16
votes
1answer
744 views

New articles by Errett Bishop on constructive type theory?

Recently two formerly unknown articles by Errett Bishop (1928-1983) were posted online by Martín Escardó. One is entitled "A general language", deals with constructive type theory, and ...
2
votes
1answer
198 views

Unorthodox constructive reasoning: The Kleene Getaway

KG (the Kleene Getaway) is the name I improvised (in my answer to a question on MO on constructive Perron-Frobenius) for a constructive principle which enables the direct constructive use of a ...
30
votes
1answer
2k views

Is there a position in infinite Go for which the life of a particular stone has transfinite game value?

As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but ...
3
votes
0answers
91 views

A conservativity result of intuitionistic set theory over arithmetic

In their 1985 paper "Arithmetic Transfinite Induction and Recursive Well-Orderings", Friedman and Ščedrov prove that the theory $\mathbf{ZFI}$ is conservative over $\mathbf{HA}^*$ (see here, Theorem ...
7
votes
1answer
509 views

Relations of axioms of choice

We start with $ZF$. The axiom of countable choice, $AC_\omega$, says that any set product of nonempty sets with a countable index set is nonempty. For any $ZF$-definable set $A$, we should be able ...
20
votes
1answer
1k views

Are classes still “larger” than sets without the axiom of choice?

Classes are often informally thought of as being "larger" than sets. Usually, the notion of "larger" is formalized via an injection: $B$ is "at least as large" as $A$ iff there is an injection from $A$...
16
votes
0answers
436 views

Gitik's work on Shelah's weak hypothesis

It seems that Moti Gitik has recently refuted some variants of Shelah's weak hypothesis. For this see the title and abstract of his talk at the Set Theory, Model Theory and Applications conference. I ...