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

3
votes
1answer
44 views

Zorn's lemma to prove existence of maximal element

Let $f : A \rightarrow A$ be bijection. I have to prove that exists maximal subset $B \subset A$ such $B \subset f(A \setminus B)$ using Zorn's lemma.I have observed that $f(A \setminus B) = A ...
0
votes
0answers
33 views

Proving a Set's Equality

This is a homework question. The problem asks Construct an algebraic proof for the given statement. Cite a property form Theorem 6.2.2 for every step. Theorem ...
2
votes
1answer
35 views

I need to verify: $\overline{A\cup \overline{B}}\cup\overline{A}=\overline{A}$

I need to prove the following equality: $$\overline{A\cup \overline{B}}\cup\overline{A}=\overline{A}$$ where $\overline A$ denotes the complement of $A$. I tried to solve it by using De Morgan's ...
2
votes
2answers
48 views

What might be meant by $\left\{0,1,2\right\}^{\mathbb{Z}}$?

What might be meant by $\left\{0,1,2\right\}^{\mathbb{Z}}$? I do not know what this notation means-
11
votes
1answer
767 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 ...
0
votes
3answers
44 views

determining the cardinality [duplicate]

Let $S$ be the collection of closed intervals in the real line whose lengths are positive rational numbers. Determine the cardinality of $S$. Justify your answer As I understand, $S$ will be an ...
-2
votes
2answers
72 views

Is the statement “the empty set is a subspace of every vector space” true of false?

Is this statement true or false, and why? The empty set is a subspace of every vector space.
3
votes
3answers
101 views

Self-studying Russell's Paradox

I'm self-studying and having trouble wrapping my head around Russell's paradox, even after looking here. I'd really appreciate a more intuitive explanation of the concept before I move on to ...
0
votes
1answer
25 views

Are the sets $\{\text{fractional part of } n\sqrt{2} : n \in \mathbb{N}\}$ and $\{(m/n)\sqrt{2} : m,n \in \mathbb{N^+}, (m/n)/\sqrt{2} < 1\}$ equal?

If so, what would be a good strategy for showing that this is true? The first set is the set of the fractional parts of integer multiples of $\sqrt{2}$. The second set is the set of all rational ...
0
votes
2answers
38 views

What is $|T|$ when $|R| = 30,\;R\cup T = 45,\;R\cap T = 8\;?$

If $|R| = 30$ and $R\cup T = 45$, and $R\cap T = 8,\,$ is $\,|T| = 15$? Do you just ignore the value of the intersection? Thanks
0
votes
1answer
38 views

Cardinality of a set of closed intervals

What is the cardinality of the set S of all closed intervals on the real number line with rational (positive) lengths? I believe the number of intervals with a specific fixed length but varying start ...
1
vote
4answers
50 views

Are these an/a $∈$ or $⊆$ of the following set?

Let $A = \{4,5,6,7\}$. Write $∈$ or $⊆$: $\{4\}\underline{\qquad}A$ $\{5,6\}\underline{\qquad}P(A)$ ${∅}\underline{\qquad}P(A)$ $5\underline{\qquad}A$ $A\underline{\qquad}P(A)$ ...
0
votes
1answer
20 views

Give an explicit mapping to show the same cardinality…

So I know that I need to form a bijection, I just need the 2 functions for the different sets. I know that the function for all positive integers divisible by 5 is f(x) = 5x, however I have no clue ...
1
vote
1answer
42 views

a question on cardinality

Suppose $S$ and $T$ are sets such that $|S|=|T|$ Prove that $|\mathcal{P}(S)|=|\mathcal{P}(T)|$. To start with, $|S|<|\mathcal{P}(S)|$; $|T|<|\mathcal{P}(T)|$. Just the statement itself sounds ...
2
votes
1answer
31 views

Finding number of relations on a set with 3 elements

How do I find find out how many non reflexive relations X on the set P = {1, 2, 3}? I know $2^{n^2 - n}$ returns how many reflexive relations there on a set. Do I subtract that from something to get ...
-1
votes
1answer
56 views

Pigeon Hole theory with 10 ints

If I have a set of 10 integers, is it possible to prove there are two that the difference is by a multiple of nine? My instinct says you can find two that differ by a multiple of 5 but not 9
1
vote
3answers
30 views

Prove $F(F^{-1}(B)) = B$ for onto function

Suppose that $f:X \to Y$ is an onto function. Prove that for all subsets $B$ subset of $Y$, $f(f^{-1}(B)) = B$. I don't know how to do this if the function is not also one to one, which it is not. Any ...
2
votes
1answer
53 views

Weird function or not

Is $f\colon\emptyset \to\mathbb{R}$ with $f(x) = (-1)^{\frac{1}{2}}$ a function where $\emptyset$ is the empty set and $\mathbb{R}$ is the set of real numbers?
1
vote
2answers
26 views

Prove that there are proper classes A, B such that $A \cap B= 0$

I am studying the book "introduction to set theory", by Donald Monk, and I am having difficulties to solve some exercises about proper classes, could anybody help me? here they are: Prove that: ...
1
vote
1answer
32 views

