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

A reform of logic to secure naive set theory? [closed]

Keywords: egg of Columbus, Gordian knot. Set-theoretic paradoxes noted by Russell and others led to attempts to produce a consistent set theory as a foundation for mathematics. (Stanford Encyclopedia ...
0
votes
0answers
38 views

Regarding equality of screens (beginning of successive regions)

This question is about a more specific notion than the previous question I asked. Let's briefly discuss this notion first. In the linked question, "eventually markable" values were discussed....
0
votes
1answer
161 views

Can we define cardinality that works under weaker grounds than Scott's cardinals?

Its known that within the perspective of $\sf ZF$ related theories, Scott's definition of cardinality can work under weaker grounds than Von Neumann's! Scott's cardinality works as long as the ...
0
votes
1answer
87 views

How may a largest fixed-point be defined in second order logic?

Adapting from Anil Gupta and & Nuel Belnap, Revision theory of truth, MIT 1993, p. 194, in the context of a second order logic, where $A(x.G)$ is a formula where $G$ only occurs positively, a ...
0
votes
0answers
68 views

Does this hereditary size based definition of cardinality work under grounds weaker than regularity and choice?

To $\sf ZF - Regularity$ add the following axiom: Hereditary size: $\forall x \ \exists H_x \ \exists f (f: x \rightarrowtail H_x)$ Where: $H_x= \{y: \forall z \in TC(\{y\})\exists f (f: z \...
6
votes
1answer
624 views

Why can't we embed Tarski's truth in PA?

I recently learned that ZFC can prove $Con(PA)$ because it can give a model of PA, but I'm not given the technical details. (My teacher thinks it is too obvious to even mention.) What plagues me is ...
8
votes
2answers
347 views

Is it consistent to have a function that is sensitive to subset relation from the power set of a set to that set?

Is it consistent with $ZF$ to have a set $S$ and a function $F: P(S) \to S$ such that: $\forall X,Y \in P(S): X \subsetneq Y \implies F(X) \neq F(Y)$
4
votes
1answer
169 views

Lob theorem for Robinson arithmetic

If i'm not wrong, the theory which Lob theorem applies to should be sufficiently strong, satisfying 3 "derivability" conditions, like PA. $Q$ is the Robinson arithmetic. I'm afraid $Q$, is ...
5
votes
1answer
203 views

Does bounded Zermelo construct any cumulative hierarchy?

ZF is sufficient to construct the von Neumann hierarchy, and prove that every set appears at some stage $V_\alpha$. This is the basis for Scott's trick, for instance. But how much of ZF is needed? Is ...
8
votes
3answers
437 views

Is there a theory in a finite language that is computably axiomatizable but not by a finite number of axiom schemas?

I was told to ask this question on mathoverflow. I asked on math stack exchange whether there is a computably axiomatizable theory that can't be axiomatized by a finite number of axiom schemas. I got ...
2
votes
0answers
143 views

Is the existence of undecidable propositions decidable?

In proving his first incompleteness theorem Godel constructed a proposition that is undecidable, i.e. neither provable nor disprovable within a consistent formal system $F$ that contains elementary ...
8
votes
0answers
179 views

Distributivity of certain infinite products

Suppose we have a sequence of posets $\{\mathbb P_n : n\in\omega\}$ such that for each $n$, $\mathbb P_{n+1}$ is $|\mathbb P_n|^+$-distributive. Is $\prod_{n>0} \mathbb P_n$ necessarily $|\mathbb ...
0
votes
1answer
83 views

Linear programming with exponential inequalities and rational variables

If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...
2
votes
1answer
102 views

Constructivity of two problems on a standard simplex?

Maximizing a hyperplane $\sum_i a_ix_i$ where $a_i\in\mathbb R$ and each $a_i$ are fixed and non-negative and $x_i$ are variables over a standard simplex $\sum_i x_i\leq 1$ with $0\leq x_i$ always ...
42
votes
1answer
2k views

Who first characterized the real numbers as the unique complete ordered field?

Nearly every mathematician nowadays is familiar with the fact that there is up to isomorphism only one complete ordered field, the real numbers. Theorem. Any two complete ordered fields are ...
-2
votes
0answers
77 views

Is the following provable in Zermelo–Fraenkel Set Theory? [migrated]

Zermelo–Fraenkel Set Theory is a system of axioms for describing set theory. For example, Zermelo–Fraenkel Set Theory says things like: For any set $x$ and any set $y$ there exists a set $z$ such ...
4
votes
1answer
310 views

Formal proof of $ZFC \vdash CON(\ulcorner ZFC-P\urcorner)$

I am wondering that if one can show $ZFC \vdash CON(\ulcorner ZFC-P \urcorner)$. There is an argument in Set Theory, An Introduction to Independence Proofs by Kunen (page 145), but I am confused about ...
3
votes
1answer
140 views

Is every extension of ZFC interpretable in a finite extension of ZC + rank?

Let's speak of the theory $\sf ZC + rank$ as the first order set theory with axioms of Extensionality, Separation, infinity, and choice (written as usual), plus iterative powers and foundation, those ...
9
votes
1answer
206 views

Distributivity of ! over?

Has anyone studied a variant of linear logic, or of its semantic counterpart (exponential modalities on linearly distributive categories / $\ast$-autonomous categories / polycategories) for which ...
5
votes
3answers
475 views

Is the class of power-associative binars finitely axiomatizable?

A binar is simply a set $S$ equipped with a single binary operation $*$. A power-associative binar is a binar where the subalgebra generated by a single element is associative. Equivalently, they can ...
4
votes
0answers
207 views

Algebraic applications of an order-theoretic idiom of recursion

Many algebraic constructions must surely use the following observation, probably disguised as one of its proofs: Lemma Let $s:X\to X$ be an endofunction of a poset such that $X$ has a least element $...
1
vote
0answers
102 views

Completeness of certain formal deduction system

Consider a certain formal system with only axiom Excluded Middle -$EM$ and 18 inference rules: 9 implicative ruules (clearly not independent) and 9 tautological rules: If we have substitution at ...
0
votes
0answers
120 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 ...
2
votes
1answer
201 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 ...
4
votes
0answers
105 views

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

Julia Robinson proved that the family of all unary computable total functions is the smallest class containing $S$, $\mathrm{Exc}$, and closed under composition, addition and inversion of surjective ...
11
votes
0answers
195 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 ...
6
votes
0answers
134 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?
7
votes
0answers
186 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
1answer
243 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?
8
votes
0answers
121 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
239 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 \...
50
votes
5answers
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
201 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
343 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
375 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 ...
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
435 views

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
68 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 every ...
9
votes
1answer
375 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
94 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
170 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
90 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
300 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
311 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
216 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
433 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 $...
24
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
230 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
264 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 ...

1
2 3 4 5
73