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
votes
2answers
84 views

The range of the function $f(x,y)=(x+y,xy)$

I have the following homework question: $$\begin{split} f: \mathbb I \times \mathbb I &\to \mathbb R\times \mathbb R\\ f(x, y) &=(x+y, xy)\end{split}$$ Does there exist $(x, y) \in \mathbb ...
-1
votes
2answers
39 views

Set Theory Proof $A=B$ [closed]

Let $A$ be the set of all integers $x$ such that $x = 2k$ for some integer $k$ Let $B$ be the set of all integers $x$ such that $x = 2k+2$ for some integer $k$ Give a formal proof that $A = B$.
3
votes
1answer
35 views

Size of Totally Ordered Set with Countable Predecessors

Assume Choice. Let $S$ be a set, and $\trianglelefteq$ be a total order on $S$. If for all $s \in S$, the set $\{t:t\trianglelefteq s\}$ is countable, what are the possible cardinalities of $S$? ...
0
votes
2answers
55 views

How do I write this set notation correctly?

I have a 2D matrix $f(m,n)$, where $1<m<M$ and $1<n<N$. The element at location $(m,n)$ is denoted as $f_{m,n}\in \{+1,-1\}$. I want to write something like set notation but I am not ...
0
votes
0answers
24 views

Prove/Disprove existence of a set [duplicate]

I would like to know if my arguments are correct. Prove/Disprove existence of a set X $\subset$ P($\mathbb{N}$) , $ |X|=\aleph$ and for every $ A,B \in X $ ,$ A \subset B $ or $ B \subset A$ I ...
1
vote
1answer
27 views

Let $R$ be an equivalence relation: How many elements are in $R$?

Let $R\subset X\times X, |X|=30$. Supposing there are only 3 distinct equivalence classes and all of these have the same amount of elements, find $|R|$. I didn't get very far on this, I thought that ...
1
vote
4answers
212 views

$\{∅\} ∈ \{∅\}$ is this right or wrong?

I am very confused about whether $\{∅\} ∈ \{∅\}$ or not. I thought it's right because in curly brackets the phy is also a member. Can anyone help me understand this?
2
votes
1answer
34 views

Manipulating sets ($+$, etc).

I was seeing a proof of the Open Mapping Theorem, in Kreyszig's book, and I have no problems with it. But there's a point in which he does something like: $$\begin{align}B_Y(0,r) \subset ...
1
vote
2answers
34 views

Comparison of two collections of 4-tuples using combinatorics - more complicated version

My problem is to show that 2 collections of unordered 4-tuples - $\mathbf{A}$ and $\mathbf{B}$ - are the same. I define a collection of objects as a set, in which multiple entries of the same object ...
6
votes
2answers
222 views

Showing a function is invertible

I came across this problem and not sure how to prove it. Show that if $ f\circ f \circ g\circ g \circ f\circ f $ is invertible then $ g $ is invertible. I'm not sure if it's correct to say that ...
1
vote
3answers
62 views

Why is the probability multiplied by $\binom{n}{k}$

A while ago I asked a question about probability here Why is binomial probability used here? I get that you can find how many ways of choosing the $6$ correct out of $10$ questions. But why do we ...
0
votes
2answers
41 views

Union of disjoint countable sets is countable [duplicate]

Suppose that $S_1$ , $S_2$ are disjoint countable sets of T .Then their union is countable ATTEMPT Let $S_1$ = ${x_1 ,x_2,...}$ $S_2$ = ${y_1,y_2,...}$ I am thinking of making pairs by doing ...
1
vote
1answer
23 views

Does all collection of sets have an index-set?

I have this form of the axiom of choice: Suppose that C is a collection of nonempty sets. Then thre exists a function $f:C\rightarrow \cup_{A\in C}A$ such that $f(A)\in A$ for each $A \in C$. ...
3
votes
5answers
138 views

Why can a closed, bounded interval be uncountable?

From what I have read, all finite sets are countable but not all countable sets are finite. As I understand it, Countably Finite --- a one to one map onto $\Bbb{N}$ with a limited number of members ...
2
votes
2answers
98 views

Can I soundly define a function which maps to itself?

A function can be defined by specifying a set of tuples. If I write the definition of a function $f = \lbrace(0, f) \rbrace$, is this function sound? Will this lead to a paradox? The domain of this ...
0
votes
1answer
39 views

Algebraic numbers as roots of polynomials of degree $n$ are countable.

