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
0answers
11 views

Proving that union of epsilon nets is an epsilon net

While reading a paper, I came across these definitions and claims: Definition: Given $p \in \mathbb R^d$, and $H$, a set of hyperplanes, let $\text{Violate}_p(H) = \{h \in H: h \text{ is strictly ...
0
votes
0answers
20 views

formulation of replacement

I just read the following formulation of the Axiom of Replacement in lecture notes, and am confused. "For all $x, v_1, v_2,...v_n$, if $F(v_1, v_2,...v_n, u, v)$ is functional, then there is a $y$ ...
3
votes
1answer
49 views

Why $C(X,Y)$ ,namely the morphisms between $X$ and $Y$, is assumed to be a set rather than a class?

I understand that we introduce the notion of class to bypass the paradox of the "set of all sets". However, shouldn't $C(X,Y)$ considered to be the set of all morphisms between $X$ and $Y$, thus not a ...
0
votes
3answers
25 views

Prove that the following statements are all logically equivalent.

Prove that the following statements are logically equivalent: $A \subseteq B$ $A \cap B = A$ $A \cup B = B$ $B^c \subseteq A^c$ Here is what I have so far. I am not sure how ...
1
vote
1answer
17 views

Set algebra and expected value, this manipulation is correct?

Im doing a problem where I must evaluate the expected value of random variable $XY$, where $Y=M-X$. My question, this manipulation is correct? $$\Bbb E[XY]=\Bbb E[X\cap Y]=\Bbb E[X\cap (M\cap ...
0
votes
1answer
67 views

Is the set of languages over an alphabet Σ missing k words from Σ* countable?

My original question is whether $\mathscr{L}$, the set of all languages over an alphabet $Σ$, each of which missing finitely number of words from $Σ$* is countable. I think I can prove the set is ...
1
vote
2answers
56 views

(exercise from Tao's analysis book) Proof of a lemma relating to power set of X

I'm stuck at one exercise from chapter of sets from Terence Tao's analysis book. I need to proof the lemma: Lemma: Let $X$ be a set. Then the set $\{Y : Y \:\text{is a subset of}\: X\}$ is a set. ...
-1
votes
1answer
44 views

Set theory trees and types. [on hold]

If we had a tree, with one mother (root node) and two terminal sister nodes, such that $x \rightarrow y+z$, and you knew that $x$ had a type of $(e,t)$, and $y$ had a type of $(e,(e,t))$, how do you ...
2
votes
3answers
60 views

How to show $A\cup(A\cap B) = A$ using set properties

I am having a hard time proving this simple and natural identity of sets. what I do is go round and round in circles: $$A\cup( A\cap B) = (A\cup A) \cap (A\cup B)$$ $$= A \cap(A\cup B)$$ Now what? I ...
1
vote
2answers
31 views

Area of piece of paper folded around straight line of orientation $\theta$

Imagine drawing a straight line $l$ through the center of a square piece of paper with area $1$. Now fold the paper along that line. Q: What is the function for the area covered by the folded ...
0
votes
0answers
22 views

Intersections: Generator

Problem Given a set $\Omega$. Define the generator: $$\mathcal{A}\subseteq\mathcal{P}\Omega:\quad\delta\mathcal{A}:=\{A\cap A':A,A'\in\mathcal{A}\}$$ Then one obtains: ...
0
votes
2answers
23 views

Proof using the laws of set algebra.

Q.Prove: $A=(A\cap B)\cup (A-B)$ I want to prove it using set laws. But I am lacking of any hint to break L.H.S into any usable result. Any hints will be appreciated.
0
votes
1answer
19 views

Classes, transitive sets and unions/intersections.

I am trying to solve: Let $X$ be a class of transitive sets. then $\cup X$ is transitive. If $X \ne \emptyset$ then $\cap X$ is transitive. My definition of transitive is: $\forall y \in x (y ...
1
vote
1answer
28 views

Reflexive and transitive closure of a binary relation

If relation A is a binary relation between terms of the form (C,s), and relation B is the reflexive and transitive closure of A, could somebody briefly explain what it means to be a 'Reflexive and ...
0
votes
3answers
52 views

Topological Continuous Functions and Non-Open Sets

Let us consider a function $\ \mathbf F $ defined from $\ \mathbf X $ to $\ \mathbf Y $ , where $\ \mathbf X $ and $\ \mathbf Y $ are topological spaces. Now by definition , a continuous function is ...
4
votes
1answer
37 views

Prove that $\sigma(F)=\Omega$

Let $F=\{A_1,...,A_n\}\subset P(X)$; $F_a=A_1^{a_1}\cap A_2^{a_2}\cap\cdots \cap A_n^{a_n}$ $ a=(a_1,...,a_n)\in \{0,1\}^n$ $$A^{a_i} = \begin{cases} A, & \text{if } a_i=0 \\ A^c, & ...
-4
votes
4answers
73 views

Find $A$ and $B$ such that $A⊈B$ and $B⊈A$? [on hold]

I need to prove that the subset relation “$⊆$” on all subsets of $\mathbb Z$ is not a total order and I'm going to do this by finding $A$ and $B$ such that $A⊈B$ and $B⊈A$? Is there a simple solution ...
1
vote
1answer
20 views

Cartesian Product: Unions

Given a set $\Omega$. Consider families: $$A:\Lambda\to\mathcal{P}\Omega\quad B:\Lambda\to\mathcal{P}\Omega$$ and sets $A_0,B_0\in\mathcal{P}\Omega$. For products one has: ...
6
votes
0answers
47 views

Does a map between topologies determine a map between sets?

Let $(X,\mathcal{A})$ and $(Y,\mathcal{B})$ be Hausdorff spaces. Consider a function \begin{equation*} \phi:\mathcal{B}\rightarrow \mathcal{A} \end{equation*} which preserves inclusion, arbitrary ...
4
votes
2answers
42 views

Ordered sets - can there be two of the same element? (set theory)

In set theory, can you have an ordered set which contains the same element? For instance, if you have a cartesian product which has an ordered pair of $\langle a,a\rangle$, do you keep these as two ...
4
votes
1answer
56 views

Show that for $\lambda<0$ we have $\inf(\lambda A)=\lambda \sup(A)$

For $A\subset \mathbb{R}$ and $\lambda \in \mathbb{R}$ let's define: $$ \lambda A = \{\lambda a: a\in A\} $$ I have to prove that for $\lambda<0$ and bounded $A$ we have $\inf(\lambda A)=\lambda ...
1
vote
1answer
34 views

Logical form of a set-theoretic statement.

From Velleman's 'How to Prove it' book, there is one statement - written below - of which I don't know how to write the logical form of, and I'm wondering if somebody could write it out. The ...
0
votes
0answers
41 views

Good ordered set [on hold]

The set [5, $\infty$) $\cap$ N is a good ordered set than the relation "<"? If it is, I must demonstrated it. So, a good ordered set = if any subsets non-empty of it, has an initial element. ...
0
votes
1answer
42 views

Union is finite implies the collection is finite

Let $C$ be a collection of sets, and $\bigcup C \in V_{\omega}$ where $V_{\omega}$ is the collection of hereditarily finite sets. Is it possible to show that $C\in V_{\omega}$? YES. Because ...
0
votes
1answer
24 views

How to prove that $(A \cup B) - C = (A - C) \cap (B - C)$ [on hold]

If true, prove else provide a counter example. This is a homework question and I cant figure it out. Please help.
1
vote
1answer
46 views

How many maps can exist between two sets?

I'm working on the following exercise. Why does the solution omit applying induction on $n$? That is, assume $P(n)$ and then use that assumption to prove $P(n + 1)$.
1
vote
0answers
41 views

Inductively show that "the ordered n-tuple $(x_1,\ldots,x_n)$ of a set so that $(x_1, \ldots,x_n) = (y_1,\ldots,y_n)$ if their coords are ordered

Full Question (Sorry for the delay): Provide an inductive definition of “the ordered n-tuple ($x_1,\ldots,x_n$) of elements $x_1,\ldots,x_n$ of a set” so that ($x_1,\ldots,x_n$) and ($y_1,\ldots,y_n$) ...
1
vote
1answer
45 views

Show that if $(x_1,x_2)$ is defined to be $\{\{x_1\},\{x_1,x_2\}\}$ then $(x_1,x_2)=(y_1,y_2)$ iff $x_1=y_1$ and $x_2=y_2$ [duplicate]

My Work: If you take the cartesian product of any set with two arbitrary elements $a$ and $b$, and the resulting set is $\{\{x_1\},\{x_1,x_2\}\}$, then the only possible values for $a$ and $b$ are ...
-1
votes
2answers
46 views

Discrete math, proving sets [on hold]

I am studying discrete math and i stumbled upon a proof i couldnt proove, can someone help me with this one? "Assume that A,B,C are three sets with no elements in all three sets. Assume further that ...
2
votes
3answers
64 views

What is a “lattice” in set theory??? [on hold]

NOTE: There is another question asking "What is a Lattice?" but when reading the question, it has to do with programming, and that is not what my question has to do with. The answer provided to that ...
-1
votes
2answers
35 views

Sets what is it equal to

http://i.stack.imgur.com/2SxwV.jpg Why is the answer D? I think the answer is B. How can it be empty - since we are removing the set A?
0
votes
5answers
37 views

Probabilty derivation using axioms

$$P((A \cap B^c) \cup (A^c \cap B))=P(A) + P(B) -2P(A \cap B).$$ I need to show this holds. I see it with Venn diagrams but I need to show it using only the axiom, for the union of two disjoint sets: ...
-1
votes
2answers
24 views

How can I further simplify $(B^c ∩ (B ∩ A)^c)^c$

I'm pretty sure this is equal to B, but I'm not sure how to go about reducing this step by step. Could I use the double negative law to eliminate the complements? I'm not positive if that would work ...
0
votes
3answers
22 views

Finding the complement of a set

I have the sets A, B, and C: $A = \{x\in\mathbb{Z} | 2 < x < 5\}$ $B = \{x\in\mathbb{Z} | 4 ≤ x ≤ 7\}$ $C = \{x\in\mathbb{Z} | 2 ≤x< 6\}$ What is $B ∩ C^c$? If the complement of C is all ...
0
votes
1answer
47 views

Subset relation ⊆ on all subsets of ℤ is a partial order, not a total order.

I need to prove that the subset relation “⊆” on all subsets of ℤ is a partial order but not a total order. I'm not experienced in these kind of proofs and was hoping to see an example of an easier one ...
0
votes
1answer
26 views

infinite countably cartesian product

Let $A^{\mathbb N}=\prod_{m\in\mathbb N} A_m$ be the infinite countably cartesian product of the sets $A_m$. Let $A_i'$ be a subset of $A_i$ for $i=1,...,n$. Is it true that $A_1'\times ...
0
votes
1answer
20 views

Union of a chain of cardinalities?

I was trying to understand the union of a chain of cardinalities and I found this equation $$\kappa=\bigcup_{\alpha<\kappa} \alpha$$ for any cardinal $\kappa$ in the answers to this question. Can ...
2
votes
2answers
24 views

subsets in the cartesian product

Let $A,B,C,D$ be sets. Consider $A\times B$ and $X\subseteq A\times B$. Is it true that $X$ has the form $A'\times B'$ where $A'\subseteq A$ and $B'\subseteq B$ ? At the same time is it true that ...
0
votes
2answers
23 views

Intersection of three sets

Suppose I have three finite sets $A, B, C$. I want to find a function $f$ such that $|A \cap B \cap C| = f(|A|, |B|, |C|, |A \cap B|, |A \cap C|, |B \cap C|)$ Does such a function exist? The only ...
1
vote
2answers
27 views

Munkres Topology , minimal uncountable well ordered set

This question is from Munkres Topology, page 67: Let $S_{\Omega}$ be the minimal uncountable well ordered set. Since there is no largest element in $S_{\Omega}$, every element in $S_{\Omega}$ has ...
0
votes
1answer
21 views

Proving that divisibility in an integral domain is a partial ordering

Given that R is an integral domain. I'm trying to prove that divisibility on this set constitutes a partial ordering. In particular, I have defined the relation $y \leq_{\,d} x$ on R by $y|x$. ...
-1
votes
2answers
52 views

How many sequences of rational numbers in $[0,1]$ exist?

I was talking with a friend of mine and we wonder how many sequences of rational numbers on $[0,1]$ there exists. My first attempt was to consider that every sequence like that must be a subset of ...
1
vote
1answer
41 views

Measurable Subsets

Let $\{E_{j}\}$, $j = 1, 2, ..., \infty$, be measurable subsets of $[0,1]$. Also, $\displaystyle\sum_{j=1}^{\infty} |E_j| = M < \infty$ Let $S_n$ be the set of points in $[0,1]$ contained in at ...
-3
votes
1answer
15 views

Proving or disproving set statements. [on hold]

I'm not sure how to approach proving or disproving these statements. I don't know where to begin, or more specifically, what it's asking me to prove or disprove. If $ A \cap B \subseteq C$ and $A ...
1
vote
3answers
39 views

How to prove that $x^2 + 3y^2 = 1$ is contained inside of the unit ball?

What is the best way to show that $S = \{(x,y) | x^2 + 3y^2 = 1\}$ is contained in the unit ball without graphing the set?
2
votes
3answers
44 views

Largest possible value of $P(A \cap B)$

Suppose $A$ and $B$ are events with $P(A)+P(B)>1$. Show that the largest possible value of $P(A \cap B)$ is $ \min(P(A), P(B))$. I suspect I'm supposed to use $P(A \cap B) = P(A)+P(B) -P(A ...
1
vote
3answers
66 views

Explicit bijection between $\mathbb{R}$ and $\mathcal{P}(\mathbb{N})$

Is there any known explicit bijection between these two sets? I know it can be proved that such bijection exists using two injections and Schröder–Bernstein theorem, but I wanted to know whether ...
1
vote
1answer
55 views

Interpretation of set operations notation

I've been given a task that reads: Prove that given formulae is correct with the use of set theory axioms: $(\forall a)(\exists b)(\forall c)((c \in b) \iff (\exists d \in a)(c \subset d))$ ...
1
vote
1answer
36 views

Show that binary words with the same numbers of 0s and 1s are countable by finding bijection from the natural numbers to the set.

Consider all finite binary words that have the same number of zeroes as ones (ex: 0101). How can we show that this is countable? I have tried listing some words in lexicographic order, but I don't ...
0
votes
3answers
56 views

Why does the equality not hold for $(A \times B ) \cup ( C \times D ) \subset ( A \cup C ) \times ( B \cup D )$

I have proved this expression but I want to prove that they both are not equal. $$(A \times B ) \cup ( C \times D ) \subset ( A \cup C ) \times ( B \cup D )$$ May be I have to prove that $( A \cup C ...