This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

12
votes
7answers
1k views

Is $1$ a subset of $\{1\}$

Is the number $1$ a subset of the set $\{1\}$ just as $\{1\}$ is a subset of the set $\{\{1\}\}$? I'm a little bit confused because $1$ is an element not a ...
12
votes
4answers
528 views

What is $\bigcup\limits_{n=1}^\infty [0,1-\frac{1}{n}]$?

This is probably a pretty dumb question, but I am confused by set theory again. The question is whether $$\bigcup_{n=1}^\infty \left[0,1-\frac{1}{n}\right]$$ equals $[0,1]$ or $[0,1)$. However, I am ...
12
votes
5answers
522 views

Prove that every set with more than one element has a permutation without fixed points

I cannot prove this statement so need help. This problem is one of exercises right after the chapter about Hausdorff's maximal principle and Zorn's Lemma. Thus, you cannot use the concept of cardinal ...
12
votes
3answers
446 views

Is every set a subset?

Is every set a subset of a larger set? In other words, for an arbitrary set S, can one always construct a set S' such that S is a proper subset of S'? Is this question even meaningful?
12
votes
4answers
1k views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change ...
12
votes
3answers
635 views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
12
votes
5answers
766 views

Why cannot a set be its own element?

When I study Topology, I met with a problem. On my book, it says 'we cannot admit that there exists a set whose members are all the topological spaces. That will lead to a logical contradiction, that ...
12
votes
1answer
875 views

Do Cantor's Theorem and the Schroder-Bernstein Theorem Contradict?

I am confused as to how Cantor's Theorem and the Schroder-Bernstein Theorem interact. I think I understand the proofs for both theorems, and I agree with both of them. My problem is that I think you ...
12
votes
4answers
342 views

What explains the asymmetry here?

The image operation distributes over unions: $$f(A \cup B) = f(A) \cup f(B)$$ but about intersections we can only say that $$f(A \cap B) \subseteq f(A) \cap f(B)$$ unless $f$ is injective. Where ...
12
votes
4answers
4k views

Overview of basic results about images and preimages

Are there some good overviews of basic facts about images and inverse images of sets under functions?
12
votes
2answers
513 views

Hyperreal measure?

If AC be accepted, then there exists a Lebesgue unmeasurable set called Vitali Set. However, I'm curious about measure valued in hyperreal numbers. Argument in disproof of unmeasurability of Vitali ...
12
votes
4answers
2k views

Need help with Recursion Theorem (Set Theory)

The recursion theorem In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set $X$, an element $a$ of $X$ and a function $f\colon X \to X$, the theorem ...
12
votes
3answers
2k views

Preimage of generated $\sigma$-algebra

For some collection of sets $A$, let $\sigma(A)$ denote the $\sigma$-algebra generated by $A$. Let $C$ be some collection of subsets of a set $Y$, and let $f$ be a function from some set $X$ to $Y$. ...
12
votes
1answer
856 views

What is the name of the $\in$ symbol and where does it come from?

It looks like a lower-case epsilon, but the Wikipedia page on epsilon states that they are not the same. Does this symbol have a typographic identification outside of mathematics? Where did the ...
12
votes
1answer
2k views

Why does Cantor's diagonal argument not work for rational numbers?

If we map every integer to a string that represents a rational number, and produce a number different from all the ones listed, we are essentially following Cantor's algorithm. But why does it not ...
12
votes
3answers
1k views

Proving the countability of algebraic numbers

I am trying to prove that algebraic numbers are countably infinite, and I have a hint to use: after fixing the degree of the polynomial, consider summing the absolute values of its integer ...
12
votes
3answers
287 views

Natural uses for the co-product of sets?

I had come across countless uses of the (Cartesian) product of sets long before I first ever met the concept of a "co-product"1 of sets. In fact, anyone who has learned basic analytic geometry in ...
12
votes
2answers
178 views

A Question regarding disjoint dense sets

If we take the standard topology on $\mathbb{R}$ we can easily find two disjoint sets that are dense, namely $\mathbb{R}\setminus\mathbb{Q}$ and $\mathbb{Q}$. Similarily, if we take the same topology ...
12
votes
2answers
5k views

Prove that the set of all algebraic numbers is countable

A complex number $z$ is said to be algebraic if there are integers $a_0, ..., a_n$, not all zero, such that $a_0z^n+a_1z^{n-1}+...+a_{n-1}z+a_n=0$. Prove that the set of all algebraic numbers is ...
11
votes
6answers
1k views

