# Tagged Questions

**0**

votes

**0**answers

72 views

### Uncountable models of set theory [duplicate]

Assume we have a countable transitive model of set theory which satisfies some set of first-order axioms $T$.
Is it possible to get from this a model $\mathcal{M}$ of set theory which satisfies the ...

**4**

votes

**0**answers

198 views

### About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...

**3**

votes

**1**answer

95 views

### Soundness of modal logics which contain the reflection rule

Let $ML$ be a modal logic which contains the Reflection Rule (from $\vdash\Box F$ infer $\vdash F$). For a modal formula $F$, let $H(F)=\{\ \Box G\rightarrow G~|~\Box G$ is a subformula of $F\}$. A ...

**4**

votes

**1**answer

182 views

### Bad subforcings of nice forcing notions

Let $\mathbb{P}$ and $\mathbb{Q}$ be two forcing notions. Recall that we say $\mathbb{Q}$ is a subforcing of $\mathbb{P}$ if there exists a regular embedding $\mathbb{Q} \to \text{r.o.}(\mathbb{P}).$
...

**10**

votes

**1**answer

314 views

### V=HOD & The Height of the Large Cardinal Tree

As we know the assumption $V=L$ adds a restriction on the height of the large cardinal tree. Also there is a strict border like $0^{\sharp}$ exists such that all large cardinal axioms which are ...

**2**

votes

**1**answer

169 views

### Variable numerical quantifiers

I posted a similar question on math stack exchange with the same title, but I didn't get a helpful response. I am trying to develop a logical language where one can express variable numerical ...

**1**

vote

**1**answer

122 views

### Real closed fields in HOD

Let $\mathfrak{M}$ be a model of set theory, and consider HOD (the hereditarily ordinal definable elements) of $\mathfrak{M}$. Let $K$ be any algebraically closed field in HOD of zero characteristic ...

**6**

votes

**1**answer

361 views

### Is there a suitably generalized Baire property for topological spaces of arbitrary cardinalities?

Is there some suitable generalization to the notion of Baire property for topological spaces of arbitrary cardinalities which satisfies the following condition:
The meager sets are sets which are ...

**3**

votes

**1**answer

132 views

### Outer Definability of a Class

Definition: Let $C$ be a class of sets and $\mathcal{L}$ a first order relational language. We say $C$ is "outer definable" by $\mathcal{L}$ if there is a first order theory $T$ and for each $n_{R}$ - ...

**5**

votes

**2**answers

378 views

### Why is there no product type in simply typed lambda-calculus?

Consider simply typed $\lambda$-calculus that has only the unit type as primitive. We would like to encode the product and the sum types. An encoding of the product type in the untyped ...

**8**

votes

**1**answer

332 views

### Can there be only one (uncountable transitive model of ZFC)?

It is an immediate consequence of Cohen's forcing that if there is one countable transitive model of $\sf ZFC$, then there are many of them. Even if all of these models are of the same height, there ...

**3**

votes

**0**answers

184 views

### Binary search with maximum consecutive lies about “is X in subset S?”

Here's the original problem:
Alice tells Bob "I have thought of an integer between 1 and 2000. Tell
me 1000 numbers. If your set contains my number, I'll give you this
prize." Bob really wants ...

**1**

vote

**0**answers

142 views

### Has the Ramified Theory of Types been applied to Predicative Set Theories?

Questions of predicativity are well-studied in the context of arithmetic. We have a base theory, first-order Peano arithmetic. Some people, like Edward Nelson (in chapter 1 of his book) and Charles ...

**4**

votes

**2**answers

337 views

### Did Gödel prove that the Ramified Theory of Types collapses at $\omega_1$?

Second-Order Arithmetic is considered impredicative, because the comprehension scheme allows formulas with bound second-order variables that range over all sets of natural numbers, including the set ...

**5**

votes

**2**answers

395 views

### How complicated is the formula expressing that a set is non-measurable?

The question is exactly stated by the title, i.e. how complicated is the formula $\psi(x)$ (in the language of set theory) expressing that a given set of reals $x$ is non-measurable?
A second ...

**3**

votes

**1**answer

124 views

### The type of nondefinable elements-2

Consider a countable transitive model $\mathfrak{M}$ of set theory.
Let $X$ be a definable collection of sets of reals.
My question is: is the type of nondefinable elements in $X$ is definable over ...

**1**

vote

**2**answers

207 views

### Logic without disjunction

I'm working on a small proof system, which in principle only has equality as predicate. This equality has some axioms which make them sort of a structural equality: two terms are equal iff their ...

**6**

votes

**1**answer

184 views

### Generalizations of Birkhoff's HSP Theorem

Let $\mathbf{C}$ be the class of algebraic structures of some fixed type satisfying some sentence $\phi$. Birkhoff's HSP theorem says that $\mathbf{C}$ is closed under homomorphisms, subalgebras and ...

