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
26 views

Predicate logic inference in a simple proof of uniform continuity.

For a function $f$ from a metric space $X$ into a metric space $Y$, uniform continuity can defined in this way: $\forall ε>0:\existsδ > 0:\forall p,q\in X:d_{X}(p,q)<δ \rightarrow ...
-6
votes
0answers
19 views

Bijection of finite and infinite sets [on hold]

Prove that a nonempty set T1 is finite if and only if there is a bijection from T1 onto a finite set T2.
1
vote
3answers
64 views

Suppose $A\subseteq \mathscr P (A)$. Prove that $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$

This is Velleman's exercise 3.3.4. Suppose $A\subseteq \mathscr P (A)$. Prove that $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$. I started reexpressing the terms in their equivalent forms ...
1
vote
1answer
41 views

How to Prove It Exercise 7.2.5

Prove that ${}^{\mathbb{Z}^+} \mathcal{P}(\mathbb{Z}^+) \sim \mathcal{P}(\mathbb{Z}^+)$ where ${}^A B$ means the set of all functions $f:A \rightarrow B$ and $\mathcal{P}(A)$ is the power set of $A$. ...
1
vote
2answers
39 views

counterexample in relations of sets

Suppose $R$ is a relation from $A$ to $B$ and $S$ and $T$ are relations from $B$ to $C$. Can anyone produce a counterexample to $(S \setminus T)◦R⊆(S◦R) \setminus (T◦R)$?
1
vote
3answers
53 views

Union of sets proof

Prove that $\{3t\}\cup\{3t+1\}\cup\{3t+2\}=\Bbb Z$, where $t$ is in the set of integers. It makes sense that you can get every integer from this Union of sets but how would you prove something like ...
3
votes
2answers
125 views

The set of all real functions of a real variable

How can I prove that the set of all real functions of a real variable, or even that the set of functions that take only the values 0 and 1, more than the continuum? I have one idea, but ...
0
votes
1answer
23 views

Determining sets using basic operations

