Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [logic]

Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).

37
votes
0answers
946 views

complete, finitely axiomatizable, theory with 3 countable models

Does it exist a complete, finitely axiomatizable, first-order theory $T$ with exactly 3 countable non-isomorphic models? A few relevant comments: There is a classical example of a complete theory ...
29
votes
0answers
350 views

Positive set theory, antifoundation, and the “co-Russell set”

Tl;dr version: are there "reasonable" theories which prove/disprove "the set of all sets containing themselves, contains itself"? Inspired by this question, I'd like to ask a question which has been ...
19
votes
0answers
229 views

Does “every” first-order theory have a finitely axiomatizable conservative extension?

I've now asked this question on mathoverflow here. There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. However $\sf NBG$ ...
17
votes
0answers
399 views

What kind of compactness does “expanding $\mathbb{R}$ by constants” have?

EDIT: Now crossposted at mathoverflow. This arose from my answer to another question. Say that a theory $T$ in the language of ordered fields + constants is $\mathbb{R}$-satisfiable if it has a model ...
16
votes
0answers
502 views

Spanning the reals with a small set - choicelessly

Working in ZF (so, no choice): is it possible that there is a set of reals $X$ such that $\vert X\vert<\mathbb{R}$, but $X$ generates $\mathbb{R}$ as a subgroup under addition? This seems weird, ...
16
votes
0answers
641 views

Non-axiomatisability and ultraproducts

Let $T$ be a first-order theory over a language $L$, and let $\mathcal{M}$ be a subclass of the class of models of $T$. As I understand it, if there is no theory $\hat{T}$ over $L$ whose class of ...
13
votes
0answers
271 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is $\sigma\...
12
votes
0answers
254 views

Write Occam's razor rigorously

What does Occam's razor look like written rigorously? Motivated by the desire to develop this idea further: https://philosophy.stackexchange.com/questions/41728/ I'm curious to see how a formal ...
12
votes
0answers
660 views

Why can't we formalize the lambda calculus in first order logic?

I'm reading through Hindley and Seldin's book about the lambda calculus and combinatory logic. In the book, the authors express that, though combinatory logic can be expressed as an equational theory ...
11
votes
0answers
315 views

Does Chaitin's constant have infinitely many prime prefixes?

Define $f(n) = \lfloor 2^n \cdot \Omega \rfloor$, that is, $f(n)$ is the first $n$ bits of Chaitin's constant interpreted as a number written in binary. I am trying to figure out if $f(n)$ can have ...
11
votes
0answers
161 views

Is there a finite list of identites in the language of $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm})$ that generates all the others?

Let $\Phi$ denote the set of all identities satisfied by $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm}).$ Question. Is $\Phi$ finitely axiomatizable? If so, I'd like to see a list of ...
11
votes
0answers
295 views

What are some arguments/counterarguments for Zeilberger's “proof certificates”?

Here is the quote I wish to ask about: "I speculate that similar developments will occur elsewhere in mathematics, and will 'trivialize' large parts of mathematics, by reducing mathematical ...
11
votes
0answers
290 views

A consequence of zero sharp (successor cardinals having countable cofinality)

