# Tagged Questions

**3**

votes

**1**answer

304 views

### “the” random permutation

I recently looked at Permutations on the random permutation which seems to talk about the notion of random permutuation as a notion from logic rather than probability.
The random permutation is ...

**0**

votes

**0**answers

89 views

### topological space of Wang Tile

When trying to reprove a theorem in Wang tile:
An established proof in Wang Tile which I doubt
, a few notions are provided which I would like to seek for more information:
For a given set of blocks ...

**3**

votes

**3**answers

731 views

### An established proof in Wang Tile which I doubt

When I was reading the paper:
Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305.
from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf
I could not ...

**6**

votes

**1**answer

274 views

### Is there a name for infinite words containing every finite words?

Apparently, the closest thing I've found would be normal number http://mathworld.wolfram.com/NormalNumber.html
But requiring that every finite words occurs is weaker than this property. So I'm ...

**3**

votes

**0**answers

119 views

### characterization of all periodic tiling of a simple set of Wang Tile

Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set.
Now, I wish to characterize all the periodic tilings of this set (better if they are ...

**10**

votes

**1**answer

453 views

### Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq:
Gonthier, Georges. Formal proof—the four-color theorem.
Notices Amer. ...

**2**

votes

**1**answer

98 views

### relationship between corner tile and edge tile of wang tile

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.
However, could we convert edge type of Wang Tile ...

**3**

votes

**1**answer

147 views

### Proof of existence of recursively inaccessible and Mahlo ordinals

As in title - I'm looking for a proof of the existence of a countable recursively inaccessible or recursively Mahlo ordinals, especially the first one. When looking for it in all the papers I stumbled ...

**4**

votes

**1**answer

345 views

### Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...

**4**

votes

**2**answers

186 views

### Conjecture of a subset of Wang tile which might be decidable

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...

**2**

votes

**1**answer

227 views

### A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of ...

**4**

votes

**1**answer

186 views

### Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate.
Is the Van der Waerden's function itself elementary in the sense of Kalmar?

**3**

votes

**0**answers

200 views

### Binary search with maximum consecutive lies about “is X in subset S?”

Here's the original problem:
Alice tells Bob "I have thought of an integer between 1 and 2000. Tell
me 1000 numbers. If your set contains my number, I'll give you this
prize." Bob really wants ...

**8**

votes

**4**answers

407 views

### Order-independent properties arising naturally in mathematics

The motivation for the following question comes from finite model theory,
but it is not a technical question about this field,
and it is particularly directed at people working in other fields.
It ...

**9**

votes

**1**answer

413 views

### A conjecture on intersection of some intervals.

It was proved here that if $a\in \mathbb{N}_{\geq3}$ then
$$\bigcap_{i = 1}^{a} \bigcup_{j = 0}^{i-1} \left[\frac{1+aj}{i},\frac{a(j+1)-1}{i}\right] = \varnothing \tag{1}$$
It may be conjectured ...

**8**

votes

**2**answers

684 views

### Sperner's lemma and Tucker's lemma

In their article "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" (American Mathematical Monthly, April 2013), Nyman and Su write "[W]e are unaware of a direct proof that Tucker's ...

**22**

votes

**4**answers

1k views

### In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?

I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems ...

**2**

votes

**1**answer

123 views

### On the Combinatorial Classification of Modal Kripke Frames

We have that S5 modal logic is characterized by the modal axioms $K$, $M$ (reflexive), $4$ (transitive), and $B$ (symmetric). That is, an equivalence relation on a set of possible world (which can be ...

**6**

votes

**1**answer

170 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

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

**9**

votes

**6**answers

1k views

### Non-constructive proofs vs. efficient algorithms

My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof begins, "a constructive ...

**2**

votes

**1**answer

165 views

### A categorical framework for Freiman s-morphisms

Let $\mathfrak A_i$ be groups ($i = 1, 2$), written multiplicatively, and $s$ a non-negative integer (here, as usual, I am abusing notation and denoting the operations of $\mathfrak A_1$ and ...

**4**

votes

**2**answers

416 views

### $\beta\mathbb{N}$ vs $\beta\mathbb{Z}$

Just started learning the Stone-Cech compactification of discrete groups this week. My motivation comes from a question on $\beta\mathbb{Z}$. Surprisingly, I realized there are muchhhh more literature ...

**9**

votes

**1**answer

437 views

### Constructing an injective reduction of equivalence relations

[Metastuff: I asked this question in a slightly different way on mathSE last week, and it didn't go anywhere, which is why I am asking here. I added the DST tag because it's basically a problem about ...

**15**

votes

**4**answers

760 views

### Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem:
Show, for all integers $1 \leq i \leq k$, that the univariate ...

**19**

votes

**5**answers

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

**11**

votes

**2**answers

4k views

### What is “Seetapun Enigma”?

A friend of mine just asked me this very question. While I had some training in combinatorics, I have never heard of the "Seetapun Enigma", which, supposedly, is related to the Ramsey's theorem. A ...

**5**

votes

**1**answer

233 views

### Existence of 'uniform transformations' of sequences of rationals (apres Friedman)

Let $\mathbb{Q}^*$ be the set of finite sequences of rationals, and let $x \sim y$ if and only if
they have the same length, and for all $1 \le i,j \le length(x)$, $x_i \lt x_j$ iff $y_i \lt y_j$ ...

**3**

votes

**2**answers

803 views

### Are context-free languages with context-free complements necessarily deterministic context-free?

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.
If $L$ and $L'$ are both context-free, are ...

**17**

votes

**6**answers

2k views

### undecidable sentences of first-order arithmetic whose truth values are unknown

Godel's undecidable sentences in first-order arithmetic were guaranteed to be true, by construction. But are there examples of specific sentences known to be undecidable in first-order arithmetic ...

**3**

votes

**2**answers

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

**5**

votes

**1**answer

520 views

### Characterization of infinite paths in graphs

First an introduction.
A directed graph we all know what is, and a graph is serial whenever
every vertex has a successor. I do not consider the empty graph. A
pair $(\mathcal{G},s)$ is called a ...

**1**

vote

**0**answers

180 views

### Maximizing the number of 'correct' literals in planar monotone 3SAT

I'm trying to find the complexity of this optimization problem:
Given an instance of planar monotone 3SAT, with positive clauses $C_i = v_{i1} V v_{i2} V v_{i3}$ and negative clauses $D_i = ...

**3**

votes

**1**answer

747 views

### Does BQP^P = BQP ? … and what proof machinery is available?

Update #3:
Over on TCS StackExchange, I have rated as "accepted" an ingenious construction by Luca Trevisan, which answers a two-part question (as reframed by Tsuyoshi Ito) that is in essence "Do ...

**7**

votes

**3**answers

822 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})$
...

**9**

votes

**2**answers

2k views

### Quantum PCP Theorem

Although I think I know the answers to these, I'd just like to collect them all in one place.
What is the quantum PCP theorem, what implications does its proof have for simulation of Hamiltonians and ...

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

**19**

votes

**2**answers

1k views

### Is there a name for a family of finite sequences that block all infinite sequences?

Let ${\bf N}^\omega = \bigcup_{m=1}^\infty {\bf N}^m$ denote the space of all finite sequences $(N_1,\ldots,N_m)$ of natural numbers. For want of a better name, let me call a family ${\mathcal T} ...

**12**

votes

**7**answers

688 views

### Replacing logician-constructive with combinatorist-constructive?

Logicians interpret the word "constructive" in a very well-defined way: they take it to mean, more or less, "computability". Taking constructivity seriously and working in a world where everything ...

**27**

votes

**2**answers

625 views

### What is the minimal size of a partial order that is universal for all partial orders of size n?

A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds
order-preservingly into $\mathbb{B}$.
For example, every partial order
...

**3**

votes

**1**answer

187 views

### characterization of regular languages among (say) those computable in linear time

For a given language A let A(n) denote the number of words in A of length smaller or equal to n. It is know that if A is a regular language then the function $ f(x) = \sum_{i=0}^\infty A(n)x^n$ is in ...

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

920 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

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

**32**

votes

**15**answers

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

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