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

0
votes
0answers
21 views

Set theory and well-ordering

Let $X \ne \emptyset, X \subseteq \omega$. Show that there is $n \in X, n \cap X = \emptyset$ I am trying to solve this, but I'm a bit confused. It's stated in relation to the wellordering ...
1
vote
1answer
30 views

Selection of subsets

This is an supplementary exercise from Miklos Bona: A walk through combinatorics. We want to select as many subsets of $[n]=\{1,2,3,..,n\}$ without selecting two subsets such that neither one of them ...
0
votes
1answer
29 views

$S_1 \subset S_2$. To show, $Span(S_1) \subset Span(S_2)$

Prove that if $S_{1} \subset S_{2}$, then $Span(S_{1}) \subset Span(S_{2})$ Approach: Suppose $S_{1} \subset S_{2}$ Let $x \in S_{1}$, then by definition of a subset, $x \in S_{2}$ All possible ...
1
vote
1answer
18 views

Well-ordering and proper subsets

I'm trying to show: $\forall m, n \in \omega (n < m \iff n \subset m)$ I have shown the forward direction, but I'm confused for the reverse. I have stated $n \subset m \iff \forall z(z \in n ...
1
vote
1answer
25 views

Existential instantiation and singleton set with known element

I have been taught that when you apply existential instantiation you cannot instantiate the variable to a particular one or the same one, e.g. from $\exists xFx$ to $Fx$, or from $\exists xFx$ to $Fa$ ...
0
votes
1answer
44 views

Is the following true: an infinite set is countable iff every element has a finite representation?

I think this works for the following: real numbers: uncountable and infinitely long elements, integers: countable and elements of finite length.
0
votes
1answer
29 views

Probability of infected but does not show symptoms of disease?

A person moving through a tuberculosis prone zone has a $50\%$ probability of becoming infected. However, only $30\%$ of infected people develop the disease. What percentage of people moving through a ...
2
votes
4answers
76 views

Is the equality $(0,1]\cup(1,2)=(0,2)$ true?

I believe this is true because the first set contains everything up to and including $1$ and the second contains everything from $1$ onwards.
1
vote
1answer
37 views

Proof that every non-empty subset of a woset (X, $\leq$) has a unique minimal element.

I want to prove that every nonempty subset of a woset (X, $\leq$) has a unique minimal element. What I’m looking for: clarification and/or hints. I want to solve it on my own, but this is all the ...
1
vote
3answers
42 views

Bijective map on $(\Bbb N \times\Bbb N)/R$

I'm not sure how to tackle this problem. Consider the equivalence relation $R$ on $\Bbb N \times\Bbb N$ given by : $$(a, b)R(c, d) \iff a + d = b + c$$ (i) Show that $R$ is an equivalence ...
1
vote
2answers
72 views

What is the intersection of the sets $\{1\}$ and $\{1,2\}$?

What is the intersection of the sets $\{1\}$ and $\{1,2\}$? For me, it would make sense that $\{1\} \cap \{1,2\} = 1$, but I'm afraid it must be $\{1\}$, otherwise for instance $T = \{ \{\}, \{1\}, ...
0
votes
1answer
31 views

Finding vectors in a set.

I am in linear algebra and was given this question as a review: Let $E \subset \mathbb{R}^3$ be the set of all vectors $(x, y, z)$ such that $x + 2y + 3z = 0$. Find two vectors $v, w \in E$ such ...
0
votes
1answer
48 views

Is the intersection of all intervals $\left( 0, \frac{1}{i} \right)$, where $i$ is in $\{1,2,3…\}$, equal to the empty set?

So, does $\big(0,\frac{1}{1}\big)\bigcap\big(0,\frac{1}{2}\big)\bigcap\big(0,\frac{1}{3}\big)\bigcap\dots = \emptyset$ ? This has bugged me for the last couple of hours. The question is whether ...
0
votes
0answers
24 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
62 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
30 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
69 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
59 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
46 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
68 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
34 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
23 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
27 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
23 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
30 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
53 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
74 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: ...
7
votes
1answer
65 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
43 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
59 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
42 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
47 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
44 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
47 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 ...
-2
votes
2answers
49 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
67 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
36 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
44 views

Probability 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 ...