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

0
votes
1answer
10 views

Showing that if $a$ is a transitive set then $\cup a$ is also a transitive set.

I am working on a problem in Enderton's text on set-theory that appears to be deceptively easy. It is likely that I making a mistake somewhere so if someone can comment it would be much appreciated. ...
1
vote
5answers
200 views

Are the real numbers really uncountable?

Consider the following statement Every real number must have a definition in order to be discussed. What this statement doesn't specify is how that loose-specific that definition is. Some examples ...
-1
votes
1answer
16 views

Prove that every finite A is Dedekind finite.

I'm trying to prove that every finite set $A$ is Dedekind finite. I have to use the theorems: that a set $A$ is finite iff there is a natural number $n$ so that there is a bijection $f: n \rightarrow ...
1
vote
1answer
30 views

I need help proving this theorem (composition of functions)

This is the statement: If $f$ and $g$ are functions, the composition $g\circ f$ is a function with $$D(g\circ f)=\{x\in D(f):f(x)\in D(g)\}$$ $$R(g\circ f)=\{g(f(x)):x\in D(g\circ f)\}$$ The ...
1
vote
2answers
50 views

An injection from $\mathbb{N}$ to $\mathbb{N}^n$.

I'm currently attempting to prove $\mathbb{N}^n \sim \mathbb{N}$ via Cantor-Schroeder-Berstein (because I found no other way). In my work so far I've managed to find an injective function $f$ from ...
1
vote
2answers
48 views

What is wrong with this proof that $f(A_1 \cap A_2) = f(A_1) \cap f(A_2)$?

Consider a function $f:A \rightarrow B$. Let $A_1, A_2 \subseteq A$. Let $x \in$$(f(A_1) \cap f(A_2))$ $\implies x\in (\{f(x)\in B|x \in A_1\} \cap \{f(x)\in B|x \in A_2\})$ $\implies x\in ...
3
votes
1answer
29 views

All Sets have bijection with cartesian products of Subsets?

I was doodling around with some math today, trying to find "representations" for sets as cartesian products of their proper subsets. For example: $\mathbb{N}\leftrightarrow 2\mathbb{N}\times\{0,1\}$ ...
2
votes
0answers
40 views

Munkres Topology Exercise 2.q

I have another doubt regarding a question from Munkres' Topology (another one on cartesian products, sorry!). I have to determine if the following statement is true: $$(A\times B)-(C\times ...
3
votes
4answers
74 views

If $B \subseteq A$, why is $\{ B \}$ not in the power set of $A$?

Define $B = \{1\}$ and $A=\{1, 2\}$. Then the power set of $A$ is $\mathcal P(A)= \{ \emptyset, \{1\}, \{2\}, A \}$. Let $C= \{ B \} = \{ \{1 \}\}$. Why is $C \notin \mathcal P(A)$? I dont see ...
0
votes
0answers
31 views

How does the Axiom of Schema of Separation lift Russels Paradox? [duplicate]

The following links expose a flaw in naive set theory known as Russell' paradox. http://en.wikipedia.org/wiki/Russells_paradox http://mathworld.wolfram.com/RussellsAntinomy.html The Axiom Schema of ...
0
votes
2answers
58 views

Problems with the cartesian product

Intro Hello, I'm starting to read Munkres' Topology, and I'm having a bit of trouble solving problems involving the cartesian product. For example, there's this problem: Sample Exercise ...
6
votes
2answers
78 views

$\Gamma \subset \mathbb{R}^{+}$ is uncountable. Can we choose a sequence from $\Gamma$ of which the sum is $\infty$

If $\Gamma$ is a set of uncountably many different positive real numbers, can we choose a sequence of pairwise different positive numbers from $\Gamma$, say $\{a_n\}$, such that $\sum a_n = \infty$ ...
0
votes
2answers
45 views

Union and Intersection of sets

I was reading Introduction to Topology by George L. Cain and found myself struggling with this definition mentioned in the book. Let X be a set and C be the collection of its subsets. Then if C = ...
2
votes
1answer
41 views

Generalizing the Monotone Subsequence theorem

In proving the Bolzaono-Weierstrass theorem, one proves the lemma that every infinite real sequence has a(n infinite) monotone subsequence. In all of the proofs I've seen so far, this is done by ...
2
votes
3answers
62 views

Are there circles in $\mathbb{R}^d$ taking no rational values?

I recently stepped over a little detail in a thesis I still wonder about. If one looks at $\mathbb{Q}$, then it is dense in $\mathbb{R}$, and we have no problem finding real numbers that don't belong ...
2
votes
2answers
19 views

How many tagged partitions of an interval are there?