Is there a notation for being “a finite subset of”?

I would gladly use a notation for "A is a finite subset of B", like $$A\sqsubset B \text{ or } A\underset{fin}{\subset} B,$$ but I have never seen a notation for that. Are there any? While ...
11
votes
6answers
3k views

Why is the supremum of the empty set $-\infty$ and the infimum $\infty$? [duplicate]

I read in a paper on set theory that the supremum and the infimum of the empty set are defined as $\sup(\{\})=-\infty$ and $\inf(\{\})=\infty$. But intuitively I can't figure out why that is the case. ...
11
votes
2answers
1k views

Why is there this strange contradiction between the language of logic and that of set theory?

In standard probability theory events are represented by sets consisting of elementary events. Consider two events for which (as sets) $A \subset B$. If an elementary event $x \in A$ takes places then ...
11
votes
4answers
3k views

Interpretation of limsup-liminf of sets

What is an intuitive interpretation of the 'events' $$\limsup A_n:=\bigcap_{n=0}^{\infty}\bigcup_{k=n}^{\infty}A_k$$ and $$\liminf A_n:=\bigcup_{n=0}^{\infty}\bigcap_{k=n}^{\infty}A_k$$ when $A_n$ are ...
11
votes
5answers
1k views

What is the meaning of set-theoretic notation {}=0 and {{}}=1?

I'm told by very intelligent set-theorists that 0={} and 1={{}}. First and foremost I'm not saying that this is false, I'm just a pretty dumb and stupid fellow who can't handle this concept in his ...
11
votes
4answers
776 views

I want to know why $\omega \neq \omega+1$.

In Kunen's book, Set Theory,chapter I.7, he said: $1+\omega=\omega \neq \omega+1$. I want to know why $\omega \neq \omega+1$.
11
votes
6answers
9k views

Is the empty set a subset of itself?

Sorry but I don't think I can know, since it's a definition. Please tell me. I don't think that $0=\emptyset\,$ since I distinguish between empty set and the value $0$. Do all sets, even the empty ...
11
votes
5answers
5k views

Example of set which contains itself

I am trying to understand Russells's paradox How can a set contain itself? Can you show example of set which is not a set of all sets and it contains itself.
11
votes
6answers
814 views

Naive set theory question on “=”

So I picked up a couple of good undergraduate-level books over the weekend and have been working through them... In Algebra: Chapter 0, the author of the text writes: The prototype of the ...
11
votes
3answers
2k views

Cardinality of the set of prime numbers

It was proved by Euclid that there are infinitely many primes. But what is the cardinality of the set of prime numbers ? Cantor showed that the sets $\mathbb{Q}$ and $\mathbb{Z}$ have the same ...
11
votes
4answers
2k views

Formal proof for A subset of the real numbers, well ordered with the normal order of $\mathbb R$, is at most $\aleph_0$

I tried to write a formal proof for the theorem: $A$ subset of $\mathbb R$ well ordered by the normal order $\implies A$ is at most of cardinality $\aleph_0$. Any suggestions? Thanks.
11
votes
3answers
614 views

How to prove that from “Every infinite cardinal satisfies $a^2=a$” we can prove that $b+c=bc$ for any two infinite cardinals $b,c$?

Prove that if $a^2=a$ for each infinite cardinal $a$ then $b + c = bc$ for any two infinite cardinals $b,c$. I tried $b+c=(b+c)^2=b^2+2bc+c^2=b+2bc+c$, but then I'm stuck there.
11
votes
6answers
863 views

Dependence of Axioms of Equivalence Relation?

This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein. These are the properties of equivalence relation given in this book. Prop 1 $a \sim a$ Prop 2 $a \sim b$ ...
11
votes
3answers
2k views

Showing any countable, dense, linear ordering is isomorphic to a subset of $\mathbb{Q}$

I'm trying to knock out a few of the later exercises from Enderton's Elements of Set Theory. This problem is #17, found on page 227. A partial ordering $R$ is said to be dense iff whenever $xRz$, ...
11
votes
4answers
988 views

Difference between a function and a graph of a function?

Formally, I learned that a function $f: X \to Y$ is a subset $f \subset X \times Y$ subject to the condition that for every $x \in X$, there is exactly one $y \in Y$ such that $(x, y) \in f$. We write ...
11
votes
2answers
2k views

