I What does n ∈ f mean in set theory notation?

[Jehannum]

I bought a maths book and have discovered it's somewhat above my level.

In particular I'm confused about one bit of notation. I understand the "is a member of" operator when it takes a set as argument (e.g. n ∈ ℝ) but not when the book uses it with functions (e.g. n ∈ f)

Does n ∈ f mean that the number n can be returned by function f?

 

[PeroK]

I bought a maths book and have discovered it's somewhat above my level.

In particular I'm confused about one bit of notation. I understand the "is a member of" operator when it takes a set as argument (e.g. n ∈ ℝ) but not when the book uses it with functions (e.g. n ∈ f)

Does n ∈ f mean that the number n can be returned by function f?

You need to give more context. My guess is that a function can be seen as a set. For example, the function $f(x) = x^2$ can be seen as the set of points $\lbrace (x, x^2): x \in \mathbb{R} \rbrace$, also commonly known as the graph of $f$.

In this case, you could use the notation: $f = \lbrace (x, x^2): x \in \mathbb{R} \rbrace$.

And, here, $n \in f$ would mean that $n = (x, x^2)$ for some real $x$.

 

[fresh_42]

I bought a maths book and have discovered it's somewhat above my level.

In particular I'm confused about one bit of notation. I understand the "is a member of" operator when it takes a set as argument (e.g. n ∈ ℝ) but not when the book uses it with functions (e.g. n ∈ f)

Does n ∈ f mean that the number n can be returned by function f?

This is strange, not to say wrong. A function $f\, : \,X \rightarrow Y$ can be written as a subset $f=\{(x,y)\,\vert \,y=f(x)\} \subseteq X \times Y$ of the Cartesian product, but this cannot explain the notation $n \in f$ unless $n$ is a pair. Can you give some more context?

 

[fresh_42]

@PeroK beat me ...

 

[Jehannum]

I've copied part of the book below:

Theorem 2.2 There are infinite sets that are not enumerable.
Proof Consider the powerset of N, in other words the collection P whose members are all the sets of numbers (so X ∈ P iff X ⊆ N).
Suppose for reductio that there is a function f : N→P which enumerates P, and consider what we’ll call the diagonal set D ⊆ N such that n ∈ D iff n /∈ f(n).
Since D ∈ P and f by hypothesis enumerates all the members of P, there must be some number d such that f(d) = D.
So we have, for all numbers n, n ∈ f(d) iff n /∈ f(n). Hence in particular d ∈ f(d) iff d /∈ f(d). Contradiction!​

 

[pasmith]

I bought a maths book and have discovered it's somewhat above my level.

In particular I'm confused about one bit of notation. I understand the "is a member of" operator when it takes a set as argument (e.g. n ∈ ℝ) but not when the book uses it with functions (e.g. n ∈ f)

Does n ∈ f mean that the number n can be returned by function f?

That's not what the text is saying.

I've copied part of the book below:

Theorem 2.2 There are infinite sets that are not enumerable.
Proof Consider the powerset of N, in other words the collection P whose members are all the sets of numbers (so X ∈ P iff X ⊆ N).
Suppose for reductio that there is a function f : N→P which enumerates P, and consider what we’ll call the diagonal set D ⊆ N such that n ∈ D iff n /∈ f(n).
Since D ∈ P and f by hypothesis enumerates all the members of P, there must be some number d such that f(d) = D.
So we have, for all numbers n, n ∈ f(d) iff n /∈ f(n). Hence in particular d ∈ f(d) iff d /∈ f(d). Contradiction!​

This is defining f as a function from the natural numbers \mathbb{N} to the collection P of subsets of natural numbers. Thus if n \in \mathbb{N} then f(n) \subset \mathbb{N}. The statement n \in f(n) is therefore perfectly sensible, since it always makes sense to ask if a particular natural number is or is not a member of a particular subset of the natural numbers.

 

[fresh_42]

I've copied part of the book below:

