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
1answer
322 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 ...
11
votes
6answers
860 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
3k 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
3answers
668 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
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
4answers
359 views

A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets

If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ?
11
votes
4answers
2k views

When do two functions become equal?

When do two functions become equal? I have stumbled over this definition of equality of functions in elementary real analysis. Let $X$ and $Y$ be two sets. Let $f:X\rightarrow Y$ and ...
11
votes
2answers
267 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. ...
11
votes
3answers
6k 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 ...
11
votes
4answers
1k 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
3answers
4k views

limit inferior and superior for sets vs real numbers

I am looking for an intuitive explanation of $\liminf$ and $\limsup$ for sequence of sets and how it corresponds to $\liminf$ and $\limsup$ for sets of real numbers. I researched online but cannot ...
11
votes
2answers
85 views

Does there exist a function $g\in \mathbb{N}^\mathbb{N}$ s.t. $\{f\mid f\circ f=g\}$ is not empty and finite?

I'm struggling with this question and can't figure it out. The question was too long for the title so I will write it once more: Does there exist a function $g : \mathbb{N} \longrightarrow ...
11
votes
3answers
486 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
4answers
2k views

Is there a shorthand notation for adding an element to a set?

I know that if you want to refer to the set $ A $ with the element $ x $ added, you can write $ A \cup \{x\} $. But is there a common shorthand for this?
11
votes
1answer
213 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
1answer
14k views

Mathematical notation for the maximum of a set of function values

I have a question about the proper notation of the following (simplified) example: I want to express that I have a value alpha, which is the maximum of a set of n values. Each value in the set is the ...
11
votes
4answers
200 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
2answers
268 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
147 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
2answers
174 views

Showing that $|A\cap B|/|A \cup B| + |B\cap C|/|B \cup C| - |A\cap C|/|A \cup C| \leq 1$ for finite sets $A,B,C$.

If $A$, $B$ and $C$ are finite sets, prove that $$ \frac{|A\cap B|}{|A \cup B|} + \frac{|B\cap C|}{|B \cup C|} - \frac{|A\cap C|}{|A \cup C|} \leq 1. $$ It seem's simple, but I tried it for ...
11
votes
1answer
165 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
205 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
14answers
3k 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 = ...
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
755 views

$\{1,1\}=\{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\} = ...
10
votes
6answers
4k 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. ...
10
votes
1answer
626 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
4k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
10
votes
4answers
2k 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
5answers
483 views

What is the canonical definition of an open set?

The definition of an open set that I see in most topology texts(like the ones found in Topology by Munkres and another w/ the same title by Hocking & Young, or Basic Topology by Armstrong) is that ...
10
votes
2answers
1k views

countable group, uncountably many distinct subgroup?

I need to know whether the following statement is true or false? Every countable group $G$ has only countably many distinct subgroups. I have not gotten any counter example to disprove the statement ...
10
votes
4answers
484 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
3answers
268 views

Are the error terms of the partial sums of inclusion-exclusion unimodal?

I often teach inclusion-exclusion: $$|A ∪ B| = |A| + |B| − |A ∩ B|$$ by suggesting that $|A∩B|$ is a correction factor for $|A|+|B|$. Then I teach the three set version: $$|A∪B∪C| = |A| + |B| + |C| ...
10
votes
5answers
1k views

In Cantor's Diagonalization Argument, why are you allowed to assume you have a bijection from naturals to rationals but not from naturals to reals?

Firstly I'm not saying that I don't believe in Cantor's diagonalization arguments, I know that there is a deficiency in my knowledge so I'm asking this question to patch those gaps in my ...
10
votes
5answers
14k 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
6answers
375 views

Why is “for all $x\in\varnothing$, $P(x)$” true, but “there exists $x\in\varnothing$ such that $P(x)$” false? [duplicate]

There exists an $X\in A$ such that $P(X)$. When $A$ is the empty set then this statement is false because there is nothing in $A$ that when plugged in for $X$, makes $P(X)$ come out True. However, ...
10
votes
4answers
3k views

Empty intersection and empty union

If $A_\alpha$ are subsets of a set $S$ then $\bigcup_{\alpha \in I}A_\alpha$ = "all $x \in S$ so that $x$ is in at least one $A_\alpha$" $\bigcap_{\alpha \in I} A_\alpha$ = "all $x \in S$ so that ...
10
votes
3answers
1k 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
1k 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
1answer
628 views

Why is the collection of all groups considered a proper class rather than a set?

According to Wikipedia, The collection of all algebraic objects of a given type will usually be a proper class. Examples include the class of all groups, the class of all vector spaces, and ...
10
votes
2answers
431 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
2k 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
3answers
4k views

The Cantor set is homeomorphic to infinite product of $\{0,1\}$ with itself - cylinder basis - and it topology

I know the Cantor set probably comes up in homework questions all the time but I didn't find many clues - that I understood at least. I am, for a homework problem, supposed to show that the Cantor ...
10
votes
4answers
427 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
4answers
3k views

Examples of transfinite induction

I know what transfinite induction is, but not sure how it is used to prove something. Can anyone show how transfinite induction is used to prove something? A simple case is OK.
10
votes
2answers
693 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
5answers
1k 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
2k views

Is the set of all finite sequences of letters of Latin alphabet countable/uncountable? How to prove either?

Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can ...
10
votes
2answers
3k views

Countable/uncountable basis of vector space

I've stumbled upon this exercise in algebra book, in chapter dealing with vector spaces' dimensions. Prove that basis of the field of real numbers $\mathbb R$ as vector space over the field of ...
10
votes
1answer
705 views

When is $x=\{ x\}$?

Inspired by this question: When/for which $x$ do we have $x=\{ x\}$ ?