A tagged partition of an interval $[a, b] \ (a, b ∈ ℝ, a < b)$ is a finite sequence $(x_i)_{i=0}^n$ in $ℝ$, where $a=x_0 < x_1 < … < x_n = b$. Consider the set of all tagged partitions of ...
0
votes
1answer
19 views

Union of Dedekind-finite sets

$F$ is Dedekind-finite if for every $A\varsubsetneq F$ we have $A<_cF$. Need help to prove that if $F,G$ are Dedekind-finite sets, $F\cap G=\emptyset$ then $F\cup G$ is also Dedekind-finite. ...
1
vote
2answers
28 views

Proof on limit superior and limit inferior of a set

I understand the result intuitively but how can I prove this? For a given integral $n \ge 1$, let $A_n = \left\{\frac mn \mid m \in \mathbb Z\right\}$. Show that $\varlimsup_{n\to\infty} A_n = ...
0
votes
2answers
23 views

Cannot understand a mapping function which include some sets

I have kept a screenshot of my problem below which describes about the various sets. At the last line, there is an expression where a function delta uses those sets and maps them into another. I am ...
1
vote
1answer
30 views

A question on relations

Problem Statement: Let $A$ and $B$ be sets. Many books define a relation $\mathcal R$ from $A$ to $B$ to be a subset $ \mathcal R \subseteq A \times B $. Show that such an R is a ...
-3
votes
2answers
65 views

problem undrestanding maximal defenition? [on hold]

i do not understand when it says "maximal is an element of S that is not smaller than ANY other element" . while we have some elements that are not possible to compare why it uses the word ANY . if A ...
0
votes
0answers
36 views

How many Euler diagrams with $n$ sets exist?

Does anyone have any thoughts on this? I have been struggling with it and I'm not sure if it's a hard problem, or easy and I'm just not getting it? For $n=2$ sets (say $A$ and $B$), it's obviously 4: ...
1
vote
2answers
29 views

Problem Involving a Generalized Cartesian Product

