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
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$?
1
vote
3answers
98 views

Proof of the Union of Power Sets

I saw the proof at ProofWiki. I know well that $X\in \mathcal{P}(A)\iff X\subseteq A$ where $A$ is a set, but why can't I show the following way \begin{align} X\in (\mathcal{P}(S)\cup ...
2
votes
2answers
55 views

a question about analysis, how to find the largest cardinality in the following examples

This is a GRE math question: My thoughts: I guess as for the cardinality, (A)=(B) and (D)=(E),but I couldn't prove whether it is true or not. Also, how to find the cardinality of (C), can someone ...
0
votes
3answers
102 views

Language that describes all real numbers

According to Wikipedia: Suppose that in a mathematical language $L$, it is possible to enumerate all of the defined numbers in $L$. Let this enumeration be defined by the function $G\colon W\to ...
1
vote
1answer
68 views

Category of Sets w/ 17 Elements: There does not exist a direct product? (Lots of questions here)

I'm having a pretty hard time with this. I'm asked to show that, in the category of sets with exactly 17 elements, no two objects have either a direct product nor direct sum. Part of me doesn't even ...
0
votes
1answer
42 views

Interesection of set

If it is given that ABC is a {0}, where A, B and C are sets, then is it true that ABCD is also {0} or null set, where D is also a set ABC means will mean intersection of A, B and C. Further, the ...
0
votes
0answers
18 views

Existence of a rank function over a well founded set

I need help in understanding a step from Jech Set Theory, theorem 2.27 In the proof, he defines a series of subsets of a well founded set $P$ under relation $E$: $P_0=\emptyset, \hspace{2mm} ...
-1
votes
2answers
39 views

Empty set Velleman's exercises

Doing an exercise from Velleman's 'How to prove it' I ended up thinking about exercise 2.3.8: Given that there are sets $ I=\{2,3\}, A_2=\{2,4\},A_3=\{3,6\},B_2=\{2,3\},B_3=\{3,4\}$. What is ...
1
vote
1answer
16 views

Ordered pairs and set -builder as function class

I'm trying to read "Set Theory" by Thomas Jech and i'm confused by statement in page 14 (1.14) It states: The separation Axioms follow from the Replacement Schema. (1) Given $\varphi$, let $F = ...
-4
votes
3answers
33 views

a question of mapping and set theory [closed]

A set $S$ is said to be infinite if there is a one-one correspondence between $S$ and any proper subset of $S$ prove The set of integers is infinite . The set of real number is infinite. If a set ...
1
vote
3answers
43 views

Order of evaluation in conditions in set theory

Halmos, in Naive Set Theory, on page 19, provides a definition of intersection restricted to subsets of $E$, where $C$ is the collection of the sets intersected. The point is to allow the case where ...
4
votes
1answer
69 views

Does Lowenheim-Skolem theorem depend on axiom of choice?

The proofs of Lowenheim-Skolem I have seen all depended on the use of choice functions. Is there any proof not dependent on axiom of choice? Or is Lowenheim-Skolem a result of axiom of choice?
6
votes
2answers
41 views

Sujection, finite set, $|X| \le n$? [closed]

Suppose that $\{1, 2, \dots, n\} \to X$ is a surjection. How do I show that $X$ is a finite set and that $|X| \le n$?
6
votes
1answer
62 views

Is it possible to choose $10$ distinct numbers from the set $\{0, 1, 2, . . . , 14\}$ so that various differences are all distinct?

From the 1991 Canada National Olympiad: Can ten distinct numbers $a_1, a_2, b_1, b_2, b_3, c_1, c_2, d_1, d_2, d_3$ be chosen from $\{0, 1, 2, \dotsc, 14\}$ so that the $14$ differences $$ ...
0
votes
2answers
40 views

What happens when we take a compliment in probability and why is sigma algebra needed?

When we take complement of a set, do we mean sigma algebra minus the set or only the sample space minus the set. Also why is sigma algebra needed in the axioms of probability ? For reference the ...
0
votes
1answer
24 views

Empty intersection in chain rule for probability [duplicate]

I am looking at the expansion of the chain rule for probability. $$ P\left(\bigcap_{k=1}^nA_k\right)=\prod_{k=1}^nP\left(A_k\middle|\bigcap_{j=1}^{k-1}A_j \right) $$ if ...
5
votes
1answer
48 views

Consider the 1000-element subsets

Consider all 1000-element subsets of the set $A = \{ 1, 2, 3, ... , 2015 \}$. From each such subset choose the least element. The arithmetic mean of all of these least elements is $\frac{p}{q}$, ...
0
votes
4answers
43 views

