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

1
vote
0answers
34 views

Cantor set - Proove it contains at least one element and find out its cardinality

$\forall\ n \in N $ I have $C_n = \bigcup{\left[{k\over3^n}, {k+1\over3^n} \right]}$ (union of intervals) for every $k\in I_n$ where: $$I_0 = \{0\} \text{ and }I_n = I_{n-1} \cup I_{n-1}', ...
1
vote
2answers
34 views

Prove: $A \cap(B\cup C^*)=(A\cap B)\cup C^*$

How do you prove this mathematically, when $C^*$ is the complement of C? I know from drawing a Venn diagram that this equation should hold. $A \cap(B\cup C^*)=(A\cap B)\cup C^*$ Thanks!
1
vote
3answers
16 views

$A \subseteq X$ and $B \subseteq Y$, show that $(X \times Y) \setminus (A \times B) = (X \setminus A) \times (Y \setminus B)$ is not always true.

I want to prove that $(X \times Y) \setminus (A \times B) = (X \setminus A) \times (Y \setminus B)$ with $A \subseteq X$ and $B \subseteq Y$ is not always true. However, I have difficulties to ...
-1
votes
0answers
23 views

Countable union of countable sets [on hold]

Let $\{A_n\}_{n=1,2...}$ be a sequence of countable sets. Show that $X=\bigcup A_n$ is uncountable.
0
votes
1answer
27 views

Real Analysis Cardinality Proof

I am trying to prove that given a finite set A and an uncountable set B, B and A union B have the same cardinality. I looks to me like I need to show that there is are injective functions from B to A ...
0
votes
1answer
20 views

For each of the following sets, determine whether 2 is an element of that set

c) {2,{2}} d) {{2},{{2}}} The answer for C is yes and d is No, However i still don't understand why the answer for c is yes and d is no anyone know thank
1
vote
3answers
41 views

Set theory proof; (subsets, universal set)

Assume $A,B,C$ are subsets of the universal set, $U$. Prove that $$(A\cap B)\cup C=A\cap(B\cup C)$$ iff $C$ is a subset of $A$. How would you go about proving this? Can I do something with De ...
0
votes
1answer
9 views

Boundedness on k-tuple euclidean space

I am currently studying, "Elementary Analysis:The Theory of Calculus" by Kenneth A. Ross, in my edition on page 82, bounded sequences in $\Re^k$, k-tuple Euclidean space is defined as follow: A set S ...
1
vote
1answer
34 views

There is no set to which every set belongs

I am reading Elements of Set Theory by Enderton H.B. This is probably a simple misunderstanding, but I have become confused by the proof of the first theorem in the book. The theorem is as follows: ...
1
vote
1answer
40 views

The truth set of the formula $\{x\mid x\subset A\}$

I have an assignment where I have to work with power sets (I think): Let $\mathcal{P}(A)$ denote the set $\{ x ~|~ x \subseteq A \}$. And the I have 2 questions: Is the set $\mathcal{P}(A)$ a ...
0
votes
2answers
19 views

Set theory venn diagram problem

Given: Suppose there are 100 students who take at least one of the following languages Japanese, Polish and Arabic. 65 take Japenese; 45 study Polish; 42 study Arabic; 12 take Japense and Arabic, but ...
1
vote
2answers
38 views

How to finish this proof about $\sigma$-algebras?

Let $\Omega$ be a countable set and $\Sigma$ be a $\sigma$-algebra on $\Omega$. Prove that there exists some countable partition of $\Omega$ that spans $\Sigma$. That is, prove the ...
0
votes
1answer
29 views

Intersection of the image of a decreasing chain of sets

Just a quick question that goes as follows. Let $X$ be a nonempty set, $\mathcal{C}$ a decreasing chain of subsets of $X$ with nonempty intersection and $f: X \rightarrow X$ a function such that ...
0
votes
0answers
27 views

