All Questions
6,026 questions
7
votes
2
answers
370
views
Wants: Polynomial Time Algorithm for Decomposing a Multiset of Rationals into Two Additive Subsets.
First, allow me to say that this problem was posed to me by a professor in the department. It is related to his research in a way that I do not know. However, since I couldn't come up with anything ...
- 4,842
9
votes
1
answer
991
views
Model of ZF + $\neg$C in which Solovay's Theorem on stationary sets fails?
It is a theorem of Solovay that any stationary subset of a regular cardinal, $\kappa$ can be decomposed into a disjoint union of $\kappa$ many disjoint stationary sets. As far as I know, the proof ...
- 1,174
0
votes
2
answers
891
views
Axiom of Choice and Order Types
A beginner's question:
We know: "Since order-equivalence is an equivalence relation, it partitions the class of all sets into equivalence classes." (from Wikipedia)
This holds since every set can be ...
- 9,720
4
votes
2
answers
551
views
Normality of an affine semigroup
An affine monoid is a finitely generated commutative submonoid of $\mathbb Z^k$ for some positive integer k. Let S be an affine monoid and let G(S) be the group generated by S. We say the monoid S is ...
- 111
4
votes
5
answers
3k
views
Is reflexivity of equality an axiom or a theorem?
Everybody knows that equality is reflexive: $\forall(x)(x=x)$. But should reflexivity of equality be taken as an axiom of logic or as a theorem of set theory?
If you choose the former then you ...
- 737
0
votes
4
answers
6k
views
Are all mathematical theorems necessarily true?
Define a formal tautology as a statement where by the nature of its atomic components there exists no truth-value assignment where it is not true. A contingent statement is a statement that is true by ...
- 69
16
votes
0
answers
626
views
To what extent does (co)homology of groups made discrete depend on set theory?
There's a well-known paper by Milnor, "On the homology of Lie groups made discrete," that discusses the relation between the homology of a Lie group $G$ and the underlying discrete group $G^\delta$. ...
- 52.6k
6
votes
2
answers
522
views
addition of definable numbers decidable?
Define a number generating machine to be a total turing machine running on input alphabet {0,1} (or, any ary), that given input n (in binary) outputs a digit (binary or decimal or whatever).
Given ...
- 119
23
votes
4
answers
2k
views
Can we recognize when a category is equivalent to the category of models of a first order theory?
Many of the most canonical early examples of categories
arise as the collection of models of a fixed first order
theory, with the related model-theoretic concept of
homomorphism. For example, the ...
- 236k
2
votes
1
answer
237
views
term equality in algebraic theories
For algebraic theories how relevant is the underlying logic? Is it possible that two terms $s$ and $t$ can be shown to be equal with respect to one set of logical axioms but not necessarily so with ...
user577
113
votes
2
answers
16k
views
Does every non-empty set admit a group structure (in ZF)?
It is easy to see that in ZFC, any non-empty set $S$ admits a group structure: for finite $S$ identify $S$ with a cyclic group, and for infinite $S$, the set of finite subsets of $S$ with the binary ...
- 3,511
6
votes
5
answers
2k
views
Set theories that do require the existence of urelements?
I am looking for an axiomatic set theory that not only admits the existence of urelements/atoms (via two-sortedness or an additional unary predicate) but requires it, e.g. by an axiom like "for each ...
- 9,720
27
votes
3
answers
2k
views
Using consistency to create new axioms in set theory
As everybody knows, the ZFC axioms may serve as a foundation for (almost)
all of contemporary mathematics, and it is also well-known that several results
are "indecidable" in ZFC, which means that ...
- 3,595
28
votes
2
answers
7k
views
Large cardinal axioms and Grothendieck universes
A cardinal $\lambda$ is weakly inaccessible, iff a. it is regular (i.e. a set of cardinality $\lambda$ can't be represented as a union of sets of cardinality $<\lambda$ indexed by a set of ...
- 23.5k
3
votes
3
answers
266
views
Name for "lower/upper bounds" of arbitrary relations?
Given a partial order $R_{\leq}$ over a set $D$, the set of upper bounds under $R$ of a subset $S$ of $D$ is commonly defined as $\{ y \in D | \ \forall x\in S, x R y \}$.
(The set of lower bounds of ...
- 53
10
votes
3
answers
1k
views
Is set-induction relatively consistent?
One way to state the axiom of foundation is that the $\in$ relation on any transitive set is well-founded in the following sense:
A relation $(X,\prec)$ is well-founded if for any subset $S\subseteq ...
- 66.8k
2
votes
3
answers
2k
views
definition of the set of natural numbers
How can the set $N$ of natural numbers be defined from the point of view of the ZF axiomatic set theory provided the concept of inductive set? Hrbacek-Jech (page 41) says that $N=\{x\in A:\forall(I)(x\...
- 31
29
votes
3
answers
3k
views
Is the theory of categories decidable?
There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
24
votes
1
answer
3k
views
When does collection imply replacement?
In ordinary membership-based set theory, the axiom schema of replacement states that if $\phi$ is a first-order formula, and $A$ is a set such that for any $x\in A$ there exists a unique $y$ such that ...
- 66.8k
3
votes
2
answers
912
views
Why is every finite set Diophantine? [closed]
I understand that every finite set is recursively enumerable, as I see that one could just encode each element of some finite set on a Turing Machines tape, and then have the machine check each member ...
4
votes
2
answers
1k
views
Is every model of ZF countable "seen from the outside"?
I'm not sure if my question make sense, but it would also be interesting to know if it didn't, so I will ask anyway:
There exist a countable model of ZF. This means (if I understand it correctly) ...
- 1,593
-2
votes
1
answer
519
views
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]
Cardinal Equivalence Theorem
For each boolean formula, |quantifications| = |assignments|.
The set of valid quantifications has some cardinality, call that |Q(B)...
40
votes
3
answers
5k
views
Is there a computable model of ZFC?
Background
Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being ...
63
votes
8
answers
16k
views
Reductio ad absurdum or the contrapositive?
From time to time, when I write proofs, I'll begin with a claim and then prove the contradiction. However, when I look over the proof afterwards, it appears that my proof was essentially a proof of ...
4
votes
3
answers
527
views
Can infinite first-order categories be specified other than as categories of models?
I am glad to see that a general question like Is there a relationship between model theory and category theory? receives quite a lot attention and no down-votes for being too general and unspecific. ...
- 9,720
25
votes
7
answers
10k
views
Is there a relationship between model theory and category theory?
According to Chang and Keisler's "Model Theory", Model Theory = Universal Algebra + Logic. Model theory generalized Universal Algebra in the sense that we allow relations while in Universal Algebra we ...
- 2,824
46
votes
15
answers
11k
views
Strong induction without a base case
Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication
"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."
for ...
12
votes
3
answers
7k
views
Is functional programming a branch of mathematics?
In Theory mainly concerned with lambda-calculus?, F. G. Dorais wrote, of the idea that the lambda-calulus defines a domain of mathematics:
That would never stick unless there's another good reason. ...
3
votes
5
answers
2k
views
Theory mainly concerned with $\lambda$-calculus?
Automata theory is mainly concerned with Turing machines and all its relatives-in-spirit. $\lambda$-calculus is rather rarely mentioned in textbooks on automata theory.
What's the common name of the ...
- 9,720
2
votes
2
answers
772
views
In what sense Fraissean view point shows Model Theory can be done without any formal syntax and deduction rule?
In this post I want to look at an issue I was in doubt when looking at the comment of F. G. Dorais in the post In model theory, does compactness easily imply completeness?
F. G. Dorais remark was:
...
- 2,824
12
votes
2
answers
1k
views
Where are we working when we prove metamathematical theorems?
I am posting my comment from this question as a separate question, as was recommended to me.
(EDIT: I'm sorry if it ended up being too similar a question, I just wanted to phrase it in the ...
- 6,792
13
votes
4
answers
2k
views
Is it possible for countably closed forcing to collapse $\aleph_2$ to $\aleph_1$ without collapsing the continuum?
Suppose the continuum is larger than $\aleph_2$. Does there exist a countably closed notion of forcing that collapses $\aleph_2$ to $\aleph_1$, but does not collapse the continuum to $\aleph_1$? ...
- 1,174
9
votes
4
answers
820
views
How much of the current logic is about syntax?
The basic logic course in school gives the impression that logic has both the syntax and the semantics aspects. Recently, I wonder whether the syntax part still plays an essential role in the current ...
- 2,824
8
votes
1
answer
585
views
a proof that L_min is not in coRE?
Define $L_{min}$ to be the language of all minimal Turing machines, in some standard encoding. (A Turing Maching is minimal if it has the shortest encoding among all the TMs recognizing the same ...
135
votes
43
answers
38k
views
What are the most attractive Turing undecidable problems in mathematics?
What are the most attractive Turing undecidable problems in mathematics?
There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
8
votes
4
answers
630
views
closure of separative quotients
Does there exist a partial order, nontrivial for forcing, that is countably closed, but whose separative quotient is not countably closed? Supposing the answer is yes, then is there a partial order, ...
- 1,174
20
votes
3
answers
3k
views
On statements independent of ZFC + V=L
Let $V=L$ denote the axiom of constructibility. Are there any interesting examples of set theoretic statements which are independent of $ZFC + V=L$? And how do we construct such independence proofs? ...
- 9,641
6
votes
1
answer
700
views
What notions of universe does predicative type theory admit?
Palmgren (1997), On universes in type theory, discusses work of several theorists that provide what we might call a family of Large Universe Axioms (LUAs) for predicative type theory, culminating in ...
- 2,283
4
votes
1
answer
734
views
Parametric polynomial solution of a single polynomial equation
Let $P$ be a polynomial in $n$ variables with rational coefficients,
$P \in {\mathbb Q}[Z_1,Z_2, \ldots ,Z_n]$, and consider the algebraic
set
$Z=\lbrace (z_1,z_2,z_3, \ldots ,z_n) \in {\mathbb Q}^n |...
- 3,595
60
votes
8
answers
6k
views
Is the ultraproduct concept fundamentally category-theoretic?
Once again, I would like to take advantage of the large number of knowledgable category theorists on this site for a question I have about category-theoretic aspects of a fundamental logic concept.
My ...
- 236k
13
votes
3
answers
978
views
Model Structure/Homotopy Pushouts in topological monoids?
Let $\mathsf C$ be the category of topological monoids, that is, the category of monoids in $(\textsf{Top}, \times)$.
Can the model category structure on $\textsf{Top}$ (Serre fibrations, ...
- 1,033
8
votes
2
answers
741
views
elementary equivalence of infinitary symmetric groups
Two questions:
Suppose a and b are two uncountable cardinals. Consider the symmetric groups on sets of sizes a and b respectively (the symmetric group on a set is the group of all bijections from the ...
- 7,320
47
votes
4
answers
4k
views
Which topological spaces admit a nonstandard metric?
My question is about the concept of nonstandard metric space that would arise from a use of the nonstandard reals R* in place of the usual R-valued metric.
That is, let us define that a topological ...
- 236k
20
votes
5
answers
2k
views
Isomorphism types or structure theory for nonstandard analysis
My question is about nonstandard analysis, and the diverse possibilities for the choice of the nonstandard model R*. Although one hears talk of the nonstandard reals R*, there are of course many non-...
- 236k
4
votes
3
answers
1k
views
Logical problems in category theory [duplicate]
Possible Duplicate:
Set theory for category theory beginners
It is frustrating to hear people speak of Yoneda embedding, category of all categories/functors, n-categories, infinity categories and ...
- 7,442
14
votes
1
answer
2k
views
When are epimorphisms of algebraic objects surjective?
Let $C$ be the category of $\tau$-algebras for some type $\tau$. Consider the statements:
Every monomorphism is regular.
Every epimorphism in $C$ is surjective.
It is easy to see that 1. implies 2. ...
- 63.1k
30
votes
6
answers
6k
views
In set theories where Continuum Hypothesis is false, what are the new sets?
So, say we are working with non-CH mathematics. This means, AFAIK, that there is at least one set $S$ in our non-CH mathematics, whose cardinality is intermediate between $|\mathbb{N}|$ (card. of ...
- 303
24
votes
2
answers
1k
views
Which are the rigid suborders of the real line?
Which are the rigid suborders of the real line?
If A is any set of reals, then it can be viewed as an order structure itself under the induced order (A,<). The question is, when is this structure ...
- 236k
26
votes
3
answers
7k
views
Presburger Arithmetic
Presburger arithmetic apparently proves its own consistency. Does anyone have a reference to an exposition of this? It's not clear to me how to encode the statement "Presburger arithmetic is ...
- 464
7
votes
1
answer
2k
views
Polynomial representing prime numbers
Along the lines of Polynomial representing all nonnegative integers, but likely well-known question:
is there a polynomial $f \in \mathbb Q[x_1, \dots, x_n]$ such that $f(\mathbb Z\times\mathbb Z\...
- 15.1k