Proof of Natural set to any power k, is countably infinite [duplicate]

Show that $N^k = N × N × \cdots × N$ ($k$ factors) is countably infinite for every positive integer $k$. where $N$ is the set of natural numbers. I first approached this question by trying ...
1
vote
0answers
40 views

Defining a function over time in terms of a random variable that is undefined at a certain time

Let $X_n$ be a random variable taking on one of three values $a,b$ or $c$ over time. That is, for each $n \in \mathbb{N}$, we have $X_n \in \{a,b,c\}$. Also, for each $n \in \mathbb{N}$, let $F_n$ be ...
2
votes
2answers
38 views

Powerset of infinite set minus original set equivalent to the poweset

I had this idea which I am fairly certain is true but I am not quite certain nor how to go about proving it. Let $\alpha$ be a given infinite set of some cardinality, that is $card(\alpha)=a$ and let ...
1
vote
0answers
41 views

Subsets of emptyset

To follow up on an earlier question of mine and in order to improve understanding I would like to ask the following: What is the power set of $ \{\{\emptyset\}\} $? Is it $ \mathscr ...
1
vote
1answer
49 views

Subsets of the empty set

Having read Velleman's 'How to prove it' I came across a question I am not sure I can answer. He states that the power set of the empty set is equal to a set consisting only of the empty set: $ ...
3
votes
0answers
91 views

I need to show a union is countable (most of proof is done)

Let: $\mathscr{J}^\circ_{\text{rat}}(\mathbb{R}^n)=\{(a_1,b_1)\times(a_2,b_2)\times\cdots\times(a_n,b_n)\subseteq\mathbb{R}^n|\ \forall i\in\{1,\cdots,n\}\ [a_i,b_i\in\mathbb{Q}]\}$ With the ...
1
vote
1answer
38 views

Let $A,B$, and $C$ be sets. If $A\subseteq B$, $B\subseteq C$, and $C\subseteq A$, then $A=C$.

Here is my abstract maths problem. Let $A,B$, and $C$ be sets. If $A\subseteq B$, $B\subseteq C$, and $C\subseteq A$, then $A=C$. I am asked to either prove or disprove this statement. I am a little ...
0
votes
2answers
36 views

Set Theory: Transitive?