Is there a general formula for this set? Or can it be simplified?

I tried to compute some terms and i got to $I_4 = {0,2,6,8,18,20,24,28,54,56,60,62,72,74,78,80}$. The formula is given by recurrence, like this: $$ I_0 = \{0\} \text{ and }I_n = I_{n-1} \bigcup ...
0
votes
0answers
27 views

Borel Measures: Atoms (Summary)

Disclaimer: This is a summary of the discussions: Measure Atoms: Definition? Borel Measures: Discrete & Continuous? Borel Measures: Atoms vs. Point Masses Reference: Further results are ...
4
votes
3answers
386 views

Rigorous proof that surjectivity implies injectivity for finite sets

I'm trying to prove that, for a finite set $A$, if the map $f: A\rightarrow A$ is a surjection, then it's an injection. I've looked at this post: Surjectivity implies injectivity but the arguments ...
-1
votes
0answers
22 views

Set Theory (Cardinality) [duplicate]

Let S be an infinite set. Let P be the set of subsets of S that are finite. Prove that S and P have the same cardinality.
-3
votes
4answers
38 views

Give an example of two uncountable sets A and B such that A ∩ B is [on hold]

Give an example of two uncountable sets A and B such that A ∩ B is a) finite. b) countably infinite. c) uncountable. This is a question in Cardinality of Sets. I was unable to figure out exactly ...
0
votes
0answers
21 views

Prove that for a subset $A$ of $\mathbb{R}$, if $|A| = \omega$ then $|\mathbb{R} - A| = 2^\omega$ [duplicate]

I'm just starting with fundamental set theory and am trying to solve the following problem: Prove that for a subset $A$ of $\mathbb{R}$, if $|A| = \omega$ then $|\mathbb{R} - A| = 2^\omega$. I think ...
6
votes
2answers
495 views

Could someone explain aleph numbers?

I am having trouble understanding aleph numbers. I understand $\aleph_0$ is a countable infinity, but after that, I'm lost. What are $\aleph_1,\aleph_2,\aleph_3$, etc. to $\aleph_n$? Is there an ...
0
votes
1answer
47 views

Show that R is an equivalence relation, where $(a, b)R(c, d) \iff a − d = c − b$ [on hold]

Let $R$ be the relation on $\mathbb Z \times\mathbb Z$, that is elements of this relation are pairs of pairs of integers, such that $((a, b),(c, d)) \in R$ if and only if $a − d = c − b$. Show ...
8
votes
1answer
78 views

seems easy set problem

let A B C be three finite set, prove that: $$|A\cap B|/|A \cup B| + |B\cap C|/|B \cup C| - |A\cap C|/|A \cup C| \le 1$$ It seem's simple, but I tried it for a long time and cannot get it out. Maybe I ...
3
votes
1answer
23 views

Negate the following sentence: If $x \in \mathbb{Q}$ and $x \neq 0$, then $\text{tan}(x) \notin \mathbb{Q}$.

Negate the following sentence: If $x \in \mathbb{Q}$ and $x \neq 0$, then $\text{tan}(x) \notin \mathbb{Q}$. I want to make sure my negation is correct. I will first convert the statement into ...
1
vote
1answer
35 views

How to show if A (A△B)△C=A△(B△C) [duplicate]

im working on problem that asks me to show that for any set a,b,c (A△B)△C=A△(B△C) In my opinion, I can just use associative law of set theory and just conclude that left equals the right. But then ...
0
votes
2answers
14 views

Proving Sets are Equivalent with Cartesian Products

$A \times B \times (A \cap C) \subseteq (A \times B \times A) \cap (A \times B \times C)$ I need some help with proving this statement. So far I've got: If $x$ in an element in $A \times B \times ...
1
vote
2answers
61 views

Prove that $\mathcal P(A \cap B)=\mathcal P(A) \cap \mathcal P (B)$

