# Tagged Questions

**0**

votes

**0**answers

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

**1**answer

209 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

**3**answers

403 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

**2**answers

275 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

**1**answer

341 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

**1**answer

462 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

**2**answers

135 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

**1**answer

636 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

**2**answers

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

**1**answer

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

**1**answer

560 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

**2**answers

178 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

**3**answers

420 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

**2**answers

479 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

**0**answers

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

**1**answer

935 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

**5**answers

13k 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

**1**answer

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

**1**answer

200 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

**0**answers

189 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

**2**answers

480 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

**1**answer

323 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

**3**answers

826 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

**2**answers

577 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 ...

**17**

votes

**2**answers

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

**1**answer

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

**1**answer

645 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

**1**answer

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

**1**answer

462 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

**1**answer

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

**2**answers

477 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

**1**answer

461 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

**2**answers

380 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

**3**answers

540 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

**4**answers

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

**4**answers

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

**3**answers

924 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

**1**answer

406 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

**1**answer

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

**6**answers

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 ...