0

In this video on PBS Infinite Series, they attempt to prove: $$|A| < |\mathcal{P}(A)| \tag{1}$$ Where $A$ is a set (possibly infinite), $|A|$ is the cardinality of $A$ and $\mathcal{P}(A)$ is the power set of A.

They use the following argument:

  1. Show that $|A| \le |\mathcal{P}(A)|$ (this is not relevant to my question)

  2. Show that there is a subset $B$ from $A$ that cannot be obtained by any bijection $G:A\to \mathcal{P}(A)$, thus $|A| \lt |\mathcal{P}(A)|$

To prove 2, they present a subset $B$

$$B = \{a\in A | a\not\in G(a)\} \tag{2}$$

They then show that $$\forall a \in A, G(a) \not= B \tag{3}$$

My objection is that $(3)$ does not prove $(1)$ because $B \not\in \mathcal{P}(A)$ unless $B = \emptyset$ in which case a bijection can map any element $a \in A$ to $B$.

RationalFragile
  • 9
  • 3
  • I don't follow your 2.: there is no bijection from $A$ to $\mathcal{P}(A)$, and so every subset of $A$ has this property (vacuously). – Angina Seng Jan 02 '20 at 12:11
  • @LordSharktheUnknown They are trying to prove "there is no bijection from $A$ to $P(A)$". – RationalFragile Jan 02 '20 at 12:13
  • I rewrote your subset $B$ in set builder notation for clarity. Written in plain English it was fairly clunky. – Cameron Williams Jan 02 '20 at 13:08
  • 2
    Note: as lord shark the unkown said, the property holds vacuously as there is no bijection from $A$ to $P(A)$ (which is what we are trying to prove)
    But what they say is different - they say that for every function (or bijection, doesn't really matter) from $A$ to $P(A)$ we have some $B \subseteq A$ (and thus $B \in P(A)$ which is not covered. This is very different than saying that there is a fixed $B$ which cannot be obtained by any bijection, the order of quantifiers matter here. Note that if we replace the bijection with function in your definition the statement is false     –  Jan 02 '20 at 13:08
  • @AsafRosemarin Can you show that $B \subset A$? (I don't see that at all, unless $B = \emptyset$ but then there is a bijection to obtain $B$). – RationalFragile Jan 02 '20 at 13:14
  • you defined $B$ using the notation $$B:= {a\in A| \varphi(a)}$$ This immediately implies that every element in $B$ must be in $A$ or equivanlently, $B\subseteq A$. –  Jan 02 '20 at 13:17
  • @AsafRosemarin (That wasn't me, I quoted the "sentence" definition from the video but it was edited to the formula.) But still, the function is not even defined; there are no elements from A that will satisfy its definition. – RationalFragile Jan 02 '20 at 13:22
  • But the function is defined. As I explained in my previous comment, you need to swap the order of quantifiers to get the statement "for every function $f: A \rightarrow P(A)$ there exists some $B \subseteq A$ such that $B \notin \text{Im}(f)$". Now $B$ can (and should) be dependent of $f$, and as $B \subseteq A$, then by the definition of the power set $B \in P(A)$ –  Jan 02 '20 at 13:27
  • @AsafRosemarin I edited the question to correct the definition of $B$ because it wasn't me who edited in that definition. Please see if you still think that $B \in \mathcal{P}(A)$. – RationalFragile Jan 02 '20 at 14:04
  • Fix the typo in $(1)$. –  Jan 02 '20 at 14:32
  • @RationalFragile My comment does not change... Every set that is defined as $B := {a \in A | \varphi(a)}$ for whatever predicate $\varphi$ must be in $P(A)$ by definition –  Jan 02 '20 at 14:35
  • @AsafRosemarin I understand. I'm sorry, I keep forgetting about the empty set being a subset of every other set. But my issue is that the argument sounds valid to me only if B contains an element of A but cannot be the output of G. In the case of an empty set, this is not true because G can map any element from A to P(A). – RationalFragile Jan 02 '20 at 14:39
  • What they prove is that there does not exists any $a \in A$ such that $f(a) = B$ for our defined $B$. It is possible that $B = \emptyset$. In that case, there is no $a \in A$ such that $f(a) = \emptyset \in P(A)$. Note that the empty set is an element of $P(A)$ just like any other element. In any case, we get a set $B \in P(A)$ that is not "covered" by any $a \in A$, proving that $f$ is not surjective –  Jan 02 '20 at 14:42

1 Answers1

1

Since $B$ consists of all elements of $A$ for which a certain assertion holds, $B\subset A$. In other words, $B\in\mathcal P(A)$.

José Carlos Santos
  • 427,504
  • No. They don't show that $B \subset A$. Just because you can formulate a sentence that involves elements in $A$ doesn't mean that it makes a valid set (e.g. the subset $C$). – RationalFragile Jan 02 '20 at 12:15
  • 1
    The set $C$ is simply the empty set, which exists. – José Carlos Santos Jan 02 '20 at 12:23
  • But the empty set can be mapped in an infinite set. Imagine a function $E$ such that $E(A) = A \cup \emptyset$. Let $A=\mathbb{N}$ and map $i$ to $i+1$ and $0$ to $\emptyset$. So showing that $B=\emptyset$ makes $B$ mapable by a bijection $G$. – RationalFragile Jan 02 '20 at 12:43
  • I don't see why that matters. You asserted that the set $C$ doesn't exist, and I proved otherwise. – José Carlos Santos Jan 02 '20 at 12:45
  • Wait, is $C$ actually the empty set? The empty set does not contain the element that the definition of $C$ says it contains. – RationalFragile Jan 02 '20 at 12:47