For fixed $n \in \mathbb{N}$, let $A_n$ be he set of all algebraic numbers obtained as roots of polynomials with integer coefficients that have degree $n$. Proof that $A_n$ is countable. (Hint: For ...
3
votes
1answer
47 views

Set Notation with exponent

I am looking at the function: $$f: \{5\}^2 \to \{5\}$$ it is certainly nothing too exceptional , but I find it difficult to understand what $\{5\}^2$ as a set notation and from then the whole ...
15
votes
4answers
1k views

Are there more transcendental numbers or irrational numbers that are not transcendental?

This is not a question of counting (obviously), but more of a question of bigger vs. smaller infinities. I really don't know where to even start with this one whatsoever. Any help? Or is it ...
3
votes
1answer
52 views

Order for sets in the real line

Consider the sets $[0,1]$ and $[1,2]$. I want to say that $[1,2]$ is greater than $[0,1]$. Is there a set order such that $$A \geq B \quad \text{if} \quad \inf A \geq \sup B.$$ What is the name of ...
1
vote
0answers
45 views

Explicit bijection $\Bbb R^{\Bbb R} \to P(\Bbb R) $. [duplicate]

Is there any simple way to construct a bijective function: $\Bbb R^{\Bbb R} \to P(\Bbb R) $ to see that $\Bbb R^{\Bbb R}$ is isomorphic to $P(\Bbb R)$?
1
vote
2answers
78 views

Set theory formula

I picked up a copy of Jech's Set Theory at my school library and I'm reading through it and taking notes. Right at the beginning, though, he mentions something called a 'formula'. Here's the quote: ...
3
votes
5answers
103 views

What is a set of bijections?

I am taking a course on abstract algebra, and the lector defined $T$ to be a set, and defined $G$ to be the set of all bijections from $T$ to itself: $$ G=\{\text{all bijections }g\colon T\rightarrow ...
0
votes
3answers
37 views

Given two specific sets, show that one is a subset of another

Given $$X = \{x : x = 4^n-3n-1 ; n\in\mathbb{N}\}$$ and $$Y = \{y : y = 9(n-1); n\in\mathbb{N}\}$$ Prove that $X \subset Y$. I've been struggling with this problem for hours but I couldn't find a ...
0
votes
2answers
41 views

Comparison of two sets of 4-tuples using combinatorics

My problem is to show that $\mathbf{A} = \mathbf{B}$. Specifically that $\forall a \in \mathbf{A} \implies a \in \mathbf{B}$ and $\forall b \in \mathbf{B} \implies b \in \mathbf{A}$, to be precise. ...
0
votes
2answers
86 views

Set Theory (Definition of a set)

A set is defined as the collection of well-defined and distinct objects. This implies that a member of a set can't be repetitive in the set. Now when we discuss groups in Group Theory, if we check the ...
0
votes
1answer
22 views

$R$ well-founded relation and $\forall y$, $\{x:xRy\}$ is finite implies $\forall y$, $\{x:xR^t y\}$ is finite (where $R^t$ is the transitive closure)

I am interested in proving the titular claim: $R$ well-founded relation and $\forall y$, $\{x:xRy\}$ is finite implies $\forall y$, $\{x:xR^t y\}$ is finite (where $R^t$ is the transitive closure) ...
3
votes
1answer
59 views

Does the Russell Set exist?

I am currently reading "Naive set Theory" by Paul Halmos. In the second chapter, on the axiom of specification we show that the Universal Set does not exist. The proof is the following: Lets ...
2
votes
2answers
47 views

What's the meaning of an element that belongs to the same element?

In classical set theory, if I consider that $x$ is an element, which means it is not a set, can I write $x \in x$ ? If yes, what this would mean? Correct me if I am wrong, but I don't need to have ...
0
votes
1answer
25 views

venn diagram and overlapping set equation

Q) Of the 24 dogs attending puppy school -six are small -twelve are brown -fifteen have long hair -one is small and brown and has long hair -two are small and brown but their hair is not long ...
1
vote
1answer
23 views

Proving statement about power sets using fact that Z = X ∩ Y

The statement I'm trying to prove is If Z = X ∩ Y , then P(Z) = P(X) ∩ P(Y). My proof is as follows: Let $U\in P(Z)$ so $U\subset Z$ and since Z = X ∩ Y, then $U\subset (X\cap Y)$. Hence ...
1
vote
2answers
36 views

If $A$ is a set and $\mathcal B$ is a set of sets, is there some shorthand for $\left\{A\times B:B\in\mathcal B\right\}$?

Let $A$ be a set and $\mathcal B$ be a set of sets. Suppose we want to define $$M:=\left\{A\times B:B\in\mathcal B\right\}\;.$$ Is there some shorthand for $M$ as we've got for $$X\times ...
0
votes
1answer
32 views

Have I actually shown that $X\subset Y$?

So I'm trying to show that $$If\ X\cup Y = Y\ then\ X \subset Y$$ I've had a go at a proof but I'm not sure if it actually proves the above at all: $$Let\ x\in Y$$ $$x\in (X\cup Y)$$ $$x\in X\ or\ ...
0
votes
0answers
33 views

$ \# \mathbb{R}^2 \geq \# \mathbb{R}$? [duplicate]

Well, I'm undergraduate in Math and was thinking about the following question: the cardinality of $\mathbb{R}^2$ is greater or equal to the cardinality of $\mathbb{R}$ (I believe it is not "less then" ...
3
votes
0answers
60 views

Proof check:$ \left | \mathbb{R} \right |= 2^{\left|\mathbb{N} \right |}$

This is my first time to post here. Sorry if this post is too simple or naive. Here I would like to prove that $\left | \mathbb{R} \right |= 2^{\left |\mathbb{N} \right |}$ I would first ...
4
votes
2answers
37 views

Number of ways to select subsets

In how many ways can two distinct subsets of the set $\text{A}$ of $k$ $(k \geq 3)$ elements be selected so that they have exactly two common elements? I started by choosing two elements (that ...
9
votes
1answer
58 views

If a set $S$ has a choice function, does $\bigcup S$ have one too?

I have an exercise in a book that asserts that if a set $S$ has a choice function on it, then so does the union of all its elements $\bigcup S$ (without assuming the axiom of choice). I, however, have ...
0
votes
1answer
64 views

Powerset with constraints

I have two sets $NUMBERS$ and $LETTERS$ with: $ NUMBERS = \{1, 2, 3, 4, 5\} \\ LETTERS = \{ A, B, C, D, E\}$ No I want the power-set of my sets, i.e. the set of subsets of elements from both ...
2
votes
2answers
43 views

If $n < \aleph^*(m)$, then $n < 2^m$.

Without $AC$ Let $\aleph^*(m)$ be the least aleph that $\not\leq^* m$. I need a help or hint that if $n < \aleph^*(m)$, then $n < 2^m$. $a \leq^* b$ means we can define a surjective map from ...
7
votes
4answers
84 views

Showing a function $f: \mathbb{N} \times\mathbb{N} \to \mathbb{N}$ is injective

Let $f: \mathbb{N} \times\mathbb{N} \to \mathbb{N}$ with $$ f(i,j) = \frac{(i+j-2)(i+j-1)}{2}+j. $$ I want to show $f$ is an injection. This is how I approached the problem: I tried to show ...
5
votes
7answers
380 views

Properties that are true for finite sets but are (non-trivially) false for infinite sets

The finite analogue of the axiom of choice is true, and it seems highly intuitive that it would be true for the infinite case. It is, however, undecidable. When explaining this to myself or to others, ...
1
vote
1answer
30 views

Hilbert's hotel prime powers method

To fit an infinite number of coaches each with an infinite number of passengers, we can assign the people in the hotel with the prime number 2, and coach $c$ is assigned with the $c$th odd prime ...
1
vote
0answers
34 views

Disjoint set sum problem.

Let us have a set, denoted by $T$, and assign each element a position starting from zero, for e.g. in the set $T=\{1,2,3,4\}$, the positions are $T[0]=1,T[1]=2,T[2]=3,T[3]=4$. Also let's denote total ...
5
votes
2answers
120 views

Determine the number of subsets

How many distinct subsets of a set $\text{A}$ are there, containing at least $9$ elements, where the total number of elements in set $\text{A}$ is $18$ ? I've solved it by making cases of either ...
3
votes
4answers
54 views

What does $f^{-1}(B)= \{ x \in X \mid f(x) \in B\}$ mean?

I have encountered the expression $$f^{-1}(B) = \{ x \in X \mid f(x) \in B\}$$ My questions are: 1) What does the $-1$ exponent mean in this context? 2) Is it right to say "if the set $X$ ...
4
votes
2answers
37 views

