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

0
votes
0answers
16 views

Equinumerous Sets Exercises

Are the following sets equinumerous? (1)$[0,1)$ and $\mathbb{Q}$ (2)$[0,1]^{\mathbb{N}}$ and $[0,\infty)$ (3)$[0,1]^{\mathbb{N}}$ and $\mathbb{Q}^{\mathbb{N}}$ The first one should be false since ...
0
votes
2answers
31 views

Proving that a set A cannot contain another set B which contains A?

From the ZFC axiom of regularity, which states that every non-empty set contains an element disjoint from it, we can deduce that there is no set $A$ such that $A \in A$. A proof is outlined here: ...
2
votes
6answers
127 views

Prove that A = B if and only if A $\subseteq$ B and B $\subseteq$ A

I want to prove that $A = B$ iff $A \subseteq B$ and $B \subseteq A$. I'm unsure of how to approach this problem. It seems really easy but I have no idea. Help would be greatly appreciated.
0
votes
3answers
36 views

If $S \subseteq T \subseteq M$. Then show that $S$ is compact in metric space $(M,d) \iff S$ is compact in the metric subspace $(T,d)$.

Let $(M,d)$ be an arbitrary metric space and $S,T$ be subsets of $M$. Assume $S \subseteq T \subseteq M$. Then show that $S$ is compact in $(M,d) \iff S$ is compact in the metric subspace $(T,d)$. ...
1
vote
4answers
30 views

Let $X$ be a closed subset of a compact metric space $M$. Then, $X$ is compact.

Theorem : Let $X$ be a closed subset of a compact metric space $M$. Then, $X$ is compact. Query : Since, $M$ is compact, then there is a finite collection $F$ of open sets which covers $M$. Hence, ...
0
votes
1answer
28 views

How could we prove the sentences?

Let $A,B$ sets. How could we prove the following sentences? $A \subset B \rightarrow \cup A \subset \cup B$ if furthermore $\varnothing \neq A$ and $A \subset B$, then $\cap B \subset \cap A$. ...
2
votes
2answers
102 views

Set theory and physics [closed]

I would like to know if there are some physical concepts (preferably accessible ones like force, torque, ...) that can be significantly better understood when looked at in the light of concepts taken ...
-1
votes
3answers
46 views

Prove $ f(A1) \setminus f(A2) \subseteq f(A1 \setminus A2) $

here is my proof but it only works for functions that have an inverse:
0
votes
1answer
49 views

Countable and uncountable sets.

a) Show that $\left \{ n^{2}+m^{2}:n,m\in \mathbb{N} \right \}$ is countable. b) Show that $\left \{ x\in \mathbb{R}:x(x-2)<0 \right \}$ is uncountable. My answers: a) Is it possible to define ...
0
votes
1answer
20 views

Proper subsets with the null set

According to one of my graded homework assignment that was returned to me, $\{\emptyset\} \subset \{\emptyset, \{\emptyset\}\}$, but $\{\{\emptyset\}\} \not\subset \{\emptyset, \{\emptyset\}\}$. Can ...
1
vote
2answers
43 views

Using elementary set theory to show the union of two sets is equal to the set difference of two sets

I am supposed to prove (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B) So far I have: (A \ B) ∪ (B \ A) = x ∈ (A ∪ B) and x ∉ (A ∩ B) [by the definition of set difference] = (x ∈ A or x ∈ B) and x ∉ (A ∩ B) ...
0
votes
1answer
26 views

Quick question cardinalities and onto mappings

If $f: A \to B$, and if $|B| \geq |A|$, does this mean that $f$ can never be surjective or is it the other way around? I used to remember a simple argument that can help me deduce these cases, but I ...
-1
votes
1answer
33 views

How to prove that $A\setminus B = A\cap A^c$ ?

I've been working on the proof of $A\smallsetminus B = (A-B)$ U $(B-A)$, when A and B are sets. I have gotten that down, however, in that proof I use (A-B) = A intersection !B. I figured that out by ...
-4
votes
2answers
32 views

Suppose S and T are two sets. Prove that if (S ∩ T) = S then S ⊆ T

I'm new to this entire proof thing, and I am so confused Suppose S and T are two sets. Prove that if (S ∩ T) = S then S ⊆ T Please help me
-1
votes
4answers
43 views

Elementary Set theory proof

Prove: $A \subseteq B$ iff $A \cap B=A$ Can someone give me a hint on how to start this? I know in order to prove two sets are equal you have to take an arbitrary item from one set and show it is ...
0
votes
2answers
53 views

Prove A ∩ B = empty set iff A ⊆ B complement

Prove $A \cap B = \emptyset$ iff $A \subseteq B'$. I can understand why this would be true if it was just $A \cap B =$ iff $A \cap B$ but I have trouble when it comes to complements and so that part ...
0
votes
2answers
64 views

How to simplify these identities?

I have to verfiy the following identities $(A \bigtriangleup B) \cup C = (A \cup C) \bigtriangleup (B \setminus C)$ using logic symbols, I have to say what it means to be an element of each set and ...
-1
votes
0answers
38 views

prove that a set is non empty

Given that $D(k)$ is an increasing sequence and $D\overset{k}{\rightarrow} A$, where $A$ is a constant real. We have to show that the set $$\{k \mid D \leq Q < A\}$$ is non empty? where $Q$ is a ...
1
vote
1answer
110 views

The set of rational numbers in the interval $(0,1)$ cannot be expressed as the intersection of a countable collection of open sets

The set of rational numbers in the interval $(0,1)$ cannot be expressed as the intersection of a countable collection of open sets I found this proof on a certain web page A direct proof would be ...
2
votes
1answer
39 views

$\forall C\subset A, \; \forall D\subset B, \; f(C)\subset D \iff C\subset f^{-1}(D)?$

I've been asked to demonstrate this in my elements of mathematics class: $$\forall C\subset A, \; \forall D\subset B, \; f(C)\subset D \iff C\subset f^{-1}(D)$$ I've made two trials: ...
0
votes
1answer
35 views

dimension of direct products

Suppose $\{V_i\}_{i\in I}$ is a family of $k$ vector spaces. Is it possible to calculate $\dim\oplus_{i\in I} V_i$ and $\dim\prod_{i\in I}V_i$?
0
votes
4answers
38 views

Proof by contradiction involving set theory

Using a contradiction, prove the following: If $S\cap T = \emptyset$ and $S\cup T = T$, then $S = \emptyset$. So far, I've written the definitions of the intersection and union, and I've ...
1
vote
4answers
58 views

Set builder of this set 0, 1, 3, 6, 10, 15

I have tried to create the set builder of this infinite set: 0, 1, 3, 6, 10, 15, 21, 28,... I have notice that n = (n - 1) + (N + 1) where ...
2
votes
1answer
40 views

Cardinality: is it true that $|X^\mathcal{inj}| \leq 2^{|X|}$?

Definition. Whenever $X$ is a set, write $X^\mathcal{inj}$ for the collection of all injections $f$ such that: $f$ has codomain $X$ There exists an ordinal $\alpha$ such that $f$ has domain ...
2
votes
1answer
37 views

Could you give an example of an injective function $f:\mathbb{Z_+}^n\rightarrow \mathbb{Z_+}$ for an integer $n$ s.t. $2\leq n$?

We know that both of the domain the the co-domain are countable sets, so there is a bijection between them, Is there any SIMPLE injection? Here is some injection which I thougt of, but It turns out ...
0
votes
2answers
25 views

Does inclusion-exclusion formula holds for coutanble index set?

Does inclusion-exclusion formula holds for countable index set? Here is the formula for index set of size 2. \begin{align} P(A \cup B)=P(A)+P(B)-P(A\cap B) \end{align}
0
votes
1answer
24 views

Alternative ways to prove an easy set relation

I have a simple set relation, which is almost trivial to prove, but surprisingly, I can only prove it with an "indirect" method, which is bugging me: Let the set $L$ be a subset of $\mathbb{R}^n$. ...
0
votes
0answers
49 views

If every infinite subset of $S$ has an accumulation point in $S$, then $S$ is bounded

If every infinite subset of $S$ has an accumulation point in $S$, then $S$ is bounded. Proof: Suppose $S$ is unbounded. then , for every $m >0,~~\exists~~x_m \in S$ s.t. $|x_m|>m.$ The ...
0
votes
2answers
29 views

Writing a set with only 0 and 1 [closed]

I want to write a set which m number of elements and the value of the elements can either be 0 or 1. How do I write this in set notation
2
votes
3answers
49 views

Number of subsets of A∪B that contain an odd number of elements

So I have a problem which defines two sets: $A = \{1,3,5\}$ and $B = \{ 1,2,3,4\}$. The question asks for the number of subsets of $A \cup B$ that contain an odd number of elements. I know the ...
-1
votes
0answers
39 views

Common character to substitute union ∪ and intersection ∩

When writing set expressions on a computer without access to the proper symbols (∪, ∩, etc.), what non-letter symbols found on a English US keyboard are commonly used as substitutes? The three ...
-1
votes
0answers
32 views

Ordered pair with empty set

Is an ordered pair $(\emptyset,a)$ equivalent with $(a)$? Or generally is n-tuple $(a_1, a_2, ..., a_k, \emptyset_1, \emptyset_2, ... ,\emptyset_l)$ equivalent with n-tuple $(a_1, a_2, ..., a_k)$? ...
0
votes
1answer
29 views

Definition of factorial function for sets

Why is the factorial function expressed in terms of $(n+1)$ for sets? $0! = 1$ $(n+1)! = (n+1) \times n! $ for all $n$ $\in\mathbb{N}$ Instead of the more "common" $0! = 1$ $n! = n \times (n-1)!$ ...
0
votes
0answers
40 views

Basic Analysis . Is there a contradiction in these two definitions of closed sets for the set $x_n=\{\dfrac {1}{n}: n \in \mathbb N\}$

Is there a contradiction in these two definitions of closed sets for the set $x_n=\{\dfrac {1}{n} : n \in \mathbb N\}$ ? I happen to have a very basic query please. Let $S$ be the set denoted by ...
0
votes
1answer
61 views

How to do a basic proof

Let $f$ be a function from $A$ to $B$; let $C$, $D \subseteq B$ such that $C\subseteq D$. Prove that $$f^{-1}(C) \subseteq f^{-1}(D)$$ Work done: $x \in f^{-1}(C)= \{x\in A \ \text{such that} \ ...
-1
votes
2answers
20 views

Cardinality of the union of infinite and countable sets

This seems evident, but I cannot come up with a reasonable proof for: Question: show that if $X$ is an infinite set and $Y$ is a countable set, then $|X \cup Y|=|X|$
1
vote
2answers
38 views

belong to and subset in the set

My question is I can't understand the difference between belong and subset. Set theory: difference between belong/contained and includes/subset? I've read this already but I didn't get it yet... ...
1
vote
1answer
15 views

If $S$ is a subset of $\mathbb R^p$, then every infinite subset of $S$ has an accumulation point in $S \implies S$ is closed

If $S$ is a subset of $\mathbb R^p$, then every infinite subset of $S$ has an accumulation point in $S \implies S$ is closed. My query is : Isn't the above statement self proving? Every infinite ...
3
votes
3answers
84 views

Is my proof by contradiction about the empty set correct?

I am trying to learn about proofs and one of the exercice in my book (Maths ABC) is about proof by contradiction. I think I understand the concept but I would like to have a feedback on the following ...
0
votes
1answer
53 views

The composition of functions and inverse of a set?

I'm a bit confused on how to do some of my discrete math work. I tried doing all of the problems, but I feel like I'm doing something wrong. If anyone could correct me, it would be greatly ...
1
vote
1answer
18 views

In what sense $\alpha \times \alpha$ is the initial segment $(0,\alpha)$ in $Ord \times Ord$?

This is from Jech's book on set theory: "We define a well ordering of the class $Ord \times Ord$ of ordinal pairs. Under this well ordering, each $\alpha \times \alpha$ is an initial segment of ...
0
votes
1answer
23 views

Set containing multiple of both x and y in a certain range

Let A be the set which contains natural numbers which are multiples of 4 in the range 200 to 12000. Let B be the set which contains natural numbers which are multiples of 100 in the range 200 to ...
-1
votes
0answers
52 views

Prove that every natural number is transitive

A set A is said to be transitive if for all $x ∈ A$, $x ⊆ A$. (a) Prove that every natural number is transitive. (b) Prove that a set A is transitive if and only if $\cup A ⊆ A$. For (a), is it ...
1
vote
2answers
53 views

When is an infinite set larger than another infinite set?

Somewhat of a basic question that I've been pondering about, suppose we have 2 finite sets $A,B$, arbitrary sets with arbitrary elements that we know nothing about, except that they are both finite. ...
3
votes
1answer
34 views

Ordinals, cardinals and how to understand $2^{\aleph_0}$ versus $2^{\omega_0}$

I have read that $2^{\omega_0}=2^{\omega}=\omega$. (in the sense that they have the same order type). On the other hand, I know that $\omega=\aleph_0$, since it is the least infinite countable ...
0
votes
2answers
40 views

Show that a set is countable

I have to show that the set $B=\{n^2 + m^2 : n, m \in\mathbb N\}$ is countable. I know that i need to find a injection or a bijection from the set $B$ to the natural numbers, but i don't know how. ...
0
votes
3answers
37 views

The set of real numbers and the set of Real valued functions are not similar (equinumerous)

We need to show that the set of real numbers and the set of Real valued functions whose domain is $\mathbb R$ are not similar (equinumerous). Let $\mathbb R$ denote the set of real numbers and $S$ ...
1
vote
1answer
27 views

How do I simplify the union and intersection of sets.

In a solution to a homework problem, it says that $P((A\cup B)\cap C')=P(A\cup B\cup C)-P(C)$. I couldn't figure out how these two are equivalent. I have tried distributing $C$ into $(A\cup B)$ but I ...
2
votes
3answers
92 views

Is $|\mathbb{R}$| = |$\mathbb{R^2}$| = … = |$\mathbb{R^\infty}$|?

I know that $|\mathbb{R}| = |\mathbb{R^2}|$ because they both contain uncountably many elements, but I find it hard to conceptually understand how $\mathbb{R}$ defined by a line is the same size as ...
1
vote
2answers
25 views

What is the complement of conditional probabilities?

I am working with a problem that uses Bayes Theorem and conditional probabilities. I have the conditional probability that a plane has an emergency locator $(E)$ given that it was discovered $(D)$ ...