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

learn more… | top users | synonyms (1)

2
votes
1answer
135 views

History of unstable formulas [on hold]

There are many equivalent definitions for stability, one of them being that being unstable is equivalent to the existence of a formula having the order property. While intuitively it makes sense that ...
7
votes
1answer
120 views

Consistency strength of being strong cardinal and indestructible under collapses

What is the consistency strength of the following statement: $\kappa$ is a strong cardinals and it is indestructible under $Col(\kappa, <\theta),$ where $\theta> \kappa$ is some fixed ...
10
votes
1answer
181 views

Does stationary reflection imply Mahloness?

Suppose $\kappa$ is strongly inaccessible and every stationary subset of $\kappa$ reflects. Must $\kappa$ be Mahlo? Remarks: It is possible for every stationary subset of $\kappa$ to reflect, but ...
4
votes
1answer
125 views

Can we always add sets without collapsing cardinals or adding [very] bounded sets?

Given a model of $\sf ZFC$, and an infinite ordinal $\alpha$. Can we prove that there is always a cardinal $\kappa$, and a forcing $\Bbb P$, such that: $\Bbb P$ does not add sets of rank ...
6
votes
2answers
371 views

Collapsing the cardinals between two singular cardinals

Question 1: Is it consistent that there is a forcing notion collapsing $\aleph_{\omega\cdot 2}$ to $\aleph_\omega$ without collapsing $\aleph_\omega$ or $\aleph_{\omega\cdot 2 + 1}$? If the ...
6
votes
0answers
156 views

$\alpha$-minimal degrees for singular $\alpha$

An important question in $\alpha$-recursion theory is whether there is a minimal $\alpha$-degree at $\alpha=\aleph_\omega.$ Question 1. Who first introduced the above question, and where can I find ...
-1
votes
3answers
220 views

A question about sentences undecidable in Peano's Arithmetic

Many examples are now known of sentences undecidable in Peano's Arithmetic (PA) assuming that PA is consistent. Are some or all of these sentences also undecidable in Second Order Arithmetic (SOA) if ...
9
votes
1answer
511 views

Are there discontinuities in the large cardinal hierarchy?

