All Questions
6,026 questions
20
votes
1
answer
936
views
A collection of intervals that can cover any measure zero set
This is a follow-up to this question (in fact, this is what originally motivated me to ask that one.)
Let's say that a sequence $\{s_i\}$ of positive reals covers a set $X\subset\mathbb R$ if there ...
- 32.4k
13
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 ...
- 3,033
27
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 ...
- 32.4k
12
votes
5
answers
5k
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 ...
- 3,079
7
votes
1
answer
531
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)\...
- 461
6
votes
1
answer
373
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-...
- 61
2
votes
1
answer
426
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?
- 29
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 ...
- 3,267
-1
votes
3
answers
496
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{...
- 3
22
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 ...
- 3,982
4
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 ...
- 1,228
3
votes
2
answers
645
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 ...
- 5,562
2
votes
3
answers
662
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 ...
- 1,659
4
votes
0
answers
373
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 ...
- 6,870
7
votes
1
answer
777
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 ...
- 17.6k
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$...
- 139
6
votes
1
answer
645
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-...
- 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)$ ...
- 111
32
votes
3
answers
7k
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 ...
- 118k
28
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)...
user10891
8
votes
1
answer
689
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 ...
- 35.5k
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 ...
- 187
10
votes
2
answers
752
views
Adding a formal inverse of an element to a free monoid
Let $FM_2=\langle a,b\rangle$ be the free monoid of rank 2. If we add a formal inverse to the word $aba$, we get the free group $F_2$ (because both $a$ and $b$ will have inverses).
Question: For ...
user6976
22
votes
4
answers
10k
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 $?
- 4,165
107
votes
36
answers
21k
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 ...
8
votes
1
answer
1k
views
Lattice-ordered commutative monoids
By a lattice-ordered monoid, I mean a structure $(A,0,{+},{\vee},{\wedge})$ such that $(A,0,{+})$ is a (not necessarily commutative) monoid, $(A,{\vee},{\wedge})$ is a lattice, and the two ...
- 44.4k
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?
...
- 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 ...
- 1,202
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 ...
- 261
1
vote
1
answer
400
views
Transitive Semigroups of $2\times 2$ matrices
Suppose $G$ is a semigroup (i.e., closed under matrix multiplication) of invertible $2\times 2$ real matrices. Suppose also that $G$ is transitive i.e., for any two non-zero vectors $u$ and $v$ there ...
- 1,045
1
vote
1
answer
673
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 ...
- 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 ...
- 66.8k
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 ...
- 33.8k
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 ...
- 639
12
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$ ...
- 20.5k
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 ...
- 93
31
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 ...
- 3,982
7
votes
2
answers
724
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 ...
- 8,688
5
votes
2
answers
537
views
If $k[S]$ is noetherian, is S finitely generated?
Let $S$ be a semigroup. If $S$ is abelian, then it follows that the semigroup algebra $k[S]$ is finitely generated if and only if $S$ is.
What if we relax the condition on $k[S]$, so that $k[S]$ is ...
- 11.6k
3
votes
3
answers
450
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 ...
- 2,180
18
votes
15
answers
14k
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
970
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 ...
- 9,201
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 ...
user5810
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} = (...
- 5,530
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
...
- 283
89
votes
10
answers
17k
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 ...
- 1,001
11
votes
2
answers
808
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, $...
- 23k
122
votes
4
answers
39k
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 ...
- 10.1k
67
votes
10
answers
14k
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 ...
- 825
1
vote
1
answer
514
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 ...
- 1,659