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

11
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 ...
11
votes
1answer
456 views

Any branch of math can be expressed within set theory, is the reverse true?

Set theory seems to have the property of being "universal", in the sense that any branch of math can be expressed on its language. Is there any other branch of math with this property? I am asking ...
11
votes
3answers
248 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 ...
11
votes
1answer
183 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
2answers
161 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 ...
11
votes
4answers
194 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
256 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
116 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
0answers
193 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

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
6answers
734 views

$ \{x : P(x)\} $ vs. $ \{P(x) : x\} $ -— When are these set-builder notations the same and different?

I should clarify that I'm asking for intuition or informal explanations. I'm starting math and never took set theory so far, thence I'm not asking about formal set theory or an abstract hard answer. ...
10
votes
4answers
753 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$.
10
votes
3answers
518 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 ...
10
votes
4answers
378 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...
10
votes
2answers
321 views

How many paths exist between two points in the plane?

Fix distinct $a,b \in \mathbb{R}^2$. In terms of cardinality (say, beth numbers), how many distinct continuous functions $f : [0,1] \rightarrow \mathbb{R}^2$ satisfying $f(0)=a, f(1)=b$ are there? ...
10
votes
1answer
272 views

In naive set theory ∅ = {∅} = {{∅}}?

In naive set theory, I believe ∅ = {∅} = {{∅}} is correct, but just wanted to make sure that I understood this correctly. ∅ is an empty set, so having an empty set as an element of a set that ...
10
votes
3answers
465 views

How does the axiom of regularity forbid self containing sets?

The axiom of regularity basically says that a set must be disjoint from at least one element. I have heard this disproves self containing sets. I see how it could prevent $A=\{A\}$, but it would seem ...
10
votes
5answers
9k views

Is the void set (∅) a proper subset of every set ?

I am a bit confused about the concept of proper subsets,precisely whether to include one or both of the void set and the set itself. An extract from my module goes like this : Obviously,every set is ...
10
votes
3answers
830 views

Cofinality and its Consequences

(1)In set theory, what is the purpose for defining the concept of cofinality?is it that important? (2)The concept of cofinality finally leads to 2 types of infinite cardinal, for which the first ...
10
votes
2answers
779 views

Is there an empty set in the complement of an empty set?

Currently taking a logic class and trying to understand this. You have two set $A$ and $B$. Both sets are empty sets. Is set $A$ a subset of the complement of set $B$? Assume the context is the ...
10
votes
2answers
255 views

Characterization properties of number sets $\mathbb{N},\mathbb{ Z},\mathbb{Q},\mathbb{R},\mathbb{C}$

When people say that a structure is defined up to isomorphism means, accordingly, that they assume certain properties that make it completely determined under certain operations and relations. ...
10
votes
2answers
363 views

Why doesn't this work imply that there are countably many subsets of the naturals?

Cantor's theorem shows us that the power set of the natural numbers is uncountably infinite. But today (and before remembering Cantor's proof) I was trying to prove the incorrect version: that the ...
10
votes
5answers
1k views

What are some examples of classes that are not sets?

After reading about Russell's paradox, I see that the set of all sets does not exist, so instead it is called a class. What other commonly known classes exist that are not sets? I know the class of ...
10
votes
4answers
280 views

An uncountable linearly independent set

I've been taking a course in linear algebra and one of the first things we defined was linear independence. It made me wonder how big a linearly independent set can be, in particular whether we can ...
10
votes
2answers
599 views

Set theory puzzles - chess players and mathematicians

I'm looking at "Basic Set Theory" by A. Shen. The very first 2 problems are: 1) can the oldest mathematician among chess players and the oldest chess player among mathematicians be 2 different ...
10
votes
4answers
707 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 ...
10
votes
3answers
3k views

Bijection from $\mathbb R$ to $\mathbb {R^N}$

How does one create an explicit bijection from the reals to the set of all sequences of reals? I know how to make a bijection from $\mathbb R$ to $\mathbb {R \times R}$. I have an idea but I am not ...
10
votes
8answers
262 views

Examples of “transfer via bijection”

