Tagged Questions

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

4
votes
1answer
25 views

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

Find the $\bigcap_{n = 1}^{\infty} (-\frac{1}{n}, \frac{2}{n})$ I know that $\{0\}$ is in the intersection because it lies between negative and positive numbers. I want to show that for $x > 0$, ...
-1
votes
0answers
32 views

Too much equality?!

It seems that the concept of equality is somewhat tricky, so I was hoping someone out there can chime in on how to disentangle the below issue: Definitions of Equality If two numbers $X$ and $Y$ ...
3
votes
3answers
50 views

Why is $\emptyset$ a subset of every set?

Please read the details of this question before answering. I am reading a book in which they say $\emptyset \subseteq S$ for any set $S$. One justification they give for this is that if $\emptyset ...
0
votes
0answers
11 views

Finding the size or bounds of a finite set from families of maps into it

Given a finite set $X$ with $x$ elements and a set $K$ with $k$ elements and knowing that there are $n$ families of functions $K \rightarrow X$, each of which has at most $2^x$ distinct functions, can ...
0
votes
3answers
33 views

Prove that there exist sets $A, B, C$ with $A \cup C \subseteq B \cup C$ and $A \not \subseteq B$

Prove that there exist sets $A, B, C$ with $A \cup C \subseteq B \cup C$ and $A \not \subseteq B$ Here is my attempt: Proof: Suppose $x \in A \cup C$. Then by definition we know that $in \in A$ or ...
0
votes
2answers
17 views

troubles proving $ \bigcup_{n\in\mathbb N}A_n = \bigcup_{n\in\mathbb N}\bigl(A_n\setminus\bigcup_{k=1}^{n-1} A_k\bigr)$ for sets $A_i$. [duplicate]

How can we show $$ \bigcup_{n\in\mathbb N}A_n = \bigcup_{n\in\mathbb N}\bigl(A_n\setminus\bigcup_{k=1}^{n-1} A_k\bigr)$$ for any family of sets? So let $x\in \bigcup_{n\in\mathbb ...
1
vote
2answers
55 views

The cardinality of a union of two sets

Assume that the cardinality of the union of two sets is continuum. How to prove that at least one of the sets has the cardinality of a continuum? I suppose that it's possible to cope with it, using ...
1
vote
3answers
19 views

$C_n:=A_n\cap (A_1\cup\cdots\cup A_{n-1})^c$ pairwise disjoint?

Let $\Omega$ be a set and $A_1,\ldots\in Pot(\Omega)$. Why are the sets $C_n:=A_n\cap (A_1\cup\cdots\cup A_{n-1})^c$ pairwise disjoint? I've tried to write it like $C_n\cap ...
0
votes
0answers
22 views

prove well-ordering of nonnull subset of positive ints using weak induction

Let $S\subseteq Z^+$. If $S$ has one element it must be the smallest element and hence it is well-ordered. Assume true for $S$ having $n$ elements. If $S$ has $n+1$ elements if the smallest is ...
1
vote
0answers
14 views

Borel Measures: Discrete 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 ...
2
votes
2answers
114 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 ...
0
votes
0answers
56 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 ...
0
votes
1answer
20 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
18 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 ...
-5
votes
0answers
27 views

n(a∪b∪c)=?? Math questions [on hold]

n(a∪b∪c)=??what formula should it be?? Thank you very much! Please explain answer with understandable process.
1
vote
1answer
48 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^+$. ...
3
votes
4answers
124 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 ...
1
vote
0answers
39 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
11 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})$ ...
1
vote
1answer
26 views

Arbitrary Union of Arbitrary Intersection of set given by formula of 2 natural variables

I've been given a problem to solve. I've got a set $A_{n,m} = \{ x \in \mathbb{R} : n - \frac{1}{m+2} \le x \le n+m, n\in\mathbb{N}, m\in\mathbb{N} \}$ And I need to find ...
0
votes
1answer
27 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
66 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
31 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
0answers
22 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
45 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
17 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
2answers
23 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
31 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
21 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 ...
0
votes
2answers
19 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
34 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$ ...
0
votes
1answer
18 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
1answer
28 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 ...
0
votes
1answer
19 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
17 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 ...
1
vote
1answer
22 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
35 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
30 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
34 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 ...
0
votes
1answer
25 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
12 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
0answers
17 views

Can binomial coefficient be defined as a natural number if n is the cardinality of a countable set?

Can binomial coefficient n choose k, k less than or equal to n, be defined as a natural number if n is the cardinality of a countable set?
0
votes
2answers
33 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
37 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
25 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
17 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
30 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
0answers
32 views

Set theory/ relations

The task is to find out whether the following notations are: reflexive symmetric antisymmetric transitive alternative $M \subseteq N$ $M \subset N$ $M \cup N$ $M \cap N$ $M \setminus N$ $M \cap N ...
0
votes
1answer
17 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
36 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: ...