Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
0answers
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 ...
0
votes
1answer
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 ...
6
votes
3answers
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 ...
6
votes
1answer
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 ...
11
votes
2answers
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 ...
2
votes
1answer
458 views

Is there anything against this function j being injective?

Language (first order logic with equality "$=$" and membership "$\in$", and constant symbol "$j$") Axiom: ID axioms + There exists a set $A$, such that: Field: $\forall x \in j \ \exists a \in A \ \...
5
votes
1answer
168 views

Random reals preserving Cohen reals

Suppose we have a model (of $\mathsf{ZFC}$) $M$, and that $x\in 2^\omega$ is random over $M$, and that $y\in 2^{\omega}$ is Cohen over $M$. My question is whether $y$ is also Cohen over $M[x]$. In ...
2
votes
1answer
185 views

A variant of Radin forcing

Suppose $\kappa$ is a large cardinal (strong cardinal seems to be enough). Is there a forcing notion $\mathbb{R}$ with the following properties: $(1)$ Forcing with $\mathbb{R}$ adds a club $C$ into $\...
3
votes
0answers
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})}$ ...
13
votes
0answers
289 views

Cardinality vs. isomorphism type of vector spaces without choice

One of the classical uses of the existence of bases of vector spaces (which is equivalent to the axiom of choice) is the following theorem: If $V$ is an infinite vector space over a field $F$, and $...
5
votes
0answers
155 views

Decomposition of forcing iterations