Prove that $f(X\cap f^{-1}(Y))=f(X)\cap Y$

Let $\ f\colon A\to B$ and let $X\subset A$, $Y\subset B$, prove that $$f(X\cap f^{-1}(Y))=f(X)\cap Y$$ The "$\subset$"$-$inclusion is easy: if $y\in f(X\cap f^{-1}(Y))$, exists a $x\in X\cap ...
2
votes
2answers
69 views

What is the actual definition of a function?

I am learning precalculus and my book defines the following: A function $f$ from a set $A$ to a set $B$ is a rule that assigns to every element $a$ in $A$ one and only one value in $B$. Well, I ...
1
vote
1answer
53 views

formal definition of ordinal addition by recursion

I'm reading Kunen's Set Theory, An Introduction to Independence Proofs (1980). On page 26 he explains how to introduce ordinal addition through recursion. For the sake of convenience i'll give the ...
1
vote
1answer
72 views

Pronuntiation of the symbol $\varnothing$ of the empty set

The symbol $\varnothing$ for the empty set was introduced by Bourbaki, inspired by the Norwegian alphabet $\varnothing.$ It has no relation with the Greek letter $\phi.$ From my schooldays, when the ...
4
votes
5answers
65 views

Explanation of $\overline{\lim} A_n$ and $\underline{\lim}A_n$

Let $(A_n)_n$ be a countable family of subsets of a set $X$. We define: $$\lim \inf A_n = \underline{\lim} A_n = \bigcup_{n \in \mathbb N} \bigcap_{k \ge n} A_k$$ $$\lim \sup A_n = \overline{\lim} ...
3
votes
3answers
65 views

Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice)

I am interested in proving the titular claim: Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice) My approach: Let $R$ be a well-founded relation. We ...