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

2
votes
1answer
89 views

Borel Measures: Atomic Decomposition

Context The notion of atoms and point masses agree to certain extent. (See Summary on Atoms.) Measures decompose w.r.t. atoms. (See Paper on Atoms.) Here, the goal is a direct approach to decompose ...
3
votes
2answers
781 views

Intersect and Union of transitive relations

Let $R$ and $S$ be relations on a set $A$. Assume $A$ has at least three elements. These are my best guesses at these two proofs. The first one I don't feel confident about at all, as it seems I'm ...
1
vote
0answers
98 views

Is “to be married” a transitive relation?

If you define a relation on the set of people, given by $R=\{x,y : x\text{ is married with } y\}$. Is this relation transitive? I would say it depends: In the western culture: If $x$ is married with ...
1
vote
1answer
58 views

Example of a well-ordered set with a specific order-type

An example of a set with order type $\omega^2$ is $\mathbb{N}\times\mathbb{N}$ with a lexicographic order. An example of a set with order type $\omega^3$ is ...
0
votes
1answer
58 views

Subset notation with the bar crossed

Reading the book 'An Introduction To Continuous Optimization', I ran across the $\subseteq$ notation, but with the little bar crossed over with a small $45^o$ dash - only the bar, not the whole ...
1
vote
1answer
343 views

Pairwise disjoint proof

Let the positive real numbers be defined as $\{x\in\Bbb R: x>0\}$. For $x\in\Bbb R^+$ let $$A_{x}=\{u \in\Bbb R^+: u/x \in\Bbb Q\}\;.$$ (a) Prove that $\bigcup_{x\in\Bbb R^+}A_x=\Bbb R^+$. ...
4
votes
5answers
218 views

Question about Cartesian products at the elementary level

Suppose $\{ X_\alpha \}_{\alpha \in A} $ is a family of sets indexed by $A$. If $A $ is $\mathbb{N}$, then the Cartesian product of them is just $$ X_1 \times X_2 \times \cdots $$ Reading ...
2
votes
1answer
107 views

cardinality of $\mathbb R$ is the same as the cardinality of $\mathbb R^2$

A problem in my homework is to prove the cardinality of $\mathbb R$ and the cardinality of $\mathbb R^2$ is the same. I'm in my first semester and I have no clue how to do this, do I need the axiom of ...
0
votes
1answer
37 views

Prove the sum and intersection of set

Let $A=(1-\frac{1}{n}, 3-\frac{(-1)^n}{n})$ then I need to find sum and intersection. If n is even then we have $A=(1-\frac{1}{n}, 3-\frac{1}{n})$ if its odd then $A=(1-\frac{1}{n}, 3+\frac{1}{n})$ ...
0
votes
1answer
134 views

Construction of uncountably many non-isomorphic linear (total) orderings of natural numbers

I would like to find a way to construct uncountably many non-isomorphic linear (total) orderings of natural numbers (as stated in the title). I've already constructed two non-isomorphic total ...
1
vote
3answers
90 views

Misconception of Cantor's Theorem(no seqeuence can contain all real numbers.)

When reading the proof of Cantor's Theorem(the one that says no sequence can contain all reals), I feel unsure. The Cantor's Theorem are proved by contradicting the fact that there are some real ...
1
vote
2answers
153 views

Cartesian Product and the empty set

I am not quite sure about the Cartesian Product in combination with the empty set. Let's say: $A := \{\{5\}\}$ and $B := \{\varnothing\}$. What's the proper Cartesian Product? Is it $A\times B = ...
2
votes
1answer
51 views

How to prove this statement $x \not\in D$ then $x \in B$

I am quite a beginner writing proofs, that's why I am asking such a simple question. I have an exercise: Suppose A\B ⊆ C ∩D and x ∈ A. Prove (by using proof techniques) that if $x \notin D$ ...
0
votes
2answers
239 views

Cantor Sets/nonempty/cardinality

