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.

Filter by
Sorted by
Tagged with
14 votes
3 answers
2k views

Forcing over an arbitrary model of ZFC

I’m learning set theory and forcing in the (french) book from Jean-Louis Krivine “Théorie des ensembles”. Given a countable transitive model $\mathscr{M}$ of ZFC together with a poset $P$, he ...
Guillaume Brunerie's user avatar
26 votes
2 answers
2k views

A set that can be covered by arbitrarily small intervals

Let $X$ be a subset of the real line and $S=\{s_i\}$ an infinite sequence of positive numbers. Let me say that $X$ is $S$-small if there is a collection $\{I_i\}$ of intervals such that the length of ...
Sergei Ivanov's user avatar
11 votes
5 answers
4k views

Proper classes and their consequences

I have two main questions: What is a proper class? I've read that it's collection of objects that's "too big" to be a set, but in what sense is such a collection "too big"? Since I'd like this post ...
Avi Steiner's user avatar
  • 3,031
7 votes
1 answer
522 views

Are innermost reductions perpetual in untyped $\lambda$-calculus?

Background In the untyped lambda calculus, a term may contain many redexes, and different choices about which one to reduce may produce wildly different results (e.g. $(\lambda x.y)((\lambda x.xx)\...
kow's user avatar
  • 461
6 votes
1 answer
358 views

Recursive Non-Well-Orders that are Sneaky, but not THAT Sneaky.

This is a variant on Sneaky Recursive Non-Well-Orders where it was asked Is there a recursive function $f$ such that whenever $a\in\mathcal{O}$, $f(a)$ is a Turing index for a linear non-well-...
anonymous's user avatar
2 votes
1 answer
416 views

First order logic

How to prove that in a first-order logic, the models of a theory cannot be only the interpretations with finite domains?
Anna Fred's user avatar
35 votes
8 answers
4k views

Is P=NP relevant to finding proofs of everyday mathematical propositions?

Disclaimer: I don't know a whole lot about complexity theory beyond, say, a good undergrad class. With increasing frequency I seem to be encountering claims by complexity theorists that, in the ...
Adam's user avatar
  • 3,247
-1 votes
3 answers
493 views

Other ways to define naturals

Is it possible to express the functions $S(x)=x+1$ and $Pd(x)=x\dot{-}1$ in terms of the functions $f_1$, $f_2$, $f_3$ and $f_4$, where $f_1(x)=0$ if $x$ is even or $1$ if $x$ is odd, $f_2(x)=\mbox{...
Tim's user avatar
  • 3
21 votes
5 answers
4k views

How much of ZFC does Quine's New Foundations prove?

Main Question: Does anyone know of a reference that can tell me which axioms of ZFC Quine's New Foundations prove, disprove, and leave undecided? Secondary Question: I've read that diagonal ...
Amit Kumar Gupta's user avatar
5 votes
3 answers
1k views

Looking for a complete exposition of the Burali-Forti paradox

In the context of ZFC, one normally uses von Neumann's definition of the ordinals. However, originially an ordinal was just the order-type of a well-ordered set (where "order-type of A" may for ...
Marcos Cramer's user avatar
3 votes
2 answers
626 views

"classes" with no cardinality; "classes" with no equality notion

Hello, If we look at the class of all vector spaces over some field, we can note two things: 1) this class should not have cardinality. 2) for two elements of this class, we should not want to be ...
Sasha's user avatar
  • 5,492
2 votes
3 answers
622 views

logics restricted in arithmetic hierarchy

Hello, I would like to know if this already has been researched. There has been lot of research done, where logics are limited. They are often limited in the axioms or inference rules, which makes ...
Lucas K.'s user avatar
  • 1,659
4 votes
0 answers
369 views

Sentences Preserved by Direct Products (including the Empty Product)

Consider the class of all structures for a given signature in first-order logic. Let $S_i$ be a family of structures, and $\oplus S_i$ be the direct product of the family. You can extend the notion ...
arsmath's user avatar
  • 6,720
7 votes
1 answer
751 views

Schemes (as in algebraic geometry) and first-order logic.

Affine schemes are simply the Zariski spectra of commutative rings, and commutative rings occurs as models of a first-order theory. I would guess that general schemes do not naturally correspond to ...
David Feldman's user avatar
13 votes
5 answers
1k views

"Let $x \in A$", beginning a proof of "$\forall x \in A$ ...", if A were empty [closed]

I work at a four-year teaching school, where we pride ourselves on teaching pure math, proof, and a rather obsessive carefulness of work. Recently I have been criticized for saying that "Let $x \in A$...
Coward's user avatar
  • 139
6 votes
1 answer
632 views

Which properties of ultrafilters on countable sets hold for filters in general?

Background/motivation: I'm investigating the construction of models for a first-order modal system (S5) as products of classical models. Since ultraproducts are all classical models and I need non-...
MikeC's user avatar
  • 327
6 votes
3 answers
1k views

A question about Transfinite Induction

The Transfinite Induction says: Let $\mathbf{P}(x)$ is a property, assume that, for all ordinal numbers $\alpha $ : If $\mathbf{P}(\beta)$ holds for all $\beta < \alpha$, then $\mathbf{P}(\alpha)$ ...
Dong xiaowei's user avatar
32 votes
3 answers
6k views

Is the statement that every field has an algebraic closure known to be equivalent to the ultrafilter lemma?

The existence and uniqueness of algebraic closures is generally proven using Zorn's lemma. A quick Google search leads to a 1992 paper of Banaschewski, which I don't have access to, asserting that ...
Qiaochu Yuan's user avatar
27 votes
8 answers
4k views

Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example. Now, in the logic courses (that I have had look at)...
user avatar
8 votes
1 answer
665 views

Explicit uses of alephs above 'small ones'

In a paper placed on the arXiv today Shelah references theorem 0.9 from this paper (also Shelah) that uses $\aleph_{736}$ as an upper bound. This strikes me as analogous to Skewes' number. Are there ...
David Roberts's user avatar
  • 33.8k
1 vote
3 answers
2k views

Modal logic - box rules

Hi guys, In modal logic i.e. propositional logic with box and diamond, are then any laws to get a box or a diamond from outside a bracket to inside? I.e. $\Box (x \rightarrow \Box x)$ I want the ...
ale's user avatar
  • 187
22 votes
4 answers
9k views

Explicit Hamel basis of real numbers

Is there an explicit construction of a Hamel basis of the vector space of real numbers $\mathbb R $ over the field of rational numbers $\mathbb Q $?
Buschi Sergio's user avatar
106 votes
36 answers
20k views

Interesting examples of vacuous / void entities

I included this footnote in a paper in which I mentioned that the number of partitions of the empty set is 1 (every member of any partition is a non-empty set, and of course every member of the empty ...
3 votes
2 answers
1k views

Modal logic - satisfiability

Hi there, Assuming X and Y are modal formulae and diamond X is satisfiable and diamond Y is satisfiable, how would one show that they X AND Y is satisfiable? I don't think it requires much effort? ...
ale's user avatar
  • 187
23 votes
5 answers
6k views

Hahn-Banach without Choice

The standard proof of the Hahn-Banach theorem makes use of Zorn's lemma. I hear that, however, Hahn-Banach is strictly weaker than Choice. A quick search leads to many sources stating that Hahn-Banach ...
Mark Kim's user avatar
  • 1,162
21 votes
1 answer
3k views

Philosophical consistency proof for set theory

In his ASL Gödel lecture (Las Vegas, Nevada, 2002), Harvey Friedman asked the following question: Are there fundamental principles of a general philosophical nature which can be used to give ...
Lianna's user avatar
  • 261
1 vote
1 answer
652 views

FOL->ZF->HOL (Interpretation)

Hello. This may not count as a research question, but I guess it's too much for math.stackexchange. Could we define ZF (Zermelo-Fraenkel Set theory) in classical first-order predicate calculus, then ...
Bubba88's user avatar
  • 305
18 votes
1 answer
1k views

Can Vopenka's principle be violated definably?

One form of Vopenka's principle (a large cardinal axiom) states that no locally presentable category contains a full subcategory which is large (= a proper class) and discrete (= contains no ...
Mike Shulman's user avatar
31 votes
2 answers
2k views

The logic of convex sets

Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
darij grinberg's user avatar
6 votes
7 answers
5k views

Compactness Theorem for First Order Logic

Hi all, I am interested in proofs without using Goedel's completeness theorem. Does anyone have a reference to a proof of this theorem that uses Skolem Functions? How come Enderton's (Introduction to ...
Eran's user avatar
  • 649
13 votes
3 answers
1k views

When can we detect forcing?

First, a rather broad question: has there been any work on what, given a model $M$ of set theory, we can say about those models of set theory $N$ and posets $\mathbb{P}$ such that $\mathbb{P}\in N$ ...
Noah Schweber's user avatar
9 votes
2 answers
2k views

Quantum PCP Theorem

Although I think I know the answers to these, I'd just like to collect them all in one place. What is the quantum PCP theorem, what implications does its proof have for simulation of Hamiltonians and ...
Noah Rahman's user avatar
32 votes
3 answers
5k views

Should there be a true model of set theory?

As I understand it, there is a program in set theory to produce an ultimate, canonical model of set theory which, among other things, positively answers the Continuum Hypothesis and various questions ...
Amit Kumar Gupta's user avatar
7 votes
2 answers
702 views

Sturm chain analogue for exponential polynomials?

I'm going to define an exponential polynomial of degree $k$ as a function $f$ of the form $f(x) = \sum_{i=1}^k c_ie^{\alpha_ix}$ ($\alpha_i$s real). My first question is: is there an algorithm for ...
zeb's user avatar
  • 8,533
3 votes
3 answers
443 views

Complexity of the statement 'P is proper'

Assume that $(P,\le)$ is a notion of forcing. There are several ways to define what it means for $P$ being proper and I would like to know: What is the complexity (in terms of the Levy-Hierarchy) of ...
Stefan Hoffelner's user avatar
18 votes
15 answers
13k views

undergraduate logic textbook

I am going to teach the standard undergraduate Logic course for math and engineering majors. What are good (bad) text-books and why. I have not taught that course for a while and wonder if there are ...
14 votes
1 answer
951 views

How is Fredkin and Toffoli's Conservative Logic related to Linear Logic?

In the answers to this question, Timothy Gowers asks: I've been interested in this question for some time. I haven't put any serious thought into it, so all I can offer is a further question rather ...
Neel Krishnaswami's user avatar
11 votes
0 answers
1k views

Reverse mathematics strength of identically zero polynomials are the zero polynomial

According to wikipedia, the statement "every polynomial over a countable field that is not the zero polynomial has only finitely many roots" is equivalent to RCA0 over RCA0* (which is called ERCA-0 in ...
user avatar
11 votes
2 answers
2k views

What is a good example of a complete but not model-complete theory, and why?

The standard examples of complete but not model-complete theories seem to be: - Dense linear orders with endpoints. - The full theory $\mathrm{Th}(\mathcal{M})$ of $\mathcal{M}$, where $\mathcal{M} = (...
Sam Derbyshire's user avatar
9 votes
6 answers
4k views

Difference between turnstile and implication

Does anyone know the difference between proving that |- phi ------------------ |- ( psi -> phi ) and proving that ...
Surikator's user avatar
  • 283
89 votes
10 answers
16k views

Is there any formal foundation to ultrafinitism?

Ultrafinitism is (I believe) a philosophy of mathematics that is not only constructive, but does not admit the existence of arbitrarily large natural numbers. According to Wikipedia, it has been ...
Michael O'Connor's user avatar
11 votes
2 answers
785 views

What is the depth of the "provability hierarchy"?

I am not a logician or set theorist, so hopefully this makes sense. Let $T$ be a theory which is expressive enough to make statements like "Statement $A$ has a proof in $T$"; for example, $...
Daniel Litt's user avatar
  • 22.2k
117 votes
4 answers
36k views

Is the analysis as taught in universities in fact the analysis of definable numbers?

Ten years ago, when I studied in university, I had no idea about definable numbers, but I came to this concept myself. My thoughts were as follows: All numbers are divided into two classes: those ...
Anixx's user avatar
  • 9,306
61 votes
9 answers
13k views

Arguments against large cardinals

I started to learn about large cardinals a while ago, and I read that the existence, and even the consistency of the existence of an inaccessible cardinal, i.e. a limit cardinal which is additionally ...
user8996's user avatar
  • 765
1 vote
1 answer
510 views

Can invariant of transitive reflexive closure in FOL+PA always been proven?

I am trying to understand FOL + PA, better. With FOL + PA I mean, first order logic, with addition and multiplication predicate and induction axiom scheme. The book I am reading explains how to ...
Lucas K.'s user avatar
  • 1,659
21 votes
0 answers
573 views

Density of first-order definable sets in a directed union of finite groups

This is a generalization of the following question by John Wiltshire-Gordon. Consider an inductive family of finite groups: $$ G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i \...
Gene S. Kopp's user avatar
  • 2,190
3 votes
1 answer
561 views

Equivalent definitions of $(M,P)$-genericity

Hi! I started to read the chapter 31 in Jechs book about proper forcing. Unfortunately it is written in a rather sketchy way and I do have some issues in proving a lemma about two equivalent ...
Stefan Hoffelner's user avatar
15 votes
2 answers
2k views

Propositional logic with categories

I have some vague sense that certain types of categories are related to certain types of logic. I've been meaning to learn more about this, so I thought I'd ask about the simplest case, propositional ...
Qiaochu Yuan's user avatar
0 votes
5 answers
940 views

finding cutting edge papers and books

Hi all, what are the best strategies to find cutting edge papers and books on a field of mathematics? .. Example: 2-3 years ago I had to analyze a time series. I found a paper and showed that to ...
16 votes
36 answers
3k views

Basic results with three or more hypotheses

Consider the following statement of the Arzela-Ascoli theorem. Theorem. Let K be a compact topological space and let S be a subset of C(K). Then S is relatively compact if and only if S is uniformly ...

1
92 93
94
95 96
103