Skip to main content
MathOverflow

Return to Answer

fixed typo
Source Link
Sam Zbarsky
Sam Zbarsky
  • 1.2k
  • 6
  • 12

2 approaches:

  1. Generate $b$ randomly, having $b(n)$ be $0$ with probability $1/2$ and having each $b(n)$ be independent. Then for each $(a,b)$ and $(a_1,b_1)$, the probability that $$ b\circ f_{a,b}=b\circ f_{a_1,b_1} $$ is $0$. Summing over all countably many such pairs, we still get a probability of $0$, so with probability $1$, our string works.

  2. Generate $b$ greedily. Go through pairs $(a,b,(a_1,b_1)$$(a,b),(a_1,b_1)$ in some order and for each, choose two entries in our string very far out to force disagreement.

2 approaches:

  1. Generate $b$ randomly, having $b(n)$ be $0$ with probability $1/2$ and having each $b(n)$ be independent. Then for each $(a,b)$ and $(a_1,b_1)$, the probability that $$ b\circ f_{a,b}=b\circ f_{a_1,b_1} $$ is $0$. Summing over all countably many such pairs, we still get a probability of $0$, so with probability $1$, our string works.

  2. Generate $b$ greedily. Go through pairs $(a,b,(a_1,b_1)$ in some order and for each, choose two entries in our string very far out to force disagreement.

2 approaches:

  1. Generate $b$ randomly, having $b(n)$ be $0$ with probability $1/2$ and having each $b(n)$ be independent. Then for each $(a,b)$ and $(a_1,b_1)$, the probability that $$ b\circ f_{a,b}=b\circ f_{a_1,b_1} $$ is $0$. Summing over all countably many such pairs, we still get a probability of $0$, so with probability $1$, our string works.

  2. Generate $b$ greedily. Go through pairs $(a,b),(a_1,b_1)$ in some order and for each, choose two entries in our string very far out to force disagreement.

Source Link
Sam Zbarsky
Sam Zbarsky
  • 1.2k
  • 6
  • 12

2 approaches:

  1. Generate $b$ randomly, having $b(n)$ be $0$ with probability $1/2$ and having each $b(n)$ be independent. Then for each $(a,b)$ and $(a_1,b_1)$, the probability that $$ b\circ f_{a,b}=b\circ f_{a_1,b_1} $$ is $0$. Summing over all countably many such pairs, we still get a probability of $0$, so with probability $1$, our string works.

  2. Generate $b$ greedily. Go through pairs $(a,b,(a_1,b_1)$ in some order and for each, choose two entries in our string very far out to force disagreement.