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
1answer
39 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.
1
vote
2answers
58 views

Can you go from $\aleph_0$ to $\aleph_1$ with tetration or other higher order operators?

The paradox of Hilbert's Hotel shows us that you can not get past the cardinality of the natural numbers ($\aleph_0$) by adding a finite number (one new guest), adding an infinite quantity (infinitely ...
3
votes
1answer
57 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
1answer
27 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
74 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.
0
votes
5answers
42 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
vote
1answer
36 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 ...
3
votes
1answer
466 views

How to Prove it 4.1 ex.10

Prove that for any sets A, B, C, and D, if A × B and C × D are disjoint, then either A and C are disjoint or B and D are disjoint. Proof(someones). Suppose (A X B) and (C X D) are disjoint. Let (x,y) ...
35
votes
7answers
13k views

Show that the set of all finite subsets of $\mathbb{N}$ is countable.

Show that the set of all finite subsets of $\mathbb{N}$ is countable. I'm not sure how to do this problem. I keep trying to think of an explicit formula for 1-1 correspondence like adding all the ...
7
votes
1answer
59 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 ...
1
vote
3answers
41 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
70 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
30 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
45 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 ...
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$) ...
2
votes
3answers
65 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
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 ...
2
votes
2answers
59 views

Should it be allowed to apply classical logic to set theory?

It is well known, that the generalized continuum hypothesis isn't provable from the standard axiom system ZFC. GCH (generalized continuum hypothesis). For every infinite set A, there isn't a set M ...
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$ ...
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
45 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 ...
0
votes
1answer
68 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 ...
0
votes
3answers
29 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 ...
1
vote
2answers
32 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
26 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
21 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 ...
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 ...
1
vote
2answers
53 views

The intersection of all events in a sequence has probability $\lim \limits _{k \to \infty} P(A_k)$

If a sequence $A_1, A_2, A_3, \dots$ of events is decreasing, show that the intersection of all events in the sequence has probability: $\lim \limits _{k \to \infty} P(A_k)$. I suck at proofs so I am ...
0
votes
2answers
47 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 ...
0
votes
1answer
52 views

Identify this relation to be an injection, surjection, bijection or non-function

Identify this relation as an injection, surjection, bijection or non-function, where $f:A \rightarrow B$, with $x$ an element of $A$, and the value of $f$ is determined by: $f(x)=$ the number of ...
0
votes
2answers
70 views

Giving a function for a $1-1$ function

Show that the given intervals have the same cardinality by giving a formula for a $1-1$ function, $f$, mapping the first interval onto the second. $[1,3]$ and $[5,25]$ So I understand that I have ...
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, & ...
1
vote
1answer
84 views

Determine if the given relation is an Equivalence relation

Determine whether the given relation is an equivalence relation on the set. $x$ is related to $y$ in the set of real numbers if $|x-y| \leq 3$ So I know to see if a set is an equivalence relation ...
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: ...
-1
votes
2answers
367 views

Well ordered set…confusing

I read the wiki article on it, but still don't get what it is. I have a question regarding it: A set is well ordered if every nonempty subset of this set has a least element. Determine which of ...
-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 ...
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
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
46 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 ...
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 ...
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
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)$.
-2
votes
2answers
47 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
1answer
38 views

Is this a valid notation in set theory?

I have three sets, $A:=\{a_1,\ldots,a_n\}$, $B:=\{b_1,\ldots,b_n\}$ and $C:=\{0\}$. Let $D:=A\times B \cup C$. I do not know if this is a valid notation? For example, Is $(0,b_2)\in D$? Or, is ...