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

2
votes
2answers
62 views

How are image and pre-image different from range and domain respectively?

How are image and pre-image different from range and domain respectively, in Layman's terms (as simple as possible)? Are they basically just keywords that often indicate more nuanced subsets of the ...
2
votes
0answers
42 views

A question on ordinal arithmetic.

I have to order these two ordinals and I was just wondering if I have done it correctly. $\omega^\omega + \omega^3$ and $\omega + \omega^3 +\omega^\omega$ I have worked out that $\omega + \omega^3 ...
2
votes
3answers
41 views

About the nature of continuity of trigonometric functions and equality

I was recently somewhat confused by the result of an exercise from a textbook that read: Question How many solutions are there to the equation $(\tan x)\sin^2(2x)=\cos x$, $-2\pi \leq x \leq ...
0
votes
2answers
25 views

Given that the relation that aRb if and only if the smallest element of a is is equal to the smallest element in b?

X is the set of all nonempty subsets of the set {1,2,3,4,5,6,7,8,9,10}. a,b are elements of X. a) Find the number of elements in the equivalence class [{2,6,7}]? ...
-1
votes
0answers
31 views

Proper subset of a vector space

Does there exist an injection between $\mathbb{R}^n$ or $\mathbb{R}^\infty$ to a proper subset of itself? My issue is the injection part. I can't think of any examples.
0
votes
1answer
17 views

How to find the number of subsets $A\subseteq \{1,2,\ldots,10\}$ so that $A$ is related to $\{1,2,7\}$ or $A$ is related to $\emptyset$?

Let $S = \{1,2,3,4,5,6,7,8,9,10\}~$, and $ARB$ if and only if $A$ union with $B$ has exactly 3 elements a) Find the number of subsets $A \subseteq \{1,2,...,10\}~$ so that $A$ is related to ...
0
votes
2answers
27 views

Show that if $C \subseteq A \cup B$, then there are sets $A_1 \subseteq A$ and $A_2 \subseteq B$ such that $A_1 \cup B_1 = C$

Show that if $C \subseteq A \cup B$, then there exist sets $A_1 \subseteq A$ and $B_1 \subseteq B$ such that $A_1 \cup B_1 = C$ Do I need to treat this question like a biconditional statement?
0
votes
3answers
116 views

Apparent contradiction regarding countable subsets of real numbers.

So I'm working through this HW problem and I think I did everything correctly but I get to a contradiction. We start with $M$ which is a set of positive real numbers such that the sum of any subset ...
-2
votes
2answers
63 views

Why to define alphabet as a set?

In formal languages, alphabet is the set of all symbols used to form words in our language. Why is the notion of "set" used in this definition, instead of some other kind of collection, e.g. class? ...
0
votes
2answers
33 views

Proving that $f$ is the identity function if $ \ f \circ g = g \circ f$ for all $g$.

This is a problem from Spivak's Calculus. I can see how it applies for some family of functions, for example, if $g$ is constant; but I need to prove it for any $g$.
-2
votes
3answers
46 views

Is there another notation for this set-theoretic formula? [closed]

I am writing a book. In my drafts there are formulas like $\prod_{X\in S} X$ or $\{ \operatorname{im} P \mid P\in\prod_{X\in S} X \}$. If there are other way to write the same expressions, I should ...
2
votes
1answer
32 views

How does ZFC solve the problem of alphabet in formal languages?

(In case someone thinks this is another question about the seeming circularity in formal languages and is going to downvote because of this, it's really not; don't downvote yet, keep reading) Perhaps ...
1
vote
1answer
37 views

Is there a set of all topological spaces?

This question is from Willard's General Topology: Is there a set of all topological spaces? My try is: Suppose $\mathfrak T $ is set of all topological spaces, then $\mathfrak T $ 'contains' ...
1
vote
1answer
37 views

Decomposition of $\mathbb N$ into mutually disjoint infinite subsets

$$\mathbb N =\bigcup_{j\in \mathbb N}\Delta_j $$ where each $\Delta_j$ is an infinite subset of $\mathbb N$ and $\Delta_j\cap \Delta_i=\Phi \ for\ i\neq j.$ Now what I need is a few examples of such ...
0
votes
1answer
31 views

Prove the intersection of events to be 1

$B_n$, $n$ from $1$ to infinity is countably infinite sequence of events and each event has probability $1$. How do I formally prove that the probability of intersection of $B_n$ from $n = 1$ to ...
6
votes
2answers
219 views

“There is no set containing everything”? [duplicate]

I was reading this question regarding codomains, and I found something interesting in User134824's answer: "On the other hand, owing to the set-theoretic fact that "there is no set containing ...
0
votes
1answer
22 views

What is the minimum number of slots to cover a set?

Suppose there is a $n$-element set $S$, i.e., $\left|S\right|=n$. One has a complete collection of $k$-element ($k<n$) subsets of $S$: $C=\left\{C_1,C_2,\ldots\right\}$, i.e., any subset of $S$ ...
-2
votes
0answers
32 views

Find all subsets M of a set S

