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, (un)...

learn more… | top users | synonyms

1
vote
1answer
134 views

What is the motivation behind the arbitrary union topological axiom?

1. Why is the arbitrary union axiom in the definition of topology necessary? 2. Why is it useful? Why might we expect ("intuitively") that it should be useful? 3. What is the (historical) ...
1
vote
1answer
55 views

Axiom in Foundations, Extensionality

In my Foundations of Mathematics Textbook I encountered the following problem. The book states that for the domain of discourse $D = \{a,b,c\}$ and binary relation defined as $E = \{(a,b),\, (a,c)\}$ ...
1
vote
1answer
24 views

What does “induced operations” means in congruence operations

It says: prove that R is a congruence (it means it's a relation of equivalence and it preserves operations) ith respect to sum and multiplication in $\mathbb{R}$. $a,b\in \mathbb{R}: aRb \iff a-b \in ...
1
vote
2answers
22 views

Indexed Families [duplicate]

I'm trying to find an indexed family {An:n∈N} that satisfies: each An is an infinite subset of the naturals N the intersection of any two arbitrary sets is empty the union of all the subsets is is ...
2
votes
2answers
80 views

Proving that the powerset of $\Bbb N$ is uncountable

The question I'm facing off with: (a) Consider the set $A$ defined as the set of all subsets of $\Bbb N$: $A = ${$B : B \subset \Bbb N$}. Show that $A$ is in one-to-one correspondence with the set of ...
-1
votes
1answer
40 views

Is this $2d$ function injective and/or surjective?

Consider a function $f:\mathbb{R}^2 \to \mathbb{R}^2$ defined by $f(x,y)=(x,xy)$. Is this function injective, surjective? I can figure out that this is injective but cannot prove it surjective. ...
-2
votes
1answer
43 views

$A$, $B$, and $C$ are sets. If $A \subseteq B$ and $B \in C$ then $A \not\subseteq C$. Is it true or false statment?

I have a problem to identify the true value of a statement. $A$, $B$, and $C$ are sets. If $A \subseteq B$ and $B\in C$ then $A\not\subseteq C$. Is it true or false statment?
1
vote
3answers
99 views

Sum of finite ordinals: $\lambda_1+\lambda_2+\dots+\lambda_n+\dots=\omega$

Prove: $\lambda_1+\lambda_2+\dots+\lambda_n+\dots=\omega$, where $\lambda_i$ are finite ordinal nonzero numbers. I tried like this. $A_i$ set and ord($A_i$)$=\lambda_i, i=\{1,2,...\}$ and ord($\...
0
votes
0answers
38 views

Any initial infinite ordinal is of the form $\omega_{\alpha}$

Let $\gamma$ be an initial infinite ordinal. Show that $\gamma=\omega_{\alpha}$ for some ordinal $\alpha$ The definition I use for $\omega_{\alpha}$ as follows: Suppose $\omega_{\beta},\aleph_{\beta}...
-1
votes
0answers
26 views

Partitioning an infinite set into sets of Aleph-Null [duplicate]

I was tasked with solving the following problem: Let $X$ be an infinite set. Prove using Zorn's Lemma that it is partition-able into subsets of cardinality $\aleph_0$. My initial thought was to try ...
2
votes
3answers
798 views

If $f:X\rightarrow Y$ and $V\subseteq Y$, does there exist $U\subseteq X$ such that $f(U)=V$?

I am afraid this is quite a trivial question. However, let $f:X\rightarrow Y$, where $X$ and $Y$ are sets. Is that true that for any subset $V$ in $Y$ there exists a subset $U$ in $X$ such that $f(U)=...
1
vote
1answer
43 views

In what space is a closed set is not or not necessarily $G_\delta$

We know that A closed set in a metric space is $G_\delta$ Is there any topological space where a closed set is not necessarily $G_\delta$? I am thinking a space where singletons are well known to be ...
0
votes
2answers
46 views

Infinite Subsets of N

Any suggestions on the following? Find three infinite subsets of the naturals N such that the intersection of any two of them is empty and the union of all three is N. I attempted to divide N into ...
1
vote
0answers
25 views

Question about composed functions [closed]

Let X be a finite set and $f : X → X$ a function. Let $f^1 = f$ and if $f^ n$ has been defined for n ∈ N then set $f^{n+1} = f ◦ f^ n$ . a) Prove for some n, $f^{n+1} = f^{n}$. b)Set Y = $Range(f^n)$ ...
0
votes
0answers
48 views

