My Math Forum My Opus

 Number Theory Number Theory Math Forum

 October 11th, 2018, 07:28 AM #1 Senior Member   Joined: Jun 2014 From: USA Posts: 479 Thanks: 36 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: 479 Thanks: 36 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: 306 Thanks: 101 Math Focus: Number Theory, Algebraic 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: 479
Thanks: 36

Quote:
 Originally Posted by cjem 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?
Yes, $H$ must be an element of $G$ by definition.

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: 306
Thanks: 101

Math Focus: Number Theory, Algebraic 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:
 Originally Posted by AplanisTophet $$x \subset H \implies x \not\subset r(x) = H$$ $$x \not\subset H \implies x \subset r(x) = H$$
For the first, $x \subset H$ just means that, for any string $y \in x$, there exists $z \in D$ such that $y \in z$ and $z \not\subset r(z)$. I can't quite see how this implies the (potentially) stronger statement that $x \not\subset r(x)$.

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: 479 Thanks: 36 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,156
Thanks: 630

Quote:
 Originally Posted by AplanisTophet I assume there may be something wrong ...
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: 479
Thanks: 36

Quote:
 Originally Posted by AplanisTophet I figured out the error. The following is a counterexample:
Quote:
 Originally Posted by Maschke I'm sure you must have an idea in there somewhere...
Yup. I'm satisfied. I incorrectly assumed $H$ would have to be in $G$ for any choice of function $r$, but I figured it out. Otherwise, it was a fun little exercise imho.

Thanks.

October 11th, 2018, 12:46 PM   #9
Senior Member

Joined: Jun 2014
From: USA

Posts: 479
Thanks: 36

Quote:
 Originally Posted by cjem For the first, $x \subset H$ just means that, for any string $y \in x$, there exists $z \in D$ such that $y \in z$ and $z \not\subset r(z)$. I can't quite see how this implies the (potentially) stronger statement that $x \not\subset r(x)$.
Each element of $D$ contains an element that isn't in any other element of $D$. Therefore, it is true that $x \subset H \implies x \not\subset r(x) = H$.

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: 306
Thanks: 101

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by AplanisTophet Each element of $D$ contains an element that isn't in any other element of $D$.
Oh, duh. I considered this, but I mixed $C$ and $D$ up in my mind (and it's not true if you swap the "$D$"s with "$C$"s). Thanks.

Quote:
 Originally Posted by AplanisTophet 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.
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.

 Tags opus

 Thread Tools Display Modes Linear Mode

 Contact - Home - Forums - Cryptocurrency Forum - Top