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, (un)...

learn more… | top users | synonyms

0
votes
0answers
32 views

Question about identities and bijective functions

Let $S$ and $T$ be sets and let $f : S \to T$ be a function. Prove the following: If $g,h:T \rightarrow S$ are functions satisfying $g \circ f =Id_S$ and $f \circ h=Id_T$ then $f$ is bijective ...
1
vote
2answers
23 views

Question about surjective functions

Let $S$ and $T$ be sets and let $f : S \to T$ be a function. Prove the following: If $R$ is a set and $h:R \rightarrow S$ is a function such that $f \circ h$ is surjetive then also $f$ is ...
1
vote
1answer
54 views

If A is finite, then P(A) is finite.

I am solving the following exercise from Munkres. I was able to prove part (a) by the use of indicator function I proved that $\phi : P(A) \rightarrow X^n$, where $\phi(B) = I_B$. Here $I_B$ is the ...
2
votes
3answers
54 views

$A \Delta C = B \Delta C$, then prove that $A = B$ where $\Delta$ is a symmetric difference operation.

I suppose that if I can prove that every element that belongs to set $A$ also belongs to set $B$ and vice versa and also any element that doesn't belong to set $A$ doesn't belong to set $B$ either and ...
0
votes
1answer
18 views

(1) let ans = empty (2) for i from 1 to n do: $ans = A \cap ( ans \cup B_i )$ How to prove that $A \cap (\cup B_i) = ans$?

I have a problem on set theory. My problem is: (1) let $ans_0 = empty$ (2) for i from 1 to n do: $ans_i = A \cap ( ans_{i-1} \cup B_i )$ How to prove that $A \cap (\cup B_i) = ans_n$ ?
8
votes
3answers
732 views

Is a data set really a set?

Originally I thought that in statistics, a data set is just a set of real numbers, and that was it. But in the case of a set, there can only be one instance of any given entry, e.g. in set theory $$\...
0
votes
1answer
46 views

Understanding direct proofs and proofs by cases?

I'm reviewing my book Mathematical Proofs a Transition to Advanced Mathematics and looking to understand things at a deeper level. I will try to explain what I've considered so far in regards to this ...
0
votes
1answer
37 views

Proving an idempotent binary operation where $(x\ast y)\ast z=(y\ast z)\ast x$ is commutative

Let $S$ be a set and $\ast$ be a binary operation on $S$ satisfying 1) $x\ast x=x$ for all $x\in S$, 2) $(x\ast y)\ast z=(y\ast z)\ast x$ for all $x,y,z \in S$. Show that $x\ast y=y\ast x$. I ...
0
votes
0answers
13 views

Axioms for a Heyting Algebra as a Set System (Partial Order Lattice Under Inclusion)

According to the corresponding section in Wikipedia: An element $x$ of a Heyting algebra $H$ is called regular iff $x = \neg y$ for some $y \in H$. Elements $x$ and $y$ of a Heyting algebra ...
0
votes
2answers
20 views

set theoretic equation to evaluate a function

In axiomatic set theory a function $F$ is defined to be a class/set all of whose members are ordered pairs. Given a function $F$ there are set theoretic equations involving union, intersection and ...
1
vote
2answers
30 views

Well ordering of the subsets of a given set

For a given set, does there always exists a well-ordering of the set of all its subsets which is stronger than the usual ordering (that is set-theoretic inclusion) of the sets of the subsets of the ...
0
votes
1answer
56 views

Russel's paradox: what is the contradiction with $R \not\in R$?

Let the Russel's Set be: $$R = \{S | S \notin S\}$$ Where $S$ is a set Suppose $R \in R$, but by definition $R \not\in R$, contradiction. Suppose $R \not\in R$... (I am not sure what should be the ...
-3
votes
3answers
46 views

Proving that if $A\subseteq B$ and $B\subseteq C$ then $A\subseteq C$. [on hold]

. If $A\subseteq B$ and $B\subseteq C$ Prove that $$A\subseteq C$$
1
vote
2answers
24 views

