0
$\begingroup$

Okay, so, I was reading a book on set theory and I stumbled upon the problem described in the title.

The only axioms and axiom schemes that are assumed are the following:

Axiom of Existence

Axiom of Extensionality

Axiom of Comprehension

Axiom of Pair

Axiom of Union

Axiom of Power Set

Axiom of Infinity

From the theory developed so far I can prove that if A is a set then, for all $n\in\mathbb{N}$, $A^{n}$ (the cartesian product of $n$ copies of $A$) is also a set.

I can also prove by induction that, for all $N\in\mathbb{N}$, $\bigcup_{n=1}^{N}A^{n}$ is also a set. But I can't seem to be able to show that the countable union is a set. Well, I can, but it feels like I'm cheating, so to speak. My idea goes as follows.

The book already outlines a proof that $A^{B}$ (the collection of functions from a set $B$ into a set $A$) is a set. I will assume this fact.

In particular, we have that $A^{\mathbb{N}}$ is a set. Now we can easily define functions $f_{n}$ from $A^{n}$ into $A^{\mathbb{N}}$ in such a way that $im(f_{i})\cap im(f_{j})=\emptyset$, whenever $i\neq j$. Informally, the idea is taking an element of $A^{n}$ and adding a trail of $n$ at the end.

Now, this is where I feel the cheat is. We can "identify" (I choose to use the quotation marks because the book hasn't formally defined this idea, even though I know this kind of trick is used all the time in other areas) $A^{n}$ with its image. So I kind of proved that all of the $A^{n}$ can be realized within $A^{\mathbb{N}}$ (with no overlapping), so their union also can be realized as a subset of $A^{\mathbb{N}}$. This in turn "shows" (with big quotation marks) that the countable union of the $A^{n}$ is a set, as intended.

However, I feel that this isn't entirely correct from the point of view of axiomatic set theory, since at no point in the book so far it was shown that if a set $X$ can be realized as a subset $Y$ of another set $Z$, then this implies that $X$ must be a set. No theorems about cardinality have been proven up to this point in the book, either. I feel like the correct way to prove something is a set is either explicitly constructing it from the axioms, or showing that it is a subset of another set, which isn't the same as showing that it can be identified with a subset of another set.

This might seem excessively nitpicky, but that's precisely the point. I'm interested in proving this without making any assumptions that don't follow from the axioms listed above.

Anyway, I would really appreciate your input. If this argument is correct (and I think it's not), I would really like to know how to justify it. If it's not, how should I go about proving this? I think a hint or two should be enough to get me on the right track.

$\endgroup$
  • 1
    $\begingroup$ But I can't seem to be able to show that the countable union is a set. Actually, how do you define a countable union? $\endgroup$ – Dmitry Aug 22 '20 at 8:25
  • 1
    $\begingroup$ Also possibly of interest: karagila.org/2019/in-praise-of-replacement $\endgroup$ – Asaf Karagila Aug 22 '20 at 8:48
  • $\begingroup$ @Dmitry The book doesn't define it. It "naively" describes it as the "collection" of finite sequences on $A$, which have been previously defined as functions from a natural number $n$ into $A$ (here, $n$ is viewed as the set that originates from the construction of the natural numbers from the axioms of set theory). Then the book encourages the reader to show that this collection is a set, in the sense that it doesn't lead to contradictions like the ones arising from assuming the "collection" of all sets is a set. In other words, I think the book means "show this isn't a proper class". $\endgroup$ – Modesto Rosado Aug 22 '20 at 18:37
  • $\begingroup$ @Dimitry The notation I used in the title and throughout the post is somewhat biased. It should be taken as a shortcut for clarity and not as an object that has been formally defined. Like I said in my other comment, anyone can conceptualize the "collection" of all sets, but we now it can't be a set because it leads to contradictions. In much the same way, one can conceptualize the "collection" of all finite sequences on A, but unless we explicitly construct it, or construct a set that contains it, we could run into another paradox. All this assuming that set theory is consistent. $\endgroup$ – Modesto Rosado Aug 22 '20 at 18:48
  • 1
    $\begingroup$ Yes, your argument, in a nutshell has a hidden use of Replacement, which is not present in your assumptions. Most people would ignore it "because we can also use partial functions", but that's exactly where rigour is usually lost. The von Neumann part is just the technical bit where I explain why Replacement may be necessary for the iterated Cartesian product argument. $\endgroup$ – Asaf Karagila Aug 22 '20 at 19:25

Browse other questions tagged or ask your own question.