Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options not deleted user 172802

Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.

42 votes
2 answers
2k views

How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?

This is a follow-up to this question by Dominic van der Zypen. For each bijection $f:\mathbb{N}\to\mathbb{N}$, let $$\operatorname{rc}(f) := \liminf_{N\to\infty} \frac{\left|\left\{(m,n)\in\{1,\dots,N …
Saúl RM's user avatar
  • 10.6k
11 votes
Accepted

Min–max reversing bijections $f:\mathbb{N}\to\mathbb{N}$

$\newcommand\N{\mathbb N}$No, it is not possible to have $\mu_{[\N]^2}\big({\operatorname{rev}(f)}\big) = 1$. Given the function $f$, we will say that $n\in\mathbb{N}$ is good if $f(n)<f(k)$ for more …
Saúl RM's user avatar
  • 10.6k
7 votes
Accepted

Shrinking and expanding pairs in bijections $\varphi:\mathbb{N}\to\mathbb{N}$

One has $\max\big\{\mu\big(\exp(\varphi)\big) :\varphi \in S_{\mathbb{N}}\big\}=1$, as mentioned by Emil Jeřábek in the comments. We can also create a function $\varphi$ with $\mu\big(\text{shr}(\varp …
Saúl RM's user avatar
  • 10.6k
7 votes
Accepted

Size of antichains in powerset of $\mathbb N$

Yes. Consider the countable set $\mathbb{Q}^2$ and for each $x\in\mathbb{R}$ the subset $\{(a,b)\in\mathbb{Q}^2;a\leq x,b\leq-x\}$. Edit: See some easier examples in the comment below by bof. There ar …
Saúl RM's user avatar
  • 10.6k
7 votes
Accepted

Inspired by a card game: finding a path through $[\mathbb{N}]^n$

$[\mathbb{N}]^n$, with edges between $a,b\in[\mathbb{N}]^n$ if $\#(a\cap b)=n-1$, is an infinite graph in which all vertices have infinite degree. Moreover, for any two vertices $a,b$ in $[\mathbb{N}] …
Saúl RM's user avatar
  • 10.6k