Proof about functions

Let $f : X \rightarrow Y$ be a function, $B$, $C$ subsets of $Y$. If $B \cap C = \emptyset$, prove that $f^{-1} (B) \cap f^{-1} (C) = \emptyset$. Approach suppose $x\in f^{-1} (B) ∩ f^{-1} (C) \...
0
votes
2answers
55 views

How to Read Notation for General Intersection and Union

I am trying to read the following two formulas in English but I am not certain how to, although I do understand their meaning. Union: $\bigcup_{i=1}^{n} A_{i} = \{x\, |\, \exists_i \in I(x \in A_i) \...
0
votes
4answers
56 views

Which one is the true statement: $B \subseteq A-(A-B)$ or $A-(A-B) \subseteq B$

Which one is the true statement: "$B \subseteq A-(A-B)$" or "$A-(A-B) \subseteq B$" ? I think the former is true but I'm not sure here could someone provide some advice? Thank you
0
votes
2answers
66 views

Prove that for all sets $A,B,C$, $A − (B \cup C) = (A − B) − C$. [closed]

Prove that for all sets $A,B,C$, $A − (B \cup C) = (A − B) − C$.
5
votes
1answer
54 views

Prove if $A ⊆ B$, then $A ∩ C ⊆ B ∩ C$.

For any sets $A, B$, and $C$ Assume $A ⊆ B$, and suppose, $x\in (A∩ C)$. Then $x\in A $ and $x\in C$ by definition of $A ∩ C$. Since $A ⊆ B$ it follows that if $x\in A$ then $x\in B$. Thus, ...
0
votes
1answer
16 views

Subsets and element examples that I wanted to double check with

I wanted to double check these practice problems to see if they were done correctly so as to reaffirm my understanding of subsets and elements. The questions are as follows: "Let $A = \{1,2,3,4,5,6,7,...
1
vote
1answer
246 views

Prove that continuous functions mapping irrationals to rationals must be constant

Let $f\colon[0,1] \to \mathbb{R}$ be a continuous function such that any irrational number is mapped to a rational number. Then $f$ must be a constant. Well, the context isn't that much, I was ...
3
votes
2answers
89 views

Is this a true statement ? $\{\emptyset\} \subseteq \mathcal{P}(\{\emptyset\})$

I was trying to confirm my understanding of $A \subseteq B$ so would this be a true statement ? $\{\emptyset\} \subseteq \mathcal{P}(\{\emptyset\})$ I am guessing it is since $\mathcal{P}(\{\...
0
votes
0answers
28 views

Let $f$ be a family of sets. Prove that there is a unique set $A$ such that $f \subseteq \mathscr P (A)$.

Suppose $f$ is a family of sets. Prove that there is a unique set $A$ such that $$f \subseteq \mathscr P (A)$$. Proof: Let $A= \cup f$. Let $X \in f$, and now let $y \in X$. Clearly, $y \in \cup f$...
1
vote
2answers
121 views

Characterization of measurable functions

Let $X$ be an uncountable set, let $\mathfrak{M}$ be the collection of all sets $E\subset X$ such that either $E$ or $E^c$ is at most countable, and define $\mu(E) = 0$ in the first case, $\mu(E) = 1$ ...
0
votes
1answer
66 views

Ordinal Arithmetic: $n+\alpha=\alpha$

Let $\alpha$ be an ordinal. Show that $n+\alpha=\alpha$. Proof: Let $W$ be the set with ordinal equal to $\alpha$. Let $A_n=\{a_1,a_2,\cdots, a_n\}$ be the set disjoint from $W$ with its ordinal ...
1
vote
1answer
35 views

Proving $n < 2^n$ by Cantor's theorem

So we know Cantor's Theorem is of course. For any set $S$, the power set $P(S)$ has a strictly greater cardinality, $\iff \#S < \#P(S)$. We seek to prove $n < 2^n$ using this information. I ...
0
votes
1answer
60 views

Mapping the reals to the naturals

Where does this argument fail? (my opinion; the conclusion is a non sequitur) Given any real number (between 0 and 1) it is possible to extract a natural number of any length that you want from that ...
2
votes
0answers
61 views

What is this function, and what are it's properties?

I made a function that determines how "prime-y" a number is; if $f(x) = 1$ then $x \in primes $. The function is $$f(x) = \frac{\pi(x) - \#\{p \in primes | p<x, p \space| \space x\}}{\pi(x)}$$ ...
1
vote
3answers
40 views

Concerning the Countability of the Set of Reals with Decimal Representations Consisting of All $1s$

The Problem: Exhibit a one-to-one correspondence between the set of of positive integers and the set, $S$, of real numbers with decimal representations consisting of all $1$s. Where I Am: I realize ...
1
vote
0answers
21 views

Are these correct extension of injective and surjective functions?

Recall the definition of injective and surjective functions: 1.a A function $f: X \to Y$, is injective if for all $a,b \in X$, if $a \neq b$, then $f(a) \neq f(b)$ 1.b A function $f: X \to Y$,...
0
votes
1answer
34 views

Trying to understand inclusion.

Let $Y_n$ and $Y$ two random variable. I want to understand why $\{\lvert 1/Y_n- 1/Y \rvert \ > \epsilon \}\subseteq \{Y<2\delta\} \cup\{\lvert Y_n-Y \rvert > \delta \} \cup \{ \lvert Y_n - ...
1
vote
6answers
91 views

If $\{x\}=\{z\}$ then $x=z$?

I think that no. For example, Let $x=\{1,2,3\}$ and $z=\{1,2,3,4\}$. So, $\{\{1,2,3\}\}=\{\{1,2,3,4\}\}$. Yet, $x\neq z$. Can you explain?
-1
votes
1answer
36 views

order-preserving function on a well-ordered set

I have a well-ordered set $(A,≤)$ and a function $f:A\to A$ that is one to one and also $f$ preserves the order (for every $a,b\in A,$ if $a\le b$ then $f(a)\le f(b).$) I need to prove that $a\le f(a)....
1
vote
0answers
30 views

Question about countable and uncountable sets

Consider the following sets: i. $Y_1 = ∅$ ii. $Y_2 = P(Y_1)$ iii. $Y = \{Y_1, Y_2\}$ iv. $Z × Z ∪ Q$ v. $N.$ vi. R vii. ${f : \{0, 1\} → R}$ viii. Set of relations on $N$. ix. $R × R$ x. $R × Q$. xi. $...
1
vote
1answer
27 views

Can one drop a triangular number and still get all $n$ as sum of three?

This question is inspired by this question, in which it is noted that every positive integer is a sum of at most three triangular numbers, and that the sum of the reciprocals of these numbers is $2.$ ...
0
votes
1answer
29 views

Let $X$ denote an infinite set. Is every partitioning of $X^2$ induced by an associative operation $f:X^2 \rightarrow X$?

Proposition. Let $X$ denote an infinite set. Then for each partitioning $\Pi$ of $X$, there exists a function $f : X \rightarrow X$ whose coimage is $\Pi$. I'd like to know whether the analogous ...
1
vote
2answers
46 views

Power sets question about $\subseteq$ and $\in$

I have a question with regards to this question as follows: Let $A = \{1,2,\{1,2\}\}$. Determine whether the following statements are true or false with a brief explanation of why. a) $\{1,2\} \...
0
votes
1answer
81 views

Set-builder notation and the notion of function

My understanding of set-builder notation is that given a set $A$ and a function $P:A\to\{true,false\}$, one can define the subset $$ B=\{a\in A:P(a)\} . $$ However, a function $f:A\to C$ is defined as ...
-1
votes
1answer
31 views

If $N \cap F^c\neq\emptyset$, when is $N \cap F=\emptyset$?

Given that $N \cap F^c\neq\emptyset$, when can we say that $N \cap F=\emptyset$? $N$ and $F$ are sets in a metric space. $F^c$ is the complement of $F$. A little bit of context: I am trying to ...
0
votes
0answers
28 views

How to show that $f(X \backslash f^{-1}(Y \backslash C)) \subseteq C$

Let $f: X \to Y$ be a continuous function, and that $C \subset Y$, then claim: $f(X \backslash f^{-1}(Y \backslash C)) \subseteq C$ Attempt: Immediately we run into a problem following: ...
1
vote
1answer
26 views

Is this a valid proof for: $A\cap B)\cup(A\cap C)\subseteq (A\cap (B\cup C))$

I want to prove that $(A\cap B)\cup(A\cap C) \subseteq (A\cap(B\cup C))$. I noticed that I recently, I have just been applying the laws of logical equivalence (ie: distributivity/commutativity/...
0
votes
1answer
22 views

Determining values of the statements

I have a hard time, solving some logical statement exercises. Given two statements $v(x): |x| = 2$ and $u(x): x > 1$, where $x \in A = \{-1, 0, 1, 2, 3, 4\}$, I have to determine all values of ...
0
votes
2answers
44 views

Let $x=\{a,b\}$ be a set. Then, $x\in\{a,b\}$? [closed]

Let $x=\{a,b\}$ be a set. Then, $x\in\{a,b\}$? I think: Yes. So, why?
0
votes
0answers
26 views

How to determine value of statement

Given statement $v(x): |x| = 2 \text{ where } x \in A = \{-1, 0, 1, 2, 3, 4\}$. What will value of $\lnot v(x)$ look like?
4
votes
1answer
40 views

Injection from $\mathcal P \left({\mathbb{N}}\right)$ to derangements of $\mathbb{N}$

Let $S$ be the set of the permutations without fixed points of $\mathbb{N}$. Is there an elegant way to exhibit an injection from the power set $\mathcal P \left({\mathbb{N}}\right)$ to $S$ ? (...
2
votes
2answers
27 views

Proof about equivalence relations

Let $R$ be a reflexive and symmetric relation on a set $X$. A pair $x,y ∈ X$ are connected via $R$ if there are elements $x = x_0, x_1, . . . , x_k = y$ such that $(x_i, x_{i+1}) ∈ R$ for all $i = 0, ...
0
votes
0answers
17 views

Proof about intersection of relations

a) Assume R and S are symmetric. Prove that R ∩ S is symmetric $R \cap S$ is set of all orders pairs in the form $(a,b)$ that are in both $R$ and $S$ Let $(a,b) \in R$ and $(a,b)\in S$, so $(a,b)\...
0
votes
1answer
26 views

Intersection and complement of $\{3^k \mid k \in \Bbb N\}$ and $\{l^3 \mid l \in \Bbb N\}$

Let A = $\{3^k \mid k \in \Bbb N\},\ C = \{l^3 \mid l \in \Bbb N\}$. a) Determine $A − C$. b) Determine $A \cap C$. Approach: if $l=3^k$ then $l^3=3^{3k}$ but we know that $2k \in N$, so ...
4
votes
2answers
36 views

Prove $(A \cup B)' = A' \cap B'$

I would like some assistance in verifying this proof? (I understand the last conjecture about "symmetry" is probably shaky, but I just want to know if the first part is right since going backwards ...
1
vote
3answers
44 views

Prove $(A-B) \cap (B-A) = \emptyset$

My first instinct with this proof is to assume the opposite of the hypothesis, as in a proof by contradiction. My work is as follows: Suppose $(A-B) \cap (B-A) \neq \emptyset$. Consider an $x \in (...