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

4
votes
1answer
29 views

Show that $(A\cup B)-(C \cup D) \subset (A-C)\cup (B-D)$

Proof of the mentioned proposition is required to construct the Lebesgue Measure in Rudin's Principles of Mathematical Analysis. As it is omitted in the textbook, I'm having some difficulty deducing ...
3
votes
0answers
25 views

Let $f(x)=\sqrt{x^2+3x+4}$ be a rational-valued function of the rational variable $x$. Find the domain and range.

Let $f(x)=\sqrt{x^2+3x+4}$ be a rational-valued function of the rational variable $x$. Then find the domain and range of the function. I tried to solve this problem but could not reach the answer. ...
-2
votes
4answers
44 views

Mathematical problem - Set theory

there is set A = {a,b,c,d,e,f}. Problem is: {d,b,f,a,e,c} ∈ A is it T or F and why? Thanks!
1
vote
1answer
44 views

How do you prove that this function is bijective?

How do you prove that this function is bijective? $f\colon (0,1)\longrightarrow \mathbb{R}$ $f(x)=\tan (\pi(x-1/2))$ In fact I want to show that $(0,1)$ is equivalent to $\mathbb{R}$ by proving that ...
2
votes
2answers
101 views

Other than $\setminus$ and $-$, are there any other notations for the set-theoretic difference of sets?

Let $X$ denote a set, and suppose that $B$ and $A$ are subsets thereof. Then the set-theoretic difference of $B$ and $A$ may be denoted in any of the following ways: $$B \setminus A, \qquad B - A, ...
0
votes
0answers
18 views

Preference Maximizing Choice Rule

Definition: A Choice Rule is a function $ C: \mathcal{P}(X) \to \mathcal{P}(X) $ such that $ C(B) \subset B, $ $\forall B \in \mathcal{P} (X) $ and $ C(B) \neq \emptyset $ if $ B \neq \emptyset $ The ...
0
votes
1answer
21 views

Showing that a set union is the smallest set

Show that $A\cup B$ is the smallest set containing both $A$ and $B$ in the sense that it is contained in every such set. I am not sure how to show that $A\cup B$ is the smallest set. It seems very ...
0
votes
1answer
19 views

Function of a set equals the set

The following is given: $x\in E \implies T(x)\in E$ and $x\in E \implies T^{-1}(x)\in E$ I'm having trouble showing that $T(E)\subset E$ or $E\subset T(E)$, let alone that $T(E)=E$. Here is my ...
3
votes
2answers
50 views

Bijection between $\Bigl\{1, 2, \dots, \frac{N(N+1)}{2}\Bigr\}$ and $\{ (i, j) \in \mathbb{N} : i \le j \le N\}$

