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
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
55 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
520 views

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

Can someone explain the difference between symbols: $\rightarrow$ and $\mapsto$ Thanks.
0
votes
0answers
22 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 ...
0
votes
2answers
59 views

A question on power set [closed]

There is a question Prove (only use the axioms of Zermelo- Fraenkel ) that there is no set $X$ such that $P(X) \subset X$, where $P(X)$ is the power set of $X$, i.e., $P(X) = \{u: u\subset X\}$. ...
0
votes
0answers
22 views

Short notation for mapping to a family of sets

I want to write a function of which the output is a family of sets over the domain. Is this a correct notation? $ f: A \rightarrow \{ A' | A' \subseteq A \} $ Is there a way I can shorten this, the ...
0
votes
1answer
33 views

prove/disprove that if $|A \mathbin\Delta B| = \aleph$ and $|A \cap B| = \aleph$ then $|A \cup B| = \aleph$

I encountered this question at one of my books that I read about logic and set theory and I can't figure how to do it, I hope someone could help me out here: if $|A \mathbin\Delta B| = \aleph$ and ...
0
votes
0answers
34 views

Proving 1:1 and onto of 2 variable function

Let $\ f: \mathbb Q^2\to\mathbb Q^2$ be defined by $\ f(x,y) = (x-3y , x + 3y- 1)$ Prove the function is 1:1, onto, find the inverse and $\ f \circ f $. I was able to prove 1:1 by showing $\ ...
0
votes
2answers
41 views

Write a set as union of disjoint sets

I was arguing with my roommate about writing any set like this: $A = (A \cap B) \cup (A \cap B^c)$ Asuming, that both $A, B \subseteq X$, where X is the Universe. No matter what the relationship ...
2
votes
1answer
40 views

Give a bijection

Give a bijection between the following sets: (1) $\mathbb{Z}$ and $ \mathbb{Z}\backslash \{0\}$ (2) $\mathbb{Q}$ and $ \mathbb{Q}\backslash \{0\}$ I think that I can the problems with "Hilbert's ...
0
votes
1answer
34 views

Show the sigma algebra containing $\{2n,2n+2,2n+4,..\}$ is uncountable

I am asked the following: 1) Show that for any family of subsets $A$ of $\Omega$ there is a smallest $\sigma - $algebra containing $A$. 2) Let $\mathcal{F}$ be a sigma algebra in the space $\Omega$ ...
0
votes
2answers
29 views

Prove that if $A\subset B$ then $P(A)\subset P(B)$.

$A$ and $B$ being sets and $P(A)$ being the power set of $A$: Prove that if $A\subset B$ then $P(A)\subset P(B)$. It seems oblivious but I'm not sure how to write the proof properly.
1
vote
3answers
66 views

Is $\mathbb{R^2}$ Hausdorff? Give an example of a non-Hausdorff topology on $\mathbb{R}$

these are two questions on Hausdorff topological spaces. The bit I am having particular difficulty with is finding an 'example of a non-Hausdorff topology on $\mathbb{R}$' A Hausdorff topological ...
-2
votes
1answer
48 views

What would non recursive enumerability means?

Edit : I think that this article is the answer i was waiting for, i stubble upon it by chance while investigating automatic proof verification and lambda calculus : ...
1
vote
1answer
27 views

Calculate the number of SDR's in $A_i:=\{1,\dots,n\}\setminus\{i\}$

Suppose that $A_1,A_2,\dots,A_n$ are sets, which we refer to as a set system. A (complete) system of distinct representatives is a set $\{x_1,x_2,\ldots,x_n\}$ such that $x_i \in A_i$ for all $i$, and ...
2
votes
1answer
30 views

Why the intersection of infinite integers is $\{1\}$?

Intersection of different sets mean that we will get only the elements that exist in each of them. Then why intersection of all $\mathbb{Z}^+$ numbers will yield $\{1\}$? It is clear that $1$ only ...
0
votes
3answers
35 views

When is a family of sets said to be non-empty?

