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)

1
vote
1answer
107 views

Notation: $Sigma$ and $Pi$ of intersections

In Jech - Set Theory, the proof of Theorem 31.7, I came along some notations I wish to understand correctly. For a countable elementary substructure $M \prec H_\lambda$ and $A \in M$ and a generic ...
2
votes
1answer
98 views

Precise interpretability strength of $\mathcal P_{DF}(\omega)$ and $L_{\omega_1^{CK}}$

I am curious about the relationship between the definable power set of $\omega$ and the $\omega_1^{CK}$th level of the constructible sets $L$. In short, $\omega_1^{CK}$ is the least nonrecursive ...
3
votes
0answers
149 views

On generic forcing conditions

Let $P$ be a forcing poset, and $Q \in V^P$ a forcing poset in $V^P$. Let $M \prec H(\lambda)$ ($\lambda$ sufficiently large) countable with $P,Q \in M$. What I want to know is if then the following ...
4
votes
1answer
272 views

What are key $\Sigma^0_2$ or $\Pi^0_3$ theorems?

I am researching a logical system that is limited to $\Pi^0_2$ sentences and I am busy to prove that FOL + PA is a conservative extension of that system. Meaning that with $\Sigma^0_n$ sentences (that ...
3
votes
0answers
84 views

Cardinality based results in Topological Vector Spaces?

Given a topological vector space $V$, let its density be the smallest cardinal $A$ such that a set of cardinality $A$ is dense in $V$. Naively, it seems one of two things happen: TVS's $V$ of ...
3
votes
1answer
167 views

May open sentences be eliminated?

Saul Kripke famously invoked a free logic to avoid validating the Barcan Formula and its converse. In that context he adduced a generality interpretation of free variables. The converse of the Barcan ...
3
votes
1answer
80 views

Understanding Corollary 3, Sec. 5.6, of Papadimitriou's Computational Complexity

I am struggling to understand Corollary 3 from Section 5.6 of Papadimitriou's Complexity Theory book (Addison-Wesley, 1993). It got me completely confused... If anyone out there has read it and ...
2
votes
0answers
113 views

RCS iteration such that the RCS limit is semi-proper

For a countable ordinal $\eta$ and an ordinal $\gamma$ let $\langle P_\alpha, \dot{Q}_\alpha \colon \alpha < \gamma \rangle$ be an RCS iteration with RCS limit $P_\gamma$, such that ...
5
votes
1answer
184 views

A question regarding strong cardinals and measure sequence

Let $E$ be a $(\kappa, \lambda)$-extender such that $j: V\to M\simeq Ult(V,E)$ is the corresponding elementary embedding with critical point $\kappa$, $M\supset V_{\kappa+2}$, $M^\kappa\subset M$. Let ...
5
votes
2answers
213 views

Is every non-empty $\Delta_0$ set provably the range of some primitive recursive function?

Suppose $A(x)$ is a $\Delta_0$ formula defining a non-empty set of natural numbers. It's an easy theorem that there is a primitive recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$ such that ...
4
votes
1answer
276 views

“set of all irreducible representations of a group”, set-theoretic issues [closed]

I am working on a problem related to representations of the Weil group of a local field $\mathcal{W}_F$. In many articles one introduces the set $\hat{\mathcal{W}}_F$ of all equivalence classes of ...
6
votes
0answers
203 views

A Banach-Tarski game

This is partially inspired by the question http://math.stackexchange.com/questions/1383397/cutting-a-banach-tarski-cake, which I find intriguing if unclearly written. A paradoxical family of subsets ...
3
votes
3answers
661 views

In which sense “closure” is a closure?

In predicate and first-order logic, if $\phi$ is a sentence, then $\forall X . \phi$ is said to be the (universal) closure of $\phi$. Is the use of the word "closure" incidental, or is there a ...
2
votes
0answers
114 views

How distributive are the bad Laver tables?

Suppose that $n\in\omega\setminus\{0\}$. Then define $(S_{n},*)$ to be the algebra where $S_{n}=\{1,...,n\}$ and $*$ is the unique operation on $S_{n}$ where $n*x=x$ $x*1=x+1\,\text{mod}\, n$ and if ...
6
votes
1answer
185 views

Reverse of a termspace forcing fact

Suppose $\kappa$ is an inaccessible cardinal. Consider the termspace forcing for adding a Cohen subset of $\kappa$ after $\mathbb P= Col(\omega,<\kappa)$. Members are Levy names for countable ...
1
vote
0answers
98 views

Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...
2
votes
1answer
151 views

A question on the name of a property

What is the name of the property that a system $T$ has if $\vdash_{T}\exists x F(x)$ only if there is a term $a$ so that $\vdash_{T} F(a)$? If I recall correctly Heyting Arithmetics has the ...
12
votes
1answer
581 views

Does “cardinal arithmetic is well-defined” imply axiom of choice?

Let me quickly explain what I mean with my question. Let $(\kappa_i)_{i\in I}$ be a collection of cardinal numbers, indexed by elements of some set $I$. We can try to define $\sum\limits_{i\in ...
3
votes
1answer
207 views

History of unstable formulas [closed]

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
176 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
248 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
161 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
404 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
173 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
241 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
552 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
186 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
97 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
118 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
374 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
80 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
279 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
2answers
374 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
230 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
205 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
133 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
94 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
400 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
831 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
181 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
73 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
264 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
171 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 ...
0
votes
0answers
302 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
262 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
105 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
75 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
155 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
88 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}$ ...