What does n ∈ f mean in set theory notation?

In summary, the conversation discusses the confusion about the "is a member of" notation when used with functions. Specifically, the conversation mentions the notation n ∈ f and its meaning in relation to the function f. The conversation also provides an example from a maths book, where the notation is used in the context of the diagonal argument to prove that the set of all subsets of natural numbers is not enumerable.
  • #1
Jehannum
102
26
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?
 
Physics news on Phys.org
  • #2
Jehannum said:
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##.
 
  • #3
Jehannum said:
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?
 
  • #5
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!​
 
  • #6
Jehannum said:
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.

Jehannum said:
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 [itex]f[/itex] as a function from the natural numbers [itex]\mathbb{N}[/itex] to the collection [itex]P[/itex] of subsets of natural numbers. Thus if [itex]n \in \mathbb{N}[/itex] then [itex]f(n) \subset \mathbb{N}[/itex]. The statement [itex]n \in f(n)[/itex] 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.
 
  • #7
Jehannum said:
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.)
 
  • #8
fresh_42 said:
Whether ##|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|## holds

That is not the continuum hypothesis and it can be proven in ZFC.
 
  • #9
fresh_42 said:
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.
 
  • #10
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.
 
  • #11
micromass said:
ZFC means Zermelo-Fraenkel with choice. Not the continuum hypothesis.
Thanks for clarification.
micromass said:
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 ... :sorry:
Thanks for the corrections.
 

What is set theory notation?

Set theory notation is a system of symbols used to represent mathematical sets and their relationships. It allows for concise and precise communication of mathematical ideas.

What is a set?

A set is a collection of distinct objects, called elements, that are grouped together based on a particular characteristic or property.

What are some common symbols used in set theory notation?

Some common symbols used in set theory notation include:
- Curly braces { } to enclose the elements of a set
- The element of symbol ∈ to show that an object is an element of a set
- The empty set symbol ∅ to represent a set with no elements
- The union symbol ∪ to represent the combination of two or more sets
- The intersection symbol ∩ to represent the shared elements between two or more sets
- The subset symbol ⊆ to show that one set is a subset of another
- The complement symbol ∁ to represent the elements not in a given set

How do you read set theory notation?

Set theory notation is read from left to right, with the elements of a set listed within curly braces. For example, {1, 2, 3} would be read as "the set containing 1, 2, and 3".

What are some tips for working with set theory notation?

Some tips for working with set theory notation include:
- Clearly define the elements of your set
- Use proper notation to indicate relationships between sets
- Double check your work to ensure you have accurately represented the intended mathematical concept
- Familiarize yourself with common symbols and their meanings
- Practice and seek guidance from a teacher or mentor if needed.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
27
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
439
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
4K
  • Calculus
Replies
4
Views
866
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
24
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
Back
Top