Is a family of sets said to be non-empty if it has some member other than ths empty set ? Or if the empty set is a member of a family of sets, is the family non-empty? (Note that the empty set might ...
2
votes
4answers
57 views

Sigma algebra question

Let $Σ_1$ and $Σ_2$ be two sigma-algebras on the same set $X$, such that their union $Σ_1 ∪Σ_2$ is also a sigma-algebra. Prove that for $A,B ⊆ X$ such that $A ∈ Σ_1 \setminus Σ_2$ and $B ∈ Σ_2 ...
1
vote
2answers
32 views

What does the ratio of a sets mean?

I'm reading a mathematical physics book and they define a couple sets like this: $\epsilon \mathbb{Z}^d/L\mathbb{Z}^d$ and $\mathbb{R}^d/L\mathbb{Z}^d$ This is in the context of lattice field ...
4
votes
1answer
41 views

Explaining whether a function is injective/surjection ($f\colon\Bbb N\to P(\Bbb N)$)

Let $f\colon\Bbb N\to P(\Bbb N)$ be given by $$f(n)=\{n+1,n+2,n+3,\dots\}.$$ $(a)$ Is $f$ an injection? Explain. $(b)$ Is $f$ an surjection? Explain. $(a)$ A function is injective ...
-3
votes
0answers
37 views

What is the cardinality of this set $P(\mathbb{R}) \setminus P(\mathbb{R} \setminus \mathbb{N})$? [duplicate]

What is the cardinality of $P(\mathbb{R}) \setminus P(\mathbb{R} \setminus \mathbb{N})$?
-1
votes
1answer
35 views

Is ${\{1\}}^\omega$ isomorphic to $\mathbb{Z}_+$?

Here is a proof that countably infinite product of countable sets is not (always/never?) countable. My question is : what if $X={\{1\}}$ ? i.e. Is $g:\mathbb{Z}_+\to X^\omega$ surjective (or even ...
1
vote
0answers
32 views

Show that if $A$ and $B$ are non-empty separated sets, then $A \cup B$ is disconnected.

Show that if $A$ and $B$ are non-empty separated sets, then $A \cup B$ is disconnected. Attempt at solution: Since $A$ and $B$ are separated, $A \cap \bar{B} = \emptyset$ and $\bar{A} \cap B = ...
4
votes
2answers
38 views

How to show this subset of $\mathbb{R}$ is countable

For a finite set $X$, we write $\sum X$ to be the sum of all the numbers in $X$. Suppose we have a set $S \subseteq \mathbb{R}$ such that $-100\le \sum X \le 100$ for all finite subsets $X \subseteq ...
0
votes
1answer
19 views

equivalence relation and sets

The question: Let $X$ and $Y$ be two sets, and let $S$ be an equivalence relation on set $X$ and $T$ be an equivalence relation on set $Y$. Define a relation $R$ on $X ×Y$ by $(a,b)R(c,d)$ if and ...
0
votes
1answer
30 views

What is the cardinal all the finite & infinite binary sequences that don't contain '10'?

What is the cardinal all the finite & infinite binary sequences that don't contain '10'? I know I can make a function $f(z, o)$ where $z, o \in \mathbb{N}$ that builds a sequence that starts with ...
0
votes
1answer
83 views

Proof that $\partial(A\times B) = ((\partial A)\times B)\cup (A\times(\partial B))$

I need to prove that: $$\partial(A\times B) = ((\partial A)\times B)\cup (A\times(\partial B))$$ In other terms, the boundary of the cartesian product is the union of the things in the RHS. I've ...
0
votes
1answer
35 views

How is the normal ordering on the Natural Numbers defined in Zermelo set theory?

A fact that often gets mentioned in the elementary development of arithmetic in ZFC is that there are a bunch of different ways one could have defined the natural numbers. The most common alternative ...
-2
votes
2answers
49 views

Cardinality of binary sequences with finitely many 1s

First of all, sorry if I repost about this issue, couldn't found nothing similar about it. Let $A$ be the set of all the infinite binary sequences. How do I find the cardinality of set $B$ - which ...
0
votes
1answer
29 views

Set addition between A and B

$$U = \mathbb{R}^2, A = \{ (x, y) \in \mathbb{R}^2 \mid x^2 + y^2 \leq 1 \}, B = \{(x, y) \in \mathbb{R}^2 \mid y = x, 0 \leq x \leq 1 \}$$ How can be addition be: $$A+B= \{(x,y) \in \mathbb{R}^2 ...
0
votes
0answers
15 views

Sum of the product of a cartesian product

I have two disjoint (though I suppose they don't need to be disjoint) sets, $M$ and $N$. I now want to take something like $$\sum_{(i,k) \in M\times N} i\cdot k$$ In english, I want a sum of the ...
0
votes
1answer
23 views

Equivalence relations and composition, intersections of them

I've been having some trouble with this one, I hope someone get's it. Let S and R be equivalence relations within X. Prove that if R∘S is an equivalence relation, then it is equal to the ...
0
votes
1answer
12 views

Sets, indexes, subspace

Let $E$ be a vector space and $X$ contained in $E$. Say I want to talk about all vector subspaces of $E$ that contain the set $X \subset E$. I could associate a family of indices $L$ to these ...
0
votes
1answer
31 views

instruction of replacement axiom

I self-studied the book "Set Theory (Jech)", but I cannot understand the 22, 25 pages(attached below) during two months. I guess 'replacement' of p.22 is used through these steps. (but I think it is ...
1
vote
1answer
33 views

proof without axiom of choice

I heard that I can't prove '$\lim_{n \rightarrow \infty} f(a_n)=f(a)$ for all $\{a_n \}$ such that $\lim_{n \rightarrow \infty} a_n = a$ $\Longrightarrow$ $f$ is continuous at $a$' without axiom of ...
0
votes
2answers
115 views

Is it possible to prove that $\{\mathbb{N}\} = \{\}$?

A standard definition of the naturals is considered once again: $$ \begin{array}{l} 0 = \{\} \\ 1 = \{0\} = \{\{\}\} \\ 2 = \{0,1\} = \{ \{\} , \{\{\}\} \} \\ 3 = \{0,1,2\} = \{ \{\} , \{\{\}\} , \{ ...
1
vote
0answers
24 views

How do I disprove that $|\mathcal P([0,1]) \setminus \mathcal P((0,1))| > |\mathcal P(\mathbb{N})|$ [duplicate]

I am trying to disprove this proposition $|\mathcal P([0,1]) \setminus \mathcal P((0,1))| > |\mathcal P(\mathbb{N})|$, where $\mathcal P (X)$ is the power set of $X$, but I am not sure how. I hope ...
0
votes
0answers
11 views

Proof Explanation of a proof on the upper bound of Frobenius Number for a bounded set.

This is a proof which shows the upper bound on the Frobenius Number for a bounded set taken from here. (Slide 47.) I don't understand it from the part where $r$ comes in. Can you please explain it and ...