Let $I$ be a set, and for each $i \in I$, let $U_i$ and $V_i$ be sets. Furthermore, suppose for each $i \in I$, there is a bijection $f_i:U_i \to V_i$. Prove that there is a bijection $g:\prod_{i \in ...
0
votes
3answers
44 views

What would make a function reflexive, transitive, and/or symmetric?

A binary relation $R$ is a subset of the Cartesian product between two sets $X$ and $Y$, containing a set of ordered pairs $\{(x,y) : x \in X, y \in Y\}$. $R$ is a function if each element of $X$ is ...
1
vote
3answers
18 views

How many reflexive binary relations there are on a finite countable set?

We know that binary relation is subset of Cartesian product made by set on to itself. let's say we have a set with two elements $A=\{0,1\}$ So Cartesian product is $C=A\times A = ...
1
vote
2answers
50 views

Wondering if proof is proper

so I have been working on learning some new math in order to prepare for next year. I have been trying to learn proofs, and doing practice questions however the only problem is there are not answers. ...
1
vote
3answers
125 views

Intersection of an Infinite Indexed Family of Sets

In a mathematics course, I came across the following problem: Identify (with a short proof) the following set: $\bigcap_{n\in\mathbb{N}}\left(0,1+\frac{1}{n}\right)$, where ...
16
votes
5answers
1k views

Why isn't the Cantor Set contradictory?

So you start with a 1-dimensional stick, remove the middle third of it, leaving 2 pieces. From each of these 2 pieces, remove the middle third. Etc. Whatever is left at the end of infinitely many ...
0
votes
1answer
56 views

$f(A) \cap f(B) = f(A \cap B)$ if $f$ is a bijection?

I found this statement in a Topology proof - $$f(A) \cap f(B) = f(A \cap B)$$ if $f$ is a bijection I haven't come across this statement before. Is this some axiom of set theory?
3
votes
2answers
48 views

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$.

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$. EDIT: Actually, this identity should hold even if $f$ is not one-to-one (injective), right? ...
-2
votes
1answer
27 views

Two distinct natural numbers are not equivalent to each other

If $m$ and $n$ are two distinct natural numbers, how to prove that they are not equivalent (one to one correspondence)to each other?
1
vote
0answers
35 views

obtaning a set from classes

Is it possible to get a set by a intersection of 2 (non-set) classes? I can see it is possible from a set and a class, simply by a set contained in the class. Also, I think that the union/product of ...
7
votes
2answers
788 views

Are there as many real numbers as there are imaginary numbers?

On the one hand, I know that $\mathbb{R}$ and $\mathbb{I}=\{xi:x\in\mathbb{R}\setminus\{0\}\}$ are both uncountable sets, so they have the same number of elements (i.e. the same cardinality) On the ...
0
votes
2answers
48 views

How to define an isomorphism between $^\omega\omega$ and $\omega^\omega$?

Let $^\omega\omega$ be the set of all functions $x: \omega \to \omega$. Define $A = \{x \in ^\omega\omega \; | \; x \text{ has finite support}\}$, where by "finite support" I mean that the set $\{x(n) ...
0
votes
2answers
39 views

Bernstein sets, Well-Ordering theorem vs Axiom of Choice

In the construction of Bernstein sets (see here), is it necessary to use the well-ordering theorem? Why can't you just use the Axiom of Choice to pick two points?
-1
votes
0answers
22 views

Relation R is symmetric if and only if it is equal to its inverse [on hold]

If $R$ is a relation on set $A$. How do we prove that $R$ is symmetric if and only if $R$ = inverse of $R$?
0
votes
1answer
37 views

Understanding the difference between relations and functions.

$R=\{(1,2),(1,3)\}$ is a relation but not function. The logic for this is that if the first element of every ordered pair must remain different, then it is said to be function. Otherwise, it's just ...
0
votes
2answers
21 views

Fine partitions

I am tasked with the following: Give four different partitions $\Pi_1,\Pi_2,\Pi_3,\Pi_4$ of the set $\Bbb N$ with $\Pi_i$ Finer that $\Pi_{i+1}$ for $i =1,2,3$ I think that partition by 8, 4,2 ...
2
votes
0answers
54 views

Existence and uniqueness up to isomorphism of the real numbers from axioms

Pretty much what the title says: how does one prove the existence and uniqueness of the real number system from the ordered field axioms together with the least-upper-bound property (or maybe some ...
3
votes
5answers
697 views

The ambiguity of set theory language

When I am learning, one thing I am puzzled is the definition. For example, we define $0$ as $\emptyset$. But when we use set language, how could we know we are talking about $0$ or the empty set. ...
0
votes
4answers
14 views

Distributing Set Intersections Over an Intersection

I was working through some examples, and found this to be true: $(A \cap B) \cap (B \cap C) = A \cap B \cap C $ $(A \cap B) \cap(A \cap C) = A \cap B \cap C$ $(A \cap B) \cap(A \cap C) \cap (B ...
2
votes
2answers
41 views

Proving existence of surjective $f:\mathbb{N} \rightarrow A$ implies $A$ is at most countable.

Definition of "at most countable" used: A set $A$ is at most countable iff it's finite or there exists a bijection $f:\mathbb{N} \rightarrow A$. Problem: I want to prove that if there exists a ...
1
vote
2answers
38 views

finding a surjective function if $A=\left \{1,3,6,7,9 \right \},B=\left \{5,8,3,7 \right \}$

Given $A=\left \{1,3,6,7,9 \right \},B=\left \{5,8,3,7 \right \}$ How can I define a function $f:A\rightarrow B$ so that $f$ is a surjective function? I can write it in pairs such as: ...
4
votes
1answer
36 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
-1
votes
0answers
42 views

Is there a total disconnect between two Zermelo Theorems?

I'm referring to the Zermelo Theorems for set theory and game theory. The set theory version deals with the well-ordering principle and axiom of choice. The game theory version deals with the role of ...
-1
votes
0answers
24 views

Does there exist a cardinal $\kappa$ such that $\aleph_{\kappa} = \kappa$? [duplicate]

Does there exist a cardinal $\kappa$ such that $\aleph_{\kappa} = \kappa$ ? Moreover is there one that is regular? Thanks in advance!
2
votes
0answers
14 views

Set with relative complement forms partition

Prove that if $S$ is a set and $ \emptyset \subsetneq A \subsetneq S $ then $\Pi = \{A , S-A \}$ is a partition of $S$. Proposed Solution: Since $ A \subsetneq S$ , we have $S - A \neq ...
0
votes
3answers
27 views

Help to prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$

Prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$ My attempt: $\begin{align} (x,y) \in (A \times B) \cup (C \times D) & \Rightarrow & (x,y) \in (A \times B) \vee ...
2
votes
1answer
42 views

Does something that is injective, surjective or bijective imply that it is a function?

As the title says. Sorry it seems like a silly question but it's something I've been wondering because it seems like sometimes the word "function" is omitted, but other times it is included
2
votes
2answers
25 views

If $A,B$ are equinumerous, then so are their complements

I'm interested to know if the following statement is true: If $A,B \subseteq X$ are equinumerous (i.e. $|A|=|B|$, or there is a bijection $A \to B$), then $X \setminus A$ and $X \setminus B$ are ...