4
votes
3answers
391 views

Infinite Partitions of the Primes and Sums of Reciprocals (Revised)

I have revised my original post. The questions I asked there were not well-put or even thought through. I don't want to delete, however, since some of the comments may be of interest to other MO ...
7
votes
2answers
266 views

Elementary Submodels in Partitions Theorems

I'am reading the paper Elementary Submodels in Infinite Combinatorics from Soukup (http://eprints.renyi.hu/45/1/elementary_submodels_revised.pdf) and there are a lot of proofs using elementary ...
2
votes
1answer
338 views

Maximal size of an almost-disjoint linearly independent family in $K^{\mathbb{N}}$

Let $K$ be a field, say infinite, and denote by $L$ the $K$-vector space $K^{\mathbb{N}}$. What is the maximal cardinality of a $K$-linearly independent subset $X$ of $L$ such that any two distinct ...
10
votes
1answer
449 views

Why does the generalised Galvin-Prikry Theorem only hold at Ramsey cardinals?

The Galvin-Prikry theorem says that Borel sets are Ramsey. This means that for every Borel set $S\subseteq[\omega]^\omega$, there is an $A\in\[\omega]^\omega$ such that either $[A]^\omega \subseteq S$ ...
4
votes
2answers
133 views

If $\kappa \rightarrow (\alpha)^r_2$ holds for every $r\in \omega$, then is $\kappa$ an $\alpha$-Erdős cardinal?

If $\kappa \rightarrow (\alpha)^r_2$ holds for every $r\in \omega$, then is $\kappa$ an $\alpha$-Erdős cardinal? (or rather, does $\kappa \rightarrow (\alpha)^{<\omega}_2$ hold?) $\kappa ...
22
votes
1answer
609 views

Does an existence of large cardinals have implications in number theory or combinatorics?

Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...
6
votes
2answers
368 views

Partition relation, almost a Ramsey cardinal?

Is it consistent with ZFC to have a cardinal $\kappa$ which is not Ramsey and $\kappa \rightarrow [\kappa]^{<\omega}_{\omega,n}$ holds for some $n\in \omega$? The partition relation $\kappa ...
6
votes
1answer
164 views

Models of ZFA corresponding exactly with a particular class of groups

I recently read [1], in which Blass exhibits a correspondence between: Permutation models of ZFA in which the axiom of choice (AC) fails but the Boolean prime ideal theorem (BPIT) holds; and ...
16
votes
1answer
503 views

Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
3
votes
2answers
177 views

Terminology for generalized relations

I have a simple terminology request: recall that given sets $A$ and $B$, a relation $R$ from $A$ to $B$ is any subset of the product $A \times B$. Thus, one may view a relation as a function $A \times ...
10
votes
3answers
407 views

Applications of idempotent ultrafilters

Recently Justin Moore has posted a solution to the amenability of Thompson's group F. A key(?) step exploits the existence of idempotent ultrafilters on $\mathbb N$ to construct an idempotent measure ...
0
votes
2answers
454 views

How to easy calculate card of union of sets? [closed]

For example I have sets A={2,3,4} B={3,4,5} C={1,2,3} for some reason I can't do |AUBUC|, only what i can do is calculate |A|, |B|, |C|. How do I do to ...
1
vote
0answers
129 views

Is there a name for this property in set-valued analysis?

Consider a set-valued, finite-valued map $F$ from a set $X$ to subsets of $X$. Consider the following property: $|F(x)| \geq |F(y)|$ for all $x,y$ such that $y \in F(x)$. I have defined this property ...
17
votes
1answer
910 views

Number of distinct values taken by $\alpha$ ^ $\alpha$ ^ $\dots$ ^ $\alpha$ with parentheses inserted in all possible ways, $\alpha\in\mathbf{Ord}$

