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

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

1
vote
1answer
62 views

Reduction of the predicate calculus to the propositional calculus in the case of one sigle object in the universe?

To what extent is it possible to formally susbstantiate the following affirmation that: "In a classical first order logical universe with exactly one unique and single object, the predicate calculus ...
-1
votes
0answers
50 views

What’s the relation between definability of a class of structure and imcompleness of the axioms trying to capture such structure? [on hold]

Please help me with confusions of following terms: 1.Incompleteness 2.undefinable 3.non-standard model If a structure has non-standard counter part under a certain set of axioms, does that mean such ...
3
votes
0answers
91 views

If any satisfiable $\mathcal{L}_{κ,κ}(Q_{=κ})$-theory remains satisfiable when replacing $Q_{=κ}$ with $Q_{=μ}$, is $κ$ huge?

Recently, I have asked a model-theoretic question concerning a weakening of different forms of compactness. I now present another model-theoretic question as a weakening of hugeness. If any ...
3
votes
0answers
133 views
+200

Can we inductively define Wadge-well-foundedness?

For a topological space $X$ (which I'll identify with its underlying set of points), we define the Wadge preorder $Wadge(X)$: elements of the preorder are subsets of $X$, and the ordering is given by $...
0
votes
0answers
48 views

Functoriality of indiscernible sequences

Let $T$ be a first order theory of, say, some type of combinatorial geometries which contain indiscernible sequences of points. Let $(\Gamma,\mathcal{O})$ be a model of $T$, where $\Gamma$ is the ...
2
votes
0answers
60 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
221 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 ...
-5
votes
0answers
268 views

Is transcendental Goldbach Conjecture true of the real numbers?

Let $x0$ be the real number $Pi$, Consider the below sequence of real numbers: $s{0}$ = .1415926535897932384626433832795028841971... $s{1}$ = .415926535897932384626433832795028841971... $s{2}$ = ....
6
votes
3answers
751 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 ...
5
votes
1answer
222 views

Proof of ¬(¬⊤ ⊗ ¬⊤) 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 ...
10
votes
2answers
625 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
450 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
156 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
174 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
450 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})}$ ...
12
votes
0answers
262 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
146 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
147 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
195 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
110 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
347 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
74 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
259 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
298 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
138 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
269 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
254 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
370 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
58 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
66 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
61 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
119 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
129 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
272 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
51 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
152 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
262 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
223 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
210 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
84 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
387 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
208 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
178 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
875 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
316 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
367 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
497 views
+200

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