Suppose that $\Phi(x,y)$ is a formula in the language of set theory so that for each natural number $n$, the axiom $\exists x\Phi(n,x)$ is a large cardinal axiom (for example consider $n$-huge ...
3
votes
1answer
163 views

Löwenheim-Skolem for many-sorted theories

Let $L$ be a many-sorted first order language, and let $\kappa$ be an infinite cardinal which is greater than or equal to the number of function and relation symbols in $L$. Let $T$ be a complete ...
2
votes
1answer
95 views

Classification of commutative ring ideal closure operators?

First, some setup: So: given a commutative ring $R$, let $Ideals(R)$ be set of ideals of $R$ and let $IdealClosure(R)$ be the set of closure operations $cl: \mathcal{P}(R) \rightarrow Ideals(R)$. In ...
0
votes
0answers
110 views

Minimum regular open set containing a given set in a T0 Alexandrov topological space

What is known about the minimum regular open set containing a given set in a T$_0$ Alexandrov topological space? I'm particularly interested in the condition for the minimum set happening to be ...
15
votes
0answers
356 views

What sort of cardinal number is the Löwenheim-Skolem number for second-order logic?

In their paper "On Löwenheim-Skolem-Tarski numbers for extensions of first order logic", Magidor and Väänänen make the following statement: "For second order logic, $LS(L^{2})$ ...
0
votes
0answers
76 views

A question on two modal formulas

I want to find out the correspondences for the following two formulas or whether they are already derivable in the modal logic $KD4.2$, i.e. whether the formulas are valid in serial, transitive and ...
7
votes
1answer
266 views

A question related to Woodin's $HOD$ conjecture

Recall that an $\kappa$ is $\omega$-strongly measurable in $\text{HOD}$ if there exists $\lambda < \kappa$ such that $(2^{\lambda})^{\text{HOD}} < \kappa$ and such that there is no partition of ...
10
votes
1answer
308 views

Constructing an $\omega_1$-sequence of functions that almost extend all previous functions

I want to construct a sequence of functions $$f_\alpha: \alpha \rightarrow \omega,\ \alpha < \omega_1$$ such that for all $\alpha < \omega_1$ the following holds: $f_\alpha$ is injective. ...
5
votes
0answers
214 views

Proving that a subgroup is normal

This question is partly inspired by the recent question on measurability and the axiom of choice. Suppose I come up with a way to define a subgroup of a group, in a way that involves "no arbitrary ...
0
votes
2answers
198 views

Propositional logic without negation

As part of a bigger project I am researching a propositional logic, without a negation. And I would like to know, whether this already exists, to avoid double work and have proper references. In this ...
1
vote
0answers
119 views

A question regarding extendible cardinals and a result of M. Magidor

The following definitions and Theorems come from M. Magidor's paper "On the Role of Supercompact and Extendible Cardinals in Logic" (Israel J. Math., Vol. 10, 1971): "Definition: Logic is called ...
-1
votes
1answer
92 views

recursively enumerable sets [closed]

A set $S$ said to be recursively enumerable if There is an algorithm that enumerates the members of $S$. That means that its output is simply a list of the members of $S$: $s_1$, $s_2$, $s_3$, ... . ...
7
votes
1answer
389 views

Why is the set-theoretic principle $\diamondsuit$ called $\diamondsuit$?

A shallow answer would just point to theorem 6.2 in Jensen's 1972 paper "The fine structure of the constructible hierarchy", where Jensen introduces this property. Or was this symbol used already ...
17
votes
1answer
811 views

the true reason of the incompleteness of formal systems

A 3/4 year ago, I read Gödel's beautiful paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme 1". There is one thing, I never understood. In a footnote, Gödel ...
2
votes
1answer
163 views

Classification Theory

It is often said that unsuperstable theories do not admit a classification in the sense of Shelah. Why exactly is this so? And also what exactly does in the sense of Shelah mean? It is hand waved in a ...
-2
votes
1answer
69 views

Reconciling undecidability of FOL with Soundness and Completeness of Hilbert Proof Systems [closed]

I am reading Logic and Declarative Languages by Michael Downward, where he describes Hilbert's Proof System for First Order Logic and states that it is both sound and complete, he then adds that: ...
5
votes
1answer
259 views

Diagonalizing against a non stationary set of functions

Suppose $\kappa$ is regular uncountable (assume $2^{< \kappa} = \kappa$ and $\kappa$ is weakly Mahlo if needed). Is the following true? For every sequence $\langle f_i: i \to 2 \mid i \in A ...
3
votes
1answer
165 views

Number of non-isomorphic models

I had this question up on Math stackexchange: http://math.stackexchange.com/questions/1349247/number-of-non-isomorphic-models/1350763#1350763 . While it was answered partially there, I'm posting here ...
-1
votes
0answers
21 views

Freedom of speech in scientific discussions - An invitation to more tolerance in Scientific debates [migrated]

I hope this post enjoys some tolerance, and don't get closed or put on hold immediately. I believe that freedom of speech in scientific discussions is one of the key values which enriches the debates ...
0
votes
0answers
296 views

Set as a (strict) infinite-category?

First, let me say that I have no idea if such a post has its place here. However, I believe that the ideas I'm going to present are important. The goal of this thread is three fold: 1) trying to ...
8
votes
0answers
254 views

preserving saturated ideals

A reliable source made the following claim: Suppose CH there is an $\omega_2$-saturated ideal on $\omega_1$. Then this is preserved by $\mathrm{Add}(\omega_1,\omega_2)$. Question 1: How do you ...
29
votes
3answers
2k views

What is the reverse mathematical strength of the fundamental theorem of algebra?

Reverse mathematics (RM) is that area that tries to pin down exactly which axioms are necessary to prove theorems, given some weak base theory. Harvey Friedman has pointed out several times (on the ...
5
votes
1answer
100 views

On an automatic translation of typed lambda calculus in untyped lambda calculus

I have a question regarding the "compilation" of typed lambda calculus in untyped lambda calculus. Take for example the inductive definition of lists, with introduction rules: and: We can ...
1
vote
0answers
67 views

Type theory: can multiple elimination rules be defined, in principle?

I'd like to ask a question on type theory: Consider the usual type theoretical definition of the natural numbers. We could give an elimination rule in the form: or in the form: I called the ...
2
votes
2answers
153 views

Pseudo-decision procedures for first order arithmetic

I was reading this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.2911&rep=rep1&type=pdf in which the author describes an algorithm, based on Groebner basis, ...
5
votes
0answers
83 views

Lascar strong types in fragments of arithmetic

Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.) Definition Given a saturated model ${\cal M}$ ...
4
votes
2answers
766 views

What lets the Square of Opposition fail in Intuitionistic Logic?

See moderator's note in the comments. I just came across the following. In intuitionistic logic and classical logic we have the following consequences: ...
7
votes
1answer
233 views

Countable group with uncountable number of subgroups $< 2^{\aleph_0}$

Is it consistent that there is a countable group $G$ such that the cardinality of the set of subgroups of $G$ is uncountable, but strictly less than $2^{\aleph_0}$?
10
votes
0answers
175 views

Generic $\mathbf{\Sigma}_3^1$-absoluteness for class forcings

In the paper "Generic Absoluteness" by Bagaria and Friedman (http://www.logic.univie.ac.at/~sdf/papers/bagfried.pdf) it is shown that in ZFC generic $\mathbf{\Sigma_3^1}$-absoluteness is false for ...
7
votes
2answers
285 views

Topological tameness beyond the Gandy-Harrington topology

The Gandy-Harrington topology on $\omega^\omega$ is the topology generated by all lightface $\Sigma^1_1$ sets; that is, all sets which are continuous-in-the-usual-sense images of $\omega^\omega$. ...
-1
votes
1answer
104 views

Non-standard naturals and goodstein sequences [closed]

By the Kirby–Paris theorem, Goodstein's theorem is independent of Peano arithmetic (PA). Therefore there are non-standard models in which every Goodstein sequence terminates. However, Tennenbaum's ...
9
votes
1answer
379 views

Just a little absoluteness might be cheaper?

Absoluteness is a wonderful thing, but expensive consistency-strength wise. My question is, when can we get large amounts of absoluteness in specific situations for much cheaper? Specifically, fix a ...
8
votes
1answer
186 views

Is the Jordan decomposition of a self-adjoint functional constructive?

Let $A$ be an abstract C*-algebra, and let $\varphi\colon A \rightarrow \mathbb C$ be a bounded linear function. Assuming the axiom of choice, there exist unique positive bounded linear functions ...
9
votes
0answers
181 views

The Chang model after collapsing an inaccessible limit of Woodins

If $\kappa$ is an inaccessible cardinal and $G \subset \operatorname{Col}(\omega,\mathord{<}\kappa)$ is a $V$-generic filter, then in $V[G]$ the Chang model $L(\text{Ord}^\omega)$ satisfies "every ...
18
votes
3answers
2k views

Who needs Replacement anyway?

The set theory ETCS famously comes without the Replacement axiom schema (or an equivalent) that is part of ZFC. One (to me, not apparently useful) set that one cannot build in ETCS is $\coprod_{n\in ...
4
votes
0answers
175 views

Primitive Closure Arithmetic

I am researching a system that was designed by myself and what I call PCA (Primitive Closure Arithmetic), because it looks like PRA. The differences are: - PRA uses recursive definition with a ...
0
votes
1answer
157 views

Definition of “Expected/Unexpected Event”

Background of my question is Martin Gardner's "unexpected hanging" paradoxon, which has once again be the subject of an article in a popular-scientific magazin (this time because this year it has been ...
11
votes
0answers
192 views

Adding a saturated ideal

Is it consistent that there is no $\omega_2$-saturated ideal on $\omega_1$, but one is introduced by an $\omega_2$-closed forcing?
10
votes
0answers
225 views

c.c.c forcing notions and adding minimal generic reals

Is the following statement consistent: ``There is no non-trivial c.c.c forcing notion adding a minimal generic real''? The question is related to Prikry's question: Is it consistent that any ...
7
votes
1answer
247 views

For a ring $k$ and a set $X$, what are the $k$-algebra homomorphisms $k^X \to k$?

Let $k$ be a commutative ring. Feel free to assume it's a field. Let $X$ be a set. This question is only interesting when $X$ is infinite. Write $k^X$ for the $k$-algebra of functions $X \to k$, ...
11
votes
3answers
508 views

The size of Lindelof space

Question. Suppose that $X$ is a Lindelof space such that every point of $X$ is a $G_{\delta}$-point. Then is it true that $|X| ≤ 2^{\omega}$?
9
votes
1answer
387 views

Is $\clubsuit_{\omega_1}$ enough to get Suslin tree?

This is problem 15.3 in Arnie Miller's problem list: (Juhasz) Suppose there exists $\langle A_{\alpha} : \alpha \in L \rangle$, where $L$ is the set of limit ordinals below $\omega_1$ and for each ...
2
votes
0answers
83 views

BL Algebras that allow for Compactness to hold

Say we have a model $M$ of a theory $T$ of some core fuzzy logic. When dealing with compactness, we run in to a situation where the new model being built (by the use of compactness over $M$), will ...