# Questions tagged [lo.logic]

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, theories of truth, truth revision, consistency.

4,992 questions
Filter by
Sorted by
Tagged with
43 views

### How exactly are realizability and the Curry-Howard correspondence related?

Consider, on the one hand: the Curry-Howard correspondence between, on the one hand, types and terms (programs) in various flavors of typed $\lambda$-calculus, and on the other, propositions and ...
65 views

### How to prove that increasing the number of constant symbols of a first-order logic by the number of formulas keeps the number of formulas the same [closed]

Let $S$ be a set of theory symbols for a first-order logic, and let $C$ be a set of constant symbols in $S$ such that $|C| = |L(S)|$, where $L(S)$ is the set of all formulas generated by $S$ in the ...
46 views

### Can the set of parafinite congruences be descriptive-set-theoretically complicated?

Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...
107 views

### Congruences that aren't "finite from above," take 2: semigroups

This is a hopefully less trivial version of this question. Briefly, say that a congruence is parafinite if it is the largest congruence contained in some equivalence relation with finitely many ...
396 views

### Congruences that aren't "finite from above"

Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with ...
101 views

### Is "$\gamma$ is admissible" necessary in lemma V.5.10, Constructibility, Devlin?

This lemma is an early step of the proof of Jensen's covering lemma. I feel that in this lemma, "$\gamma$ is admissible" is not required. $\gamma$ being a limit ordinal is enough. In the ...
460 views

### Con(PA) via non-well-foundedness?

Lumsdaine made the following interesting comment: if Con(PA) fails in a non-standard model, it means it contains a “proof of non-standard length” of a contradiction from PA. With a little work, one ...
82 views

2k views

### Is GCH useful in proving theorems?

By GCH I mean the Generalized Continuum Hypothesis. Let me give some context before presenting my question. When the axiom of choice was introduced by Zermelo in his 1904 proof of Well-Ordering ...
1 vote
13 views

### Reference request for dinatural transformations arising from free Cartesian closed categories

Let $g_n$ be a discrete graph with $n$ nodes and $\operatorname{F}$ the free functor of the adjunction between the category of graphs and the category of Cartesian closed categories and functors, as ...
174 views

### Is the Rado graph the unique countable graph that has all finite graphs as induced subgraphs?

I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado ...
116 views

### Elementary equivalence for rings

Let $\mathcal{L}$ be a first-order language, and $M$ and $N$ be two $\mathcal{L}$-structures. We say that $M$ and $N$ are elementarily equivalent (write $M \approx N$) if they satisfy the same first-...
522 views

### Is "the purely probabilistic version of Freiling's axiom of symmetry" disprovable in ZFC?

I'm trying to pinpoint the "intuitive argument" for Freiling's Axiom of Symmetry. It's meant to be a "probabilistic" argument, so thinking about what seems to me to be the ...
115 views

### Posets of equational theories of "bad quotients"

This is a follow-up to an older question of mine: Suppose $\mathfrak{A}=(A;...)$ is an algebra (in the sense of universal algebra) and $E$ is an equivalence relation - not necessarily a congruence - ...
1 vote
210 views

### Hahn-Banach theorem and ultrafilter lemma

I'm unable to understand a remark in "Two application of the method of construction by ultrapowers to analysis" by Luxemburg, which uses the ultrafilter lemma to prove the Hahn-Banach ...
249 views

### An imaginary disaster scenario - second order arithmetic is inconsistent

I think my question is a natural follow up of What would be some major consequences of the inconsistency of ZFC? Regarding the later question, I agree with the commentaries that probably an ...
276 views

### Proving finiteness in Reverse Mathematics

In (second-order) Reverse Mathematics, a (code for an) open set $U\subset \mathbb{R}$ is given by two sequences of rationals $(a_n)_{n \in \mathbb{N}}, (b_n)_{n \in \mathbb{N}}$. The idea is that $U$ ...
75 views

### Is the following combinatorial identity correct? $\sum_{k=1}^{n}k \cdot 2^k = n \cdot 2^n$ [closed]

During my studies in mathematical logic, I learned a new concept called a truth table. I saw as an example that for $3$ atoms, in the context of a binary connector, there are $8$ different cases for ...
106 views

### Classes of algebras axiomatizable by special formulas; and free objects

Let $\mathcal{L}$ be a first-order language without relation symbols, and let $\mathcal{K}$ be a class of $\mathcal{L}$-algebras. $\mathcal{K}$ is axiomatizable if there is a set $T$ of first-order ...
176 views

### Is Morse-Kelley set theory with Class Choice bi-interpretable with itself after removing Extensionality for classes?

Let $\sf MKCC$ stand for Morse-Kelley set theory with Class Choice. And let this theory be precisely $\sf MK$ with a binary primitive symbol $\prec$ added to its language, and the following axioms ...
1k views

158 views

### Strengthening Determinacy in constructive set theory?

Recall how games work. Let $X$ be a set (the "game space") and $\alpha$ an ordinal (the "game clock"). Alice and Bob take turns naming elements of $X$. We write them down in order ...
297 views

### Are there $2^{\aleph_0}$ pairwise non-isomorphic countable groups containing every finite group?

Let us call a group $(G,\cdot)$ finitarily complete if $G$ is countable, and every finite group is isomorphic to a subgroup of $(G,\cdot)$. Is there a collection of $2^{\aleph_0}$ pairwise non-...
277 views

167 views

### The approximate mean value theorem / Rolle's theorem in pure constructive mathematics

In the replies of this very similar question, there is a fascinating answer that is beautiful in its simplicity. In particular, it seems to use perhaps the most minimal assumptions one can possibly ...
378 views

### Trading Choice for Comprehension (or Replacement)

This question is basically a request for clarification about a remark made by Sam Sanders in a comment to another question: IIUC what he's saying, there are statements that can be proved either with a ...
149 views

### Does allowing Ur-elements in $\sf ZF^*GC$ break bi-interpretability with $\sf ZF^*GC$?

Is $(\sf ZF^*GC - Extensionality)$ bi-interpretable with $\sf ZF^*GC$? Where $\sf ZF^*GC$ is $\sf ZF - Replacement + Separation + Collection + Global \ Choice$
322 views

### "Compactness length" of Baire space

Intuitively, my question is: how many times do we have to mod out by an closed equivalence relation with all classes compact in order to collapse Baire space $\omega^\omega$ to a singleton? In more ...
397 views

### A strange product forcing

Given two forcing notions $\mathbb{P}_0,\mathbb{P}_1$, we know that the product $\mathbb{P_0}\times\mathbb{P_1}$ will produce the following diagram of models ordered by inclusion: where $M$ is the ...