Let $S =\{x \in \mathbb{R} : 1\leq |x|\leq 100\}$. find all subsets $M$ of $S$ such that for all $x,y \in M$, the product $xy$ is also in $M$.
4
votes
3answers
38 views

Proof intersection is finite and non-empty

Course: Analysis (1st year course). Question: If $A_3$ is a subset of $A_2$ and $A_2$ is a subset of $A_1$ and so on... are all finite, nonempty sets of real numbers, then the intersection ...
0
votes
0answers
26 views

Is this set of sequences countable?

Consider the metric space $l^p$, with $1 \leq p \leq \infty$, the space of sequences $x = (\xi_j)$ of real number such that $$ \sum_{j=1}^\infty {\left|\xi_j \right|^p} < \infty. $$ The metric is ...
2
votes
1answer
29 views

For a given relation in $\mathbb{N}\times \mathbb{N}$ find the number of elements in it's equivalence class

The whole problem goes like this: We define the relation $R$ in $\mathbb{N}\times \mathbb{N}$ in the following way: $(a,b)R(c,d)$ iff $a-d=c-b$ First find proof the it's a relation of equivalence ...
0
votes
1answer
21 views

Symbolize a finite set by $\in \mathbb{N}$

Lets say that $A$ is a set. I looking for a way to show that $A$ is finite. I thought about a way and I'd like to know if this way is correct: $$|A|\in \mathbb{N}$$ or, there is a better (or ...
0
votes
6answers
39 views

Proof of the formula for the number of subsets of an n-element set

Given a set $A = \{1,2,...,n\}$, the number of subsets of this set can be given by the cardinality of the powerset of A: $$|\mathscr P(A)| = 2^n$$ This is fairly standard and I'm happy with the ...
-2
votes
1answer
52 views

How to prove that $x\notin {\{a,b,c}\}$? [closed]

Let there be a set $\{a,b,c\}$. I want to prove that for an element $x$, such that $x \ne a, x \ne b, x \ne c$, it's true that $x\notin {\{a,b,c}\}$. Assuming only ZFC axioms, the law of ...
13
votes
2answers
810 views

Why doesn't this definition of natural numbers hold up in axiomatic set theory?

I was reading about older definitions of the natural numbers on Wikipedia here (in retrospect, not the best place to learn mathematics) and came across the following definition for the natural ...
0
votes
1answer
59 views

Is set membership relation a set?

Relations in set theory are sets. But is the set membership relation, being a primitive term, a set too? How would it be defined as a set?
0
votes
1answer
32 views

Functions $X\to \mathcal P(X)$.

$X$ is a set and $f: X \to P(X)$ is a mapping, where $P(X)$ is the power set of $X$. Suppose $Z=\{x \in X: x\notin f(x)\}$, what's correct? 1) $Z$ is empty. 2) $Z$ is nonempty. 3) $Z=X$. 4) ...
0
votes
4answers
59 views

Prove that $A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C)$

I need to prove this: $$A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C)$$ I've done Venn Diagrams and they don't seem to be equal. Plus I want to know how you would do it, because I had to ...
2
votes
2answers
54 views

Natural numbers sorted uncountable?

