Questions tagged [elementary-set-theory]

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, differences and complements, De Morgan's laws, Venn diagrams, relations and functions, countability and uncountability, etc. More advanced topics should use (set-theory) instead.

Filter by
Sorted by
Tagged with
0
votes
3answers
47 views

How to prove that an irrational number to an irrational number could be irrational.

There exists $a,b \in \mathbb{R}-\mathbb{Q}$ such that $a^b \in \mathbb{R}-\mathbb{Q}$. I am lost as to where to begin. In my class, the only irrational numbers we've really covered is $\sqrt{2}$ and ...
0
votes
1answer
19 views

Well-ordered sets two examples

Say I have the following two sets: $\mathbb{R} \cup \{ 0\}$ under < (less than operator) $\{(a,b) | a,b \in \mathbb{Z^+} \}$ under $(a,b) \prec (c,d) \iff (a<c) \land (b <d)$. For $\mathbb{...
-2
votes
1answer
26 views

If A ∩ B is an infinite set, then A is an infinite

If A ∩ B is an infinite set, then A is an infinite how you prove that sentence is right?
-1
votes
1answer
33 views

What is the cardinality of the set of all matrices

Let $S$ be the set of all matrices whose components are complex numbers.(including infinite matrices) Then what is $Cardinality(S)$? The problem is that I don't really know much about advance ...
2
votes
1answer
24 views

Constructing injections between sets proof

$\DeclareMathOperator{\card}{card}$ Show that $\card(\mathbb{R}) = \card(\mathbb{R} \setminus \mathbb{Q})$. My attempt: We have to find two injections $\mathbb{R}\setminus\mathbb{Q} \rightarrow \...
0
votes
0answers
28 views

Distances between Countably Many Points in the Plane

If one has a set of countably many points in the plane $\mathbb{R}^2$, is it necessarily true that the distance between any pair of these points needs to be finite? I see a similar question someone ...
0
votes
0answers
41 views

Set is countable proof

Suppose that $\cal P = \{a_nx^n + a_{n-1}x^{n-1} + \cdots + a_0 : a_k \in \mathbb{Z}$ for all $1 \leq k \leq n$ with $a_n \neq 0\}$. Show that $Q = \{x \in \mathbb{R} :$ there is a $p\in P$ so that $p(...
3
votes
2answers
34 views

In a competition of $45$ people, how many received medals in exactly two categories?

Background I've been learning the basics of set theory and this is a reference to Business Mathematics and Statistics by Asim Kumar Manna, section 2.56: In a competition, a school awarded medals in ...
0
votes
1answer
40 views

If $f:S\to S$ is a bijection and $T$ is a subset of $S$ such that $f(t) \in T$ for every $t \in T$, is $f:T \to T$ itself a bijection? [closed]

Clearly $f:T \to T$ must be injective but I can't figure out whether it's is surjective.
1
vote
1answer
37 views

If $S\subset \mathbb{R}^n$ is closed, then $\bigcap_{k=1}^{\infty}(1+\frac{1}{k})S=S$

Based on the comment I edited the question. Let $S \subset \mathbb{R}^n$ be a bounded symmetric convex set. Question: How to show that if $S$ is closed, then $\bigcap_{k=1}^{\infty}(1+\frac{1}{k})S$ ...
0
votes
2answers
49 views

Equivalent sets for naturals

Prove that the sets $\{0, 1\}^\mathbb{N}$ and $\mathbb{N}^\mathbb{N}$ are equivalent. My friend gave me the following proof: Proof. It suffices to show that $\{0, 1\}^\mathbb{N}$ and $\mathbb{N}^\...
0
votes
1answer
20 views

Two countable sets proof [duplicate]

If we know that $\mathbb{N} \times \mathbb{N}$ is equivalent to $\mathbb{N}$ (same cardinal), can we conclude that the cartesian product $A \times B$ of two countable sets $A$ and $B$ is countable? In ...
1
vote
1answer
129 views

Counting number of functions such that $f(f(x)) = f(x)$

Let $Z$ be the set with $n \geq 3$ elements. A function $f: Z \rightarrow Z$ is considered a "selfie" when for each $x \in Z$ we have $f(f(x)) = f(x)$. How many functions with domain and ...
1
vote
2answers
36 views

How do you generate the numbers from an empty set?

In a short 2007 Scientific American article, the former Harvard mathematician and author Dr Robert M Kaplan stated that: in mathematics we can generate all numbers from the empty set I've not been ...
0
votes
1answer
42 views

Prove that $A = \{P(A)\}$

Prove that If $A=\{B\}, B=\{\{\},A\} $ then $A=\{P(A)\}$ $P(A)$ denotes the power set of $A$. I have studied well founded set theory but this proof calls for Anti Foundation Axiom. I am not familiar ...
2
votes
1answer
28 views

A question about “rearranging” finite unions.

I am working on this simple problem: Show that $$\overline{A\cup B}=\overline{A} \cup \overline{B}$$ where $\overline{X}$ denotes the closure of $X$. Now I have already proved it by showing that LHS ...
0
votes
1answer
39 views

Definitions of well ordered set, maximal element and upper bound

I am currently studying equivalents of the Axiom of choice such as the well ordering theorem and the Zorn's lemma. I understand partially and linearly ordered set is a primitive definition in both ...
-2
votes
0answers
13 views

DFA set builder problems [closed]

Write L in set builder if the language only has an English descrption. Write L complement in set builder Please find the link of the questions below. DFA questions Link
0
votes
1answer
31 views

Contradiction In Defining Symmetric Difference

One definition of set difference is $A\Delta B=(A-B)\cup (B-A).$ If we let $x\in A\Delta B,$ by our definition, we have that $x\in A \space\wedge\space x\notin B$ or $x\in B \space\wedge\space x\notin ...
1
vote
1answer
26 views

What is a matrix of tuples?

Consider the prisoner's dilemma, in this game, you have a matrix, $$A = \begin{bmatrix} (2,2) & (0,5) \\ (5,0) & (1,1) \end{bmatrix}$$ (or something like this) But what is this object exactly? ...
0
votes
1answer
79 views

Confused with a proof about paradoxical groups.

I am reading about the Banach-Tarski paradox, however, there are a couple of things about theorem 6 that confuse me. The image of theorem 6 and the proof can be found below. The first thing that ...
2
votes
1answer
75 views

Proof that two sets are equal

$X$ is finite, if and only if, the affirmation is true, $$Y\subseteq X \text{ and } f:Y\to X\text{ surjective } \Rightarrow Y=X$$ It is easy to see that this result is true, but I am not able to ...
-1
votes
0answers
37 views

Standard notations for some sets of functions [closed]

What are standard (or widely used) notations for the following sets: The set of all functions from $A$ to $B$; The set of all bijective functions from $A$ to $B$; The set of all injective functions ...
1
vote
1answer
36 views

How to use axioms for a proof in axiomatic set theory?

I am learning set theory and find it confusing sometimes to understand how to use an axiom in order to solve an exercise. My main problem is beginning the proof and understanding how to proceed. ...
3
votes
1answer
34 views

Set theory difficult question on proving that set $\mathbf {H}$ always exists

I have been puzzling over this question for literally hours: Let H be a 1011-element subset of the set {0, 1, 2, ..., 2021}. Prove that it has two (not necessarily distinct) elements a and b such ...
2
votes
2answers
72 views

Help with the proof of Zorn's Lemma: if $A$ and $B$ are conforming subsets, why must it be that $A\subseteq B$ or $B\subseteq A$?

Here we can find a simple proof of Zorn's Lemma, but I find something that I can't really understand. There is an statement that say: If A and B are conforming subsets of $X$ and $A\neq B$, then one ...
0
votes
2answers
41 views

Is the Cardinality of all Lines in the Extended Euclidean Plane $\mathfrak{c}$?

Consider the surjection $[0,2\pi)*\left(\mathbb{R}^2\cup\ell_\infty\right)\rightarrow L$ (such that $L$ is the set of all lines determined by the binary operation $*$ between a point and an angle). ...
0
votes
1answer
35 views

Minimum number $s$ such that all the unions of $s$ of the $p$ subsets are equal

I'm asking for references in literature on the following problem. Given a positive integer $n$, $S=\{1,\dots,n\}$ and $p$ distinct subsets of $S$, $A_1,\dots,A_p$, what is the minimum number $s>0$ ...
2
votes
1answer
45 views

If $g:X\to Y$ be a one-to-one correspondence and $X$ is finite, then $Y$ is finite too.

Corollary. Let $g:X\longrightarrow Y$ be a one-to-one correspondence. If the set $X$ is finite, then $Y$ is finite. Proof. Exercise. Book :"Set Theory With Applications" by You-Feng Lin and ...
0
votes
1answer
24 views

Proving set identities involving conditionals.

How can I prove the following conditional set identity? For any three sets A, B, C we have $A\triangle(B\triangle C)=\varnothing \rightarrow(A\cup B\cup C)=((A\cap B)\setminus C)\cup((A\cap C)\...
0
votes
2answers
47 views

Proving that the cross product of two injective functions is bijective.

I've been asked to prove the following property: If $f$ and $g$ are injective then $F3$ is bijective, where $F3$ is given by $A×B→f⁢(A)×g⁢(B), (x,y)⟼(f⁢(x),g⁢(y))$ Here's what I have so far... To ...
2
votes
1answer
16 views

Why is the sum of two functions expressed as simple functions is the sum of the weighted indicator variable of the intersection?

If $$g=\sum_{i=1}^n a_i \mathbb I_{A_i}$$ and $$h=\sum_{i=1}^m b_j \mathbb I_{B_j}$$ why is $$g + h = \sum_{i=1}^n \sum_{j=1}^m (a_i + b_j) \mathbb I_{A_i\cap B_j}$$ I would have guessed that the sum ...
0
votes
0answers
14 views

Conjecture on simple algebraic expressions for complemetary sets

This question/conjecture started in a different discussion regarding arithmetic series. Conjecture: If we have a set that is defined by a single algebraic expression, e.g., $$A := \{a \in \mathbb{Z}^+ ...
0
votes
1answer
33 views

Meaning of the expression “$\mu$ a.e.”

In the monotone convergence theorem: Let $g_n\geq 0$ be a sequence of measurable functions, such that $g_n \uparrow g\;\; \mu \text{ a.e.},$ i.e. $g_n(\omega) \leq g_{n+1}(\omega)\;\; \mu \text{ a.e.},...
0
votes
1answer
30 views

Is $\mathcal{F}=\{\{2,4,6\},\{3,4,5,6\}, \Omega, \emptyset\}$ a $\sigma$-algebra over $\Omega = \{1,2,3,4,5,6\}$?

Hello so I'm trying to understand when a set can be defined as a $\sigma$-algebra (I'm new to this :)). I stumbled upon this question: Is $\mathcal{F}=\{\{2,4,6\},\{3,4,5,6\}, \Omega, \emptyset\}$ a $\...
1
vote
0answers
16 views

Numerical equivalence between Cartesian products

Let $J$ be some (non-empty) set of indices, and let $\left\{ A_\alpha \right\}_{\alpha \in J}$ and $\left\{ B_\alpha \right\}_{\alpha \in J}$ be any two indexed families of sets such that, for each $\...
0
votes
2answers
47 views

Wondering how these two sets are countably infinite

We have $A = \mathbb{R}$ and $B = \{x|x \in \mathbb{R} \land \exists y (y\in \mathbb{Z} \land |x-y| < \frac{1}{2})\}$ How is $A-B$ countably infinite? I know the definition of set minus is $A \cap \...
1
vote
0answers
28 views

For all $n,m\in\mathbb{N}$ if $\vert X\vert=n$ and $\vert Y\vert=m$, then $\vert X\times Y\vert=nm$

I've been studying some basic set theory on my own and as I solved exercises I stumbled upon the statement in the title. At first glance it seems pretty obvious that it should be true. But this is set ...
1
vote
0answers
17 views

Which of the given relations is also a function?

Which of the following relations are also a functions? $ S \subset R \times R $ $(x, y) \in S \iff x = y$ (mod 7) (2, 9) $\in S$ and (2, 16) $\in S$, so I assume this is not a function. $(x, y) \in ...
4
votes
1answer
46 views

Prove that the given set is a finite set.

$A = \{(a,b) \in N^2 | (2+a)(2-b) \ge 2(a-b)\}$. Prove that A is a finite set. I'm having problem with proving A is a finite set. So far, Let $x, y \in A$. Then, \begin{equation*} \begin{aligned} (...
2
votes
0answers
53 views

Prove if the following sets are topologies in $\mathbb{Z}$

I've been solving the following problem from the start of my general topology course, and I'd like to check if my answers are correct. The problem is: Study if the following sets of subsets of $\...
0
votes
2answers
73 views

Two sets have the same cardinal proof

Suppose that $S, T$ are sets such that $S$ is infinite and $T = \{t_i: i = 1, ..., n\}$ with $T$ having $n \geq 1$ distinct elements. If $S \cap T = \{\}$, show that $card(S) = card(S \cup T)$. Hint: ...
0
votes
2answers
25 views

Prove $(A_1 \smallsetminus B) \cup (A_2 \smallsetminus B) = (A_1 \cup A_2) \smallsetminus B$

Prove $(A_1 \smallsetminus B) \cup (A_2 \smallsetminus B) = (A_1 \cup A_2) \smallsetminus B$ If I used the set identity to prove it and it seems it goes on and on, did I make a mistake or ... $(A_1 \...
1
vote
1answer
28 views

Specific question about example of Family of sets & Set builder notation

I encountered the following example whilst studying Equivalence Classes from How to prove it, Velleman. : Let $ B= \{(p, q) ∈ P × P | \text{the person p has the same birthday as the person q } \} $ ...
1
vote
2answers
51 views

Is the inverse image function injective?

It seems that the inverse image function(see my previous question) is injective. Where a proof of that can be found?
5
votes
1answer
78 views

Is there a notation for the inverse image function itself?

Let $f$ be a function. If $B \subset im(f)$ then the inverse image of $B$ under $f$ in the current standard notation is $f^{-1}(B) = \{x \in dom(f) : f(x) \in B\}$. But $f^{-1}$ does not denote the ...
3
votes
0answers
60 views

Proof for $\alpha \times \beta \cong \alpha \otimes \beta$

I need to prove the following theorem: Let $\alpha$ and $\beta$ be ordinals. Then $\alpha \times \beta \cong \alpha \otimes \beta$, where $\alpha \times \beta$ is in anti-lexicographic order. I have ...
0
votes
1answer
42 views

Are all sets in Set, with the same cardinality, isomorphic?

It is said, that all singleton sets are isomorphic(and terminal objects). I wonder if this is true for any cardinality in the category of sets. For example, are all two element sets isomorphic in the ...
0
votes
1answer
36 views

Is a subset contained in a union of its superset?

For context, I'm taking an introductory real analysis course, and our current topic is intervals. One of the questions requires to prove that, for every $x, y$ in some real interval $I$, with $x<y$,...
1
vote
2answers
42 views

Maximal element of a poset

I am currently studying Zorn's lemma and its my understanding that the definition of a maximal element is a primitive to the lemma. From my understanding a maximal element $M$ of a partially ordered ...

1
2 3 4 5
491