Let $\alpha\in\mathbf{Ord}$ and $n\in\mathbb{N}^+$. Let $F_\alpha(n)$ be the number of distinct values taken by ordinal exponentiation $\underbrace{\alpha \hat{\phantom{\hat{}}} \alpha ...
19
votes
5answers
11k views

How large is TREE(3) ?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...
2
votes
1answer
89 views

“Stably” finite-fiber maps of the integers

Suppose $\varphi:\mathbb{N}\rightarrow\mathbb{N}$ is a finite-to-one map. We can then define a function $\varphi_1:a\mapsto |\varphi^{-1}(a)|$. If this function is finite-to-one, we can similarly ...
3
votes
1answer
198 views

Lower bounding the maximum size of sets in a set family with union promise

The following problem has come up while working on the relationship between certificate and randomized decision tree complexities of boolean functions. However, I think it is of interest by itself and ...
0
votes
0answers
188 views

How many minimal pair-wise coverings can there be?

Suppose I have a set of finite sets: $X = \{V_1, V_2, V_3\}$ where each set called $V_i$ in $X$ contains a number of symbols (i.e. $V_1 = \{a,b,c\}$). $Z$ contains all of the Cartesian products of ...
3
votes
2answers
474 views

Is there Ramsey Theorem for infinitary tuples?

I'm wondering if there's any sort of Ramsey relation that allows for the tuples to be of arbitrary infinite size $\mu$? This $\mu$ is below some strongly compact cardinal, so I'm not worried about ...
8
votes
1answer
315 views

Decomposing posets into countably many chains

A conjecture of Galvin's is that the following is possible (which I take to mean that the consistency of the following can be proven relative to the consistency of something like ZFC, or ZFC plus some ...
7
votes
3answers
815 views

Singular Cardinals, and A Strange Question.

Let $\mu$ be any infinite cardinal, and define a collection $N\subset[\mu]^\mu$ to be, maximal almost disjoint (MAD) over $\mu$, iff $\forall\{A,B\}\in[N]^2$ $( A\cap B \in [\mu]^{<\mu})$ ...
5
votes
1answer
495 views

Given a cardinal k, what's the biggest dense linear order with a dense subset of size k?

It's not hard to show that for any cardinal $\kappa$, there is no dense linear order without endpoints (DLO) of size greater than $2^{\kappa}$ that has a dense subset of size $\kappa$. But one can ...
16
votes
2answers
2k views

Cantor's argument revisited

This was inspired by this recent question. In my answer there, I pointed out that, given $F:{\mathcal P}(X)\to X$, an argument dating back to Zermelo allows us to define a pair $(A,B)$ of distinct ...
3
votes
1answer
212 views

A small collection of large subsets covering all small subsets.

Let $r,s,n$ be positive integers with $r < s < n$. Let $U = \{1,\ldots,n\}$. Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that ...
1
vote
1answer
638 views

Infinite graphs as functional operators

Original Question Consider an infinite tree of constant degree $k$. For such a tree we can consider the total number of nodes at depth $n$, $g(f)$, and the total number of paths from the root, ...
2
votes
1answer
142 views

Inverse formula for counting marginals

I am interested in a formula which relating two functions over a multiset. I have a multiset $X$ of sets where each element in $X$ is a set $x \subseteq \{1,2,\ldots,m\}$. Now I have two ``count'' ...
8
votes
1answer
452 views

monochromatic cycle-free colouring of the complete graph on R?

Hi So there is an edge-colouring of a complete graph on R (the reals), with countably many colours that as no monochromatic triangle. To find it map R to (0,1) write the numbers in binary and if 2 ...
4
votes
1answer
286 views

Subsets of sequences of natural numbers vs. strategies under ZFC

This question is related to a previous question of mine: Determinacy interchanging the roles of both players Given any set A of sequences of natural numbers, every strategy (no matter for which ...
3
votes
2answers
476 views

Determinacy interchanging the roles of both players

Let me refer to Jech's "Set Theory" Chap. 33 Determinacy: "With each subset A of $\omega^\omega$ we associate the following game $G_A$, played by two players I and II. First I chooses a natural ...
10
votes
1answer
456 views

I am searching for the name of a partition (if it already exists)

I derived this definition by searching for a representation of a family of sets. I am quite sure that someone should have thought to this before, because it seems to be quite straightforward given a ...
4
votes
2answers
377 views

A family of subsets with a “gluing” property

Somewhat in line with this previous MathOverflow question: I'm looking at a combinatorial structure consisting of a finite set $S$ of objects, and a family $F$ of designated subsets of $S$. We call ...
4
votes
3answers
537 views

Minimum cover of partitions of a set

Given $n,k\in\mathbb{N}$ where $k\leq n$, I want to compute the minimum subset of the set of partitions of $N$={$1,\ldots,n$}, satisfying these properties: Each block of every partition has at most ...
8
votes
4answers
1k views

the delta system lemma outside set theory

The lemma: Any uncountable set $S$ of finite sets has an uncountable subset $\Delta \subseteq S$ and an $x$ such that $\forall a,b \in \Delta$, if $a \neq b$ then $a \cap b = x$. $\Delta$ is called a ...
5
votes
4answers
2k views

Examples of inductive proofs that can be generalized by transfinite induction

Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial ...
4
votes
3answers
905 views

Pigeonhole Principle for infinite case

Suppose $X_n$ are finite sets for any natural integer $n$. let $Y$ be an infinite subset of $\prod_n X_n$. Do there exist $y$ and $y'$ in $Y$ and an infinite subset $S$ of $\mathbb N$ such that ...
0
votes
1answer
391 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 ...
10
votes
1answer
2k views

Collection of subsets closed under union and intersection

Suppose A is a set and S is a collection of subsets closed under arbitrary unions and intersections. Can we find a collection F of functions from A to itself such that a subset B of A is in S if and ...
12
votes
6answers
1k 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 ...