All Questions
6,026 questions
69
votes
19
answers
9k
views
What are some results in mathematics that have snappy proofs using model theory?
I am preparing to teach a short course on "applied model theory" at UGA this summer. To draw people in, I am looking to create a BIG LIST of results in mathematics that have nice proofs ...
- 65.4k
7
votes
2
answers
1k
views
Recursively dependent types?
Is there such a thing as "recursively dependent types"? Specifically, I would like a dependent type theory containing a type $A(x)$ which depends on a variable $x: A(z)$, where $z$ is a particular ...
- 66.8k
22
votes
3
answers
6k
views
Satisfiability of general Boolean formulas with at most two occurrences per variable
(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
- 4,729
8
votes
3
answers
2k
views
randomness in nature [closed]
What is the explanation of the apparent randomness of high-level phenomena in nature?
For example the distribution of females vs. males in a population (I am referring to randomness in terms of the ...
- 307
25
votes
3
answers
7k
views
In model theory, does compactness easily imply completeness?
Recall the two following fundamental theorems of mathematical logic:
Completeness Theorem: A theory T is syntactically consistent -- i.e., for no statement P can the statement "P and (not P)" be ...
- 65.4k
33
votes
3
answers
7k
views
Category of categories as a foundation of mathematics
In
Lawvere, F. W., 1966, “The Category of
Categories as a Foundation for
Mathematics”, Proceedings of the
Conference on Categorical Algebra, La
Jolla, New York: Springer-Verlag,
1–21.
...
- 2,399
3
votes
3
answers
1k
views
Countable atomless boolean algebra covered by a larger boolean algebra
Suppose $Q$ is an atomless countable boolean algebra, and $B$ is an arbitrary atomless boolean algebra. $Q$ is unique modulo isomorphisms. There is a subalgebra in $B$ that is isomorphic to $Q$. There ...
- 355
7
votes
4
answers
1k
views
Is the theory of incidence geometry complete?
Consider the basic axioms of planar incidence geometry, which allow us to speak of in-betweeness, collinearity and concurrency. These axioms per se are not complete, since for example, Desargues ...
user2529
13
votes
5
answers
2k
views
Categorification of logic
Has there been an effort to categorify first order logic? More particularly, structures in the sense of logic.
If so, then every structure of a first order theory is a category. So in particular, the ...
user2529
3
votes
2
answers
889
views
computation, algebra, logic
So a really simple way of describing a digital computer is to say that it is a device for performing boolean operations. You feed it a bunch of bit strings, which is a description of the problem and ...
user577
13
votes
2
answers
2k
views
Ordinals that are not sets
The class of all ordinal numbers $\mathbf{Ord}$, aside being a proper class, can be thought of an ordinal number (of course it contains all ordinal numbers that are sets, not itself). Then one could ...
- 918
30
votes
7
answers
3k
views
What is a logic?
I am not interested in the philosophical part of this question :-)
When I look at mathematics, I see that lots of different logics are used : classical, intuitionistic, linear, modal ones and weirder ...
- 445
8
votes
3
answers
739
views
What assumptions and methodology do metaproofs of logic theorems use and employ?
In logic modules, theorems like Soundness and completeness of first order logic are proved. Later, Godel's incompleteness theorem is proved. May I ask what are assumed at the metalevel to prove such ...
user2529
7
votes
4
answers
2k
views
Alternative axiom to induction
Is anyone aware of alternative axioms to induction? To be precise, consider peano axioms without induction PA-. Is there any axiom/axiom schema that is equiconsistent to induction, assuming PA-? If so,...
user2529
53
votes
5
answers
20k
views
Categorical foundations without set theory
Can there be a foundations of mathematics using only category theory, i.e. no set theory? More precisely, the definition of a category is a class/set of objects and a class/set of arrows, satisfying ...
user2529
12
votes
4
answers
4k
views
cut elimination
What is the cut rule? I don't mean the rule itself but an explanation of what it means and why are proof theorists always trying to eliminate it? Why is a cut-free system more special than one with ...
user577
34
votes
3
answers
2k
views
How much choice is needed to show that formally real fields can be ordered?
Background: a field is formally real if -1 is not a sum of squares of elements in that field. An ordering on a field is a linear ordering which is (in exactly the sense that you would guess if you ...
- 65.4k
11
votes
4
answers
3k
views
intuitionistic interpretation of classical logic
Basically intuitionistic logic is classical logic minus the law of the excluded middle, i.e. $\neg A\vee A$ is not necessarily valid for all formulas. So I would take this to mean that classical logic ...
user577
11
votes
2
answers
1k
views
Adding a random real makes the set of ground model reals meager
This is a question about forcing. I have seen the following fact mentioned in multiple places, but have not been able to find a proof: if a random real is added to a transitive model of ZFC, then in ...
- 2,701
47
votes
5
answers
9k
views
Proof assistants for mathematics
This question is related to (maybe even the same in intent as) Intro to automatic theorem proving / logical foundations?, but none of the answers seem to address what I'm looking for.
There are a lot ...
7
votes
1
answer
1k
views
Encoding fuzzy logic with the topos of set-valued sheaves
One of the canonical examples used by Barr & Wells in order to motivate the use of topoi is that we can construct a theory for fuzzy logic and fuzzy set theory as set-valued sheaves on a poset (...
- 2,537
3
votes
2
answers
510
views
Semilattices in atomless boolean algebras
Let S be a bounded semilattice without maximal elements. Can we always construct an atomless boolean algebra B, containing S as a subsemilattice, such that S is cofinal in B-{1}? That is, for every x&...
- 355
3
votes
3
answers
447
views
Representations of finite commutative band semigroups
I think it's clear that commutative semigroups S that are also bands, i.e. $e^2 = e$ for all e, correspond to finite posets (consider the elements of the semigroups as sets, where the intersection of ...
- 2,216
13
votes
11
answers
6k
views
A problem of an infinite number of balls and an urn
I think that the following problem originated in a probability textbook :
You have a countably infinite supply of numbered balls at your disposal. They are all labeled with the natural numbers {1,2,3,...
8
votes
1
answer
655
views
Coherent spaces
In Proofs and Types, Girard discusses coherent (or coherence) spaces, which is defined as a set family which is closed downward ($a\in A,b\subseteq a\Rightarrow b\in A$), and binary complete (If $M\...
- 475
25
votes
7
answers
3k
views
When can we prove constructively that a ring with unity has a maximal ideal?
Many commutative algebra textbooks establish that every ideal of a ring is contained in a maximal ideal by appealing to Zorn's lemma, which I dislike on grounds of non-constructivity. For Noetherian ...
- 118k
37
votes
7
answers
8k
views
Model theoretic applications to algebra and number theory(Iwasawa Theory)
One of my favorite results in algebraic geometry is a classical result of AX (see http://terrytao.wordpress.com/2009/03/07/infinite-fields-finite-fields-and-the-ax-grothendieck-theorem/) I'll recall ...
- 2,396
2
votes
4
answers
1k
views
nonstandard set theories
Does anyone know of good references for nonstandard set theories and their applications to various branches of mathematics like category theory, algebra, geometry, etc.?
Edit: What I mean by "...
user577
9
votes
5
answers
1k
views
References/literature for pushouts in category of commutative monoids? [ed. - amalgams]
This is more of a request for pointers to relevant literature than a question per se. I am, erm, looking at a paper which uses a kind of iterated pushout construction to obtain a commutative monoid ...
- 25.8k
2
votes
2
answers
980
views
increasing bijection
Using the back-and-forth method we can construct an increasing bijection from the set of rational numbers to the set of of rational numbers except zero.
http://en.wikipedia.org/wiki/Back-and-...
- 566
20
votes
7
answers
2k
views
Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)
Let us say that a set B admits a rigid binary relation, if there is a binary relation R such that the structure (B,R) has no nontrivial automorphisms.
Under the Axiom of Choice, every set is well-...
- 236k
28
votes
13
answers
4k
views
Are there any good nonconstructive "existential metatheorems"?
Are there any good examples of theorems in reasonably expressive theories (like Peano arithmetic) for which it is substantially easier to prove (in a metatheory) that a proof exists than it is ...
5
votes
2
answers
1k
views
Applications of propositional dynamic logic
Propositional dynamic logic (PDL) is an example of a (multi)modal logic with a structure on the set of modalities. In particular, the set of its modalities is indexed by "programs" and one can use ...
- 483
5
votes
3
answers
1k
views
Where does the generic triangle live?
This is a reformulation of my question Characterizing triangles unembeddedly.
Motivation 1: There is such a thing as a generic group. In category theory this is done by constructing "theory" of ...
- 1,160
15
votes
3
answers
1k
views
A rigid type of structure that can be put on every set?
Call a type of structure rigid if any automorphism of such a structure is an identity. (This is a bit different from some other uses of the word, but hopefully I'll be forgiven.) For example, well-...
- 66.8k
72
votes
31
answers
9k
views
Can infinity shorten proofs a lot?
I've just been asked for a good example of a situation in maths where using infinity can greatly shorten an argument. The person who wants the example wants it as part of a presentation to the general ...
- 29k
27
votes
5
answers
3k
views
Algebraic description of compact smooth manifolds?
Given a compact smooth manifold $M$, it's relatively well known that $C^\infty(M)$ determines $M$ up to diffeomorphism. That is, if $M$ and $N$ are two smooth manifolds and there is an $\mathbb{R}$-...
- 6,546
9
votes
2
answers
1k
views
"Requires axiom of choice" vs. "explicitly constructible"
I think I'm a bit confused about the relationship between some concepts in mathematical logic, namely constructions that require the axiom of choice and "explicit" results.
For example, let's take ...
- 5,992
20
votes
3
answers
4k
views
Basis of l^infinity
Is it possible to exhibit a (Hamel) basis for the vector space l^infinity, given by the bounded sequences of real numbers?
- 1,638
25
votes
5
answers
4k
views
Logic comment in Mumford's Red Book
In Mumford's "The red book of varieties and schemes" one of the examples (G on pg 74) is the space Spec $(\prod_{i=1}^\infty k)$, where $k$ is a field. He mentions that "Logicians assure us that we ...
- 1,292
7
votes
6
answers
3k
views
Independence of the continuum hypothesis on ZFC
Can anyone point out some good reference to understand how Paul Cohen proved that the continuum hypothesis is independent of ZFC? I know he used the so called forcing technique to construct two ...
- 1,638
2
votes
2
answers
892
views
Is the existence of a well-ordering on R independent of ZF?
I am reasonably certain this is the case, but can't find a reference that actually states this, although the Wikipedia article states something close.
- 118k
27
votes
5
answers
4k
views
What is induction up to $\varepsilon_0$?
This is a question asked out of curiosity, and because I can't understand the Wikipedia page.
I have often been told that PA cannot prove the validity of induction up to $\varepsilon_0$, which has ...
- 156k
11
votes
5
answers
6k
views
Finding minimal or canonical expressions for Boolean truth tables
This is not an urgent question, but something I've been curious about for quite some time.
Consider a Boolean function in n inputs: the truth table for this function has 2n rows.
There are uses of ...
- 524
3
votes
5
answers
2k
views
Independence from Set Theory Axioms
I have often heard of various statements being independent from the axioms of set theory (typically ZFC). Some examples include
The continuum hypothesis is probably the most famous
The independence ...
- 445
8
votes
3
answers
408
views
How does one identify properties of objects with good "inheritance"?
When you are dealing with a very general object like a topological space or a ring, usually you impose an additional condition (such as compact Hausdorff or Noetherian) with the property that the ...
- 118k
12
votes
3
answers
1k
views
Is formal proof (formalized mathematics) interesting to practicing mathematicians? To educators? [closed]
Formalizing mathematical proofs so that they can be checked for correctness and manipulated by computer is a recurrent proposal, most notably stated in the QED manifesto (1994). The December 2008 ...
8
votes
5
answers
1k
views
Examples of left reversible semigroups
I am looking for concrete examples of cancellative, left reversible semigroups. Left reversible semigroups are also called "Ore semigroups". See this wikipedia page for the definition of a left ...
- 550
23
votes
8
answers
2k
views
Can we disallow finite choice?
When people work with infinite sets, there are some who (with good reason) don't like to use the Axiom of Choice. This is defensible, since the axiom is independent of the other axioms of ZF set ...
- 12.6k
14
votes
9
answers
3k
views
Is there a non self-referencing non-computable function?
I've seen in college that some functions are not computable.
The proof for that was the case of Halt(x,y) function.
The thing is, the proof used a very artificial (IMHO) case
which is evaluating ...
- 317