This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

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

Can a countable group have uncountably many subgroups?

If $G$ is a countable group,can it have an uncountable number of distinct subgroups?
10
votes
2answers
1k 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
725 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
7answers
6k views

Example of Partial Order that's not a Total Order and why?

I'm looking for a simple example of a partial order which is not a total order so that I can grasp the concept and the difference between the two. An explanation of why the example is a partial ...
10
votes
4answers
746 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
4answers
363 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
315 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
270 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
415 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
8k 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
779 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
253 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
349 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
1answer
3k views

The cardinality of the set of all finite subsets of an infinite set

Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subests of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?
10
votes
2answers
581 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
653 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
8answers
255 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
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 ...
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
712 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
169 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
543 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
1answer
109 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)$.
10
votes
6answers
244 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
111 views

What does it take to divide by $2$ (or even $3$)?

Theorem 1 [ZFC, classical logic]: If $A,B$ are sets such that $\textbf{2}\times A\cong \textbf{2}\times B$, then $A\cong B$. That's because the axiom of choice allows for the definition of ...
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
4answers
201 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
477 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
565 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
397 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 ...
9
votes
4answers
301 views

Infinite sets and their Cardinality

(I am a 13 year old so when you answer please don't use things that are TOO hard even though I actually can understand quite complex stuff) I was studying Infinite sets and their cardinality (not in ...
9
votes
2answers
2k views

Cardinality of the infinite sets

Consider the following problem: Which of the following sets has the greatest cardinality? A. ${\mathbb R}$ B. The set of all functions from ${\mathbb Z}$ to ${\mathbb Z}$ C. The ...
9
votes
5answers
707 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 ...
9
votes
4answers
1k 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.
9
votes
3answers
233 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| ...
9
votes
6answers
295 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, ...
9
votes
2answers
480 views

Are known transcendental numbers countable?

Do all known algorithms that generate infinitely many transcendental numbers like Gelfond-Schneider or Liouville only generate countably many? If uncountably many, is this set of measure zero?
9
votes
2answers
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$, ...
9
votes
2answers
724 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 ...
9
votes
3answers
289 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 ?
9
votes
4answers
244 views

injection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$

Today a friend of mine told me a nice fact, but we couldn't prove it. The fact is that there is an injection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ defined by the fomula $(m,n)\mapsto ...
9
votes
3answers
368 views

“The set of all true statements of first order logic”

In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true ...
9
votes
2answers
813 views

How do the sets $\emptyset\times B,\ A\ \times \emptyset, \ \emptyset \times \emptyset $ look like?

If we have a function $f:A \rightarrow B$, then one way to give meaning, I think, to this function, in terms of set theory, is to say, that $f$ is actually a binary relation $f=(A,B,G_f)$, where $G_f ...
9
votes
4answers
1k views

Is the fact that there are more irrational numbers than rational numbers useful?

Although it is known that the cardinality of the set of irrational numbers is greater than the cardinality of the set of rational numbers, is there any usefulness/applications of this fact outside of ...
9
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 ...
9
votes
1answer
767 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 ...