Probably this is an easy problem, but this time I am not understanding these concepts. The problem starts with: Let $\mathcal{P}(A)$ denote the set $\{ x ~|~ x \subseteq A \}$ What I think is ...
0
votes
2answers
22 views

Equation with infinite set difference and intersection

Given $$ \dots A_2\subseteq A_1\subseteq A_0 = U$$ and $$\bigcup_{n=0}^\infty (A_n \backslash A_{n+1})\cup\left(\bigcap_{n=0}^\infty A_n\right) = U$$ when $U$ is the universal set, prove that ...
0
votes
0answers
15 views

Cofinite Topology: Borel Algebra?

Given the cofinite topology: $$\mathcal{T}:=\{U\subseteq\Omega:\#U^c<\infty\}$$ and generate its Borel algebra: $$\sigma(\mathcal{T})=\{E\subseteq\Omega:\#E\leq\aleph_0\lor\#E^c\leq\aleph_0\}$$ Why ...
4
votes
2answers
78 views

Borel Measures: Atoms vs. Point Masses

Let a measure be $\mu:\Sigma\to\mathbb{R}_+$. Call a measurable $A\in\Sigma$ an atom if: $$\mu(A)>0:\quad\mu(E)<\mu(A)\implies\mu(E)=0\quad(E\subseteq A)$$ and a singleton $\{a\}\in\Sigma$ a ...
2
votes
1answer
28 views

Show that $(\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A)$.

Let $A, B,$ and $C$ be sets. Show that: $$ (\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A) $$ I’ve simplified to the following: $$ (\overline A ∪ B) ∩ (\overline{C \cup A}) = ...
1
vote
1answer
19 views

inclusion of sets and inverse function

Is it true that for any function $f$, and sets $S_1,S_2$ such that $f:S1\rightarrow S2$, if g is the inverse of f $g = f^{-1}$, then $f(g[S1])\subseteq S1\subseteq g(f[S1])$?. If yes, is there a ...
0
votes
3answers
97 views

Why there is a unique empty set?

I Have a question. Given only the definition of equality of two sets, how can we prove that there is one and only one empty set. I mean by equality of two sets the following: $$A=B \iff \forall x (x ...
2
votes
2answers
34 views

Prove that $(\mathbb{N},\le)$ and $(\mathbb{Z}, \le)$ are not order isomorphic

I want to prove that $(\mathbb{N},\le)$ and $(\mathbb{Z}, \le)$ are not order isomorphic. So what I want to show is that the following is not true: $$x \le_\mathbb{N} y \iff f(x) \le_\mathbb{Z} ...
0
votes
2answers
25 views

For all $X \subseteq \mathbb{N}$ there exist $n \in \mathbb{N}$ with $|X| < n$.

True or false? For all $X \subseteq \mathbb{N}$ there exist $n \in \mathbb{N}$ with $|X| < n$. I think this is false because if you pick $X = \mathbb{N}$, then the inequality $|X| < n$ does ...
1
vote
1answer
21 views

intersection of antisymetric relations is antisymetric

Suppose $A$ is some set, and $R$ and $S$ are relations on $A$ s.t. $R$ and $S$ are anti-symmetric. I want to prove that $R\cap S$ is anti-symmetric. Let $a,b \in A \ $ s.t. $a\ne b$ and $(a,b)\in ...
-4
votes
2answers
23 views

Simple set theory proof [on hold]

Prove that the intersection $$ \bigcap_{n \in \mathbb{N}}\left(-\frac{1}{n},1\right) = [0,1)$$ without using limits. I know that I need to prove subset in both directions.
0
votes
1answer
24 views

“if f is an injection, then $f^{-1}(f(x))=x$ for all x in D(f) and $f(f^{-1}(y))=y$ for all y in R(f)”

How can I prove that "if f is an injection, then $f^{-1}(f(x))=x$ for all x in D(f) and $f(f^{-1}(y))=y$ for all y in R(f)" Does anyone could help keep? Thanks!
1
vote
1answer
28 views

Restriction of an equivalence relation on a subset.

If we have an equivalence relation defined on a set E and S its subset. Is the relation defined on S is also an equivalence one? Thank you for your answers.
3
votes
3answers
68 views

Existence of a countable $\sigma$-algebra on an uncountable set

Let $\Omega$ be a set. If $\Omega$ is finite, then any $\sigma$-algebra on $\Omega$ is finite. If $\Omega$ is infinite and countable, a $\sigma$-algebra on $\Omega$ cannot be infinite and ...
3
votes
1answer
17 views

Can I represent $S = \{x: \sin(x) > 0\}$ as $\bigcup_{k\in\Bbb Z} \left[\frac {\pi}{6}+2\pi k,\frac {5}{6} \pi+2\pi k\right]$?

Is it correct to represent $S = \{x: \sin(x) > 0\}$ as $\bigcup_{k\in\Bbb Z} \left[\dfrac {\pi}{6}+2\pi k,\dfrac {5}{6} \pi+2\pi k\right]$?
0
votes
0answers
25 views

Cardinality of the set $\mathbb{Z}_{26}^5$

I am trying to compute the unicity for a Vigenère cipher with $m=5$ to compute this I need the sizes(cardinality) of the plaintext space and key space they are the sets $\mathbb{Z}_{26}^5$. Integers ...
4
votes
1answer
38 views

Would you accept this proof for $(A^c)^c = A$?

In my exercises I had the following question: Prove that $(A^c)^c = A$. My solution: Let $A$ be a set where $A\subset X$. $A = \{x \in X, x \in A\}$ by definition. $A^c = \{x \in X, x \notin A\}$ ...
1
vote
1answer
43 views

How to write $H = \{x: \cos(x) > 0\}$ as the union of the intervals?

I have $\dfrac {1}{2}\left( 4\pi k\pm k \right) ,k\in \mathbb{Z}$. But I don't understand how to represent it as the union of the intervals.
-2
votes
2answers
46 views

Prove that $ |A∪B|=|A|+|B|-|A∩B|$ [on hold]

If $A, B$ and $C$ are finite sets, prove that $$|A\cup B|=|A|+|B|-|A\cap B|$$ $$|A\setminus B|=|A|-|A\cap B| $$ $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|$$
0
votes
0answers
17 views

Inductive Property of Sets?

Why doesn't the set: $ {2,4,6,8,10,.....}$ have the inductive property. For example $ n = 2k$. So for every value of k you get a value of $n$. Plus $k+1$ is also present. So shouldn't this set have ...
1
vote
1answer
31 views

My question is a very basic one about relations

I am learning about relations right now and I have a question about some terms. I am told a relation on $A$ is a subset of $A\times A$. Then I am told a relation $R$ on $A$ is reflexive if for all ...
0
votes
1answer
47 views

Countability for Subset of Irrational Number [on hold]

I know that the set $I$ of irrational numbers is uncountable. But how to know that $$C=\{{x\in I, 0\leq x^2 \leq25}\}$$ is uncountable or not?
2
votes
3answers
22 views

Please help me with this set operation (Corrected question)

"$A$ and $C$ are disjoint sets, schematize $(A^c \cup B^c)\cap C$." Please help me. My answer was "$C$". Thank you. (I can't comment, so I put the upgraded question...)
-1
votes
1answer
23 views

Could you help me with this set operations? [on hold]

"$A$ and $B$ are disjoint sets, schematize $(A^c \cup B^c)\cap C$." Please help me. My answer was "$C$". Thank you.
1
vote
1answer
28 views

Is this proof correct (Cartesian Products and Subsets)?

I am trying to prove that if $A \times B$ is a subset of $A \times C$ then $B$ is a subset of $C$ given that $A$ is not empty. I've looked at this question on here and I'm aware it's been asked. My ...