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

0
votes
4answers
113 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 ...
-1
votes
0answers
38 views

ISO information on powerset functor [closed]

This site has the very bare bones, but I'd like to see more.
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
19 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
56 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
29 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
19 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
27 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
2answers
45 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
63 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
51 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
291 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
38 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
36 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
538 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 ...
2
votes
1answer
34 views

In a transitive relation does x and z have to be the same element?

I am new to relations on sets and am trying to get my head around transitive relations. I understand the definition of $(x,y) \in R, (y,z) \in R$ and $(x,z) \in R$ However what i am not sure about ...
0
votes
1answer
17 views

Number of ways to build a collection of numbers where $sum = k$, each $0 < n_i <= d_i$ for some corresponding $d_i$, and sum of all $d_i >= k$

I apologize for any (mis|ab)use of notation since I'm not a mathematician. My background is software engineering and computer science. I ran into this problem while trying to figure out the ...
2
votes
1answer
30 views

Formal proof that $N$ is the smallest infinite set [duplicate]

I wish to write a formal proof of the following statement: For any infinite set $X$, there exists an injection $f:\mathbb{N}\to X$. I'd like the proof to explicitly use the full axiom of choice (for ...
2
votes
1answer
24 views

What is the cardinality of an infinite set of closed disjoint intervals?

The question is : Let A be a set of a closed disjoint intervals, what is the cardinality of A ? I need to prove it using the Density property of the rational numbers in the real numbers. So i know ...
0
votes
1answer
38 views

how to prove that the set of positive real numbers is uncountable

I am trying to show that R+ cardinality is c but i'm stuck at finding a bijection from R or even from (0,1]. Thanks in advance !
0
votes
3answers
20 views

How to prove that the set of rational numbers that are not integers is countable and infinte?

The question is Prove : The set of rational numbers that are not integers is countable and infinte. Well, Q \ Z is actually a subset of Q, thus |Q\Z| <= |Q| = א0 So this is a way to show that it ...
1
vote
1answer
49 views

Defining integer sum without using infinite sets

In ZFC minus infinity (let us call this system $T$), one can still define ordinals, and then define integers as ordinals all of whose members are zero or successor ordinals. Combining the power set ...
3
votes
2answers
254 views

How to prove every partition of same cardinality sets has same cardinality?

Assume $A$ is a set, and $A$ is partitioned into two ways, $\{A_i\}$ and $\{B_i$} where any $A_1,A_2 \in \{A_i\}$ and $B_1,B_2 \in \{B_i\}$ we have $|A_1|=|A_2|=|B_1|=|B_2|$. Then is that true ...
3
votes
1answer
85 views

Total number of unordered pairs of disjoint subsets of S

Let $S = \{1, 2, 3, 4\}$. Find the total number of unordered pairs of disjoint subsets of $S$. I know the answer is $41$ since it's solved in the book as the expression $$\frac{3^4 -1}{2!} +1 ...
1
vote
3answers
46 views

What's the supremum of the following set $\{ n + \frac{(-1)^n}{n} : n \in \mathbb{N}\}$

What's the supremum of the following set $\{ n + \frac{(-1)^n}{n} : n \in \mathbb{N}\}$? I know that the infimum is $0$, but what about the supremum? I have calculated with Maxima the first $1000$ ...
1
vote
1answer
20 views

The power set under intersection and addition as a ring

If $D$ is a set and $P(D)$ its power set, and $A+B=(A-B) \cup (B-A)$, $AB=A \cap B$ how come $P(D)$ is not a suitable identity? Also, I would appreciate it if someone could elaborate on why if $A ...
0
votes
1answer
32 views

Set notation - products of subsets

In terms of conventional set notation, a set and it's corresponding power set of cardinality $2$ can be defined: \begin{align} &A&=\quad&\{a,b,c,d\}&\\ ...
0
votes
0answers
25 views

Deciphering whether a set relying on a predicate exists

I'm having some trouble with these style of questions in my Set Theory course and I'm not sure how to proceed with them. Screenshot of the question For part i) I tried something along the lines of ...
0
votes
2answers
33 views

how can we express finiteness as a first order property?

I don't know much about set theory but I read that in ZFC a set is finite when there are no bijections from the set to a proper subset of itself. It seems to me however that quantifying over subsets ...