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.
5,126
questions
2
votes
0
answers
201
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 ...
-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 ...
7
votes
2
answers
409
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 ...
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 ...
10
votes
1
answer
629
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 ...
0
votes
0
answers
138
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 ...
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 ...
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 ...
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 ...
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}$...
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}$ ...
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 ...
-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:...
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\...
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, ...
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 ...
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]^...
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(...
-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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$,...
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 ...
-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 ...
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 ...
-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 ...
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$? ...
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)$ ...
-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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$, ...
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 ...
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 ...
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 $\...
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. ...
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 ...
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 ...
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. ...
-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 \...
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 ...