Let A={ O, {O}, 1, a, cat, {1, a, cat}} where O has been used to represent the null set. Determine the follwing: (a) A \ {a, b, c} = {O,{O}, 1, cat, {1, a, cat}} (b) AU{X}= {O,{O}, 1, a, cat, {1, a, ...
0
votes
2answers
39 views

Cardinality of a set containing sets

I've just started learning basic set theory and am puzzled by this question I came up with: What is the cardinality of {1, {2,3}}? Do I treat sets within sets as just one element and so the answer ...
3
votes
4answers
94 views

$S$ and $T$ are two sets. Prove that if $|S-T|=|T-S|$, then $|S|=|T|$.

Here is the problem that I am currently working on: $S$ and $T$ are two sets. Prove that if $|S-T|=|T-S|$, then $|S|=|T|$. I have access to the answer for this proof, and wanted help with the first ...
4
votes
1answer
45 views

Cardinality of a set of natural sequences

Let $a=(a_n)_{n\ge 1}$ a sequence such that for every $n\ge 1$ we have: a) $a_n \in\mathbb{N}$ b) $a_n\lt a_{n+1}$ c) Exists $\displaystyle\lim_{n\to \infty} \frac{\#\{j\mid a_j\le n\}}{n}$ Let ...
1
vote
1answer
41 views

Set-builder Notation

In set-builder notation we describe a set in the following way: $A=\left\{x:\phi (x)\right\}$ Is it correct to say the following? Fix any $x_{0}\in X$ Evaluate the predicate $\phi(x_{0})$ ...
0
votes
2answers
30 views

Totally ordered $\sigma$-algebras

I know that every $\sigma$-algebra is partially ordered with respect to the inclusion operator $\subset$. However, it seems as though every $\sigma$-algebra should be totally ordered with respect to ...
1
vote
2answers
33 views

Triangular number method - Hilbert's hotel

There is a hotel with and infinite number of numbered rooms, each occupied by a single guest. An train with an infinite number of (numbered) coaches, each with an infinite number of (numbered) seats, ...
1
vote
1answer
38 views

Intersection of Countably Infinite Sequence of Sets [on hold]

Suppose $\{\Omega_k\}_{k=1}^{\infty}$ is a sequence of sets, where $\Omega_k$ is countably infinite and $\Omega_{k+1}\subset\Omega_k$ for all $k$. Is it possible to show that $\cap _{k=1}^{\infty} ...
-4
votes
0answers
28 views

All the subset of $A = \{ m,n,o,p,q,r\}$ [on hold]

List all the subset of a set $A = \{ m,n,o,p,q,r\}$
1
vote
0answers
24 views

How to prove partial ordering formally?

The question is: The set $S$ is defined as $\varnothing \in S$, If $x \in S$, then also $\{x\} \cup x \in S$. Prove or disprove it is partial ordering. So the set $S$ looks ...
4
votes
1answer
29 views

Confused about a well-ordering lemma

I happened to stumble across the following lemma in Kenneth Kunen's set theory book: $\textbf{Lemma:}$ Let $\langle$ $A,R$ $\rangle$ be a well ordering. Then for all $x \in A$, $\langle$ $A,R$ ...
3
votes
3answers
39 views

Prove that equality holds only if $f$ is one-to-one.

I am just looking for a hint. Not a solution as I am just trying to solve these for fun. Let $f:A \rightarrow B$ with $A_0 \subset A$ and $B_0 \subset B$. Show that $$A_0 \subset f^{-1}(f(A_0))$$ ...
0
votes
1answer
32 views

Injective function, $f:X\to X$ with $f(X)\subset X$, but $T\subseteq X$ is not inductive set.

I'm looking for an example of the following manner: Suppose that $f:X\to X$ is a injective function(where $X$ some set), such that the following property not holds: If $T$ is subset of $X$, with ...
-1
votes
1answer
47 views

Given a class function, is the preimage of a set a set? [on hold]

Is the preimage of a set under a class function again a set?
1
vote
2answers
14 views

A finite set and the set of its fixed points under any involution have cardinalities of the same parity

I am trying to write down a formal proof of the following fact: Let $A$ be a non-empty finite set and $f$ an involution on $A$. If $A'$ is the set of fixed points of the involution $f$, then $|A| ...
-1
votes
1answer
13 views

How to prove: Union of a chain of well-ordered sets w.r.t continuation is well ordered [on hold]

How to prove: Union of a chain of well-ordered sets w.r.t continuation is well ordered
3
votes
1answer
26 views

The set is closed (resp. open) iff the complement set is open (resp. closed)

There's a theorem in my small danish course book. Let $(M,d)$ be a metric space. Theorem: The concepts of open and closed are dual: A set $A\subseteq M$ is closed (resp. open) if and only if the ...
0
votes
0answers
22 views

With a sequence $\{B_n\}$ and a function defined on all of its elements, what are the spaces between the outputs of the function?

I have a sequence $\{B_n\}$ and a function defined for every member of that sequence: $f(B_i,C_j)=a_j^i$ (Where the spaces between any two adjacent $C$'s is always constant). Such that the following ...
1
vote
1answer
26 views

Proof of $f^{-1}(B_{1}\setminus B_{2}) = f^{-1}(B_{1})\setminus f^{-1}(B_{2})$

I want to prove the following equation: $$ f^{-1}(B_{1}\setminus B_{2}) = f^{-1}(B_{1})\setminus f^{-1}(B_{2}) $$ Is this a valid proof? I am not sure, because at one point I am looking at $f(x) \in ...
0
votes
2answers
60 views

Confusion about the definition of reflexive relation

The definition of a reflexive relation over $A$ is: $R$ is reflexive over $A$ iff $\forall a \in A :(a,a) \in R$ Why the '$\forall a \in A$'? Def. of transitive and symmetric relations don't have ...
4
votes
2answers
52 views

Notation of an infinite union

Is there any difference between: $$ \bigcup_{n =1}^\infty a_{n} \\ \bigcup_{n \in \mathbb{N}} a_{n} $$ From my understanding they both define an infinite union. Is this correct?
1
vote
2answers
28 views

Number of possible unions of a countable number of sets

If $\{ A_{n} \}_{n=1}^{\infty}$ is a countable sequence of distinct sets, then is the number of possible distinct unions between any two or more of the sets in the sequence uncountable? I would like a ...
1
vote
1answer
10 views

Partitions of a power set and equivalence classes

I got the set: $$ M=\{1,2,3,4\}. $$ I could split the power set of M into the following subsets: $$ P_{0}=\{\emptyset\} \\ P_{1}=\{\{1\},\{2\},\{3\},\{4\}\} \\ ...
1
vote
2answers
36 views

Conceptual question about equivalent relations and bijections?

What is the correlation between equivalence relation and bijection? Is equivalence relation a synonym for bijection? Does equivalence relation always imply there exist a bijection? I was ...
1
vote
1answer
43 views

Logical equivalence - Russell's Paradox

In 'How to Prove it' Velleman creates the following set: $R = \{A\in U| A \notin A \}$. This is, according to Velleman, equivalent to $\forall A \in U (A \notin A \iff A\in R) $. That is clear. ...
1
vote
2answers
50 views

Third axiom of Kolmogorov axioms

Let us define for a countably infinite set $S$ of real numbers that can be enumerated as $x_1,x_2,\cdots$, $$P(S) = \sum_{x \in S}p(x) = \sum_{i=1}^\infty p(x_i) = \lim_{n \to \infty}\sum_{i=1}^n ...
0
votes
0answers
19 views

Examples of proper classes besides the universe and Russell's class

Is there any other interesting proper class besides the universe $U$ and Russell's class $R$? $U=\{x:x=x\}$ $R=\{x:x\notin x\}$ Background: I'm studying the appendix on elementary set theory from ...
3
votes
1answer
27 views

Show that $T$ is the Set of All Sets Using the ZF Axioms

Let x be a set. Define the "set" $S = \left\{ y:x\subseteq y \right\}$ and $T = \cup\left\{y:y\in S \right\}$. Given any set $w$, let $z=x \cup \left\{w\right\}$. Then $x \subseteq z$, so $z \in S$. ...
-1
votes
0answers
18 views

Is a class of sets indexed by all the abelian groups a proper class [duplicate]

Let $\{K^i \mid i \in \mathbb{N}\}$ be a set indexed by $G \in \textbf{Ab}$. Is the class of all $\{K^i \mid i \in \mathbb{N}\}_{G \in \textbf{Ab}}$ a proper class? My understanding is that since ...
1
vote
1answer
16 views

Two “adjunct” (quasi-inverse) functions

Let $A$, $B$ be fixed sets. What "means" the formula $Y \cap \alpha X \neq \emptyset \Leftrightarrow X \cap \beta Y \neq \emptyset$ for functions $\alpha:\mathscr{P}A\rightarrow\mathscr{P}B$ and ...
1
vote
2answers
57 views

Can someone explain to me why set proof involve the words “or” and “and”

For example, on proving the distributive law of set theory, the following constitutes as a proof Proof : I am new to proof involving sets but this to me seems nothing more than replacing unions ...
0
votes
0answers
46 views

What is a proof of the union law in set theory $|A \cup B| = |A| + |B| - |A \cap B|$ without using Venn Diagram [duplicate]

$|A \cup B| = |A| + |B| - |A \cap B|$ can be easily demonstrated using a Venn diagram (along with some x-ray vision) But according to my prof a Venn Diagram is not really a proof. How should one ...
0
votes
0answers
16 views

Bijective Function from n-fold Cartesian Product to set of functions

This is my first posting, so I apologize for the cumbersome formatting; I am not yet familiar with MathJax/Latex commands. Let $Y$ be a set and let $n$ be an element of $\mathbb N$ (natural numbers). ...
0
votes
1answer
44 views

How to view beth number as ordinal?

The following is the snippet of the paragraph given in my lecture note: (Note: $\beth$ is the beth-number.) (When I introduced $\beth_\alpha$ I told you that it was to be a particular size of ...
-4
votes
3answers
83 views

If you remove an element from an infinite set, does the set remain infinite? [closed]

Say you have the infinite set of all positive integers. If you remove the number 2, is this set still infinite? If yes, why? If no, also why?
1
vote
3answers
45 views

$A \cap B \subset (A \cap C) \cup (B \cap C')$

How do i show this? $A \cap B \subset (A \cap C) \cup (B \cap C')$ $$ x \in A \cap B$$ $$ \implies x \in A \cap B \cup \emptyset$$ $$ \implies x \in A \cap B \cup (C \cap C')$$ $$ \implies x \in (A ...
0
votes
1answer
28 views

Determine whether, for any set A, it is true that $P(\bar{A})= P(U) - P(A)$

I'm currently working on a easy enough logic question, however I'm having trouble proving or disproving it's validity. The question goes as follows: Determine whether, for any set A, it is true ...
1
vote
1answer
21 views

Prove that family of sets generates partition

Let $X$ be any set. Let $\mathcal{F}$ be family of subsets of $X$ closed under aritrary intersections and complements. Let $P(x)=\bigcap \{A\in\mathcal{F}:x\in A\}$. I need to prove that family ...
1
vote
2answers
37 views

Is there a powerset with the cardinality of the natural numbers? [duplicate]

Under the axiom of choice I believe, the powerset of a set with cardinality $\aleph_0$ has cardinality $\aleph_1$, the powerset of a set with cardinality $\aleph_1$ has cardinality $\aleph_2$, and so ...
1
vote
1answer
28 views

What is the cardinality of a string set with finite alphabet?

We can construct a language $\mathcal L$ with the finite alphabet $\mathcal A $ (e.g. $\{0,1,\dots,9\}$): $$ \mathcal L=\{string|string=x^* \land x\in \mathcal A\} $$ $x^*$ is $x$'s Kleene Closure, ...
2
votes
4answers
93 views

What is the cardinality of the set of roots of unity?

Consider the geometric interpretation of "roots of unity": My intuition says that you can place arbitrarily many equidistant points on the unit circle and catch every point that lies on it. ...
1
vote
1answer
13 views

Name for a collection of subsets of a set $E$ such that every element of $E$ is in some member?

Let $X$ be a set. A partition of $X$ is a collection of subsets $\{E_\alpha\}\subset\mathcal{P}(X)$ such that the following holds. For every $x\in X$, there is some $\alpha$ such that $x\in ...
2
votes
4answers
48 views

What is a simple example that shows equivalence classes constitute a partition?

Can someone illustrate using a simple concrete example that the equivalence classes defined by $\sim$ constitute a partition of a set $A$?