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

-1
votes
1answer
13 views

How to prove that $(A \cup B) - C = (A - C) \cap (B - C)$

If true, prove else provide a counter example. This is a homework question and I cant figure it out. Please help.
1
vote
1answer
34 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)$.
0
votes
0answers
26 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

I believe that the $n=1$ step is more or less trivial because there is no order to a step that involves only a single element However, I have extreme difficulty determining how to prove the n=k+1 ...
0
votes
1answer
20 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$

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
31 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
4answers
52 views

What is a “lattice” in set theory???

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
34 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
32 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
21 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
20 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
20 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
25 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
18 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
23 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
19 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
23 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
17 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
45 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
40 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
13 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
37 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
37 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
63 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
53 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
33 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
55 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 ...
2
votes
3answers
144 views

Can the cardinality of a power set ever be odd? [on hold]

Can the cardinality of a power set ever be odd? If it can, what conditions must be met?
0
votes
2answers
25 views

Elementary Set Theory ~ Partitions

I tried searching for a related thread to this, so please don't roast me too hard if one already exists. Anyways, if I have a set $A = \{a, b, c\}$ then $\{a, b, c\}$ would not be considered a ...
1
vote
2answers
37 views

Separation and Russell's paradox

I just want to be sure that I understand the connection between "Naive Comprehension", the Axiom of Separation, Russell's Paradox, and the existence of a universal set. Is the following correct? The ...
1
vote
3answers
61 views

Power set, Why is a right?

Can someone tell me why the first choice is the correct answer?
0
votes
1answer
27 views

Proof of Sets involving the Cartesian Product

The question goes: Let $A,B,C,D$ be sets. Prove that $\big(A\times B\big)\bigcup \big(C\times D\big)=\big(A\bigcap C\big)\times \big(B\bigcap D\big)$ I started with the definition of the cartesian ...
0
votes
2answers
77 views

Does ZFC allow for the existence of any paradoxical sets? [on hold]

ZFC doesn't allow for classes like the Russell Set (aptly named as a set I suppose...) to be sets, but my question is the following: In general, if X is a set in the ZFC universe, then for some ...
0
votes
1answer
23 views

If P(i) is true for all integers i with 2≤i≤k as inductive hypothesis, then why also p(t) is true by the inductive hypothesis?

"Let P(n) be the property n is divisible by a prime number. We prove that P(n) is true for all integers n with n> 1. Basis step. If n=2, then P(n) is true because 2 is a prime and every ...
0
votes
1answer
50 views

Cardinality of infinite sets

Georg Cantor postulated a theorem that states that for any set (even if it's an infinite set) $A$, the power set of A ($\mathbb{P}(A)$) has cardinality greater than $A$. Could this theorem also be ...
0
votes
1answer
36 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 ...
2
votes
2answers
51 views

Proof on Functions /Set Theory

Let $S$ be the set of all numbers of the form $a + b\sqrt 2$ where $a$ and $b$ are rational. Let $f : S \to R$ be a function such that $f(x+y)=f(x)+f(y)$ for all $x$ and $y$ in $S$. Then $f(x)=f(1)x$ ...
0
votes
1answer
20 views

Equality between 3 sets using 3 inclusions

Let $A$, $B$ and $C$ be 3 sets. I want to show that $A=B=C$, can we use only three inclusions to do that ? For example we use $A \subset B\subset C\subset A$. Is this the only way to do this with ...
2
votes
3answers
102 views

Russell's paradox question

Tao's analysis book uses following example for Russell's paradox: $$P(x) \Longrightarrow `` x\text{ is a set, and }x \notin x"\\ \Omega := \{x : P(x)\text{ is true} \} = \{x : x\text{ is a set and }x ...
1
vote
2answers
48 views

Is my proof of the principle of backward induction using well-ordering correct?

I'm trying to prove backward induction, which I'll state as follows: Consider the set $\mathsf{A}$, where $n\in{\mathsf{A}}$, and $m+1\in{\mathsf{A}}$ $\implies$$m\in{\mathsf{A}}$. Then ...
0
votes
1answer
39 views

Mathematical induction condition “p(k)$\Rightarrow$p(k+1)” for the divisibility by a prime number

" Mathematical induction If p(n) is a statement involving the natural number n such that: p(1) is true, and p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true ...
1
vote
1answer
31 views

$A$ and $B$ be non-empty bounded set of real numbers, give a counter example to the following.

Assume $A \cap B \neq \emptyset$. Find a counter-example to the claim: $\sup(A \cap B) = \min\{\sup(A), \:\sup(B)\}$ I cant seem to find a counter example to the above claim, can anyone provide a ...
0
votes
1answer
22 views
+50

Finding the data regarding the four racket games.

In a vijantkhand sports stadium, athletes choose from $4$ different racket games (apart from athletes which is compulsory for all) These are tennis, table tennis, squash and badminton. It is ...
1
vote
1answer
12 views

Partition generated $\sigma$-algebra

I saw this example given as a $\sigma$-algebra in various places. It goes like this: Let $X$ be a set and assume that the collection $\{A_1,\dots, A_N\}$ is a partition of $X$. Then the collection ...
0
votes
0answers
21 views

Term for a “Cartesian union/intersection/difference” of set families

Let $A,B$ be two families of sets. What is a term for the following families: $$C = \{a\cup b|a\in A, b\in B\}$$ $$D = \{a\cap b|a\in A, b\in B\}$$ $$E = \{a\setminus b|a\in A, b\in B\}$$ Since ...
-5
votes
1answer
42 views

Prove that $(A \cup B)\setminus B=A$ if and only if $A$ and $B$ are disjoint. [on hold]

Like the title says. Prove that $(A \cup B)\setminus B=A$ if and only if $A$ and $B$ are disjoint.
1
vote
2answers
52 views

Countable Union of Countable Sets [duplicate]

Why can't I use this proof to prove that the countable union of countable sets is countable without the axiom of countable choice? Take the set of integers; some proper subset of it, call it $A$, ...
-2
votes
1answer
49 views

How good is Naive Set Theory by Halmos? [on hold]

I happened to run into this book in an old shop and got it for like half a dollar. Has anyone read this book? Is it worth the time? (Please don't respond things like "every math book is worth the ...
1
vote
1answer
46 views

Prove or disprove if set is uncountable

Prove or disprove: The set Y of numbers in (0,1) with a decimal expansion that contains only 0s and 1s, and only finitely many 0s, is an uncountable set. Uncountable means it's not finite or not ...
1
vote
1answer
18 views

From sets of subsets to partitions

Let S be a non-empty set, and Q be a set of non-empty subsets of S such that $\bigcup Q=S$. Let $P'$ be the set of all non-empty subsets x of S such that: $\forall q\in Q. x\subseteq q \lor x\cap ...
0
votes
0answers
13 views

Successor function and transitive sets

proof I'm struggling to follow this proof, I understand the first line, but why does this give us the result. Note, $S(x)$ is the successor function, defined $S(x) = x \cup \{x\}$