Subset of a finite set is finite

We define $A$ to be a finite set if there is a bijection between $A$ and a set of the form $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$. How can we prove that a subset of a finite set is finite? It is ...
11
votes
3answers
455 views

Why is the collection of all algebraic extensions of F not a set?

When proving that every field has an algebraic closure, you have to be careful. In this article https://proofwiki.org/wiki/Field_has_Algebraic_Closure, and as I have been told on this site, if we have ...
11
votes
3answers
3k views

Bijection between an open and a closed interval

Recently, I answered to this problem: Given $a<b\in \mathbb{R}$, find explicitly a bijection $f(x)$ from $]a,b[$ to $[a,b]$. using an "iterative construction" (see below the rule). My ...
11
votes
1answer
205 views

What does it mean for a set to have “structure”?

I understand that a set is like a list of things, except that the order doesn't matter and that you can't have any duplicates in a set. For example: $\{3, 1, 4, 2\}$ is the same set as $\{1, 2, 3, ...
11
votes
4answers
199 views

How find this minimum of the value $f(1)+f(2)+\cdots+f(100)$

Give the positive integer set $A=\{1,2,3,\cdots,100\}$, and define function $f:A\to A$ and (1):such for any $1\le i\le 99$,have $$|f(i)-f(i+1)|\le 1$$ (2): for any $1\le i\le 100$,have ...
11
votes
3answers
260 views

Problem about subsets of $\{1, 2,\dots,n\}$

Let $A=\{1, 2,\dots,n\}$ What is the maximum possible number of subsets of $A$ with the property that any two of them have exactly one element in common ? I strongly suspect the answer is $n$, but ...
11
votes
1answer
129 views

Coloring of positive integers

Suppose $f:\mathbb{Z}^+\longrightarrow X$ is a function, with $X$ a finite set. Is it true that there are $a,b\in\mathbb{Z}^+$ such that $f(a)=f(b)=f(a+b)$.
11
votes
1answer
156 views

Analogue of the term 'summand' for unions and intersections.

If we have a sum $\sum\limits_{i=1}^na_i$, we call the terms $a_i$ summands. In fact, in the cases of addition, subtraction, multiplication, and division, we have a large vocabulary to describe the ...
11
votes
0answers
197 views

Can $[0,1]$ be partitioned into an uncountable union of uncountable sets? [duplicate]

I was thinking about this: $[0,1]$ can be partitioned into a countable union of uncountable sets. Write $[0,1]=(0,1]\cup \{0\}:$ $$(0,1]=\bigcup_{n=1}^{\infty}\Big(\frac{1}{n+1},\frac{1}{n}\Big]$$ ...
10
votes
9answers
4k views

What is an Empty set?

We define the term "Set" as, A set is a collection of objects. And an "Empty set" as, An empty set is a set which contains nothing. First problem I encountered: How the definition of ...
10
votes
9answers
5k views

Is the sum of all natural numbers countable?

I do not even know if the question makes sense. The point is rather simply. If I have the sum of all natural numbers, $$\sum_{n\in \mathbb{N}}n$$ this is clearly "equal to infinity". But since ...
10
votes
5answers
1k views

Is $\{\emptyset\}$ a subset of $\{\{\emptyset\}\}$?

$\{\emptyset\}$ is a set containing the empty set. Is $\{\emptyset\}$ a subset of $\{\{\emptyset\}\}$? My hypothesis is yes by looking at the form of "the superset $\{\{\emptyset\}\}$" which contains ...
10
votes
2answers
2k views

Which symbol should be used for an empty set?

Currently, a discussion started on the German Wikipedia article for Empty Set (the German discussion), whether $\emptyset$ or $\varnothing$ should be used or is more common as a symbol for an empty ...
10
votes
1answer
557 views

Why is CH true if it cannot be proved?

Continuum hypothesis (CH) states that there can be no set whose cardinality is strictly between that of integers and real numbers. Godel, 1940 and Paul Cohen,1963 showed that CH can neither be proved ...
10
votes
4answers
1k views

Is any relation which contains only one ordered pair transitive?

I need clarification. Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$. Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
10
votes
4answers
441 views

Looking for a problem where one could use a cardinality argument to find a solution.

I would like to find an exercise of the type: Find some $x$ in $A\setminus B$. Solution: since $A$ is uncountable and $B$ is countable such $x$ exists...