October 11th, 2018, 07:28 AM  #1 
Senior Member Joined: Jun 2014 From: USA Posts: 422 Thanks: 26  My Opus
I assume there may be something wrong and this isn't actually my opus because the result of this work is to show that two sets of equal cardinality do not have equal cardinality (a contradiction) using only standard theory that can be adapted to a model of ZF. ZF would therefore be inconsistent. 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: $$f(x = x_1x_2x_3\dots) = \{ x_1, x_1x_2, x_1x_2x_3, \dots \} $$ Let $g: A \rightarrow D$ be bijective: $$g(x = x_1x_2x_3\dots) = \{ x_1, x_1x_2, x_1x_2x_3, \dots \} \cup \{ x \}$$ Let $\mathcal{P}(B)$ denote the powerset of $B$. Let $v: \mathcal{P}(B) \rightarrow E$ be surjective: $$v(x) = \{ p \in A : f(p) \subset x \}$$ Let $w: \mathcal{P}(B) \rightarrow F$ be surjective: $$w(x) = \bigcup \{ g(p) : p \in v(x) \}$$ Let $k: \mathcal{P}(B) \rightarrow G$ be bijective: $$k(x) = x \cup w(x)$$ Let $r: D \rightarrow G$ be any arbitrary surjective function. Let $H = \bigcup \{ x \in D : x \not\subset r(x) \} \in G$ $$x \subset H \implies x \not\subset r(x) = H$$ $$x \not\subset H \implies x \subset r(x) = H$$ $$\not\exists x \in D \text{ such that } r(x) = H \implies \text{ function } r \text{ is not surjective}$$ $$D < G$$ This is a contradiction because we know that $D = G = \mathcal{P}(\mathbb{N})$. The above proof can be done in a model of ZF, so ZF is inconsistent. Last edited by AplanisTophet; October 11th, 2018 at 08:16 AM. 
October 11th, 2018, 09:18 AM  #2 
Senior Member Joined: Jun 2014 From: USA Posts: 422 Thanks: 26 
I would like to add one line for clarity that doesn't otherwise change the proof: Let $H = \bigcup \{ x \in D : x \not\subset r(x) \} \in G$ Add this line $\downarrow$ $$\text{Function } r \text{ is surjective } \implies \exists x \in D \text{ such that } r(x) = H$$ $$x \subset H \implies x \not\subset r(x) = H$$ $$x \not\subset H \implies x \subset r(x) = H$$ $$\not\exists x \in D \text{ such that } r(x) = H \implies \text{ function } r \text{ is not surjective}$$ 
October 11th, 2018, 09:59 AM  #3 
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 284 Thanks: 86 Math Focus: Algebraic Number Theory, Arithmetic Geometry 
After a cursory glance, it's not clear to me why $H$ is an element of $G$. Would you mind explaining this? Or at least confirming that it'll be obvious if I work through the details?

October 11th, 2018, 10:25 AM  #4  
Senior Member Joined: Jun 2014 From: USA Posts: 422 Thanks: 26  Quote:
The set $H$ will be the union of elements of $D$, so it will contain both finite and infinite binary strings. For each infinite binary string $x$ in $H$, we can be assured that $f(x)$ is also a subset of $H$. In turn, $H$ must be an element of $G$. We can note that for any elements $p \in G$ and $q \in A$, $q \in p \iff f(q) \subset p \iff g(q) \subset p$.  
October 11th, 2018, 11:39 AM  #5  
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 284 Thanks: 86 Math Focus: Algebraic Number Theory, Arithmetic Geometry 
That seems to make sense, thanks. I'll have proper think about it in a while. I guess another issue I have is with the following implications: Quote:
Edit: I'm happy with the second implication, actually. Last edited by cjem; October 11th, 2018 at 11:52 AM.  
October 11th, 2018, 11:47 AM  #6 
Senior Member Joined: Jun 2014 From: USA Posts: 422 Thanks: 26 
I figured out the error. The following is a counterexample: Let $K = k_1, k_2, k_3, …$ be a listing of the elements of $A$ that contain an infinite number of 0's but only a finite number of 1's. We then have $L = \{ g(k) : k \in K \} \subset D$ and $\bigcup L = B \cup K \implies B \subset \bigcup L$. Assume function $r$ is such that $l \not\subset r(l) \iff l \in L$ so that $H = \bigcup L$. In this case, $H \notin G$ because the only element $g$ of $G$ such that $B \subset g$ is $k(B) = g = B \cup A$. Therefore, the following line of the proof was incorrect because $H = \bigcup L \notin G$ when $\{ x \in D : x \not\subset r(x) \} = L$: Let $H = \bigcup \{ x \in D : x \not\subset r(x) \} \in G$ 
October 11th, 2018, 11:48 AM  #7 
Senior Member Joined: Aug 2012 Posts: 2,099 Thanks: 604  My first issue: You didn't bother to define C or D. Since you are trying to make a cardinality argument, you have to be very precise about the sets you're using. Also your notation for f and g is unclear. f seems to map a sequence to a set. g maps a sequence to another set that's the union of two sets. I'm sure you must have an idea in there somewhere but your notation is incoherent. Last edited by Maschke; October 11th, 2018 at 12:04 PM. 
October 11th, 2018, 12:34 PM  #8  
Senior Member Joined: Jun 2014 From: USA Posts: 422 Thanks: 26  Quote:
Thanks.  
October 11th, 2018, 12:46 PM  #9  
Senior Member Joined: Jun 2014 From: USA Posts: 422 Thanks: 26  Quote:
I thought $H$ would be an element of $G$ for any possible $H$. That isn't true, so that is where the proof breaks down. Thank you also.  
October 11th, 2018, 01:14 PM  #10  
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 284 Thanks: 86 Math Focus: Algebraic Number Theory, Arithmetic Geometry  Quote:
Interesting. Given that the rest of the argument looks fine (and assuming ZF is consistent), this means $H$ isn't an element of $G$ for any surjection $r$. It seemed plausible to me that $H$ would at least sometimes be an element of $G$, even if I wasn't convinced it always would be.  