Number of true relations of the form $A\subseteq B$ where $A,B\in\mathcal{P}(\{1,2,\ldots,n\})$

I just started "Introduction to Topology and Modern Analysis" by G.F. Simmons and came across this problem in the exercises. Q. Let $U=\{1,2,\ldots,n\}$ for an arbitrary positive integer $n$. If $...
-1
votes
1answer
42 views

Is $R=\{(a,b)\in \Bbb N\times \Bbb N\,:\,(a - b)$ is an odd number $ \}$ an equivalence relation?

$R \subset \Bbb N \times \Bbb N$ Is this an equivalence relation? $R=\{(a,b)\in \Bbb N\times \Bbb N\,:\,(a - b)$ is an odd number $ \}$ I say it is not because $(a, a)$ is always $0$ which is ...
1
vote
0answers
53 views

please explain the cartesian product.

What does the Cartesian product really mean. It is said that the Cartesian product of two sets $A$ and $B$ means the set of all ordered pairs $(a,b)$, where $a\in A$ and $b \in B$. But what is the use ...
0
votes
2answers
46 views

How to prove that $A-(B\cap C)=(A-B)\cup (A-C)$ [duplicate]

Prove that $A-(B\cap C)=(A-B)\cup (A-C)$. I have tried to prove it but I can't get precious proof. I am grateful if anyone give correct proof.
2
votes
0answers
37 views

What operations on infinite sets are allowed? [on hold]

I'm trying to solve one puzzle, which deals with infinite set, so I wonder what operations on infinite sets are allowed in mathematics and what operations have no sense? Let me explain my problem in ...
0
votes
2answers
29 views

If $f:A\to P(A)$, show that $Z_f := \{x \in A | x \notin f(x)\}$ is not in the Image of $f$

How can I prove that for a function $f: A \to P(A)$, $Z_f := \{x \in A | x \notin f(x)\}$ is not in the Image of f? It can be shown using Russel's Paradox, but i have really no clue on how to start. ...
0
votes
0answers
15 views

Intersection of converse well-founded quasiorders