Let $S_0=[0,1]$ and define every $S_k$ for $k\geq 1$ \begin{align*} S_1&=\left[0,\frac{1}{3}\right]\cup\left[\frac{2}{3}, 1\right],\\ S_2&=\left[0,\frac{1}{9}\right]\cup\left[\frac{2}{9}, ...
0
votes
1answer
40 views

The result of the following set expression

Can someone please explain the following expression to me and what is the result set? $$ (\{2i \;\vert\; i \in \mathbb{N} \} \cap \{p \;\vert\; p \text{ is a prime number } \} ) \setminus \{z \in ...
1
vote
3answers
78 views

Proof Using cartesian products

Suppose that $A$, $B$, and $C$ are sets. Prove that $(A\cap B)\times C =(A\times C)\cap(B\times C)$. Prove the statement both ways or use only if and only if statements.
1
vote
2answers
49 views

How to change two elements in an uncountably infinite product

I have an uncountable product, say $$\prod_{i \in I}A_i$$ And i want to replace $A_{i_0}$ and $A_{i_1}$ by $B_{i_0}$ and $B_{i_1}$ respectively. However I know that $$\left( \prod_{i \in I, \ i ...
1
vote
1answer
37 views

proof checking - power set and family set

Decide if it is true that $P(A) \subseteq P(B) \implies \bigcup A \subseteq \bigcup B $ where $P(A), P(B)$ are power set and $A,B$ are family of sets My proof: Let $x \in P(A)$ then we have ...
1
vote
2answers
49 views

How can I express that a n-tuple contains an element at least once?

This is a very simple question, yet I could not find a satisfying answer for it. Consider the set $S =\{a, b, c\}$. To describe the fact that the set $S$ contains $b$, you can write $b \in S$. But ...
0
votes
5answers
69 views

Why existence of bijective function between two sets means that they have the same number of elements?

What is wrong with the following logic - let's say there exists $f:A\rightarrow B$ that is bijective, and $g:A\rightarrow B$ that is injective but not bijective. Then in $g$ for every member of $A$ ...
1
vote
1answer
105 views

Cartesian product using family of sets

I have been reading both "Naive set theory - Halmos" and "Joy of sets - Delvin". I couldn't really get what the family of sets mean. $I$ set that they frequently use is i guess a subset of $N$. Other ...
2
votes
3answers
370 views

Proof that every closed subset of $\mathbb R$ is finite or countable or continuum.

I want to prove that every closed subset of $\mathbb R$ is finite or countable or continuum. I know that for arbitrary subset we can not make similar statements - because of continuum hypothesis. ...
2
votes
1answer
32 views

Largest proper subfamily of $P(S)$ closed under unions and intersections

Take a set $x$ with $10$ distinct elements. Every time you have two subsets $A$ and $B,$ you also have $A \cup B$ and $A \cap B.$ What is the maximum number of subsets you can have such that ...
5
votes
3answers
1k views

Inverse of a Function exists iff Function is bijective

How to mathematically prove that inverse of a function, let's say, $f^{-1}$, exists, if and only if $f$ is bijective? I know how to prove it using diagrams but I'm looking for a rather mathematical ...
0
votes
1answer
26 views

When are the following inclusions $\subsetneq$

When does the "equality" part of inclusion fail in: $$\overline{A \cap B} \subseteq \overline{A} \cap \overline{B}$$ and $$Int(A \cup B) \supseteq Int(A) \cup Int(B)$$ ? Can you provide an simple ...
0
votes
2answers
77 views

Is this the middle fourth cantor set?

Let $ D $ be the set of all $ x ∈ [0, 1] $ having a representation in the form $$ \sum_{i=1}^{\infty} {a_i}/{4^i} $$ where each $ a_i $ is either 0 or 3. Does this represent the middle fourth ...
0
votes
2answers
93 views

Can Cantor's theorem prove that $\mathbb N$ is uncountable (paradox)?

I am struggling a bit trying to understand Cantor's theorem about the reals being uncountable. How can you choose a real number that is different from all real numbers in an enumeration $S$? I ...
1
vote
1answer
39 views

Does a surjection from x to y imply a surjection of their power sets?

If there exists a surjection f: X -> Y for some sets X and Y, does this imply there exists a surjection g: P(X) -> P(Y)?
1
vote
1answer
53 views

Set theory, operation with products, union and intersection

I need to show the following using logical connectives: $B\setminus (B \setminus A)=A \cap B $ $(A \setminus B)\cup(B\setminus A)=(A \cup B)\setminus(A \cap B)$ $(A\times B\setminus C )=(A\times ...
2
votes
1answer
39 views

Sum of 3 bijections

This is one problem from my set theory course, which I can't solve. So here is the statement that has to be proven: For every function $f:\mathbb{N} \rightarrow \mathbb{Q}$, there exist $3$ bijections ...
0
votes
3answers
48 views

Verifying that $\mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})=\text{ the }\sigma\text{- algebra generated by }\mathbb{N}\times\mathbb{N}$

I am asked to show that the product $\sigma$-algebra of $\mathcal{P}(\mathbb{N})$ with $\mathcal{P}(\mathbb{N})$ consists of all subsets of $\mathbb{N}\times\mathbb{N}$, or in other words that ...
1
vote
1answer
187 views

Is it bad practice to define a matrix in which the entries are sets?

In one of my other questions (which has no answers by the way - I admit it's rather difficult!), I define a matrix in which each entry is a set. Now that I think about it, I wonder if defining a ...
2
votes
1answer
14 views

Isn't the formulation of Separation shema using finite sets before the term finite is defined?

In Jechs book "Set theory" Jech gives in page 8 a formulation of Separation schema as follows: $Y= \{ u \in X : \phi(u(p_1,...,p_n)) \}$ On the other hand, in page 12, when describing Axion of ...
0
votes
2answers
144 views

Is my proof that the set of all finite subsets of a countable set is countable correct?

Q. Let $X$ be a countable, infinite set. Prove that the set of all finite subsets of $X$ is countable. So I say; Let $X$ countable be given. Let $F$ be the set of all finite subsets of $X$. Let ...
4
votes
2answers
56 views

Find the $\bigcap_{n = 1}^{\infty} (-\frac{1}{n}, \frac{2}{n})$

Find the $\bigcap_{n = 1}^{\infty} (-\frac{1}{n}, \frac{2}{n})$ So the way I understand it is that I'm trying to find $(\frac{-1}{1}, \frac{2}{1}) \bigcap (\frac{-1}{2}, \frac{2}{2}) \bigcap ...
0
votes
2answers
53 views

Step-by-step help using the distributive law in set theory

I need to prove the following set identity but I'm confused as to how to apply the set identities. $\left(A\cup C\right)\cap[\left(A\cap B\right)\cup\left(C'\cap B\right)]=A\cap B$ I tried doing the ...
0
votes
1answer
3k views

Prove the following set identity using the laws of set theory (set identities)

$A$,$B$,$C$, are subsets of a set $S$. Prove the following set identity using the laws of set theory (set identities) $\left(A\cup C\right)\cap[\left(A\cap B\right)\cup\left(C'\cap B\right)]=A\cap B$ ...
1
vote
1answer
44 views

What can be said about $A$ if $P(A) = \{ \emptyset, \{x\}, \{y\},\{x,y\}\}$

What can be said about $A$ if $P(A) = \{ \emptyset, \{x\}, \{y\},\{x,y\}\}$ I'm not entirely sure what this question is asking, but here is what I would assume my answer should be: $A=\{x, y\}$ Am ...
0
votes
1answer
47 views

Set of Monotonic functions , power

I want to determine whether the set of monotonic functions defined on $[0,1]$ has the cardinality of continuum or not. I want to use the fact that monotonic functions have at most countable ...
0
votes
1answer
57 views

Finest Measurable Partition

Disclaimer: This question is part of: Borel Measures: Atoms (Summary) Given a sigma algebra $\Sigma$ over a countable space $\#\Omega\leq\aleph_0$. Does it admit a finest measurable partition: ...
1
vote
3answers
87 views

Find the power set $P(S)$ for $S=\{\emptyset, \{\emptyset\}, \{\emptyset \{\emptyset\}\}\}$

Find the power set $P(S)$ for $S=\{\emptyset, \{\emptyset\}, \{\emptyset \{\emptyset\}\}\}$ OK this problem confuses me for many reasons, but here is what I know. The cardinality of a set is $2^n$ ...
1
vote
2answers
162 views

Describe the following set by giving a characteristic property $\{1, 3, 5, 7, 9, 11, …\}$

Describe the following set by giving a characteristic property $\{1, 3, 5, 7, 9, 11, ...\}$. The book I'm reading doesn't describe how to do this, but do I basically need to describe the pattern I ...
1
vote
1answer
47 views

Cardinality of the power set $\mathcal P\left(S\right),$ where $S$ is a set of $15$ elements?

What is the cardinality of the power set $\mathcal P\left(S\right)$ where $S$ is a set of $15$ elements? I think the power set is a set of all the subsets of a given set or $2^n$. So would the ...
1
vote
2answers
111 views

Finding a function $\mathbb{N} \to \mathbb{N}$ that is surjective but not injective.

The mapping is supposed to be from $\mathbb{N}$ to $\mathbb{N}$. I'm still trying to understand if this is possible, I mean if it was from $\mathbb{R}$ to $\mathbb{N}$, I guess $x^2$ would work.
1
vote
1answer
36 views

Does it exist a family $A$ of subsets of $\mathbb{N}$, with special propertie listed below?

Does it exist a family $A$ of subsets of $\mathbb{N}$, such that $A$ has cardinality of continuum and for any two elements of $A$ one of them is subsets of another? Note - elements of $A$ are subsets ...
0
votes
1answer
41 views

How to show that set B is a subset of A?

We have the following two sets, $A=\{-l,....a,..b,....l\}$ and $B=\{a,....b\}$. I wanted to prove that B is subset of A. I have tried the following way, I wounder whether it is the right one or ...
0
votes
1answer
56 views

Show that $(A \oplus B) \oplus B = A$

I having some trouble proving $(A \oplus B)\oplus B = A$, I understand the truth table logic but can someone example to me in theory what the equation mean in set theory?
1
vote
1answer
71 views

Formal proof that diameter of subset is bounded by diameter of superset (in metric space)

I am asked to show that if $A \subset B$, then $\delta(A)\leq \delta(B)$, where $\delta(A)=\sup_{x,y \in A}d(x,y)$ is the diameter for the non-empty set A in the metric space $(X,d)$. The fact that ...
1
vote
1answer
54 views

Finding the maximum and minimum of sets

1) Does $[0, \sqrt{2}] \cap \mathbb{Q}$ have a minimum? Maximum? Minimum is $0$ since $0$ is also a rational number. $\sqrt{2}$ cannot be the maximum because it is not a rational number. How can I ...
0
votes
2answers
82 views

How to show that 1/4 is in the standard Cantor set?

I have studied the method that shows 1/4 belongs to the standard Cantor set, proving that it has only {0,2} as digits in its ternary expansion. But how can I do this in some other way?