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
2answers
46 views

Construct an explicit bijection $f:[0,1] \to (0,1]$, where $[0,1]$ is the closed interval in $\mathbb R$ and $(0,1]$ is half open.

The problem: Construct an explicit bijection $f:[0,1] \to (0,1]$, where $[0,1]$ is the closed interval in $\mathbb R$ and $(0,1]$ is half open. My Thoughts: I imagine that I am to use the fact that ...
2
votes
1answer
73 views

If there is an injection $f: X \to Y$ with $m=n$ then $f$ is a bijection.

The Statement of the Problem: Let $X,Y$ be finite sets with $ \lvert X \rvert = m $ and $ \lvert Y \rvert = n $. Prove the following statement by induction on $ m \ge 1$: If there is an injection ...
0
votes
1answer
37 views

Proof by Contradiction to show that if $f^{-1}$ exists, $f$ must be onto

Use proof by contradiction to prove that if $f^{-1}$ exists, then $f$ must be onto where $f:A→B$. Proof: I think the contradiction of the theorem would be: if $f$ exists then $f^{-1}$ must be ...
1
vote
2answers
63 views

Showing $(f^{-1}∘g^{-1})=(g∘f)^{-1}$

If the functions $f$ and $g$ are both bijections then the in inverse of the composition function $(f∘g)$ will exist. Show that it will be $(f^{-1}∘g^{-1})=(g∘f)^{-1}$ For the proof assume ...
2
votes
2answers
35 views

Give an example of a set $A$ and a function $f\colon A \to A$ where $f$ is onto but not one-to-one.

I am currently trying to decipher this question but I have been unable to thus far. If a set $A$ is mapped onto itself, it seems that you would always have a function that is both onto and one-to-one. ...
0
votes
0answers
26 views

Proving associativity of symmetric set difference

I'm proving that $P(X)$ (the set of the subsets of $X$) is a ring with the following operations: If $A, B \subset X$, then $A+B := (A \cup B) \backslash (A \cap B) $ and $A \cdot B = A \cap B $. I ...
1
vote
1answer
31 views

Proof that the following integer multiplication is well defined

Prove that multiplication given by $[(a,b)][(c,d)] = [(ac + bd,ad + bc)]$ is well defined. My work: $(a,b) \sim (a_1,b_1) \rightarrow a + b_1 = a_1 + b$ $(c,d) \sim (c_1,d_1) \rightarrow c + d_1 ...
0
votes
1answer
40 views

A doubt about real analysis concerning countable sets [duplicate]

I sometimes get confused when dealing with the notion of countable sets. MY book says that $A$ I countable if there is bijection $f: A \to \mathbb{N }$. but then I frequently see people refer to ...
-1
votes
1answer
21 views

if there is an injection between $A$ and $B$, does there exists an injection between $P(A) $ and $P(B)$?

Suppose $f: A \to B $ is injective, does it follow that there is injective $f :\mathcal{P}(A) \to \mathcal{P}(B) $ ? I mean the obvious choice would be $f( \{ a \} ) = \{ f(a) \} $. does it work ?
0
votes
1answer
34 views

Proving the set identity $(X \cup Y) = X + Y - (X \cap Y)$

I wanted to know if the identity $(X \cup Y) = X + Y - (X \cap Y)$ holds true for any set X and Y? Here, X + Y means all elements in X and Y including repeated elements.
0
votes
2answers
16 views

Trying to find injection between two sets

Let $A,B, C$ be sets such that $f: A \to B $ is injective and $|B| = |C| $. prove there is an injection from $A$ to $C$. Obviously, if we can find and injection $g: B \to C $ then the composition $g ...
1
vote
0answers
58 views

Name of the set $B:= \overline{A}\setminus A$

Let $(X, \mathcal{T}_X)$ denote a topological space and let $A$ be a subset of $X$. We define the set $B:=\overline{A}\setminus A$. Does the set $B$ have a special name in the literature? All I could ...
0
votes
0answers
9 views

Closure systems [duplicate]