Let $\mathcal{O}$ be a family of reflexive transitive relations on a set $A$, such that, for each $\preceq\in\mathcal{O}$ and each non-empty subset $B$ of $A$, the set $ \{ b\in B \mid \forall b'\in B ...
1
vote
2answers
31 views

Notation for binomial coefficient set

I've been searching for a way to express "the set of all combinations generated by taking $\binom{n}{k}$ items". For example, if I have the set $\{3,7,6,5,9\}$, and I want the set of all sets that ...
0
votes
2answers
25 views

Proving set theory subsets using element argument

How do you even prove a set theory subset statement using element argument? I simply just can't find any relevance to the question with the notes i was studying. Any guidance would be much ...
1
vote
2answers
34 views

Simplifying $(A \cup E) \cup E$.

For example $$(A^c\cap B^c)^c\cup E$$ First of all, De Morgan is definitely a must to simply this to $$\big((A^c)^c\cup(E^c)^c\big)\cup E$$ Then double negation to remove the double complement to ...
-1
votes
1answer
23 views

A question in set theory about intersection of two groups.

I've reached the answer, that Cn = to all prime numbers, but i really didnt know how to put it on paper and how to prove its right. I would thank your help.(question below) Question
1
vote
1answer
33 views

Difference between set theory proof and logic proof of complete induction

Set theory proof: Let $\mathbf{A}$ be the set such that $\{0,1,2,...,n\} \subset \mathbf{A} \implies n+1 \in \mathbf{A}$. Our goal is to show that $\mathbf{A} = \mathbb{N}$. To do this, we construct ...
5
votes
1answer
34 views

Intuitive reconciliation between Dedekind cuts and uncountable irrationals

I've looked around, haven't found a good explanation of this one. Basically, I'm looking for the simplest route to get from these starting points: The set of all rational numbers is countably ...
1
vote
1answer
47 views

Look for a one-to-one function that maps a square to R

I am looking for a one-to-one function which maps (0,1)^2 to R. It is preferable that the function doesn't involve trig functions. I have tried several mappings like $\ln(\frac{x_2}{1-x_1}),$ but they ...
0
votes
1answer
17 views

Correctness of a proof by induction of number of bijective functions between finite sets

My very first post. Checked this site and MathOverflow for answer but did not find. Statement: If A and B are finite sets with |A| = |B| = n , then there are n! bijective functions from A to B. A ...
0
votes
2answers
44 views

Proof on surjective functions

I have this assignment: given a function $f:A\longrightarrow B$ between two sets $A,B$ prove that $f$ is surjective if and only if there exists a function $\psi:B\longrightarrow A$ such that $f\circ\...
0
votes
1answer
20 views

Show that $\bigcap_{\alpha} A_{\alpha}\times \bigcap_{\beta} B_{\beta}=\bigcap_{(\alpha,\beta)} A_{\alpha}\times B_{\beta}$

Show that $\bigcap_{\alpha} A_{\alpha}\times \bigcap_{\beta} B_{\beta}=\bigcap_{(\alpha,\beta)} A_{\alpha}\times B_{\beta}$ Surely this question is a duplicate but I dont know how to search these ...
1
vote
2answers
47 views

Number of equivalence classes based on a relation regarding a non-principal ultrafilter

We have an equivalence relation on $\mathbb{N}^\mathbb{N}$ given by $$f\equiv g \iff \{n\in\mathbb{N}: f(n)=g(n)\}\in\mathbb{U},$$ where $\mathbb{U}$ is a non-principal ultrafilter on $\mathbb{N}$. ...
1
vote
4answers
71 views

what does “a set of sets that are not members of themselves” of Russell’s Paradox mean

Russell’s Paradox begins with a statement of "Let $R$ be the set of sets that are not members of themselves", i.e. $R=\{S\mid S\notin S\}$. I'm a little bit confused with the statement, for example, ...
0
votes
1answer
26 views

$S$ be $\pi$-system on a set, given two measures on $\sigma(S)$, is there a topology on $\sigma(S)$ making $S$ dense, and the two measures continuous?

Let $\Omega$ be a non-empty set , $S \subseteq \mathcal P(\Omega)$ be a Pi system (https://en.wikipedia.org/wiki/Pi_system ) on $\Omega$ , let $\sigma(S)$ be the $\sigma$-algebra generated by $S$ (i.e....
0
votes
2answers
25 views

How do I find the powerset of $A\cap B$?

$A = \{0,1\}$ $B = \{1,2\}$ My Working : $P(A\cap B)= P(\{\varnothing, \{1\}\}) = \{\varnothing,\{1\},\{\varnothing,\{1\}\}\}$ But the correct answer is $P(A\cap B)= \{\varnothing , \{1\}\}$.
0
votes
2answers
25 views

Finding an example of a bijection from $\Bbb N$ to $E^+$.

Give an example of a bijection $h$ from $\Bbb N$ to $E^+$ such that $h(1) = 16, h(2) =12, \text{ and } h(3) = 2. $ $\Bbb N = \text{ natural numbers }$ , $E^+= \text{ positive even integers. }$ So ...
2
votes
1answer
86 views

Without AC is there a relationship between $\beth$ and $\aleph$ numbers?

Assuming AC we know that all $\beth_\alpha$'s will be $\aleph_\beta$ for some $\beta$ since they can be well ordered. Can anything interesting be said about their relationship without AC? Is it ...
8
votes
2answers
690 views

Is the set of aleph numbers countable?

If I write the set of aleph numbers in this way $\{\aleph_0, \aleph_1, \aleph_2, \aleph_3, \dots\}$ it seems obvious to me that this set is countable, because aleph numbers have integer coefficients. ...
1
vote
0answers
31 views

P(P(N)) is equinumerous to the set of real functions

I need to show that (the power set of power set of N) P(P(N)) is equinumerous to the set of real functions. I know that P(N) is equinumerous to R, thus it is equivalent to show that $\{0,1\}^R $ is ...
0
votes
4answers
38 views

Let $R$ be a relation on a set $A$. Show that if $R \circ R \subseteq R$, then $R$ is transitive

On a recent quiz I encountered the problem: Let $R$ be a relation on a set $A$. Show that if $R \circ R \subseteq R$, then $R$ is transitive. I gave the following answer: Assuming $R$ is a relation ...
-1
votes
2answers
27 views

Question on finite subfamilies of an infinite family of sets

Let $A$ be an infinite set, $B\subseteq A$ and $a\in B$. Let $X\subseteq \mathcal{P}(A)$ be an infinite family of subsets of $A$ such that $a\in \bigcap X$. Suppose $\bigcap X\subseteq B$. Is it ...
0
votes
1answer
15 views

Question about distributive laws for indexed families of sets

Let $X=\{ A_i \}_{i \in I} \cup \{ B_j \}_{j \in J} \cup \{ C_k \}_{k \in K}$ Is it the case that $\bigcap X = \bigcap \{ A_i \}_{i \in I} \cup \bigcap \{ B_j \}_{j \in J} \cup \bigcap \{ C_k \}_{k \...
2
votes
2answers
166 views

Two well orders on an uncountable set

We have two well orders $\preceq_1, \preceq_2$ on an uncountable set $X$. Why would there be a set $Y\subseteq X$ such that $Y\restriction_{\preceq_1} = Y\restriction_{\preceq_2}$ and Y is ...
0
votes
0answers
13 views

proof of preimage of union and intersection of sets

I was learning to proof the following proposition "the inverse image of an intersection or union equals the intersection or union of the inverse image" following these two really good youtube videos: ...
1
vote
1answer
28 views

Proof about Finite set (Surjectivity and Injectivity)

Let $B$ be a non-empty set. Then the following are equivalent: (1) $B$ is finite. (2) There is a surjective funtion $f:\{1,...,n\}\rightarrow B$ for some $n\in \mathbb{N}$ (3) There is an injective ...
0
votes
0answers
21 views

Given S={0,1,2,3,4,5}, find the partition induced by the equivalence relation R where…

Given S={0,1,2,3,4,5}, find the partition induced by the equivalence relation R where R={(0,0),(0,4),(1,1),(1,3),(4,5),(0,5),(5,4),(5,0),(5,5),(2,2),(3,1),(3,3),(4,0),(4,4)}. Hey guys, after reading ...
0
votes
1answer
30 views

Mapping finite discrete numbers to the infinite set

This is an extension of my earlier question: Mapping discrete numbers Given that we can "map" $\mathbb{N}$ to $\mathbb{Z}$ via a bijection, I then wondered if it is possible to map a small subset of $\...
0
votes
1answer
22 views

Proving transitivity of a relation

Let R be a reflexive relation on a nonempty set X. The asymmetric part of R is defined as the relation $P_r$ on X as $xP_ry$ iff $xRy$ but not $yRx$. The relation $I_r$ = $R\setminus P_r$ on X is ...
9
votes
2answers
829 views

How Can You Define Successors Over The reals?

I've been going through Introduction To Modern Set Theory by Judith Roitman, and am confused by her exposition of well orderings. She gives the following proof that every element $x$ of a well-ordered ...
-1
votes
0answers
66 views

Topology: What does sets in $\bigcup_{i \in \mathbb{N}} A_i$ look like?

Let $\tau$ be the topology on some set $Y$, and $f_i: X \to Y$ be some continuous function. Let $A_i = \{f^{-1}_i(U)| U \in \tau\}$ and $A = \bigcup\limits_{i \in \mathbb{N}} A_i$ My question is ...
1
vote
2answers
52 views

How do I prove that for any finite subsets A and B exists one set R?

How do I prove that for any finite subsets A and B exists one set R $\left | A\cup B \right |=\left | A \right |+\left | B \right | -\left | A\cap B \right |$ Deduce from this an adequate formula ...