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
2 votes
0 answers
199 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 ...
Logan 's user avatar
  • 21
-10 votes
0 answers
148 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 ...
Dave Selke's user avatar
7 votes
2 answers
406 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 ...
sai's user avatar
  • 73
4 votes
0 answers
153 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 ...
Lxm's user avatar
  • 221
10 votes
1 answer
626 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 ...
Anonymous grad student's user avatar
0 votes
0 answers
137 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 ...
Zuhair Al-Johar's user avatar
3 votes
1 answer
92 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 ...
Lukas Holter Melgaard's user avatar
4 votes
0 answers
130 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 ...
Alexey Slizkov's user avatar
2 votes
0 answers
123 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 ...
Mike Battaglia's user avatar
7 votes
1 answer
163 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}$...
Miha Habič's user avatar
  • 2,279
5 votes
0 answers
164 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}$ ...
Noah Schweber's user avatar
6 votes
1 answer
294 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 ...
user524506's user avatar
-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:...
Zuhair Al-Johar's user avatar
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\...
paulotorrens's user avatar
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, ...
DeadRingerAmbassador's user avatar
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 ...
Fiona's user avatar
  • 71
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 ...
Ilk's user avatar
  • 679
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]^...
Dominic van der Zypen's user avatar
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(...
David Feldman's user avatar
-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 ...
Speltzu's user avatar
  • 169
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 ...
Mikhail Katz's user avatar
  • 15.1k
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 ...
XL _At_Here_There's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 ...
Ben Sprott's user avatar
  • 1,281
12 votes
1 answer
362 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 ...
Lajos Soukup's user avatar
  • 1,415
18 votes
1 answer
979 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$,...
Alma Arjuna's user avatar
11 votes
1 answer
1k views

Are there mutually independent undecidable statements?

In a recursively axiomatized theory such as PA, are there undecidable statements that are arithmetically true but mutually independent (i.e., are there two statements A and B that are each undecidable ...
Jacques Sentier's user avatar
-1 votes
0 answers
78 views

Minimal metatheory for Gödel's first incompleteness theorem [duplicate]

When studying the complete proof of Gödel's first incompleteness theorem, I started to harbor a metamathematical worry of circularity. For reference, I am studying the proof in A Concise Introduction ...
God bless's user avatar
  • 107
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 ...
Joel's user avatar
  • 103
-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 ...
Zuhair Al-Johar's user avatar
1 vote
1 answer
171 views

Gödel coding and the function $z(x)$

The function $z(x)$ that associates to each formula $\alpha$ of $P$ its Gödel number $z(\alpha)$ is external to the system. How then can expressions in which $z(x)$ be involved be expressed in $P$? ...
Speltzu's user avatar
  • 169
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)$ ...
Zuhair Al-Johar's user avatar
-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 ...
Zuhair Al-Johar's user avatar
6 votes
2 answers
293 views

What would you do with a new model of linear logic?

I have been working for some time with collaborators developing some models of linear logic which we are confident are new. However, none of us is deep enough in the field to answer the sceptic's ...
Morgan Rogers's user avatar
3 votes
1 answer
87 views

Is this form of replacement suitable for ZF - Powerset + well-ordering principle?

The following scheme can be understood as a form of replacement. Axiomatizing $\sf ZF$ with it instead of the usual replacement schema renders it immune to removal of extensionality; see here. In an ...
Zuhair Al-Johar's user avatar
2 votes
0 answers
66 views

Reverse mathematics on lightface $\Pi^1_1$-uniformization for unary relation

It is known that the following form of $\Pi^1_1$-uniformization is equivalent to $\Pi^1_1$-Comprehension over $\mathsf{ATR}_0$ (cf. VI.2.6 of Simpson's book) : (Kondo's uniformization theorem) For ...
Hanul Jeon's user avatar
  • 2,774
4 votes
2 answers
140 views

Are there outer models $V \subset W$ of $L$ such that $V$ is "far" from $L$ but $W$ is "not too far" from $V$?

In the following, whenever I say "$V_1$ is an outer model of $V_2$", I mean $V_1, V_2$ are transitive models of $\mathsf{ZFC}$, $V_2 \subset V_1$,and $ORD^{V_1} = ORD^{V_2}$. I am curious ...
Zoorado's user avatar
  • 1,215
18 votes
3 answers
2k views

What's the earliest result (outside of logic) that cannot be proven constructively?

Although mathematicians usually do not work in constructive mathematics per se, their results often are constructively valid (even if the original proof isn't). An obvious counter-example is the law ...
Christopher King's user avatar
2 votes
1 answer
219 views

A possible ${\sf (ZF)}$-theorem in the spirit of the $3$-set-lemma

The number $3$ plays an interesting role in the following statement: $\newcommand{\S}{\sf(S_3)}\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 ...
Dominic van der Zypen's user avatar
5 votes
1 answer
194 views

On the number of complete Boolean algebras

In their 1972 paper On the number of complete Boolean algebras Monk and Solovay showed that if $\lambda$ is an infinite cardinal, then there are $2^{2^\lambda}$ many isomorphism types of complete ...
Mohammad Golshani's user avatar
4 votes
1 answer
189 views

Weak Power Hypothesis and Dependent Choice

Consider in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$ the following statement: Weak Power Hypothesis (WPH): if $X,Y$ are sets and there is a bijection between $\newcommand{\P}{{\cal P}}\P(X)$ and $\P(Y)$, ...
Dominic van der Zypen's user avatar
4 votes
1 answer
164 views

Generic absoluteness

In Theorem 14 of "On The Question Of Absolute Undecidability" Peter Koellner describes a generic absoluteness result which could be summed up as $\Sigma^2_1(\Gamma^\infty)$-generic ...
Rupert's user avatar
  • 1,985
5 votes
1 answer
252 views

Is univalence equivalent to every type function being a functor over equivalence?

Introduce a rule in type theory that if $\Gamma \vdash f : \text{Type} \to \text{Type}$ and $\Gamma \vdash e : A \simeq B$ then $\Gamma \vdash f[e] : f(A) \simeq f(B)$. It may seem like such a rule is ...
Christopher King's user avatar
12 votes
0 answers
188 views

Are there times when replacement is "more natural" than collection?

There are a couple examples I'm aware of where choosing to axiomatize $\mathsf{ZF(C)}$ using collection instead of replacement results in a much nicer (or at least less surprising) picture: Let $\...
Noah Schweber's user avatar
5 votes
0 answers
190 views

Are there Dedekind-infinite amorphous sets?

An amorphous set is an infinite set (i.e. cannot be put into bijection with any finite set $\{ 1, \dots, n \}$ for any $n$) that cannot be partitioned into two mutually disjoint infinite subsets. ...
Ahraman's user avatar
  • 51
14 votes
1 answer
566 views

Changing the cofinality of a regular cardinal without collapsing any cardinals?

I have a short but hopefully interesting question on cardinal arithmetic and collapsing cardinals: Is it possible to change the cofinality of a regular cardinal without collapsing any cardinals? Is ...
user2925716's user avatar
2 votes
0 answers
111 views

Adding partitions of one but not the other kind

Say that two partitions $(P_i)_{i\in I}, (Q_j)_{j\in J}$ are isomorphic iff there is a bijection $f: I\rightarrow J$ such that $\vert P_i\vert=\vert Q_{f(i)}\vert$ for all $i\in I$. (Note that in the ...
Noah Schweber's user avatar
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. ...
Zoorado's user avatar
  • 1,215
-3 votes
0 answers
185 views

Can Mereological Container theory be bi-interpretable\synonymous with ZF-Regularity?

Intuitive background: Objects of this theory are totalities of mereological atoms (indivisible objects), for simplicity they can be depicted as linear aggregates of atoms $\bullet \bullet \bullet \...
Zuhair Al-Johar's user avatar
6 votes
1 answer
361 views

How much choice is needed to prove the completeness of equational logic?

All the proofs of the completeness of (Birkhoff's) equational logic I have read seem to pick representatives for equivalence classes of terms and hence require the axiom of choice. Is AC (or a weak ...
ralphS16's user avatar

1
2 3 4 5
103