On some occasions I have seen the following situation: We want find out whether a set of a given cardinality $\varkappa$ has some property P. If this property is invariant under bijective maps, then ...
10
votes
2answers
1k 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 ...
10
votes
5answers
736 views

The simplest way of proving that $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = c$

What is the simplest way of proving (to a non-mathematician) that the power set of the set of natural numbers has the same cardinality as the set of the real numbers, i.e. how to construct a bijection ...
10
votes
2answers
172 views

Bolzano-Weierstrass for sequences of sets

Let $\mathcal{A}_n,\,n\in\mathbb{N}$ be a sequence of subsets of, say, $\mathbb{R}$. Let $\limsup_{n\rightarrow\infty} \mathcal{A}_n = \{x:x\in\mathcal{A}_n\mbox{ for infinitely many } n\}$, and ...
10
votes
4answers
575 views

How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?

When showing that $\mathbb{N}\times\mathbb{N}$ is in bijection with $\mathbb{N}$, it seems standard to give a proof by picture that shows a way to systematically weave through all the points in ...
10
votes
1answer
84 views

a totally ordered set with small well ordered set has to be small?

doing something quite different the following question came to me: 1)If you have a totally ordered set A such that all the well ordered subset are at most countable, is it true that A has at most the ...
10
votes
2answers
4k 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 ...
10
votes
6answers
245 views

what is a function? please.

Axiom schema of replacement: Let the domain of the function $F$ be the set $A$. Then the range of $F$ (the values of $F(x)$ for all members $x$ of $A$) is also a set. — Tarski–Grothendieck ...
10
votes
0answers
56 views

There's no cardinal $\kappa$ such that $2^\kappa = \aleph_0$

I am trying to prove that a cardinal $\kappa$ such that $2^\kappa = \aleph_0$ . My attempt: We suppose it exists. Since $\kappa<2^\kappa$, in particular, $\kappa<\aleph_0$. But that implies ...
9
votes
14answers
2k views

Using set notation, define the set of even natural numbers between 100 and 500.

Using set notation, define the set of even natural numbers between 100 and 500. This is what I have so far: $P$ is even numbers so the set of natural numbers between 100 and 500 would be $$P = ...
9
votes
7answers
5k views

difference between maximal element and greatest element

I know that it's very elementary question but I still don't fully understand difference between maximal element and greatest element. If it's possible, please explain to me this difference with some ...
9
votes
5answers
903 views

Contradictory definition in set theory book?

I'm using a book that defines $A\setminus B$ (apparently this is also written as $A-B$) as $\{x\mid x\in A,x\not\in B\}$, but then there was an exercise that asked to find $A\setminus A$. Wouldn't it ...
9
votes
8answers
3k views

What is larger — the set of all positive even numbers, or the set of all positive integers?

We will call the set of all positive even numbers E and the set of all positive integers N. At first glance, it seems obvious ...
9
votes
5answers
1k views

Countable set having uncountably many infinite subsets

Can a countable set contain uncountably many infinite subsets such that the intersection of any two such distinct subsets is finite ?
9
votes
3answers
662 views

Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? [duplicate]

Possible Duplicate: What's the cardinality of all sequences with coefficients in an infinite set? Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? I thought I saw this ...
9
votes
6answers
2k 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. ...
9
votes
4answers
2k 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 ...
9
votes
4answers
211 views

$\bigcup \emptyset$ is defined but $\bigcap \emptyset$ is not. Why?

Why does $\bigcup \emptyset = \emptyset$ but $\bigcap \emptyset$ is not defined? If I had to guess, I'd say it's also equal to $\emptyset$.
9
votes
1answer
513 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 ...
9
votes
5answers
580 views

Set {1,1} = Set {1}, origin of this convention

Is there any book that explicitly contain the convention that a representation of the set that contain repeated element is the same as the one without repeated elements? Like $\{1,1,2,3\} = ...
9
votes
5answers
505 views

If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$? [duplicate]

Prove, disprove, or give a counterexample: If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$. Assume $\mathcal{P}(A)=\mathcal{P}(B)$. Since we know $A \subseteq A$, we know $A \in ...