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)

7
votes
1answer
330 views

Is the axiom schema of replacement used in algebraic number theory (or more generally outside logic)

Here's a precise question. Does Wiles' proof of FLT run just fine in the set theory that logicians would perhaps call "Zermelo + choice" -- i.e. drop the axiom schema of replacement but assume the ...
2
votes
1answer
92 views

What are the adequacy conditions for Rosser Provability?

Famously, Rosser introduced a provability predicate $\pi[A]$ that holds iff $\exists x(xP[A]\wedge\forall y(y\le x\to\lnot yP[\lnot A]))$. Supposing $PA$ is consistent, what are the adequacy ...
6
votes
1answer
146 views

Different ways of making $HOD$ far from $V$

There are different criteria for building a model $V$ of $ZFC$ which is far from its $HOD$, for example: $(A)$ Cardinality criteria: For this in a joint work with James Cummings and Sy Friedman, we ...
8
votes
2answers
362 views

Some “axiom of choice” and “dependent choice” issues

I am probably about to ask some fairly basic questions, and yet I have found it quite hard to find the answers to these. If I understand correctly, mathematicians tend to be quite happy working with ...
21
votes
0answers
533 views

Relative null-ness

Here, "measure" always means Lebesgue measure on $\mathbb{R}$. This question is partly motivated by my answer ...
4
votes
1answer
120 views

Analogy of $\omega$-models in constructive mathematics

I apologize that this question is a bit vague, however that is partially the point. In subsystems of second order arithmetic, one considers $\omega$-models, these are models of $\mathsf{RCA}_0$ whose ...
2
votes
2answers
190 views

type theory that does not treat the terms of $\mathrm{Prop}$ as types

In type theory there is a type $\mathrm{Prop}$ that contains every proposition, so $p\colon\mathrm{Prop}$ (in words, "$p$ is of type $\mathrm{Prop}$") where $p$ is a proposition. In all type theories ...
1
vote
2answers
108 views

classical typed higher order logic natural deduction

Has somebody worked out a typed higher order logic? I mean something like type theory but not with this intuitionistic touch. Is there a natural deduction system for this logic?
8
votes
0answers
103 views

Two cardinal obstructions

Given a theory $T$ and a formula $\phi(x)$ we say that they admit a $(\kappa, \lambda)$ model if there is a model $M$ such that $|M| = \kappa$ and $|\phi(M)| = \lambda$. In all examples that I know ...
6
votes
0answers
240 views

The least admissible above a dominating real

Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, ...
11
votes
1answer
234 views

Partition relation at successor cardinal

Is it consistent that there are regular cardinals $\kappa < \lambda$, such that $\lambda$ is a successor cardinal and for every coloring $d\colon[\lambda]^2\to\kappa$ there is some ...
3
votes
1answer
130 views

Does totally proper forcing imply countable distributivity?

For a suitable model $M$ for $Q$ and a condition $q \in Q$ we say that $q$ is $(M,Q)$-generic if whenever $r \leqslant q$, $D \in M$ dense, $D \subset Q$, $r$ is compatible with an element of $D \cap ...
7
votes
1answer
209 views

Fuzzy logic of Godel

In Gödel logic, is conjunction definable from implication, negation , and disjunction? We know that conjunction in that logic is not definable from negation and implication.
6
votes
0answers
140 views

How “small” can an ordinal be made by forcing?

I know that forcing essentially does not change the ordinals, but by small I mean in comparison with other ordinals whose definition might not be stable under forcing, like the smallest uncountable ...
8
votes
0answers
215 views

On an unpublished result of Magidor

In 1970th, Magidor proved the following important results: (1) Assuming the existence of a supercompact cardinal, it is consistent that $\aleph_\omega$ is strong limit and ...
2
votes
1answer
178 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 ...
1
vote
2answers
141 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
1answer
249 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
320 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
98 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
194 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
104 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
127 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 ...
6
votes
2answers
245 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
289 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
298 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 ...
8
votes
0answers
267 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
694 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 ...
3
votes
0answers
146 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
194 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 ...
3
votes
0answers
105 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
196 views

A question on the name of a property

What is the name of the following property of a system $T$? If $\vdash_{T}\exists x F(x)$ then there is a term $a$ such that $\vdash_{T} F(a)$ If I recall correctly Heyting Arithmetics has ...
13
votes
1answer
661 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
236 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
193 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 ...
11
votes
1answer
262 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
181 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 ...
1
vote
0answers
30 views

Relation between indexed languages (OI-macro or context-free tree) and scattered context languages

I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by scattered context grammars--J Hopcroft). I think that ...
6
votes
2answers
419 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 ...
7
votes
0answers
182 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
287 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
597 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
250 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
115 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
140 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 ...
16
votes
1answer
486 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
91 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
321 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
397 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
250 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 ...