November 6th, 2018, 04:48 AM  #1 
Senior Member Joined: Jun 2014 From: USA Posts: 528 Thanks: 43  Today's Fun
Sometimes I like to think of a little question in the morning and ponder it here and there throughout the day. I'm sure there is probably a fairly easy answer to the following and I'll come up with it later, but until then I thought I would share 'today's fun' with the forum if anyone cares to take a crack at it too. Let $A$ equal the set of infinite binary strings. Let $B$ equal the set of finite binary strings. Let $f: A \rightarrow C$ be bijective (where, trivially, $C$ is simply the image of function $f$ across $A$): $$f(x = x_1x_2x_3\dots) = \{ x_1, x_1x_2, x_1x_2x_3, \dots \} $$ $$\text{E.g., }f(10101...) = \{ 1, 10, 101, 1010, 10101, \dots \} $$ Question: Is it possible to have a subset $T$ of $A$ where: $$1) \bigcup f\{T\} = B \text{, and }$$ $$2) \text{ omitting any one element } q \text{ of } f\{T\} \text{ from the union would imply that } \bigcup (f\{T\} \setminus \{q\}) \neq B \text{.}$$ 
November 7th, 2018, 08:00 AM  #2 
Senior Member Joined: Jun 2014 From: USA Posts: 528 Thanks: 43 
It seems that no set $T$ having the above properties can exist. Assuming the existence of $T$ allows for a proof by contradiction. If there is an $x \in T$ such that $\bigcup (f\{T\} \setminus \{f(x)\}) \neq B$, then there must be an infinite subset of $f(x)$ that is not a subset of $\bigcup(f\{T\} \setminus \{f(x)\})$. Such an infinite subset of $f(x)$ implies that $\bigcup f\{T\} \neq B$ because some elements of $B$ that are not in $f(x)$ must also not be in $\bigcup (f\{T\} \setminus \{f(x)\})$. Last edited by AplanisTophet; November 7th, 2018 at 08:06 AM. 
November 7th, 2018, 10:59 AM  #3 
Global Moderator Joined: Dec 2006 Posts: 20,919 Thanks: 2202 
As you haven't explained why your two uses of "must" are correct, your reasoning can't be checked in detail.

November 7th, 2018, 01:24 PM  #4 
Senior Member Joined: Jun 2014 From: USA Posts: 528 Thanks: 43  Sorry, I wasnâ€™t looking for a check on my reasoning here, but I am happy to post the proof instead of just the mere overview above if anyone is curious.

November 8th, 2018, 05:07 AM  #5  
Senior Member Joined: Jun 2014 From: USA Posts: 528 Thanks: 43  Quote:
Quote:
By the definition of $T$, we're given that $\exists x \in T$ such that $\bigcup (f\{T\} \setminus \{f(x)\}) \neq B$. We can then list the elements of $f(x)$ by their length so as to find the first element of the list, $x_j$, such that $x_j \notin \bigcup (f\{T\} \setminus \{f(x)\})$. Where $x_j$ is not in the union, we know that $x_{j+i}$ is also not in the union for any $i \in \mathbb{N}$ (this is because $x_{j+i}$ can only be in the union if $x_j$ is in the union by the definition of function $f$). We are left with our infinite subset of $f(x)$ that is not a subset of $\bigcup(f\{T\} \setminus \{f(x)\})$: $$\{ x_i \in f(x) : i \in \mathbb{N} \text{ and } i \geq j \}$$ Quote:
If $b \in B$, $b \notin f(x)$, and $b \notin \bigcup (f\{T\} \setminus \{f(x)\})$, then $\bigcup f\{T\} \neq B$. This is a contradiction because $\bigcup f\{T\} = B$ by the definition of $T$, so $T$ cannot exist.  

Tags 
fun, today 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
promise last one for today, 3+x/3 >= x/51  GIjoefan1976  Algebra  3  October 24th, 2016 01:12 AM 
good day today  goodlooking  Geometry  1  April 2nd, 2015 07:10 AM 
I need help please for today :)  Queen  Elementary Math  2  September 11th, 2009 10:42 AM 
i need this one for school today (please)  croatiandan  Calculus  2  October 23rd, 2007 04:32 AM 