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)

0
votes
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
362 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
1answer
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
2answers
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
1answer
333 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
0answers
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
0answers
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
2answers
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
201 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
1answer
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
3answers
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
2answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
341 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
2answers
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
2answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
191 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
4answers
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
1answer
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
1answer
387 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
4answers
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 ...