Let A be any set. A system $\mathscr{C}$ of subsets of A is said to be a closure system if $\mathscr{C}$ is closed under intersections, i.e. $$\textrm{for any subsystem ...
1
vote
1answer
26 views

Prove if $x$ is greatest lower bound of $U$ then $x$ is the least upper bound of $B$

This is one of the problem I have been solving from Velleman's How to prove book; Suppose $R$ is a partial order on $A$ and $B \subseteq A$. Let $U$ be the ...
1
vote
0answers
51 views

Natural bijection between $\mathbb{N}$ and algebraic numbers?

Q. Is there a canonical, explicit bijection between the natural numbers $\mathbb{N}$ and the algebraic numbers? The earlier MSE question, "Bijection for algebraic numbers," does not quite ...
0
votes
4answers
118 views

If a function maps A to its PowerSet, is it Surjective?

Given an arbitrary set A, let F : A → 2^A be the function defined for all a ∈ A by f(a) = {a} If A maps to its power set, does this make F surjective? If somebody could help to prove this that ...
6
votes
2answers
114 views

Explicit bijection between $\mathbb Q$ and $\mathbb Z \times \mathbb Z$?

Any idea of an explicit bijection between $\mathbb Q$ and $\mathbb Z \times \mathbb Z$? Even if I think of rational elements as $\frac {m}{n}$, sending them to $(m,n)$ won't work, because all pairs ...
1
vote
3answers
37 views

A little doubt about set notation.

Is $ A \setminus B = A \setminus (A \cap {B})$. I am learning sets and it is given that A minus B is {x $\in$ A such that x $\notin$ B}. Is it the same as A minus A intersection B. One word answer ...
0
votes
2answers
18 views

Generalized Union and Intersection Problem [duplicate]

Can anyone help me with this question? I would greatly appreciate it!
2
votes
1answer
21 views

Power set functors preserve monicness

This link discusses power set functors. Proposition 5.7 If $f$ is a epimorphism then so is $\exists_f$. Proposition 5.8 If $f$ is an monomorphism then so is $\forall_f$. A little ...
0
votes
2answers
20 views

Quadratic reciprocity: $\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$

Prove $\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$, where $p$ is an odd prime, and the LHS is the legendre symbol. I've got $-1 = x^2 \pmod p \implies (-1)^{\frac{p-1}{2}} = x^{p-1} = 1 = ...
0
votes
2answers
58 views

How to remember various set operations very easily?

I need an way to remember the set operations very easily. Does anybody have any idea? For example, how do you remember the distinction between Set-Intersection and Set-difference? I regularly mess ...
0
votes
3answers
43 views

f bijection on some set $X$ with property $f(A) \subseteq A$, does $f(A) = A$ follow?

I have a very simple question I can't seem to figure out on my own. Let's say we have a bijection $f: X \rightarrow X$ on some set $X$ and we have a subset $A \subseteq X$ with the property $$f(A) ...
1
vote
1answer
35 views

Prove a collection is a $\sigma$-algebra

I have to prove that a collection of sets is a $\sigma$-algebra. I'm stuck with the axiom of closure under countable unions. The collection is $$ \mathcal{A}=\{A\in\mathcal{B}:m(A\Delta T^{-1}A)=0\} ...
0
votes
1answer
30 views

Given the following, is there equivalence relation?

Let $n$ be an integer. On the set $F$ of all integer-valued functions of a set $A$, suppose we define $f$ and $g$ to be related if $f(a)\equiv g(a)\pmod{n}$ for every $a\in A$. Is this an equivalence ...
0
votes
1answer
21 views

Complementary Relation Proof

If $R$ is reflexive, prove that $R^c$ is irreflexive. If $R$ is asymmetric, prove that $R^c$ is reflexive. Where $R^c$ = complement of $R$. I just can't figure out anything to say for the first one ...
1
vote
1answer
28 views

Proof on sets $(A\cap B)\cup(A\cap \bar{B}) = A$ [duplicate]

Original question : To Prove : $(A\cap B)\cup(A\cap \bar{B}) = A$ My Response to it : We have, $(A\cap B)\cup(A\cap \bar{B}) = A$ $\Rightarrow (A \cap B) + (A \cap \bar{B}) - (A \cap B \cap A ...
2
votes
3answers
55 views

Power set of a subset

Proof that if $A \subseteq B$, then ${\mathscr P}(A) \subseteq {\mathscr P}(B)$. I tried using the definition of a subset: $A \subseteq B = \forall x(x \in A \to x \in B)$, but get stuck as to how to ...
1
vote
1answer
25 views

Cardinality of an open dense set in a compact Hausdorff space

Let $\kappa$ be an infinite cardinal and let $X$ be a compact Hausdorff space of size $2^\kappa$. Let $U$ be a dense open subset of $X$. Can you give a lower bound for the cardinality of $U$. ...
3
votes
3answers
68 views

How can I prove if $A\subseteq B$, then $A\cup B=B$?

I need to prove that $$A\subseteq B \implies A\cup B=B$$ I defined the subset relation as the statement $x\in A\Rightarrow x\in B$. I tried to convert the claim into a logic statement, then proceeded ...
3
votes
1answer
64 views

Introduction to proofs: proving a set is a partition.

I've been really trying to understand how some of these proofs work; I've spent a majority of my time studying the material for this class, but I'm still performing poorly in it. It doesn't help that ...
1
vote
2answers
52 views

for some or for all

The following text is from Velleman's How to Prove book from the reflexive closure section: According to the definition we gave in the last section, the ...
1
vote
2answers
31 views

Cardinality of $\{ (x, y) \in \mathbb{R}^2 \mid \left| x \right| + \left| y \right| = 1 \}$ and $\{ (x, y) \in \mathbb{R}^2 \mid x^2 + y^2 = 1 \}$

Do $\{ (x, y) \in \mathbb{R}^2 \mid \left| x \right| + \left| y \right| = 1 \}$ and $\{ (x, y) \in \mathbb{R}^2 \mid x^2 + y^2 = 1 \}$ have the same cardinality? One can draw a square in the two ...
0
votes
2answers
43 views

Can a Subset be considered an Element for Field Axioms

I have the subset $L\subset \Bbb Q$ that is Dedekind cut. I want to prove that $L+(-L)=0$ I want to do this using the field axiom of Additive Inverse, but Additive Inverse specifically deals with ...
2
votes
2answers
52 views

$\forall \alpha \exists \beta: \beta > \alpha$ where $\alpha$ and $\beta$ cardinals

I have to prove ZF $\vdash$ $\forall \alpha \exists \beta:\beta > \alpha$, where $\alpha, \beta-$ cardinal numbers. I can prove it only in ZFC. Let's fix some cardinal number $\alpha$. By ...
2
votes
3answers
31 views

Let $A_i= \left \{…,-2,-1,0,1,…,i \right\}$. Find $\bigcup_{i=1}^{n} A_i$ and $\bigcap_{i=1}^{n} A_i$

I have the following assignment: Let $A_i= \left \{...,-2,-1,0,1,...,i \right\}$. Find a) $\displaystyle \bigcup_{i=1}^{n} A_i$ b) $\displaystyle \bigcap_{i=1}^{n} A_i$ I think the first one ...
1
vote
3answers
44 views