Theorem 2.2 There are infinite sets that are not enumerable.
Proof Consider the powerset of N, in other words the collection P whose members are all the sets of numbers (so X ∈ P iff X ⊆ N).
Suppose for reductio that there is a function f : N→P which enumerates P, and consider what we’ll call the diagonal set D ⊆ N such that n ∈ D iff n /∈ f(n).
Since D ∈ P and f by hypothesis enumerates all the members of P, there must be some number d such that f(d) = D.
So we have, for all numbers n, n ∈ f(d) iff n /∈ f(n). Hence in particular d ∈ f(d) iff d /∈ f(d). Contradiction!​

O.k., but this is not what you wrote. $n \in f$ is something different to $n \in f(n)$ where $f: \mathbb{N}\rightarrow \mathcal{P}(\mathbb{N})$ is a function which values are sets $X$, so $n \in X=f(n) \in \mathcal{P}(\mathbb{N})$ makes sense. This is not the same as $n \in f \in \mathcal{P}( \mathbb{N} \times \mathbb{N})$ which we explained in the previous posts.

The theorem is proven by the so called diagonal argument. It is a formal notation of the following principle:

We want to show, that the set of all subsets of $\mathbb{N}$ isn't enumerable.

If we have an element $X \in \mathcal{P}(\mathbb{N})$, i.e. a subset $X \subseteq \mathbb{N}$, then we can write it down number by number: $X= n_1n_2n_3n_4 \ldots$
Now let's assume $\mathcal{P}(\mathbb{N})$ is enumerable. Then there would be a complete list like
$$\begin{matrix} 1: &X_1 & = & n_{11}n_{12}n_{13} \ldots \\ 2: &X_2 & = & n_{21}n_{22}n_{23} \ldots \\ 3: & X_3 & = & n_{31}n_{32}n_{33} \ldots \\ &\vdots &&\\ \end{matrix}$$
which contains all elements of $\mathcal{P}(\mathbb{N})$, or subsets of $\mathbb{N}$.
The diagonal $d$ is now the number $d=n_{11}n_{22}n_{33} \ldots$ We next add $+1$ to all of the numbers $n_{ii}\,$.
Since by assumption we have enumerated all, this new number $d'$ (or subset $d'=\{n_{11}+1,n_{22}+1,n_{33}+1, \ldots\}$ if you like) has to occur somewhere, say $d'=X_k$. However the $k-$th position of $d'$ is $n_{kk}$ by enumeration of the $X_i$ and $n_{kk}+1$ by construction of $d'$. This cannot both be true, which means there is no way to enumerate $\mathcal{P}(\mathbb{N})$.

You might want to read the proof in the book again and figure out, why both are basically the same. It is also the method used to show why $[0,1]$ or $\mathbb{R}$ are uncountable. Whether $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$ holds is called the continuum hypothesis. It cannot be deduced from the usual axioms of set theory, i.e. by the Zermelo-Fraenkel axioms (ZF). If you read ZFC somewhere, then Zermelo-Fraenkel + Contnuum hypothesis is meant. (Usually it is also assumed, if nothing is said.)

 

[micromass]

Whether $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$ holds

That is not the continuum hypothesis and it can be proven in ZFC.

 

[micromass]

If you read ZFC somewhere, then Zermelo-Fraenkel + Contnuum hypothesis is meant. (Usually it is also assumed, if nothing is said.)

ZFC means Zermelo-Fraenkel with choice. Not the continuum hypothesis.

 

[Jehannum]

Thanks. It's becoming clear now.

Boggled by some of the unfamiliar notation and concepts, I was not appreciating the fact that the function f returns a set as its result, so the ∈ operator can of course be used on the outputs of f such as f (n).

The book itself moves onto such diagonal proofs.

 

[fresh_42]

ZFC means Zermelo-Fraenkel with choice. Not the continuum hypothesis.

Thanks for clarification.

That is not the continuum hypothesis and it can be proven in ZFC.

Oops, I just had a quick look on Wiki to be sure, for I know I tend to forget where the "gap" really is, and only saw $\mathfrak{c}=\aleph_1$ and next $2^{\aleph_0}=\aleph_1$. I should have read it with more care ...
Thanks for the corrections.