0
votes
0answers
73 views

Rank function and closure operator for a set system

I would like to trace the concepts "rank function" and "closure operator" back to some structures as primitive as possible. For a set system $(E,F)$ which is an independence system or a greedoid, I ...
4
votes
1answer
215 views

Circulant matrix with integer entries and determinant 1 or -1

CONJECTURE Let $A= (c_0,c_1,\ldots,c_n)$ be a circulant matrix, i.e if $(c_0,c_1,\ldots,c_n)$ is the first column of $A$ then the $i$th column of $A$ is obtained by applying the permutation ...
4
votes
3answers
407 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
278 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
348 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
466 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$ ...
5
votes
2answers
136 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
642 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
372 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
172 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
571 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
179 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
424 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
499 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
130 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
942 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
14k 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
203 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
190 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
481 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
325 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
829 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})$ ...
6
votes
2answers
578 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 ...
18
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
217 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
648 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
145 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
471 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
287 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
481 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
465 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
381 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
542 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 ...
9
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
936 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 ...
-1
votes
1answer
409 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 ...