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
-1 votes
0 answers
15 views

Existence of long $\preceq^*$-chain in $\text{Part}(\omega)$

Let $\newcommand{\Part}{\text{Part}}\Part(\omega)$ denote the collection of partitions of $\omega$ (the first infinite ordinal). We have $|\Part(\omega)|=2^{2^{\aleph_0}}$. For $P,Q \in \Part(\omega)$ ...
16 votes
3 answers
2k views

Recommendations to learn about the use of toposes in logic?

I'd like to learn about the use of toposes in logic. The "logic" side I know quite well, but of the "topos" side I am totally ignorant. Which books/articles (formal and/or casual) ...
5 votes
0 answers
171 views
+100

Do maximal compact logics exist?

By "logic" I mean regular logic in the sense of abstract model theory (see e.g. the last section of Ebbinghaus/Flum/Thomas' book). My question is simple: Is there a logic $\mathcal{L}$ ...
2 votes
0 answers
207 views

Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?

If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not. But ...
7 votes
2 answers
411 views

Whether the pure implicational fragment of intuitionistic propositional logic is a finitely-many valued logic

Gödel (1932) showed that intuitionistic propositional logic (more precisely, any fragment with implication and disjunction) is not a finitely many-valued logic. What about the pure implicational ...
-10 votes
0 answers
153 views

Does this bijection prove the continuum hypothesis? [closed]

This is a cross-post from math stackexchange. It has been a week, but I can't provide a link because the original post was deleted. First, I want to show the bijection that is going to be built. It ...
11 votes
1 answer
370 views

Does every finite affine plane have the doubling property?

Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms: Any distinct points $x,y\...
3 votes
1 answer
201 views

Another implication of the Affine Desargues Axiom

Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms: Any distinct points $x,y\...
9 votes
2 answers
361 views

Does the Affine Pappus Axiom imply the Affine Desargues Axiom in affine planes?

I am interested in the affine version of the well-known Hessenberg's Theorem (saying that Pappian projective planes are Desarguesian). First I introduce all necessary definitions. Definition L. A ...
6 votes
4 answers
1k views

Is every Heyting algebra the Lindenbaum algebra of an intuitionistic first order theory?

This question comes after the comments in the recent related question Sigma-complete Lindenbaum algebras?, but in its current form is sufficiently different in my opinion, and so I decided to follow ...
10 votes
0 answers
438 views

(A little bit) Beyond the E-recursive

The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
4 votes
0 answers
155 views

Friedman's proof of covering lemma for $L$

There is a two-page proof of the covering lemma for $L$ using $\Sigma_n$ substructures (Theorem 3.10) in Sy Friedman's Fine Structure and Class Forcing, compared to the proof that spans about twenty ...
5 votes
1 answer
384 views

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
0 votes
0 answers
139 views

How does the cardinality of a set and its powerset compare in the hereditarily rank-concordant constructible world?

Working in the constructible universe "$L$", if we define two kinds of ranks for any constructible set $x$, one being the ordinal index of the first $L_\alpha$ where $x$ appears as a subset ...
10 votes
1 answer
632 views

Can proper classes have different sizes?

I'm presently working in a non-ZF set theory, where there are proper classes. (Think MK or VNBG.) And I'm interested in how to think about the possibility (or impossibility) of proper classes with ...
19 votes
3 answers
2k views

Algebrization of second-order logic

Is there an algebrization of second-order logic, analogous to Boolean algebras for propositional logic and cylindric and polyadic algebras for first-order logic?
4 votes
0 answers
131 views

Higher-order equivalence of ordinals

I wonder which ordinals are second-order equivalent, and similarly for other logical equivalences. Let the signature be fixed and include only <. For concreteness, let us first ask for the first ...
3 votes
1 answer
93 views

Does this hierarchy of fragments of $I \Sigma_1$ collapse?

Does anyone know whether the following hierarchy of fragments of $\mathrm{I} \Sigma_1$ (or rather $\mathrm{I} \Pi_1$) collapses or not? Let $\Sigma^b_n$ denote formulas in the language of arithmetic ...
7 votes
1 answer
295 views

Literature about formalization of "natural reasoning" in mathematical logic

In "Logic of sheaves of structures", X. Caicedo justifies the logic he introduces stating (more or less) that assertions about a point should really be understood as assertions about a ...
8 votes
1 answer
165 views

A reference for forcing projections

The idea of a projection $\pi\colon\mathbb{Q}\to\mathbb{P}$ of forcing notions is something like a combinatorial stand-in for the fact that forcing with $\mathbb{Q}$ produces a generic for $\mathbb{P}$...
3 votes
0 answers
124 views

Simplified method of building an Aronszajn tree

There is a very interesting method to build an Aronszajn tree in Judith Roitman's "Introduction to Modern Set Theory", on pages 100-102. In short, we build a tree $T$ in which the nodes are ...
42 votes
9 answers
5k views

The sets in mathematical logic

It is well known that intuitive set theory (or naive set theory) is characterized by having paradoxes, e.g. Russell's paradox, Cantor's paradox, etc. To avoid these and any other discovered or ...
52 votes
7 answers
6k views

Are there any undecidability results that are not known to have a diagonal argument proof?

Is there a problem which is known to be undecidable (in the algorithmic sense), but for which the only known proofs of undecidability do not use some form of the Cantor diagonal argument in any ...
28 votes
2 answers
1k views

Applications of Categorical Logic to Logic

This is definitely a very open ended question. I have been studying Categorical Logic for a while now --- I've read Sheaves in Geometry and Logic, Adámek & Rosický's Presentable Categories, ...
-3 votes
0 answers
208 views

Are there known examples like this almost official exposition of ZFC that is very weak?

Pseudo-ZFC is a theory written in the usual language of set theory, i.e. mono-sorted first order logic with equality and membership. The extra-logical axioms are: Extensionality: $\forall x \forall y:...
4 votes
1 answer
136 views

Does $A \leq_{\alpha} B$ imply $A \leq_{\beta} B$ for admissible ordinals $\alpha < \beta$?

My very superficial intuition of $\alpha$-recursion is that it replaces the tape in a Turing machine with $L_{\alpha}$ for some admissible $\alpha$, so that $L_{\alpha}$ functions as working memory. ...
2 votes
1 answer
115 views

Proof of Lindenbaum lemma without deduction theorem

I'm working on a formalization of Lindenbaum's completeness lemma for modal logic systems, but I've been stuck in a property. Namely, when trying to prove that: $$\forall\Gamma,\forall\phi,\enspace\...
18 votes
3 answers
2k views

How do I apply the Boolean Prime Ideal Theorem?

I have become aware of an amazing phenomenon from a myriad of questions and answers here on MathOverflow: many of the results that I would typically prove using the Axiom of Choice can actually be ...
7 votes
4 answers
414 views

A conservative extension of Peano Arithmetic

Ulrich Kohlenbach makes the following intriguing comment here: "In the 70s S. Feferman introduced a mathematically strong system S=restricted(PA^omega)+QF-AC+mu for classical mathematics (and in ...
10 votes
1 answer
266 views

Complexity of the set of models of TA

Recall that the theory of true arithmetic $TA$ is the theory of standard model of arithmetic $\mathcal N$. I am interested in the complexity of the set of countable models of $TA$ in the lightface or ...
7 votes
2 answers
600 views

Ideals generated by Turing independent sets

Recall that $X \subseteq 2^{\omega}$ is Turing independent if no $y \in X$ is computable from the Turing join of any finite subset of $X \setminus \{y\}$. Question 1. Can we construct a Turing ...
5 votes
0 answers
99 views

Variation on definition of logical functors avoiding power objects

Without power sets in meta-theory not every Grothendieck topos is an elementary topos, Set is still Grothendieck, but it lacks power objects. Now I am looking for a definition of a logical functor ...
20 votes
2 answers
2k views

Tennenbaum's Theorem and polynomials

Tennenbaum's Theorem theory says that in a countable non-standard model of arithmetic with an underlying set consisting of standard numbers, neither the polynomial $A(x,y):=x+y$ nor the polynomial $M(...
26 votes
2 answers
7k views

Large cardinal axioms and Grothendieck universes

A cardinal $\lambda$ is weakly inaccessible, iff a. it is regular (i.e. a set of cardinality $\lambda$ can't be represented as a union of sets of cardinality $<\lambda$ indexed by a set of ...
18 votes
1 answer
980 views

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$. Alice's color is $\color{red}{\text{red}}$ and Bob's color is $\color{blue}{\text{blue}}$. In each step, for each $s\in S$,...
14 votes
1 answer
1k views

Hilbert's sixth problem and QFT description

The Wikipedia entry on Hilbert's sixth problem about QFT description is “Since the 1960s, following the work of Arthur Wightman and Rudolf Haag, modern quantum field theory can also be considered ...
5 votes
1 answer
183 views

Chromatic number of the infinite Erdős–Hajnal shift-graph

For any set $X$, let $[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$. Let $\kappa$ be an infinite cardinal. Let $G_\kappa = ([\kappa]^2, E_\kappa)$ where $E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^...
67 votes
5 answers
10k views

Decidability of chess on an infinite board

The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
3 votes
1 answer
428 views

Decidability survives new constants

Let $L$ be a finite first order language and let $M$ be an $L$-structure with universe $\mathbb{N}$ that interprets all $L$-symbols as recursive sets (so $M$ is a recursive $L$-structure). Let $L(c)$...
12 votes
1 answer
363 views

Partition into antichains

I've read that the following statement is a result of Balcar, but I am unable to find a reference or a proof: Theorem: If $\kappa\ge \lambda$ are infinite cardinals, then $[\kappa]^{<\lambda}$ can ...
-4 votes
1 answer
171 views

Is Bounding Reflection consistent?

Working in the first order language of set theory. Let $\varphi^{*B}$ be the formula obtained from $\varphi$ by merely bounding all open quantifiers in $\varphi$ by the symbol "$B$". Here a ...
2 votes
1 answer
125 views

Is it consistent to add a generalization axiom on top of Ext.+Subworld Separation+Reduciblity?

Let's work with Harvey Friedman's theory ${\sf K}(W)$ as in his seminar notes "Axiomatization of Set Theory by Extensionality, Separation, and Reducibility", formulated in the language of ...
-3 votes
1 answer
282 views

Can this form of reflection be consistent?

Is this form of reflection consistent? First I'll begin by clarifying the notation I'm using here: By a quantifier being relativized or bounded it means that the first occurrence of the quantified ...
-2 votes
0 answers
224 views

Demonstration of the Diagonal Lemma

Let $f(x)$ be a recursive function, $\alpha(x)$ a class-sign and $\alpha_f(x)$ a class-sign equivalent to $\alpha(f(x))$, i.e.: $$\alpha_f(n)\Leftrightarrow\alpha(f(n))\,\textrm{ is provable for each ...
3 votes
0 answers
134 views

Homotopy type theory for semantics

It looks like I have been building up a theory that might require looking closely at Homotopy Type Theory vs. Category Theory with respect to semantics. I am considering two types of semantics that ...
23 votes
7 answers
3k views

When can we prove constructively that a ring with unity has a maximal ideal?

Many commutative algebra textbooks establish that every ideal of a ring is contained in a maximal ideal by appealing to Zorn's lemma, which I dislike on grounds of non-constructivity. For Noetherian ...
6 votes
0 answers
132 views

Complexity of transfinite 5-in-a-row and other games

Suppose that 5-in-a-row is played on an infinite board, and after an infinite number of moves, if no one won yet and there is an empty square, the game just continues. At limit steps, it is the first ...
10 votes
1 answer
241 views

How short can the axioms of propositional logic be?

There are a number of axiom systems for classical propositional calculus. Here, I focus on those which use negation ($\neg$) and implication ($\to$) as the connectives, with Modus Ponens and ...
5 votes
1 answer
237 views

When are the congruence lattices nicer?

This is a purely idle question, but one I'm increasingly interested the more thought I put into it: For $\mathcal{A}$ a universal algebra (that is, nonempty set together with some named functions), a ...
5 votes
1 answer
333 views

What is the proof of consistency of anterior reflection?

Let Anterior Reflection be the following principle: $$\forall \vec{v}~ \exists X: \operatorname {transitive} (X) \land \, (\varphi \to \varphi^{X"}) $$ where $\varphi$ is a formula in $\sf FOL(=,\in)$ ...

1
2 3 4 5
103