Show that if $A$ and $B$ are sets, then $(A\cap B) \cup (A\cap \overline{B})=A$.

Show that if $A$ and $B$ are sets, then $(A\cap B) \cup (A\cap \overline{B})=A$. So I have to show that $(A\cap B) \cup (A\cap \overline{B})\subseteq A$ and that $A \subseteq(A\cap B) \cup (A\cap ...
2
votes
0answers
20 views

Set Theory Jech - Induction Proof Ex. 1.9

Exercise 1.9 in Set Theory (Jech) asks : Let $A$ be a subset of $\mathbb N$ such that $\emptyset \in A$, and if $n \in A$ then $n + 1 \in A$. Then $A = \mathbb N$ . I have seen some solutions using ...
1
vote
1answer
33 views

How to represent a function that says “send least element to least element and next to next” using a first order formula?

Suppose that $A$ is a finite set. $<_1$ and $<_2$ are two well-orderings on $A$. Suppose that I want to find a formula that repesents the function $F$ that says " send least element in ordering ...
-1
votes
0answers
21 views

What is the image of $S_1$ under $f$ if $f$ is mapped onto $S_1$ and $f$ is some continuous function?

How am I to visualize the image of $S_1$ $f\colon S_1 \to S_1$ given that $f$ is some arbitrary function that is continuous?
4
votes
3answers
293 views

What is the mistake in this proof?

During a long night without sleep I managed to come up with a proof for a statement I know is false, and for the life of me I cannot figure out what I did wrong. Where is my mistake? Theorem: Let ...
1
vote
2answers
23 views

Clarifying the Definition of an Inductive Set

I'm having trouble understanding this particular definition of an inductive set. Definition. $\exists S (\varnothing\in S\land (\forall x \in S)x\cup \{x\}\in S)$. We call a set with this property ...
1
vote
1answer
40 views

Assuming the axiom of choice ,how to prove that every uncountable abelian group must have an uncountable proper subgroup?

Assuming the axiom of choice , how to prove that every uncountable abelian group must have an uncountable proper subgroup ? Related to Does there exist any uncountable group , every proper subgroup ...
5
votes
1answer
38 views

Function on a Power Set

Let $f\colon \mathcal{P}(A)\mapsto \mathcal{P}(A)$ be a function such that $U \subseteq V$ implies $f(U) \subseteq f(V)$ for every $U, V \in \mathcal{P}(A)$. Show there exists a $W \in \mathcal{P}(A)$ ...
20
votes
1answer
543 views

Does there exist any uncountable group , every proper subgroup of which is countable?

Does there exist an uncountable group , every proper subgroup of which is countable ?
1
vote
2answers
31 views

Proving intervals are equinumerous to $\mathbb R$

Let $a$, $b$ elements of $\mathbb R$ with $a < b$. By combining the results of the past exercises and examples, show that each of the following intervals are equinumerous to the set $\mathbb R$ ...
0
votes
1answer
39 views

Proving intervals are equinumerous

a.) Show that (0, 1] is equinermous to the interval (0, 1) by giving an example of a bijection from (0, 1] to (0, 1). My attempt: ...
2
votes
1answer
54 views

Can you verify this proof of the Schroeder-Bernstein theorem?

I'm a freshman in college and my professor challenged us to find a proof of this theorem. Please don't give me the answer but please verify if this proof works or, if not, if it is the start of a ...
0
votes
1answer
33 views

Prove that there is a surjection $ f:X \to Y$ if and only if $ |Y| \le |X| $.

Here's the problem: Let $X$ and $Y$ be sets. Prove that there is a surjection $$ f:X \to Y$$ if and only if $$ |Y| \le |X| $$. My work so far: I am working on the following direction: If $ |Y| ...
0
votes
1answer
16 views

Terminology for when a variable is implicitly a member of some set?

I have sets $N = \{1, \ldots, n\}$ and $M = \{1, \ldots, m\}$. When referring to a generic element of these sets, I typically use variables $i \in N$ and $j \in M$. Is there any standard ...