# 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).

2,710 questions
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 ...
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 ...
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$ ...
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 ...
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, ...
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 ...
271 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
570 views