**2**

votes

**1**answer

211 views

### $(\kappa,\lambda)$ - Minimal Models & Stronger Version of Rowbottom's Theorem

Definition 1: Let $M$ be a $\mathcal{L}$ - structure and $A\subseteq Dom(M)$. Define:
$Def_{A}(M):=\{X\subseteq Dom(M)~|~\exists n\in \omega~~\exists \varphi (x,y_1,...,y_n)\in ...

**1**

vote

**1**answer

243 views

### $(\kappa , \lambda)$ - Minimal Models of $\text{ZF}$

The notion of minimality in model theory is related to the existence of a gap in the size of definable subsets of a model. Now consider the following generalization:
Definition 1: Let $M$ be a ...

**2**

votes

**1**answer

540 views

### Subsets of Real Numbers (Edited & Revised Version)

Question 1: Is it consistent with $\text{ZF}$ that only countable subsets of $\mathbb{R}$ are well-orderable?
Question 2: Is it consistent that for some $\lambda$, $\aleph_0 < \lambda < ...

**4**

votes

**1**answer

200 views

### Can the Burgess-Hazen analysis of Predicative Arithmetic be extended to Transfinite Types?

Around page 300 of his book "Mathematical Thought and its Objects", Charles Parsons discusses the work of Edward Nelson, who believes that mathematical induction is impredicative, because it can be ...

**1**

vote

**1**answer

98 views

### Is there a characterization of the topos of finite sets in the internal language?

The topos ${\mathcal{Set}}$, at least as axiomatized in ETCS, is a well-pointed topos that satisfies the axiom of choice and has a natural numbers object.
Is there a characterization of the topos ...

**4**

votes

**3**answers

318 views

### Minimal Generalized Continuum Hypothesis & Axiom of Choice

It is well known that working in the frame of $\text{ZF}$, the Generalized Continuum Hypothesis ($\text{GCH}$) implies the Axiom of Choice ($\text{AC}$), i.e. $\text{ZF}+\text{GCH}\vdash \text{AC}$.
...

**5**

votes

**2**answers

194 views

### When are all greater cardinals sharply greater?

Makkai and Paré introduced the following binary relation on regular cardinals: given $\kappa$ and $\lambda$, $\kappa \vartriangleleft \lambda$ (read, $\kappa$ is sharply less than $\lambda$) when ...

**0**

votes

**1**answer

642 views

### Is there any danger far from home? (Edited & Revised Version) [closed]

The notion of formal proof is defined by finite sequences ($<\omega$ - sequences) of sentences. In some sense if a sentence $\sigma$ is (finitely) provable from the theory $T$ it is very "near" to ...

**2**

votes

**1**answer

197 views

### From elementary equivalence to isomorphism

A few years ago, when I took the basic course in Logic, I was very surprised to discover that given a signature $\sigma$ and two structures $M$ and $N$ of $\sigma$ which are elementarily equivalent ...

**5**

votes

**1**answer

238 views

### Failure of Shoenfield's Absoluteness

Shoenfield's absoluteness states that if $M \subseteq N$ are models of $ZF$ and $M \supseteq \omega_1^N$, then every $\Sigma^1_2$ formula with parameters in $M$ is absolute between $M$ and $N$. In ...

**4**

votes

**2**answers

158 views

### On the number of models between a ground model and its forcing extension

Let $\kappa$ be a (finite or infinite) cardinal. Assuming consistency of $\text{ZFC}$ (and probabely some additional assumptions) is the following consistent with $\text{ZFC}$?
There is a countable ...

**4**

votes

**1**answer

147 views

### Discontinuous representations of GL(n,C) in ZF

Discontinuous linear representations of $GL(n,\mathbb{C})$ can be obtained from the so-called "wild" (field) automorphisms of $\mathbb{C}$; but these wild automorphisms in turn require some choice to ...

**1**

vote

**1**answer

186 views

### An informal version of the recursion theorem

In T. Taos Analysis 1 book, on page 26, we have a proposition that tells us that recursive definitions are actually well-defined.
Proposition 2.1.16: Suppose for each naturla number $n$, wh have ...

**2**

votes

**0**answers

78 views

### How are measurable functions morphisms?

I am trying to encode the theory of measurable sets in higher order logic. I already did so with the theory of topology. I think it is relevant because it enables one to see continuous or measurable ...

**8**

votes

**1**answer

391 views

### Well founded induction attributed to Noether

What I know as well founded induction, namely the rule
$$ \big(\forall y.(\forall z.z\lt y\Rightarrow\phi z)\Rightarrow\phi y\big)\Longrightarrow\big(\forall x.\phi x\big), $$
whose validity is the ...

**6**

votes

**0**answers

85 views

### What classes of complex manifolds are known to be definable in an o-minimal expansion of the real field?

It is a widely known (perhaps slightly folkloric) fact that compact complex manifolds, understood as first-order structures with a predicate for each analytic subset, are definable in an expansion of ...

**9**

votes

**2**answers

311 views

### Is equivalence of functions built from nested exponentiations a decidable problem?

Let $\mathcal{E}$ be the minimal set of symbolic expressions (without any predefined meaning) such that
The symbol $x$ is in $\mathcal{E}$, and
If expressions $P,Q\in\mathcal{E}$, then the ...

**9**

votes

**0**answers

190 views

### Are there trees for $(\Sigma^2_1)^{\text{uB}}$?

If there is a proper class of Woodin cardinals, then Woodin showed (using stationary towers) that $(\Sigma^2_1)^{\text{uB}}$ statements are generically absolute, where $\text{uB}$ denotes the ...

**7**

votes

**1**answer

191 views

### A special c.c.c forcing notion and adding minimal generic reals

This question is related to my question "Forcing with c.c.c forcing notions, Cohen reals and Random reals".
A natural way to answer Prikry's conjecture is to build a c.c.c. forcing notion which adds ...

**7**

votes

**1**answer

262 views

### Is definability of a basis for $\mathbb{R^N}$ independent of ZFC?

By $\mathbb{R^N}$ I mean the real vector space with the natural componentwise addition and scalar multiplication. Certainly ZFC+(V=L) gives definable bases, but does ZFC?

**8**

votes

**1**answer

340 views

### Shelah's book on “Classification Theory”

As we know one of the most important and fundamental books in stability, simplicity, forking and ... classification theory, is Shelah's "Classification Theory" where lots of original ideas of the ...

**16**

votes

**2**answers

699 views

### An order type $\tau$ equal to its power $\tau^n, n>2$

(This is a re-post of my old unanswered question from Math.SE)
For purposes of this question, let's concern ourselves only with linear (but not necessarily well-founded) order types.
Recall that:
...

**17**

votes

**2**answers

759 views

### Deep theorems and long proofs

I ran across this discussion by Daniel Shanks,
"Is the quadratic reciprocity law a deep theorem?."
Solved and Unsolved Problems in Number Theory. Vol. 297. AMS, 2001. p.64ff.
which made me ...

**8**

votes

**2**answers

397 views

### Is the tree of large cardinals linear?

Kanamori in the introduction of his book "The Higher Infinite" says:
"The investigation of large cardinal hypotheses is indeed a mainstream of modern set theory, and they have been found to play a ...

**5**

votes

**1**answer

174 views

### Computing $L$-rank (constructible universe)

I posted this question on Math StackExchange but did not get a full answer. I hope it's not a problem if I ask again here.
Is there a way to compute explicitly the $L$−rank $\rho(\bigcup x)$ of ...

**1**

vote

**1**answer

165 views

### The type of nondefinable elements

Consider a countable transitive model of ZFC $\mathfrak{M}$.
Let $X$ in $\mathfrak{M}$ be some definable set.
Can we define the "type" $p$ of nondefinable elements of $X$? (By type I mean the set of ...

**2**

votes

**1**answer

149 views

### Meaning of notation $\mathbb{Q}^\wedge k$, $-\infty^\wedge \mathbb{Q}$ for linear orders

I am reading Friedman & Stanley A Borel reducibility theory for classes of countable structures (J. Symbolic Logic 54 (1989), 894–914; MR1011177) and a caret (${}^\wedge$) appears as notation in ...

**2**

votes

**1**answer

190 views

### Forcing Language

I asked the following question (slightly paraphrased) about a week ago in Stack exchange but no one knew the answer to the particular question. I was hoping someone here might be able to help me.
...

**14**

votes

**4**answers

1k views

### A New Continuum Hypothesis (Revised Version)

Define $N_n$ as $n$ th natural number: $N_0=0, N_1=1, N_2=2, ...$.
What happens after exponentiation?
We have the following equation: $2^{N_n}=N_{2^{n}}$.
(Which says: For all finite cardinal $n$ ...

**5**

votes

**1**answer

193 views

### $\Sigma_1$ Statements and Forcing Extensions

Assuming consistency of $\text{ZFC}$ (with some large cardinal axiom), is the following statement consistent with $\text{ZFC}$?
Any $\Sigma_1$ statement with parameters $\omega_1,\omega_2$ which ...

**5**

votes

**1**answer

386 views

### Original proof of Gödel's completeness theorem compared to Henkin's proof

May I have some clarification about original proof of Gödel's Completeness Theorem compared to "standard" Henkin's proof based on Model Existence Lemma ?
My understanding of Gödel's original proof is ...

**6**

votes

**4**answers

1k views

### Interactions of number theoretic conjectures and other fields of mathematics

There are many interesting open conjectures in number theory. My question is not about partial results or possible ways to prove them. It is about their interactions with the other fields of ...