One of the great things about a finite support iteration $\Bbb P_\delta$, is that if $\alpha<\delta$, we can write $\Bbb P_\delta$ as the iteration of $\Bbb{P_\alpha\ast\dot Q_\alpha\ast P_\delta/...
4
votes
1answer
156 views

Embedding ordinals with the order topology into connected $T_2$-spaces

Is there a limit ordinal $\kappa_0$ with $\kappa_0 \lt 2^{\aleph_0}$ and such that for every limit ordinal $\lambda$ with $\kappa_0\leq \lambda\lt 2^{\aleph_0}$ there is a connected $T_2$-space $X_\...
5
votes
0answers
197 views

Bad forcing permutations

Let $P$ be the finite-support product of the Cohen forcing. It adjoins a sequence of Cohen-generic reals say $a_n$, $n<\omega$, which one naturally calls a $P$-generic sequence. Suppose that $\pi$ ...
5
votes
0answers
117 views

Self-additive posets

We say that a partially ordered set $(P,<)$ is self-additive if the two natural embeddings of $P$ in $P\oplus P$ (the linear sum of $P$ and itself) are elementary. We have the following. ...
16
votes
1answer
371 views

What non-standard model of arithmetic does Hofstadter reference in GEB?

Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...
0
votes
0answers
73 views

Would Singletons+ Boolean union+ Relative complements+ Composition terminate over sets $N, P(N), P(P(N))$?

The following question is related to question asked at How to decide if a recursive addition of subsets after certain formula would terminate? But here it will be asked about a specific situation. ...
2
votes
0answers
81 views

Relation of $\omega_{\omega_1+1}^{CK}$ to some other ordinals

This was posted as a side question in Formal definition of this ordinal?. Splitting this as a separate question based upon suggestion in comments. Here is the statement of question. If we consider an ...
2
votes
1answer
277 views

Formal definition of this ordinal?

Few days I asked this question (https://math.stackexchange.com/questions/2907733/simple-ordinal-question) on MSE. Summary of the question is that I defined a certain function over ordinals $x \mapsto \...
5
votes
1answer
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 ...
7
votes
0answers
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 ...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
2
votes
0answers
68 views

How to decide if a recursive addition of subsets after certain formula would terminate?

Lets call a definable property $\phi(y,z_1,..,z_n)$ as terminating over a set $A$ if and only if recursive successive additions of every set $\{y \in A| \phi(y,z_1,..,z_n)\}$ from parameters $z_1,..,...
1
vote
0answers
64 views

Looking for help in defining a new epistemic logic

I'm looking for some guidance in defining a new epistemic, temporal logic. I am looking to extend a logic called Sequential Epistemic Logic (SPAL): https://pdfs.semanticscholar.org/dae6/...
1
vote
0answers
129 views

Proof of the Specker-Blatter theorem

The theorem in the title states the following: If $\mathcal{C}$ is a class of structures definable in monadic second order logic with unary and binary relation symbols only, then the function $f_\...
0
votes
1answer
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 ...
7
votes
1answer
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 ...
0
votes
1answer
58 views

Probabilistic generalization of trial-and-error predicates

The notion of a limiting recursive set (Gold 1965, J. Symb. Log. 30: 28–48) or trial and error predicate (Putnam 1965, J. Symb. Log. 30: 49–57) is defined as follows. A guessing function is a total ...
3
votes
1answer
162 views

Strong partition property + DC + existence of non-principal ultrafilter on $\omega$

It was mentioned after Theorem 30.27 in Kanamori's Higher Infinite that Woodin constructed a model of $DC$ + there exists unboundedly many many $\kappa<\Theta$ such that $\kappa \to (\kappa)^\...
9
votes
1answer
273 views

What is the consistency strength of weak Vopenka's principle?

Weak Vopěnka's principle says that the opposite of the category of ordinals cannot be fully embedded in any locally presentable category. Recall that one form of Vopěnka's principle says that the ...
0
votes
0answers
237 views

Consistency of Nontrivial Elementary Embedding from $\omega_1$ to itself?

I was wondering about a way to make really large countable ordinals. It turns out that in certain models of ZFC (for example pointwise definable ones) every ordinal is definable with no parameters, ...
5
votes
2answers
230 views

Complete atomless Boolean algebras with abelian automorphism group

Is there any example of a complete atomless Boolean algebra with a non-trivial abelian automorphism group? This is equivalent, by Stone duality, to asking for an extremally disconnected compact ...
3
votes
1answer
92 views

Internal equality for Eq-fibrations' morphisms

I have posted this question here on M.SE but since it received little attention and since it seems difficult to find helpfule references I reposting it here. In Jacob's Categorical logic and Type ...
3
votes
2answers
399 views

What fragments of ZF are consistent with a set being equal in size to its power set?

What examples of fragments of ZF are consistent with: $$\exists x \exists f\, (f\colon x \to P(x) \wedge f \text{ is bijective})$$ and are not too weak, ideally with at least the consistency strength ...
0
votes
1answer
214 views

Is it consistent with Z - Regularity to have a set that is bigger than any set in the cumulative hierarchy of Z?

Edit: the question was answered to the negative because $ZF$ proves the existence of Hartog numbers. So this calls for a modification of the question to be in just $Z-\text{Regularity}$ Is it ...
5
votes
0answers
189 views

Examples in which probabilistic heuristic reasoning fails

There are examples of conjectures in which one can use probabilistic heuristic reasoning to show that they are very likely to be true. For instance, Freeman Dyson used probabilistic heuristic ...
9
votes
2answers
903 views

Examples of set theory problems which are solved using methods outside of logic

The question is essentially the one in the title. Question. What are some examples of (major) problems in set theory which are solved using techniques outside of mathematical logic?
13
votes
1answer
326 views

Does this consequence of measurability in terms of games of length $\omega+1$ imply measurability?

For any two structures $\mathcal{M}$ and $\mathcal{N}$ in the same first-order language $\mathcal{L}$ and any ordinal $\theta$, let $G_\theta(\mathcal{M},\mathcal{N})$ be the two-player game of ...
10
votes
0answers
377 views

On the Number of Parallel Automorphism Lines

Given a group $G$, one can define the transfinite line of iterative automorphisms of $G$ to be the following chain of the groups where $G_{\alpha+1}=Aut(G_{\alpha})$ for each ordinal $\alpha$ and the ...
34
votes
7answers
3k views

Paradoxical Mathematical Objects Pending for Construction [duplicate]

The possible properties and applications of some mathematical objects have been described far before their rigorous mathematical definition. Some of them even had a seemingly paradoxical description ...
8
votes
1answer
691 views

Interpreting a space in Baire space: how many facts do I need to understand the whole thing?

Below I'm working in ZF+DC+AD or similar; I want enough choice that things don't explode, but I also want the Wadge hierarchy to be well-behaved everywhere. Since this question is a bit long, I've put ...
2
votes
1answer
144 views

Is any real closed extension of $\mathbb R$ characterized up to isomorphism by its ladder?

Let $R$ be a real closed field. Recall that the ladder of $R$ is the divisible, ordered abelian group obtained by quotienting $R$ by a certain equivalence relation. Note that $R$ has trivial ladder ...
4
votes
2answers
187 views

Strongly reducible but not effectively interpretable

A countable structure A is strongly reducible to a structure B if there is a uniform turing functional which, given a copy of the atomic diagram of B, computes a copy of the atomic diagram of A. A is ...
8
votes
4answers
769 views

Formalizations of the idea that something is a function of something else?

I'll state my questions upfront and attempt to motivate/explain them afterwards. Q1: Is there a direct way of expressing the relation "$y$ is a function of $x$" inside set theory? More ...
18
votes
1answer
262 views

Proof as a Σ₁ approximation to truth: what about higher degrees?

Let us posit that the goal of mathematics is to study mathematical truths, and let us stick to arithmetic for simplicity: so let $\mathscr{T} \subseteq \mathbb{N}$ be the set of (Gödel codes of) true ...
11
votes
1answer
363 views

Fixed points of injective self-maps

Is it consistent in $\mathsf{ZF}$ that there is a set $X$ with more than $1$ point such that every injective map $f:X\to X$ has a fixed point?
31
votes
1answer
946 views

Is this conjecture strictly weaker than P=NP?

My three computability questions are related to the following group theory question (first asked by Bridson in 1996): For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn ...
3
votes
2answers
164 views

Time functions of non-deterministic Turing machines (a better question)

This is a more precise version of that question. Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation ...