Questions tagged [elementary-set-theory]

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, differences and complements, De Morgan's laws, Venn diagrams, relations and functions, countability and uncountability, etc. More advanced topics should use (set-theory) instead.

Filter by
Sorted by
Tagged with
1
vote
2answers
26 views

Is A a subset or and element of set C?

Let A, B, C be 3 sets. If A belongs to B, and B is a subset of C, is it true that A is a subset of C? They say A is a set. So A should be a subset of C. But my textbook says it’s not because A is an ...
1
vote
1answer
19 views

A doubt on the question $C = f^{-1}(f(C)) \iff f$ is injective and the similar surjective version

Prove that $C = f^{-1}(f(C)) \iff f$ is injective and $f(f^{-1}(D)) = D \iff f$ is surjective I have a doubt in the question asked above. In this statement, $C = f^{-1}(f(C)) \iff f$ is injective I ...
2
votes
3answers
52 views

How can a counterexample be used to disprove $(A\setminus B)\setminus C \equiv A\setminus(B\setminus C)$? [closed]

How can a counterexample or logical proof be used to prove the following non-equivalence? (established using a Venn diagram) $$(A\setminus B)\setminus C \neq A\setminus(B\setminus C)$$ This arose ...
1
vote
2answers
37 views

How does the identity function $id_X$ imply injectivity of the right inverse function of the composition $g \circ f$?

$f: X \rightarrow Y$, $g: Y \rightarrow X$, $g \circ f = id_X$ I can see, graphically, how having $f(x) = f(x')$ with $x \neq x'$ would mean that $f(x)$ (or $f(x')$ for that matter) would have to map ...
2
votes
2answers
34 views

Prove that A-(B⋃C) = (A-B)⋂(A-C)

Please let me know if this proof is right, I think it is but I still want confirmation ...
-2
votes
1answer
29 views

True or False Statement [Set Theory]

Statement Problem Hi, I just need help with this true or false statement. $A\setminus(B\cup C)=(A\setminus B)\cup(A\setminus C)$ for all sets $A$, $B$, and $C$. I think its true because $A\cup A=...
2
votes
2answers
33 views

Denote if string contains any member of a set of characters

I come from a computer science background and trying to properly document the following python if statement. ...
0
votes
1answer
25 views

There is not the set of all compactification.

Definition (0) Let be $X$ a topological space. So a pair $(h,K)$ is a compactification of $X$ if $K$ is a compact space and if $h:X\rightarrow K$ is an embedding of $X$ in $K$ such that $h[X]$ is ...
0
votes
3answers
49 views

If $f \circ f$ is bijective for $f: A \to A$, then is $f$ bijective?

I am trying to prove the following statement: Let $f: A \to A$. If $f \circ f$ is a bijection, then $f$ is bijective. My proof looked like this: We know that $|A| = |A|$. Since this is the case, ...
1
vote
3answers
32 views

Why is a function $g$ surjective if its composition with an injective function $s$ forms an identity function $id_K$?

I'm trying to prove the surjectivity of a function $g : N \to K$ when its composition ($g \circ s$) with an injective function $s : K \to N$ equals the identity $id_K$, but I can't seem to figure out ...
0
votes
1answer
24 views

Prove that (A-B)⋃B=A if and only if B⊂A

How do I complete this proof :- ...
0
votes
1answer
36 views

How to resolve this paradox involving Cantor's diagonal argument?

Let's define the elements of a countable infinite set of numbers as follows: $$s_1 = 0.0000000...$$ $$s_2 = 0.1000000...$$ $$s_3 = 0.1100000...$$ $$s_4 = 0.1110000...$$ $$s_5 = 0.1111000...$$ $$...$$ ...
1
vote
0answers
34 views

Prove that A = B ⇒ A⋂B = A⋃B

This one's a simple one, just asking for confirmation... Here's my proof : ...
0
votes
1answer
39 views

Showing that set $X$ is countable or finite if there is an injective mapping $f:X \to N$

I am trying to prove that if there is an injective mapping $f:X\to \mathbb{N}$, then $X$ is finite or countable. My proof goes like this: Suppose that $X$ is infinite and uncountable. Since $X$ is ...
0
votes
1answer
43 views

Build a Bijective function to show that $\left |(0,1) \right | = \left |(1,2)\cup (3,4) \right |$ [closed]

I would love to get some insight and explanation on how to build such function. Thanks alot.
5
votes
1answer
40 views

Prove that A-B=A ⇔ A⋂B=Φ

Another question from my 11th grade Mathematics textbook. I actually proved it but I still want to confirm if it's right or not. Please check it out : ...
1
vote
3answers
34 views

Show that at least one of the intervals is contained in the union of the other two.

Question: Let $I_1,I_2,I_3$ be three open intervals of $\mathbb{R}$ such that none is contained in another. If $I_1\cap I_2\cap I_3$ is non-empty, then show that at least one of these intervals is ...
0
votes
1answer
20 views

Uniqueness of Cardinality Proposition and Interpretation of Induction Method

I have always wanted to ask this question and finally encountered an exercise that incentivized the question further. In Tao's Analysis I, the reader is asked to prove the following proposition: ...
1
vote
3answers
36 views

Find limsup and liminf of a sequence

From Probability through problems by Marek Capinski,Jerzy Zastawniak,: Find $\limsup_{n \to \infty}A_n$ and $\liminf_{n \to \infty}A_n$,where \begin{eqnarray*} A_n &=&\left(\frac 13-\frac1{...
0
votes
1answer
37 views

Why is P(A⋃B) ⊄ P(A)⋃P(B)?

I had a question in my 11th grade Mathematics book : Prove that P(A⋃B) ⊄ P(A)⋃P(B) I did a proof for why P(A⋃B) ⊂ P(A)⋃P(B) Which step in the following proof is wrong? ...
2
votes
1answer
69 views

Doubt about the logic defining transitivity of a relation

Kindly, correct me where I am wrong. Modified(11:50 AM, 26 March 20): [ for all a, b, c ∈ X ] Let us define P: $(a, b), (b, c)∈R$ ; and Q: $(a, c)∈R$; [A] When P is true: P is true, Q is true: ...
1
vote
1answer
64 views

How many open sets of R do exist?

I was reading a set theory book and they claim that there are as many open sets in $\mathbb R$ as real numbers (usual topology). I tried using the base of intervals with irrational extremes but ...
1
vote
1answer
40 views

Is a set A a subset of B if all of the elements of A are within sets within B?

How "deep" does the subset operator go? If I have a set A = {1, 1, 2} and a set B = {1, {2}, {1}, {1, 2}, {2, 2, 1}}, is A a subset of B? Thanks
2
votes
1answer
26 views

Cardinality question about continuous bijections

I have been thinking about continuous bijections that map some non-empty open path-connected set $D \subseteq \mathbb R^n$ onto some non-empty open path-connected $E \subseteq \mathbb R^n$ and I got ...
0
votes
1answer
25 views

The cardinality of a countable union of sets with cardinality $\mathfrak{c}$ has cardinality $\mathfrak{c}$

I am trying to prove that: union of countably many sets with cardinality $\mathfrak{c}$ is $\mathfrak{c}$. I have tried to use the Cantor-Bernstein theorem, and here is what I have so far: To prove ...
4
votes
2answers
92 views

Cantor's diagonal argument, is this what it says?

I've been reading about Cantor's diagonal argument all day, it's pretty confusing, but I think I get it now and I want to make sure asking you guys to confirm it. So, this is my understanding: Two ...
3
votes
1answer
51 views

Any errors? My proof that if $\left(A - B\right) \cup \left(B - A\right) = A \cup B$, then $A \cap B = \emptyset$

If $A\cup B=(A-B)\cup(B-A)$, then $A\cap B=\emptyset$. Proof by Contrapositive. If $A\cap B\ne\emptyset$, then $A\cup B\ne(A-B)\cup(B-A)$. Suppose that there exists a member of $A\cap B$, $x$. Then, $...
-1
votes
2answers
27 views

What is the meaning of $\{1,\dots,k \}^n$? [closed]

I'm trying to figure out what the set $\{1,\dots,k \}^n$ is. I know that the number of $n$-tuples formed from the numbers $1,\dots,k$ is the cardinality of that set, but I'm not sure what the ...
0
votes
3answers
26 views

How does this recursive power set algorithm work?

I've discovered and am trying to understand power sets, specifically how to calculate the power sets of a set. I found the algorithm's description, which concluded with this: $$P\left(S\right) = P\...
1
vote
0answers
23 views

Exercise about the axiom of choice [duplicate]

Prove that the following statements are equivalent: If $A$ is a non empty set, there exists a function $f:\mathcal{P}(A) \setminus \{\emptyset\} \rightarrow A$ such that $f(X) \in X$ for every $X \in ...
-1
votes
1answer
18 views

Show that if a set A is finite then there is no bijection of A with a proper subset of itself. [closed]

Show that if a set is finite then there is no bijection of a set with a proper subset of itself
0
votes
1answer
45 views

What is the cardinality of this absolutely outrageous set?

Burning question. Consider the following set: $$A=\left\{\frac{0}{0},\frac{\infty}{\ \infty},\ 0\cdot\infty,\ 1^{\infty},\ \infty-\infty,\ 0^{0},\ \infty^{0}\right\}$$ The A stands for Any Self-...
-2
votes
0answers
30 views

|P(R) x P(R)|=|P(R)|? [closed]

I want to prove that |P$(\mathbb{R})$$\times$P($\mathbb{R})$|=|P$(\mathbb{R})$|, where P$(\mathbb{R})$ is the power set of $\mathbb{R}$. I try: |P$(\mathbb{R})$$\times$P($\mathbb{R})$|=$|2^{2^{\...
-1
votes
1answer
58 views

Property of a set

Let $U$ be a universe set of living objects. A subset $M$ is the set of males. Every element in $M$ has the property that it is a male. So I think we can say that $M$ has the property of being male. ...
2
votes
1answer
45 views

Understanding what $\phi(f)(b,c) = f(b)(c)$ means

Consider $\phi: (A^B)^C \to A^{B \times C}$ given by $\phi(f)(b,c) = f(b)(c)$. I'm trying to understand the definition of $\phi$ as given above. Suppose $k \in A^B$. Then $k: B \to A.$ Now let $f \in ...
0
votes
0answers
22 views

A question about set

I have a sets $E_0,...,E_N$, then i define $F_0=E_0$, $F_k=E_k\setminus\bigcup_{i=0}^{k-1} E_i$, $k=1,...,N$. I want to prove that: $E_k=\bigcup_{i=0}^k F_i$, $\forall k=0,...,N$.I have no idea how to ...
0
votes
0answers
45 views

Does $\operatorname{card} \operatorname{ran} f \leq \operatorname{card} \operatorname{dom} f$ imply choice? [duplicate]

I am considering the following statement: If $f$ is a function, then $\operatorname{card} \operatorname{ran} f \leq \operatorname{card} \operatorname{dom} f$. This can be proved using the axiom of ...
3
votes
1answer
68 views

Prove $\bigcup (F\setminus G) \subseteq (\bigcup F) \setminus (\bigcup G)$ iff $\forall A \in (F\setminus G) \forall B\in G (A\cap B = \emptyset)$

This is an exercise from Velleman's "How To Prove It": Prove that $\bigcup (F \setminus G) \subseteq (\bigcup F) \setminus (\bigcup G)$ iff $\forall A \in (F \setminus G) \forall B \in G (A \cap B =...
3
votes
3answers
61 views

Evaluating $\sum_{0\leq k \leq l \leq n}\binom{k}{2}\binom{l}{k}\binom{n}{l}$

I'm trying to understand the process of evaluating this sum. I know the above equals to: $$|\{(A,B,C)\mid A\subseteq B \subseteq C \subseteq [n] \wedge |A| = 2\}|$$ ...Yet, how can I express this ...
2
votes
2answers
42 views

Order of minimun and maximum difference

I want to prove firstly on $Fun(\mathbb{N},\mathbb{N})$ that "$f < g$ if and only if $f(k)<g(k), k=\min\{n|f(n) \neq g(n)\}$" is a total order, but not a well-order. Then, on the set $\{f:\...
3
votes
4answers
149 views

How to find an inverse of this type of functions?

Let $F(x,y)$ and $G(x,y)$ Be functions from where $x,y$ are whole numbers. ($Z^2 \to Z^2$) $F(x,y) = (x+3y,x+5y)$ $G(x,y) = (2x+3y,3x+5y)$ The question: One of these functions has an inverse, ...
-1
votes
2answers
38 views

Doubt regarding Universal set and union of two sets

A question in my textbook is as follows:- Que. A survey shows that 76% of the Indians like oranges, whereas 62% like bananas. What percentage of the Indians like both oranges and bananas? My approach ...
0
votes
0answers
14 views

$A \setminus B$ is infinite, $B$ - finite. Proof that $(A \setminus B) \sim A$ [duplicate]

Let $A, B$ - sets such that $A \setminus B$ is infinite, $B$ - finite. Proof that $(A \setminus B) \sim A$
0
votes
1answer
24 views

How would I do this set partition problem?

A = {red, blue, green, purple} B = {red, red, green} Let E = {blue, red, green, purple, orange, black} and Let F = {black, orange}, do A, B, F form a partition of E? If not, which condition of a ...
2
votes
3answers
36 views

Would duplicates matter in cartesian product of a set?

For example: \begin{align} A &= \{1, 1, 2\} \\ B &= \{3, 3, 3, 2, 2, 4\} \end{align} Would $A$ cross $B$ equate to $\{(1,3),(1,2),(1,4),(2,3),(2,2),(2,4)\}$ without the dupes of $(1,3)$, etc.
0
votes
1answer
32 views

How would I solve these problems (Mainly want to know what to do with the set containing sets a.k.a set C)

A = {red, blue, green, purple} B = {red, red, green} C = {red, {green}, red, {red, green}, {green, green, red}} Let the universal set for A, B, C be defined by: U = {red, blue, purple, green} ⋃ 𝒫({...
0
votes
1answer
29 views

What is the overline above the letters I don't understand how to find the elements of this symmetric difference.

Assume the universal set $\,\mathcal U = \{1, 2, 3, 4, 5, 6, 7, 8\}$. If $A = \{1, 2, 4, 6, 7\}, B = \{1, 2, 4, 6\}$ and $C = \{1, 3, 4, 7\}$, what is $\overline{A}⊕\overline{B ⊕ C}$ ? What does is a ...
1
vote
1answer
23 views

Would my method of solving this symmetric difference set be correct and is my answer correct?

Problem: If A = {1, 2, 4, 6, 7} and B = {1, 2, 4, 6} and C = {1, 3, 4, 7}, what is A ⊕ B ⊕ C? 1) A − B = {1, 2, 4, 6, 7} − {1, 2, 4, 6} = {1, 2, 4, 6, 7} − {1, 2, 4, 6} = {7} 2) B − A = {1, 2, 4, 6} ...
1
vote
2answers
52 views

Probability and subsets

I was working through this (Cambridge STEP 3 probability) question: The set S is a set of all integers from $1$ to $n$. The set $T$ is the set of all distinct subsets of $S$, including the empty ...
0
votes
2answers
38 views

Need some help with some homework problems

A = {x ∈ R: 1 < x < 5} B = {∅} C = {4, 5, 9, 10} Determine whether each of these is true or false based on the given above. 1) π ⊂ A 2) {π} ⊂ A 3) B ⊆ C What I think: 1) False, because ...

1
2 3 4 5
436