So the existence of $0^\sharp$ in set theory is really the assertion on the existence of indiscernibles for the constructible universe $L$ that also "generate" $L$ (see http://en.wikipedia.org/wiki/...
11
votes
0answers
371 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need $\omega_1$-...
11
votes
0answers
208 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
10
votes
0answers
157 views

What can the reals of an inner model be?

This is probably a silly question. Call a set of reals $X$ a constructibility ideal (in analogy with a Turing ideal) if $X$ is closed under effective join $r\oplus s: n\mapsto 2^{r(n)}3^{s(n)}$ and ...
10
votes
0answers
432 views

Fixed points in computability and logic

I asked this question on CS.SE, too: https://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
10
votes
0answers
736 views

How strong is the statement that Thompson F is amenable?

Justin Moore's proof turned out to have an error I just attended Justin Moore's talk on this today. Since I am neither a group theorist nor a combinatorist, and is not familiar with ultrafilters I ...
9
votes
0answers
57 views

Simpler way to build large $\omega$-models

Consider the following statement: $(*)\quad$ There are $\omega$-models of ZFC of arbitrarily large cardinality. This is provable in ZFC + "There is an $\omega$-model of ZFC" alone. The proof I ...
9
votes
0answers
162 views

Is ZFC+V=L consistently $\omega$-complete?

Say that an extension of ZFC is $\omega$-complete if any two of its $\omega$-models are elementarily equivalent. While "ZFC+V=L is $\omega$-complete" is easily disprovable in theories only slightly ...
9
votes
0answers
969 views

Is this a way to construct mathematics?(logic vs. set theory)

I recently asked a question about the fact that logic and set theory seems circular. link I got a lot of good and thoughtful answers, that probably explains everything, but I must admit I did not ...
9
votes
0answers
278 views

ZF and weakly inaccessible cardinals

This question should probably have been asked 3 years ago (perhaps it has and was removed for some reason?) In 2011, Alexander Kiselev claimed to have proved in ZF that there are no weakly ...
9
votes
0answers
333 views

Is Kunen's claim about non-equivalent forms of Axiom of Choice, true?

Consider the following forms of the axiom of choice: $AC_1:\forall F\neq \emptyset~~~(\emptyset\notin F~\wedge~\forall x,y\in F~~~(x\neq y\rightarrow x\cap y= \emptyset))\rightarrow \exists C~\forall ...
8
votes
0answers
129 views

Set-theoretical semantics vs categorical semantics

Yo! I'm trying to understand the relation between set theoretical models (in the usual Tarskian sense) and categorical models. I don't care whether you gonna use the hyperdoctrine of the subobjects or ...
8
votes
0answers
186 views

What system was Grothendieck working in when he introduced universes?

I was reading that the universes which we now call "Grothendieck universes" were introduced by Grothendieck in order to avoid proper classes; from Grothendieck universe on Wikipedia: The idea of ...
8
votes
0answers
256 views

“Clubbiness” of $\Pi^1_n$ sets

I'm sure this is just my google-fu failing me, but: what are sufficient large cardinal axioms to guarantee "Every (boldface) $\Pi^1_n$ set of countable ordinals contains or is disjoint from a club ...
8
votes
0answers
116 views

Infinite palindromes in number of nonisomorphic posets is independent of $\mathsf{ZF}$

The following is an "exercise" in P. Stanley's book "Enumerative Combinatorics": Let $f(n)$ be the number of nonisomorphic $n$-element posets (...) let $\mathcal{P}$ denote the statement that ...
8
votes
0answers
571 views

Foundation for category theory

Before a little premise: It's well known that we can internalize the notion of category, functor and natural transformation in any category with enough structure: for instance we can define what an ...
8
votes
0answers
384 views

Using the compactness theorem to show a set of first-order formula is equivalent to a set of quantifier-free formula

I am going through some theorems in Hodges' ``A shorter model theory'' and I have realized that I do not understand a certain argument regarding compactness. My question has two forms, I am sure that ...
7
votes
0answers
114 views

Research in the intersection of mathematical logic and algebraic topology

Coming from logic background, the connection of topos theory and geometry motivates my study in algebraic geometry and algebraic topology in my first year graduate study. I'm interested in the ...
7
votes
0answers
134 views

What features of a logic make possible the proof of Downward Lowenheim-Skolem?

The Downward Lowenheim-Skolem Theorem asserts that if a countable first-order theory has an infinite model, then it has a countable model. Although associated with first-order logic, the result also ...
7
votes
0answers
193 views

Does naturality imply independence from choice?

My question concerns the notion of naturality defined in Section 12.3 of Hodge's (longer) Model Theory. See the addenda for the definition. Hodges proves a result that if an algebraic construction ...
7
votes
0answers
163 views

Why are the laws of sines/cosines “laws” and not “theorems”?

So in logic we have every line of a proof being either an axiom or a theorem -- but then why do we have concepts like the "law of sines" and the "law of cosines"? Are these technically "theorems" as ...
7
votes
0answers
88 views

Are “Discovery Systems” still not viable in mathematics?

I am currently reading Why did AM run out steam?, an article regarding Douglas Lenat's Automated Mathematician (AM). AM is an early example (from 1976) of a "discovery system" - a system that attempts ...
7
votes
0answers
205 views

Axiom of Choice as similar to Parallel Postulate?

I'm looking for resources that have drawn a comparison between the Parallel Postulate and the Axiom of Choice. That is, if we treat ZFC as an analogue to Euclidean geometry, can we view the ...
7
votes
0answers
570 views

The Hahn-Banach theorem and the axiom of choice

Let us recall the Hahn-Banach theorem about extensions of linear functionals: Theorem: Let $E$ be a real vector space and $F$ a subspace. If $p:E\to \mathbb{R}$ is a sublinear function, and $g:F\to ...
7
votes
0answers
392 views

Why don't the quantifiers split in linear logic?

Every presentation of linear logic I've seen seems to either omit or treat quantifiers as an after-thought. Even Girard says that there is "little to say" about them. However, if we view universal (...
7
votes
0answers
196 views

Transexponential Functions

Recall that $\exp(1,x) = e^x$ and $\exp(n+1,x) = e^{\exp(n,x)}$. Recall that $f(x)$ is transexponential if $f(x)$ is eventually greater than $\exp(n,x)$ $\forall n \in \mathbb{N}$ I am looking for a ...
7
votes
0answers
188 views

Skolem Hulls in $H_{\omega_2}$

Consider a model of the form $\mathfrak{A} = (H_{\omega_2}, \epsilon, \prec, f_0, f_1, ...)$, some expansion of $H_{\omega_2}$ in a countable language, with $\prec$ giving a well-order. Does there ...
7
votes
0answers
1k views

The Cantor Space as $\{0,1\}^{\mathbb{N}}$ and as $[0,1]$.

The Cantor-Space is defined as the space of all infinite binary sequences, i.e. the space $\{0,1\}^{\mathbb{N}}$. It has a natural metric, $$ d(x,y) = \inf\{ 2^{-|w|} : w \in pref(x) \cap pref(y) \} ...
6
votes
0answers
159 views

For any pair of definable sets of the same cardinality, is there a definable bijection between them?

The answer is no. My question actually is, what are the sufficient and necessary conditions so that an arbitrary $\mathcal{L}$-structure $\mathcal{M}$ is rich enough to be able to define bijections ...
6
votes
0answers
112 views

The elementary theory of finite commutative rings

I have wondered the decidability of elementary theory of finite commutative rings. Since we know that the elementary theory of finite fields is decidable shown by J.Ax (The Elementary Theory of Finite ...
6
votes
0answers
246 views

A paradox involving complexity class separations and arithmetical soundness

Here is a paradox I came up with that I've only partly unraveled. The question is about how to mathematically model this situation in a way that satisfactorily explains both points of view. In the ...
6
votes
0answers
191 views

What is this property exhibited by some logical systems?

The following property exhibited by some logical systems has captured my attention: $$\forall X\; ( {\vdash x_1[X]} \implies {\vdash x_2[X]} ) \implies \forall X\; {\vdash (x_1[X]\to x_2[X])},$$ ...
6
votes
0answers
53 views

Can I construct a complete (as a Boolean algebra) $\aleph_0$ saturated elementary extension of a given Boolean algbera?

This is a follow-up to my previous question: Let $B$ be an arbitrary Boolean algebra. Can one construct a $\aleph_0$-saturated $B^* \succ B$ that is complete, i.e., all joins and meets exist in $B^...
6
votes
0answers
107 views

Does introducing a new type create a different extension, and is it still conservative?

In this comment on Terry Tao's page about his Analysis I textbook, he writes, If one wanted to do things by the book, what one should actually do each time one introduces a new mathematical object, ...
6
votes
0answers
94 views

Surveys on classification theory

By classification theory, I mean the branch of model theory in which people aim to extend the original classification theory by Shelah on stable theories by considering other nice properties (simple, ...
6
votes
0answers
123 views

“Nicely definable” endomorphisms in universal algebra

Conjugation in a group satisfies a nice extendibility property: namely, if $a\in G$ and $f: G\rightarrow H$, then the map $$Conj_a[f]="x\mapsto f(a)xf(a)^{-1}"$$ is again an automorphism of $H$. In ...
6
votes
0answers
207 views

Anti-random reals

EDIT: This has now been crossposted at MO: https://mathoverflow.net/questions/219366/antirandom-reals. This is partially motivated by my question at mathoverflow: https://mathoverflow.net/questions/...
6
votes
0answers
252 views

Quantum and Paraconsistent Logics

Is there any relation between these two logics? I know both are completely different "from construction", but recently I've read that paraconsistent logics tries to explain some things in quantum ...