Algebra and partions of a set

My book in mathematical finance introduces algebras and partitions of a set, in order to explain how information is modeled to the investor. But there is one thing I don't get. They say that for every ...
2
votes
1answer
36 views

$A_1,A_2,A_3$ forms a partition of $\mathbb N_{>0}$ and $a,b,c \in A_i \implies a+b+c \in A_i$ then at-least one of $A_i$ is closed under addition?

If $A_1,A_2,A_3$ forms a partition of $\mathbb N_{>0}$ such that for any $i=1,2,3$ ; $a,b,c \in A_i \implies a+b+c \in A_i$ then is it true that at-least one of $A_i$ is closed under addition ? I ...
2
votes
1answer
9 views

Proof of quotient set is a partition

To prove a quotient set S/R is a partition of S, one of the requirements is that Union of S/R = S This is a proof that i dont quite understand (proving S is a subset of S/R) ∀x∈S:x∈[x] ...
1
vote
2answers
42 views

If $ X \subseteq A \cup B$, then $X \subseteq A$ or $X \subseteq B$.

If $ X \subseteq A \cup B$, then $X \subseteq A$ or $X \subseteq B$. My counterexample: Let $A = \{1\}$ and $B = \{2\}$. Then $\{1, 2\} \subseteq A\cup B$, but $\{1,2\} \not\subseteq A$ and $\{1,2\} ...
3
votes
2answers
87 views

Bijective function $f: \mathbb{Z} \to \mathbb{N}$

Is it possible to have a bijective function between two sets if the domain is bigger than the co-domain, for instance, a function $f:\mathbb{Z} \to \mathbb{N}$?
-4
votes
1answer
55 views

Injective and Surjective Sets [closed]

Take it on faith that any nonempty subset of $N$ has a smallest element. Write $P(N)$ for the power set of $N$. Define a function $f \colon P(N) \rightarrow P(N)$ as follows: If $S = ∅$, then ...
0
votes
1answer
19 views

$h(\frac{z}{4^{n}})=0$ $\forall z\in\mathbb{Z}$ and $ \forall n\in\mathbb{N}$, prove that $\forall x\in \mathbb{R},\ h(x)=0$

Let $h: \mathbb{R}→\mathbb{R}$ be continuous on $\mathbb{R}$ and $h(\frac{z}{4^{n}})=0$ $\forall z\in\mathbb{Z}$ and $ \forall n\in\mathbb{N}$, prove that $\forall x\in \mathbb{R},\ h(x)=0$ What I ...
0
votes
0answers
20 views

representing intervals as infinite intersectiom or union

I searched for this questions but didn't fine the topic yet. I'm just curious if there is an "easy" way of representing intervals in $\mathbb {R}$ as infinite intersection and or union. For example, ...
2
votes
3answers
34 views

Why is a Symmetric Relation also Transitive?

A relation R on set A is as follows: R = {(1,1), (2,2), (3,3)} R is symmetric! But WHY is R Transitive?
0
votes
1answer
38 views

Open and closed complex sets

was wondering if someone could shine some light on the highlighted half of this question? Any help would be greatly appreciated. Please excuse me for the poor format of the question, I'm new to this! ...
2
votes
1answer
41 views

Chain of elements of a chain of order ideals

Let $P$ be a partially ordered set, and let $I(P)$ be the set of order ideals (i.e. downward-closed sets) in $P$ ordered by inclusion. Suppose that $X$ is a chain of non-empty elements of $I(P)$. ...
1
vote
2answers
44 views

Cartesian product sets

I'm preparing a lesson on the Cartesian product of two sets and I have run into the following confusion: I understand that the Cartesian product is not a commutative operation. Generally speaking, ...
2
votes
2answers
28 views

Why is the bit sequences of infinite length not the same size as bit sequences with finite length?

By sequences of fixed size I mean: say the one with length 1: $$\{ 0,1 \}$$ then length 2: $$\{ 00,01,10,11 \}$$ so let the squence be : $$F =\{\{0,1\}^k : k \in\mathbb{N}\}$$ Let the sequence with ...
0
votes
1answer
42 views

Find chain and antichain equivalent to R

Given partial order $(P(\mathbb{N}), \subset)$. I have to find chain and antichain in this partiar order equipotent to $\mathbb{R}$. Actually, I don't have any idea how to begin :) Any hints?
0
votes
2answers
28 views

Prove $\bigcup_\alpha A_\alpha - \bigcup_\alpha B_\alpha \subset \bigcup_\alpha (A_\alpha - B_\alpha)$

Prove $$\bigcup_\alpha A_\alpha - \bigcup_\alpha B_\alpha \subset \bigcup_\alpha (A_\alpha - B_\alpha)$$ Suppose $x \in \bigcup_\alpha A_\alpha - \bigcup_\alpha B_\alpha$ Then $x \in \bigcup_\alpha ...
1
vote
1answer
56 views

Show that a subset of a Dynkin's class is also a Dynkin's class