I have a question regarding Relations on Sets. Here is the problem: Let $S=\left\{ a, b, c\right\}$. Then $R=\left\{ (a,a), (a,b), (a,c)\right\}$. Which of the properties (reflexive, symmetric, or ...
1
vote
0answers
26 views

Is the concept of a Universal Set an example of Russell's paradox? [duplicate]

In my book on functional analysis it is defined that a Universal Set is the union of all sets. Is "union" used in the same sense as "set containing all sets"? In other words, is the "set of all ...
4
votes
2answers
111 views

Maths Puzzle: Partitioning a set into two disjoint sets

Le $X$ be the set of all non-empty subsets of $\{a,b,c,d,e,f\}$. So $X=\{a,b,c,d,e,f,ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef,abc,\cdots,abcdef\}$; i.e., $|X|=63$. We want to partition $X$ into ...
2
votes
2answers
39 views

Find a non injective function between a set of integers and itself

Say we have a set of integers: $ A = \left\{1,2,6,8\right\}$ is there any way to find a non-injective function that when fed any of the numbers in $A$ gives another number in $A$ (Basically a ...
0
votes
1answer
30 views

Given the size of $\mathscr{U}, A, B$, how many possible combinations of $A$ and $B$ such that $A\cap B \neq \varnothing$?

Given the $\mathscr{U} = n, |A| = c_1$, how many possible set $B$ with size $|B| = c_2$ are there, such that $A \cap B \neq \varnothing$.
3
votes
3answers
69 views

Can we have $x\in A$ and $x\in A\times B$?

Is it possible, for sets $A$ and $B$, to have $x\in A$ and $x\in A\times B$? It seems unlikely to me, but maybe some degenerate case? $x=\emptyset$?
2
votes
1answer
23 views

What characterizes the equivalence classes of the quotient ring, P(N)/Fin(N)?

Let P(N) be the powerset of the natural numbers. Let Fin(N) be the collection of all finite subsets of N. Then (P(N),symmetric difference, intersection) is a ring. I am taking my first course in ring ...
1
vote
1answer
40 views

onto mappings on itself

QUESTION. If $S$ is any set, prove that it is impossible to find a mapping of $S$ onto $S^{\ast}$. ( $S^{\ast}$ is the set of all subsets of $S$). MY PROOF: i ask my proof is right or wrong..... if ...
0
votes
4answers
64 views

Understanding the proof technique of $A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$.

I used to learn it in a different way; \begin{align} x\in A\cup (B\cap C)&\implies x\in A \textrm{ or } (x\in B \textrm{ and } x\in C)\tag{1}\\ &\implies (x\in A \textrm{ or } x\in B) ...
1
vote
1answer
27 views

Why are nonincreasing and nondecreasing sequences named this way?

When we say a sequence of sets is nondecreasing or nonincreasing, are we talking about the cardinality of the set? I understand that if $A_{n} \subset A_{n+1}\subset A_{n+2}$ then the sets get bigger ...
2
votes
2answers
28 views

Confused about one to one functions and cardinality

There is something that I'm not getting about functions and cardinality of sets. I've read the following: If $F$ is a one to one function, then $F^{-1}$ (the inverse) is also a one-to-one ...
2
votes
1answer
52 views

Easiest way to find the 'area of a Venn diagram,' given certain information.

We have a bunch of intersecting regions: $$X_1,\dots, X_n,$$ all with non-negative volume, and we know $V(X_i)$ and $V\left((\cup_{a\in A}X_a)\cap (\cup_{b\in B}X_b)\right)$ for any disjoint ...
0
votes
3answers
36 views

Set equality comparison of union

I was reading an introductory set theory book and came across the following question. Give an example where $A \cup B = A \cup C$, But $B \ne C$. I am lost. Any ideas?
-2
votes
1answer
55 views

Does $2$ belong to $\{1, \{2, \{3\}\}\}$?

$2$ belongs to $\{1,\{2,\{3\}\}\}$ State true or false. I don't know how to write all the subsets of this set and also to check if $2$ belongs to the given set. Please help.
1
vote
0answers
17 views

Measuring the difference in two sets of numbers

I have multiple sets of numbers considered prediction and then a final set called the result. I would like to have a measurement of the difference between each prediction and the result. Obviously, ...
1
vote
1answer
22 views

Terminology help for a set relation: for sets $X, Y$, not necessarily disjoint, such that neither is a subset of the other.

Is there an existing term for pairs of sets $X, Y$, not necessarily disjoint, such that neither $X \subseteq Y$ nor $Y \subseteq X$? Would it be incorrect (or misleading) to call them something like ...
5
votes
2answers
546 views

Olympiad question on Pigeonhole principle

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is ...
1
vote
1answer
498 views

Is this enough for a set to be countable?

Given set $\mathcal{P}$ of subsets of a countable set $X$. For each $A, B \in \mathcal{P}$ it is given that $A \subset B$ or $B \subset A$. Does it follow that $\mathcal{P}$ is countable itself?
1
vote
1answer
26 views

When will $A_1^c \Delta A_2^c = (A_1 \Delta A_2)^c$ holds?

I tried many cases but all failed. I thought because $$A_1 \Delta A_2 = A_1^c \Delta A_2^c,$$ so that the question is really asking $$A_1 \Delta A_2 = (A_1 \Delta A_2)^c.$$ Can I say it will never ...
0
votes
1answer
33 views

Using the well ordering principle to prove a certain property of an integer

The Well ordering principle states that A least element exists in every non empty set of positive integers Use the well Ordering principle to prove the following statement ' Any nonempty subset of ...
1
vote
1answer
37 views

How to prove generalized DeMorgan's Law? [duplicate]

How to prove generalized DeMorgan's Law that $$\neg(A_1 \land A_2 \land \cdots \land A_n) = \neg A_1 \lor \neg A_2 \lor \cdots \lor \neg A_n.$$ Or in the set theory language, $$\Bigg(\bigcap_{i\in ...
0
votes
0answers
27 views

Bijectivity of the Inverse of a Bijection

If $f:A\to B$ is a bijective mapping, is $f^{-1} : B\to A$ also bijective? Can you also give a detailed proof?
1
vote
1answer
31 views

Calculate the cardinal of $\{f:\Bbb{N}\to \mathcal{P}(\Bbb{N}):n \notin f(n)\}$

Calculate the cardinal of $A=\{f:\Bbb{N}\to \mathcal{P}(\Bbb{N}):n \notin f(n)\}$. Ok, so I'm having some trouble with this problem. I know that since $A\subset \{f:\Bbb{N}\to \mathcal{P}(\Bbb{N})\}$ ...
0
votes
0answers
38 views

How to compute and compute the follow questioners about () and []

Compute the intersection of all sets of the form $(0, b)$, for $b$ a positive real number Compute the union of all sets of the form $[a, 1]$, for $a$ a positive real number Really don't know how to ...