Let $N$ be some positive integer and $A$ be the following set $\{ (i, j) \in \mathbb{N}^2 : 1 \le i \le j \le N\} = \{ (1, 1), (1, 2), \ldots, (1, N), (2, 2), (2, 3), \ldots, (2, N), \ldots, (N, N) ...
2
votes
2answers
55 views

There exists no injective function from the power set of A to A

It is not so hard to see that there doesn't exist a surjective function from a set $A$ to $\mathcal{P}(A)$, the power set of $A$. Namely, let us suppose there does exist such a function ...
-6
votes
0answers
21 views

write brief notes on set, types of set, operation of sets, mogan laws of sets, venn diagrams [on hold]

write brief notes on the following types of sets operation of sets Morgans laws of sets vein diagrams
2
votes
1answer
33 views

Halmos, Naive Set Theory, recursion theorem proof: why must he do it that way?

Summary: I understand the proof Halmos gives in his Naive Set Theory for the recursion theorem, but I don't understand why he has to do it that way. I give an alternative proof which may be flawed. If ...
0
votes
1answer
40 views

Simple set theory problem

List all the elements of the set: $\{1/n \mid n ∈ \{3, 4, 5, 6\}\}$ My understanding is that, first we must understand what n is. n is a set of its own, and its elements also are inside of {3, 4, 5, ...
0
votes
3answers
56 views

Prove: set of the polynomials of degree $n$ with coefficients in $\Bbb Q $ is countable

Let $P_n =\{p(x)=a_n x^n+ a_{n-1} x^{n-1}+...+ a_1 x+a_0 |a_i \in \Bbb Q \}$ the set of the polynomials of degree $n$ with coefficients in $\Bbb Q $ Prove that $P_n$ is countable and tell why $P= ...
1
vote
2answers
27 views

Prove the size of the result of a cartesian product is equal to the product of the size of the two sets.

We want to show: $$|S_1 \times S_2| = |S_1| \cdot |S_2|$$ I am not sure how to go about showing this in general terms. I believe that we will need to use the definition of the cartesian product ...
1
vote
0answers
32 views

Alternate proof of Cantor-Bernstein Theorem

Let $E$ and $F$ be two sets. If $f\colon E\longrightarrow F$, $g\colon F\longrightarrow E$ are two injections, prove that there exists a bijection $h\colon E\longrightarrow F$. My confusion lies ...
1
vote
3answers
28 views

Proving size of two finite sets is equal to the size of their union

I am struggling to understand how to prove the following for ALL numbers. ...
2
votes
1answer
28 views

How to complete this proof? Union of a countably infinite set and a finite set is countably infinite

Theorem. Let $X$ be a countably infinite set and $Y$ be a finite set. Then $X\cup Y$ is countably infinite. Proof. Since $X$ is a countably infinite set, then there exists a bijection function ...
5
votes
2answers
41 views

prove that if X is a countable set of lines in the plane then the union of all lines in X can't cover the plane

here's my try: Let $X$ be a countable set of lines in the plane. the cardinality of the set of all lines in the plane with a slope between $0$ and $2\pi$ is $\aleph$ so there must be some line in the ...
3
votes
3answers
385 views

can real line be written as a disjoint unions of set with cardinality 5

Can the real line be written as a disjoint union of sets with cardinality 5? I tried using to write it as a set of sets.. but I didn't end up to a good position.
7
votes
4answers
638 views

Does positive real numbers contain a least element?

Does positive real numbers contain a least element? If so, then why? Does every non empty subset of positive real numbers contain a least element? If so, why? If it is not, then why not? I should ...
0
votes
2answers
40 views

Proving relationship between set complement, intersection and union

Show that $S_1 \cup S_2 = \overline{\overline{S_1}\cap \overline{S_2}}$. So we want to show that the union of $S_1$ and $S_2$ is equal to the compliment of the intersection of the compliments of ...
3
votes
1answer
29 views

Can elements in a subset of the rational numbers be ordered from lowest to highest?

Suppose there is a set defined as [0,1]$ \cap \mathbb{Q}$ . I am wondering if it is conceptually possible to make an argument about ordering the numbers in this set in a sequence from lowest to ...
3
votes
3answers
34 views

Help with partitions, equivalence classes, equivalence relations.

The following definitions and results are from my textbook. A partition $\mathcal{P}$ of a set $X$ is a collection of nonempty sets $X_1, X_2, \dots$ such that $X_1 \cap X_j = \emptyset$ for $i ...
3
votes
4answers
42 views

Into how many equivalences classes does $R$ partition $\mathbb{Z}$?

Let $R= \{ (a,b) \in\mathbb{Z}\times\mathbb{Z} \mid a^2\equiv b^2 \bmod 7\}$. Into how many equivalences classes does $R$ partition $\mathbb{Z}$? My best guess is that there are $7$ equivalence ...
2
votes
4answers
79 views

Set Builder Notation for Prime Numbers

How can I express the set of primes using set builder notation. The less words, the better! I was thinking something along the lines of: $P = \{x_i \mid x_j \equiv x_k \pmod\alpha \Rightarrow x_k = ...
-1
votes
2answers
37 views

Basic set theory [on hold]

Consider these $3$ sets: $X = \{1,2,3\}$ $Y = \{\{1,2,3\}\}$ $Z = \{\{\{1,2,3\}\}\}$ Is it fair to say: $X$ is an element of $Y$ $Y$ is an element of $Z$ $X$ is NOT an element of $Z$?
-1
votes
1answer
24 views

If A is an infinite set, prove that |A| = |A\F| if F is finite

If A is an infinite set, prove that |A| = |A\F| if F is finite. Can I use a theorem? or must find a bijection between A and A\F? also I have to answer: What happen if F is countable? What happens if ...
0
votes
0answers
37 views

Does this set contain these numbers?

How would I go about proving whether or not every number $n=k^8$ is included in the set of all numbers $m=k^4$ ($n$ and $k$ are integers in both cases)?
0
votes
1answer
31 views

Suppose $f\colon X \rightarrow Y$. Prove that if $A \subset B\subset X$, then $f(A)\subset f(B)$.

I would like to verify that this is a correct, clear and concise solution. I am new to set theory. Problem: Suppose $f\colon X \rightarrow Y$. Prove that if $A\subset B\subset X$, then ...
1
vote
4answers
31 views

a problem on the algebra of sets

trying to prove that $A \cup ( A \cap B) = A $ for any set $A,B$. I am trying to use distributive law for sets, but keep coming to the same form. Is there a way to prove this ?
1
vote
2answers
77 views

What's the disjoint union?

I'm self-studying some analysis, and ran into the term 'disjoint union'. I googled it, and it seems that it's just a normal union of any sets, but where we pair each duplicate with an index ...
1
vote
0answers
19 views

Prove that if $|X|=\aleph _0$ then there exist a family of sets, $\mathcal{F}$, of subsets of $X$, s.t $|\mathcal{F}|=\aleph$ [duplicate]

Let $X$ be a set such that $|X|=\aleph _0$. I need to find a family of sets $\mathcal{F}$, of subsets of $X$ such that $|\mathcal{F}|=|\mathbb{R}|$. I saw a couple of examples of Specific X but I ...
6
votes
3answers
49 views

What phenomenon is this? $(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$

$(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$ Proof: $$ \begin{align*} 2\Bbb{Z} &= \bullet \circ \bullet \circ \bullet \circ \bullet \circ \dots \\ 3\Bbb{Z} &= \bullet \circ ...
-3
votes
1answer
28 views

prove that f is one-to-one if the sign ⊃ in f^(-1)(f(A))⊃A can be replaced by = for all A ⊂ X [on hold]

I have no clue as to how to go about this problem. I have the proof for $$f^{-1}(f(A)) ⊃ A $$ but i don't know where to go from here
1
vote
4answers
31 views

prove that$ A \backslash (B \backslash C) = (A\backslash B) \cup ( A \cap B \cap C)$ [on hold]

I drew the Venn's diagram and could visualize it, but I am having trouble proving it.
2
votes
2answers
29 views

I am issues with proving the following problem: $f^{-1}(f(A)) ⊃ A$ [duplicate]

I am unsure as to where to start with this problem. The way I read it is that $f^{-1}(f(A)) ⊃ A$ means that $A$ is a subset of the preimage of the image of $A$. But I am unsure.
-1
votes
2answers
40 views

Inclusion exclusion principle in set theory

Can some one help me as i am struck in how to prove inclusion exclusion principle in set theory without using Venn diagrams That is we have to prove: $|A \cup B \cup C|=|A|+|B|+|C|+|A \cap B \cap ...
0
votes
0answers
18 views

Explicit Description for an Equivalence Relation

Given a set function $f : X \to X$ let $\sim$ be the equivalence relation $x \sim f(x)$. Contextually, I am working with the coequalizer of $f$ and $1_X$. I want to have as much information about the ...
0
votes
3answers
29 views

“Either A and B is open, then A + B is open” (typo sense-making, Stein Shakarchi Real Analysis)

Please advise about the most reasonable way to read this statement. My interpretations are below. The authors do not define the set operation A + B; I assume A + B = $A \cup B$. Their statement ...
0
votes
2answers
15 views

Prove that the set of all periodic sequences (from some index) of natural numbers is countable

This exercise is from my course textbook and comes with a bunch of other exercises which practice the theorem that countable union of countable sets is countable. So I started by notating for every ...
6
votes
6answers
182 views

How is $\mathbb N$ actually defined?

I know perfectly well the Peano axioms, but if they were sufficient for defining $\mathbb N$, there would be no controversy whether $0$ is a member of $\mathbb N$ or not because $\mathbb N$ is ...
-1
votes
1answer
39 views

Reposting Question about Schroder-Bernstein

Assume there exists a $1$-$1$ function $f:X\to Y$ and another $1$-$1$ function $g:Y\to X$. Follow the steps to show that there exists a $1$-$1$, onto function $h:X\to Y$ and hence $X\sim Y$. a) The ...
0
votes
1answer
13 views

Product of countably many 1-dimensional spaces does not have cardinality $\aleph_0$

From Bergman's "Universal Algebra: Fundamentals and Selected Topics" page 52, constructing a directly indecomposable algebra (one which does not admit a decomposition into directly indecomposable ...
13
votes
5answers
2k views

How is an empty set truly “empty”?

In a related question, an answerer says: an empty bag is a bag with nothing inside it. Makes sense, but I'm reading a textbook right now that says: The empty set has only one subset (namely, ...
1
vote
1answer
24 views

Set theory: Symmetric Difference properties.

I would like to know if my procedure was correct in proving the next property ($\oplus \equiv$ symmetric difference): $$(A_1\cup A_2)\oplus (B_1\cup B_2)\subset (A_1\oplus B_1)\cup (A_2\oplus ...
3
votes
1answer
41 views

How can you prove the equivalance relation for the following model?

Given two Kripke-frames $M=(W,R)$ and $U=(E,S)$ where $W,E$ are 'possible worlds' and $R,S$ are equivalence relations on $W,E$ respectively. we define $M\otimes U = (W',R')$ as follows: $W'=\{\ ...
0
votes
1answer
49 views

Show equivalence using venn diagram, subset argument, membership table

Show that A \ (B ∩ C) = (A \ B) U (A \ C) Using: a) Venn diagram b) Subset argument c) Membership table I can do the venn diagram, you just draw the shapes and show that the end shape for both ...
0
votes
2answers
40 views

Express as a set

Let the universal set $U$ be the set of all people, let $M$ bet the set of all males, let $C$ be the set of all children, let $H$ be the set of all dutch people. Express as sets: a) boys b) girls ...
4
votes
2answers
114 views

Show that f is surjective

So im having a little trouble proving this. Can anyone help me out? Let $A$, $B \subseteq E$. Moreover, let $$f: \mathscr{P}(E) \to \mathscr{P}(A) \times \mathscr{P}(B)$$ be defined by $$f: X ...