# 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.

3,219 questions
94 views

### Lengths of proofs and quasilinear time

Length of proofs depends not only on the theory but also on its axiomatization. Once an axiomatization is fixed, typical proof systems are equivalent up to a polynomial factor. But what if we care ...
336 views

### What are the difficulties involved in proving that the Kunen inconsistency holds in $NGB$

or (contrariwise) that $NGB$ + "There exists a Reinhardt cardinal" is consistent? The question is partially in the title. $NGB$ is used for the reasons stated in the Hamkins, Kirmayer, and ...
824 views

### Are there logical systems where formal proofs are not computer verifiable?

In a set-theoretic system using first-order logic, every proof could be written as a goal followed by a finite sequence of sentence where each one is justified by an axiom or previously established ...
307 views

### Proof of ¬(¬1 ⊗ ¬1) in tensorial logic

I believe I once had a proof of this proposition, but it's been lost to the mists of time and old hard drives, so who knows if it was correct, and try as I might I can't seem to reproduce it. Is it ...
671 views

### Is being close to a Halting set computable?

Let $\Phi$ be a universal Turing machine and let $S$ be the set on which it halts. I’m curious about if its decidable to check if a number is close to $S$. There are two notions of distance that come ...
458 views

473 views

### “Antiforcing” - Is there a method to 'remove' sets from a model of ZF?

Forcing is a method of "adding sets" to a model $M$ of ZF by making a new set $M^{(\mathbb{P})}$ consisting of every set of $M$, but you have the option to add certain sets out of $M^{(\mathbb{P})}$ ...
289 views

156 views

305 views

### Buying more absoluteness for countable transitive models?

Let $M$ be a countable transitive model of (enough of) ZFC. Mostowski's Absoluteness Theorem says that $\Pi^1_1$ statements are absolute between $M$ and larger models, in particular, between $M$ and ...
142 views

### How much can complexities of bases of a “simple” space vary?

Given a countable subbase of a topology, we can consider its complexity in terms of the difficulty of determining whether one family of basic open sets covers another basic open set. My question is ...
274 views

### Vopenka's principle is equivalent to the existence of a strong compactness cardinal for any “logic”?

According to Cantor's attic, Vopenka's principle is equivalent to the existence of a strong compactness cardinal for any "logic". But I can't find a definition of what a "logic" is either there or in ...
269 views

### Stationarity and Fodor's lemma for a (nice) poset?

The notion of a stationary set is peculiar in that it applies to subsets of certain very particular posets -- ordinals or powersets. At least to a non-set-theorist, the situation seems to beg for the ...
413 views

### Going beyond the strength of Peano arithmetic “without sets”

First-order arithmetic is fairly weak, as measured for example by its consistency strength. When a stronger theory is desired, it is common to work with (fragments of) second-order arithmetic or set ...
76 views

### Reasonable reference index or list of the interpretability/consistency hierarchy

In Kanamori's The Higher Infinite a diagram is included towards the end of the book which illustrates the large cardinal hierarchy by listing many large cardinal axioms and drawing their direction ...
68 views

139 views

### Can cardinality be defined with essentially no practical restriction on non-well-ordered combinatorics or ill-foundedness of sets?

Question: Can we have a model of $ZF-\text {Regularity}$ where there exist an ordinal $\kappa$ such that $H_{\kappa}$ exists and $H_{\kappa}$ is not equinumerous to any well founded set? The ...
319 views

### Is the smallest $L_\alpha$ with undefinable ordinals always countable?

Let $\mathfrak{t}$ be the least ordinal such that $L_{\mathfrak{t}}$ has undefinable ordinals; i.e. there is an $\alpha<\mathfrak{t}$ such that $L_{\mathfrak{t}}$ cannot define $\alpha$. This ...