If $\mathbb{K}$ is a Dynkin's class, let $$ \mathbb{K}_A=\left\{B\in\mathbb{K}\mid A\cap B\in\mathbb{K}\right\} $$ My textbook claims that it is easy to show that $\mathbb{K}_A$ is also a Dynkin's ...
0
votes
0answers
19 views

Is stable under some “manipulation” the same as closed

Is claiming that a set is stable under the formation of some "manipulation" (e.i union, intersection, difference etc.), the same as saying that the set is closed under the manipulation?
2
votes
3answers
48 views

Prove that $|\mathbb{R} - \{r\}| = c$ for every real number $r$

I am looking to prove the statement in the title, namely $|\mathbb{R} - \{r\}| = c$ for every real number $r$. Obviously $|\mathbb{R}| = c$, so I was wondering if I was supposed to find a bijection ...
1
vote
5answers
93 views

Let A be a set of all infinite sequences consisting of 0's and 1's. Prove that A is not countable.

Sequences such as {010101010101...., 10100100100...., etc} if i am not wrong these sequences can represent all the real numbers in the binary format, so a such a set will not be countable. but i am ...
1
vote
2answers
30 views

Prove set intersection is null

The questions asked me to prove this. I have no idea what I'm doing and I do not have the book. Prove If $A$ is a subset of $B$, and $B\cap C=\emptyset$, then $A\cap C=\emptyset$.
4
votes
3answers
78 views

Is there an injection between $\mathbf{R}$ and $[0,1)$

I want to find an injective map $f\colon\mathbb{R}\to[0,1)$ that is not a transcendental function (I prefer a rational function). Is it possible to find such a function or do I need a transcendental ...
0
votes
0answers
30 views

Ultrametric Sets? How could I make one?

I have been trying to figure out how I might use sets in the ultrametric property could be satisfied on them; for example: $\{X \cup Y\} \leq max\{X,Y\}$ where X and Y are sets. I see that on ...
1
vote
2answers
40 views

Proof of set identities

The question asks to prove that $$(A\cup B')\cap(A'\cup B) = (A\cap B) \cup (A'\cap B')$$ where $A,B$ are sets. How could could i approach and solve this question, and also if there are additional ...
1
vote
1answer
29 views

Identifying sets

I keep seeing written in texts the phrase 'identify sets', for example: Identify $A$ as a subset of $F(A)$ by $a\mapsto f_a$, where $f_a$ is the function which is 1 at a and 0 elsewhere. This is in ...
1
vote
1answer
78 views

What sets does $\mathbb{N}$ include?

My text states that the set $\{1, 2, 3...\}$, and the set $\{101, 102, 103, 104...\}$ are elements of $\mathbb{N}$. Doesn't this imply that $\mathbb{N}=\{1, 2, 3... 101, 102, 103, 104...\{1, 2, 3 ...
1
vote
1answer
21 views

Show that the product $\sigma $-algebra is generated by the $\pi $-system $\{B _1 \times B _2 : B \in \Sigma _1 , B _2 \in \Sigma _2 \} $

Show that the product $\sigma $-algebra is generated by the $\pi $-system $\{B _1 \times B _2 : B_1 \in \Sigma _1 , B _2 \in \Sigma _2 \} $ Let $(X , \Sigma _1) $ and $(Y , \Sigma _2 ) $ be two ...
2
votes
2answers
32 views

Prove that $(\bigcup _{i=1 } ^{\infty } E _i )_x = \bigcup _{i=1 } ^{\infty } (E _i) _x $

Prove that $\left(\bigcup_{i=1}^\infty E _i\right)_x = \bigcup _{i=1}^\infty (E_i)_x$. where $E _x= \{y : (x,y) \in E \}$ I'm not really content with the following, which is my attempt, ...
0
votes
1answer
37 views

How do I prove that $A\subseteq B \Leftrightarrow W-B \subseteq W-A$

I am writing a proof to another statement and this Lemma is missing in order to be complete. How do I prove this formally? $$(A\subseteq B) \Longleftrightarrow (W-B \subseteq W-A)$$
0
votes
2answers
26 views

infinite union and intersection of disjoint sets

Find the sets $$ \bigcup_{N=1}^\infty\left(\bigcap_{n=N}^\infty A_n\right) \text{ and } \bigcap_{N=1}^\infty\left(\bigcup_{n=N}^\infty A_n\right) $$ if (1) $A_1,A_2,\dots$ are pairwise disjoint ...
3
votes
1answer
49 views

If $A \subseteq B$, $a \in A$ and $a \not\in B \setminus C$, then $a\in C$

This is the question: Suppose that $A \subseteq B$, $a \in A$ and $a \not\in B \setminus C$. Prove by the method of contradiction that a ∈ C. This is my proof: Suppose by contradiction $a ...
1
vote
1answer
37 views

Are $A = \{A\}$ and $B = \{B\}$ sets equal?

Let $A$ be a set so that $A = \{ A \}$, and let $B$ be a set so that $B = \{ B \}$. Ignoring the axiom of foundation, are the sets A and B equal ?