$|\mathbb{N}|$ by definition is countable infinite. Going to sets of elements indexed by a finite number of indices labelling countable components yields again countably infinite sets (like when ...
0
votes
1answer
18 views

Edward's Venn diagram for Three sets

please can anyone explain? what is meant for three hemispheres in Edward's Venn diagram for 3 sets? and where do we represent intersecting regions in Edward's Venn diagram for 3 sets?Edward's Venn ...
2
votes
2answers
48 views

How do I find the cardinality of set with all the infinite binary sequences which consist of infinite “ones” and “zeros”?

Set $S$ contains all the infinite binary sequences which must consist of infinite "ones" and infinite "zeros", first of all I am not sure if it is countable or not.. I thought about cantors diagonal ...
1
vote
1answer
44 views

Bijection between $[\mathbb N\to \{0,1\}]$ and $[\mathcal P(\mathbb N) \to \{0,1\}]$

In ZFC (edit : and other axiomatic systems), does there exists a bijection between $[\mathbb N\to \{0,1\}]$ and $[\mathcal P(\mathbb N) \to \{0,1\}]$? Extrapolating from ...
5
votes
1answer
133 views

How does the cardinality of the set of all probability measure on a set $X$ change according to the cardinality of $X$?

I was wondering concerning the following problem: Take $X$ as a parameter space endowed with its Borel $\sigma$-algebra. What is the cardinality of $\Delta (X)$, understood as the set of all ...
0
votes
1answer
24 views

Let $f:S\to T$. For each $B\subset T$, we have $f[f^{-1}[B]]=B$ iff $B\subset range(f)$

Let $f:S\to T$. For each $B\subset T$, we have $f[f^{-1}[B]]=B$ iff $B\subset range(f)$ I have the following to prove the $\leftarrow$ of the iff: Suppose $B\subset range(f)$. *Then, for some $y\in ...
1
vote
1answer
12 views

Let $f:A\to B$. For each $B\subset T$, we have $f[f^{-1}[B]]=B$ iff $B\subset range(f)$

Let $f:S\to T$. For each $B\subset T$, we have $f[f^{-1}[B]]=B$ iff $B\subset range(f)$ I have the following to prove the $\to$ of the iff: Let $B\subset T$. Suppose $f[f^{-1}[B]]=B$. *Then, ...
0
votes
1answer
26 views

Why is the Relation R3 Transitive?

Given $A = \{1,2,3,4\}$ in the Relation $\mathcal{R} = \{(1,1),(2,2),(3,3),(4,4)\}$ I understand why $\mathcal{R}$ is Reflexive, Symmetric but why is it also transitive? In my understanding for a ...
2
votes
0answers
70 views

Prove if $(x+1/x)$ is an integer then $(x^n+1/x^n)$ is an integer [duplicate]

So this question was given as a bonus question on my practice exam, but I am interested in solving it... So if $(x+\frac{1}{x}), x \in \mathbb{R}$ is an integer then show $x^n + \frac{1}{x^n}$ is an ...
0
votes
1answer
35 views

Building a set of sets with different sizes

Let $n$ be a positive integer and $N$ be a set of ordered sets that meet some condition, whose size goes from $1$ to $n$. My question is how to write this downs by using set-builder notation. Here go ...
0
votes
2answers
28 views

Prove if statements are ligically equivalent

Is P(A)∪P(B) = P(A∪B) true for all sets of A and B? If so prove it? How do I prove this? I am not showing any attempt because I do not know how to even begin this. Any help would be appreciated.
0
votes
1answer
29 views

Quantifier in Set definitions

Can the definition be made more readable: $\overline{R_1} = \{ (j_1,j_2)\mid j_2 < j_1 + \Gamma^r_a + c^r_w \text{ and } j_1 \in J^r_v \text{ and } j_2 \in J^r_v \text{ and } a = (v,w) \in A^r ...
0
votes
1answer
22 views

Prove if statements are ligically equivalent

Q) Is (A∩B)C = (AC)∩(BC) true? If so prove it. I think it is true just to check it out i took A={x}, B={x,y}, C={x,y,z} So A∩B = {x}, then (A∩B)C = {(x,x),(x,y),(x,z)} So (AC)∩(BC) = ...
0
votes
1answer
60 views

Power set of set of all integers $\Bbb Z$?

Let $S$ be the set $\{ x\in \mathbb Z\, |\, x \le -2 \; \text{or} \; x \ge 5 \}$. What is $P(S) \cap \{\{-3,-2,1\},\{4\},\{6,7\},\{-5,6,9\}\}$? That is the question, how do I find the power set of ...
0
votes
2answers
30 views

Why can't a strictly injective function have a right inverse?

let $A = \{a \in A\}$ and $B = \{b \in B\}$. Let $f$ be a strictly surjective map $f: A \to B$ meaning for every $b$ in $f$'s codomain there must exist some $a$ in $f$'s domain. $f$ is surjective if ...
3
votes
3answers
54 views

Does every set with at least two or more elements admit a fixed-point free self-bijection?

Assume $X$ is a set with at least two elements. Is there a bijection from $X$ to $X$ such that for every $x\in X$ , $f(x) \ne x$ ?
0
votes
2answers
27 views

Understanding order and countability

I am confused with how to defining the order of countable set. Let me express my thoughts by some examples: $\Bbb{N}$ has a 'natural' order, namely $1\lt2\lt3...$ For any countable set, we can define ...
2
votes
1answer
31 views

the intersection of an empty family of sets; what's wrong with this proof?

I have an exercise which says Prove $\bigcap S$ exists for all $S\neq\emptyset$. Where is the asssumption that $S\neq\emptyset$ used in the proof? The definition of intersection is ...
0
votes
1answer
25 views

Which is the correct notation for denoting Dom(f)? X, {$x∈X$|(x, y)$\in f$ for some y}, or {$x ∈ X$ : $∃y(y ∈Y$ ∧ (x, y) $∈ f$)}

I'm not sure after reading definitions and explanations about notation of Dom(f) in books. Which is correct notation for denoting Dom(f) between X, {$x\in X$|(x, y)$\in f$ for some y}, and {$x ∈ X$ : ...
1
vote
2answers
84 views

Why polynomial functions f(x)+g(x) = (f+g)(x)?

Why polynomial functions f(x)+g(x) is the same notation as (f+g)(x)? I've seen the sum of polynomials as f(x)+g(x) before, but never seen a notation as with a operator in a prenthesis as (f+g)(x). ...
6
votes
3answers
519 views

Different arrows in set theory: $\rightarrow$ and $\mapsto$ [duplicate]

Can someone explain the difference between symbols: $\rightarrow$ and $\mapsto$ Thanks.
0
votes
0answers
21 views

example of quasi-transitive relation that is not transitive

I'm trying to come up with an example of a relation that is quasi-transitive but not transitive. The relation $ x R y $ is a subset of the cartesian product $XxX$, and the asymmetric relation is $xPy ...