Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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, etc. More advanced topics should use (set-theory) instead.

0
votes
0answers
25 views

Natural number between two real numbers y,x such that y-x > 1

Prove that for $x,y \in \mathbb{R}$ such that $y-x>1$ there is a natural number $n$ such that $x < n < y$. Consider the following set: $$ S := \{n \in \mathbb{N} | x < n < y\} $$ ...
1
vote
2answers
29 views

Find all equivalence classes of $R_{A,B}$

Let $A$ and $B$ be sets. We define $R_{A,B}$ on $B^A$ such that: For all $f,g:A\to B$, $f\,R_{A,B}\,g$ if and only if exists $h:A\to A$ such that $h$ is bijective on $A$ and $g=f\circ h$. ...
2
votes
6answers
216 views

Prove that the countable union of countable sets is also countable

I know this seems like a repeated question, but what I find the other answers laking is how they are dealing with the fact that our sets aren't mutually disjoint. If anyone could explain how the ...
0
votes
1answer
20 views

In an infinite linearly ordered set every initial section is finite. ¿Is it isomorphic to $\langle\mathbb{N}\,,\,\text{<}_{\mathbb{N}}\rangle$? [duplicate]

As the title of the question suggests, if $\langle A\,,\,<\rangle$ is an infinite linearly ordered set such that for each $a\in A$, the initial section $\text{sec}(a,A,<)$ is a finite set, ¿is ...
-3
votes
0answers
18 views
0
votes
2answers
22 views

How to prove $f$ is injective $\Longleftrightarrow$ $f(A) \cap f(B)=\emptyset$ for all disjoint $A,B⊂X$

How to prove $f(A) \cap f(B)=\emptyset$ for all $A,B⊂X$ with $A∩B=∅$ $\Longleftrightarrow$ $f$ is injective For "$\Longrightarrow$" Let $x \in A$ and $y\in B$. Since $A∩B=∅$, it is $x\neq y$ and ...
-1
votes
1answer
37 views

Can anyone explain what this means?

Can anyone explain what this is supposed to do? If possible maybe outline the first few results? Its in part of a set theory question. $$ \Pi_{1}^\infty\{0,1\} $$
0
votes
0answers
22 views

Question on union and intersection of sets

The question in my Book is as under The set (AUB')' U (B ⋂ C ) is equal to : (a) A' U B U C (b) A' U B (c) A' U C' (d) A' ⋂ B I simplified in the following way (AUB')' U (B ⋂ C ) ...
0
votes
2answers
55 views

Why is $\mathbb{R}$ unbounded, despite being equinumerous to various bounded sets? Is there a name for this “distinction”?

$[0, 1] \approx (0,1) \approx \mathbb{R}$, for example. Intuitively, it seems that the infinity of $\mathbb{R}$ is of a different nature than that of the intervals; with $\mathbb{R}$ I can “explode” ...
2
votes
1answer
37 views

Notation: $P(x)$ iff $x$ has property $P$

In set theory (for example), people write $P(x)$ to indicate that $x$ has property $P$. What is the meaning of this "expression" formally? Is $P$ a predicate (a Boolean-valued function on some set [...
1
vote
1answer
46 views

How to prove $f^{-1}(f(A))=A \quad \Longrightarrow f(A\cap B)=f(A)\cap B$

$X,Y$ are Quantites and $f:X\rightarrow Y$ a function that is injective. i have already proven that $f^{-1}(f(A))=A$ when $f$ is injective. How to prove $f^{-1}(f(A))=A \quad \Longrightarrow f(A\cap ...
0
votes
2answers
41 views

Attempt at proving using natural deduction “ The intersection of the set of R-equivalence classes on A is empty”

I've tried to present in a natural deduction style the proof of the proposition "For any two different R-equivalence classes on A, their intersection is empty". Please tell me which improvements ...
-1
votes
0answers
23 views

How to prove $f(A\backslash B)=f(A)\backslash f(B)$ for every $A,B⊂X$ with $B⊂A$ if $f$ is injective? [duplicate]

How to prove $f(A\backslash B)=f(A)\backslash f(B)$ for every $A,B⊂X$ with $B⊂A$ if $f$ is injective? Unfortunately, I have no base to start with. Hope you could help me out.
0
votes
0answers
15 views

$f(A)\cap f(B)=\emptyset$ for every $A,B ⊂ X$ with $A\cap B=\emptyset$ $\Longleftrightarrow$ f is injective. [duplicate]

I have already proven$f(A\cap B)=f(A)\cap f(B)$ if $f$ is injective. But how do i prove $f(A)\cap f(B)=\emptyset$ for every $A,B ⊂ X$ with $A\cap B=\emptyset$ $\Longleftrightarrow$ f is injective.
-1
votes
0answers
42 views

Why is $f({x}∩{y}) = f({x}) ∩ f({y}) = {f(x)} ∩ {f(y)} = {f(x)}$ when $f(x)=f(y)$? [on hold]

Why is $f({x}∩{y}) = f({x}) ∩ f({y}) = {f(x)} ∩ {f(y)} = {f(x)}$ when $f(x)=f(y)$. Couldn't it also be ${f(x)} ∩ {f(y)}=\{f(y)\}$?
2
votes
0answers
35 views

Proof of : “ Union of all R-equivalence classes on A is included in A” based on “ R is a subset of A² ”. ( Q° on Ayres, Problems Modern Algebra)

I'm studying Ayres Theory and Problems of Modern Algebra. In Chapter 2, Solved Problem 6, the question is asked to prove that " An equivalence relation R on a set S effects a partition of S." ...
0
votes
2answers
22 views

Invariant subset

Suppose $\Phi: A\to A$ is a transformation of the set $A$. I want to understand what it means for a subset $B\subseteq A$ to be invariant under $\Phi$. Halmos states that this means $\forall b\in B (...
1
vote
1answer
50 views

Cardinality of a power set $2^{2^A}$

The question I want to answer is : if $A$ is finite set of cardinality $2$, find $2^{2^A}$ I know that $|2^{2^{A}}| = 2^{2^{|A|}}$, but does this mean that there are 16 elements in the power set? ...
-1
votes
4answers
63 views

Find any 1-1 function from $\mathbb{Z}$ to $\mathbb{N}$.

I was thinking $f(n)=|n|$, but realized that would be a surjection. I'm not sure of how to solve this. Thank you.
2
votes
1answer
50 views

Number of permutations differing in at least $d$ spots in pairwise comparisons

A friend and I were thinking about this problem today but we were unable to come up with a solution. Problem: Consider the the numbers $S=\{1,\ldots,n\}$. Given $2\le d \le n$ what is the ...
0
votes
1answer
15 views

Countability of sets, usage of cantor set

How could I prove that the set $S_1$ of all infinite sequences that consists of 0's and 2's, implies $S_1$ is uncountable. Could I say $S_1$ is equivalent to the cantor set?
-1
votes
1answer
34 views

Constructing a set by picking the first element in each set in a family of sets. How to do that?

Suppose I have a set of sets, say, disjoint sets of children born from the same parents. F = { C1, C1, C3, C4 }. Which set theoretic construction would allow to obtain the set : { x | x is the ...
0
votes
0answers
15 views

Examples of solvable set equations. ( References on this topic?)

I recently asked a question concerning set equations and a possible mechanical method to solve them. If I am correct ( and after having read the answer given) there isn't such a method. I conclude ...
0
votes
1answer
55 views

Union of a set with empty set

If $A = \{1,1,2\}$ what is its union with the empty set? I am confused as A has a duplicate element so is the union $\{1,2\}$ or $\{1,1,2\}.$
0
votes
2answers
37 views

Question on associative property of sets

In the proof of A ∩ (B - C) = (A ∩ B) - (A ∩ C) Most of the proofs I have seen involve the following steps: i) Let x be an arbitrary element of A ∩ (B - C) ii) ⇒ x ∈ A and x ∈ (B - C) ...
-4
votes
0answers
22 views

Cardinality/ pidgeonhole principle question [on hold]

Let A be a non-empty finite set, and $|A|=n$. How would I prove $|A\setminus\{a\}|=n-1$ if $a \in A$
0
votes
2answers
37 views

Prove: $f$ is injective if and only if for any non-empty set $C$ and for all functions $g, h : C \to A$ such that $f ◦ g = f ◦ h$ we have $g = h$.

I’m attempting to prove this exercise for my elementary analysis class, however, I am having difficulty deconstructing the iff statement. Any help in understanding how the implications are working ...
0
votes
0answers
8 views

Looking for the explicit formula of a possible bijection from natural numbers to integers. [duplicate]

As a gratuitous exercice, I'm trying to find a way to establish a 1-1 correspondance between the set of natural numbers and the set of integers. Can it be done in the following way? My idea would ...
0
votes
1answer
42 views

Is there a general and mechanical method to solve algebra of sets (or alg.of propositions) equations?

In some simple cases it seems possible to solve for X a set equation. For example, if I am given : X Inter U = U , and knowing the law according to which S Inter U = S for any set S, I can find ...
0
votes
1answer
27 views

Useful bijections

Could someone please provide me with some useful bijections one ought to know for an upcoming examination on cardinality with an emphasis on proofs? For example, the bijective mapping $f : (-1, 1) \...
1
vote
1answer
39 views

Term for “inverse image” of element under set-valued map?

Say I have a function $f: A \to 2^B$. Given an element $b \in B$, I want to refer to the set $f_b := \{a \in A: b \in f(a)\}$. Is there a standard name for such sets? Notice it's not technically ...
-2
votes
1answer
51 views

Suppose A = {1, 2, 3, 4, 5}. Mark the statement TRUE or FALSE. [on hold]

I got the first few, but im not sure about these: {2,4}⊂A×A. {∅} ∈ P(A). (1,1)∈A×A.
0
votes
2answers
31 views

Let $f:A\rightarrow B$ be a function, and $X\subseteq A$. Prove or disprove that $f(f^{-1}(f(X)))=f(X)$.

Let $f:A\rightarrow B$ be a function, and $X\subseteq A$. Prove or disprove that $f(f^{-1}(f(X)))=f(X)$. Let $A=\mathbb{N}$, $B=\mathbb{R}$ and $X=\mathbb{N\setminus\left\{0\right\}}.$ Hence, $f$ is ...
1
vote
2answers
34 views

Show that the image of the function $f:(0,\infty)\rightarrow \mathbb{R}$, $f(x)=x+\dfrac{1}{x}$ is the interval $[2,\infty)$. [duplicate]

Show that the image of the function $f:(0,\infty)\rightarrow \mathbb{R}$, $f(x)=x+\dfrac{1}{x}$ is the interval $[2,\infty)$. If $x=1$, then $f(1)=2$. So how can I show that the mage of the function ...
0
votes
1answer
27 views

Trying to get it right regarding “ inverse” applied to relations, functions and operations…

[ The discussion ( see below) tends to show that my question was based on the erroneous assumption that the expression " inverse operation" is standard. Apparently, it is an informal expression used ...
1
vote
3answers
37 views

Show the function $f(n)=\dfrac {(-1)^n (2n-1)+1} {4}$ is a surjection

Let $f:\mathbb{N}\rightarrow\mathbb{Z}$ be a function which $f(n)=\dfrac {(-1)^n (2n-1)+1} {4}$. Show that $f$ is surjection. Proof. Let $m\in\mathbb{Z}$. We need to find $n\in\mathbb{N}$ such that $...
0
votes
1answer
25 views

If $x \in \liminf\limits_{n\to \infty}{E_n \cup F_n}$, can $x \in F_n$ for infinitely many $n\in \mathbb{N}$?

Context: I wasn't sure if it was valid to consider the case where $x \in F_n$ for infinitely many $n\in \mathbb{N}$ because my intuition tells me that $x \in \liminf\limits_{n\to \infty}{E_n \cup F_n}...
0
votes
0answers
26 views

about cardinal ,mapping on X [duplicate]

if A is a infinite set ,define B={f|f is 1-1 correspondence on A} I want to compute Card(B) My attempt when A is finite ,then card(B)=$2^{card(A)}-2$ Such as A={$a_1,a_2$},then there exist two ...
3
votes
3answers
90 views

Bijection from $\Bbb N\to \Bbb Z \times \{1, 2, 3, 4\}$.

Find a bijection from $\Bbb N\to \Bbb Z \times \{1, 2, 3, 4\}$. Ok, so I know some element $x$, in $\Bbb N$ maps to an element $(y,z)$ in $\Bbb Z.$ I know to to get from $x$ to $y.$ But since $z$ ...
0
votes
1answer
61 views

Formal definition of “ inverse operations” on a set?

Suppose f1 and f2 are two operations on A, that is functions from A² to A. My question is : how to express in general and formally the fact that each operation is the inverse of the other? Is it ...
1
vote
0answers
50 views

“Truth set” approach to validity and logical consequence: how does it relate to the standard approach? what are the possible drawbacks?

References : I think the " truth set approach" to validity and logical consequence can be linked to the name of R. Carnap ( who defines L-truth and L-implication in this way in his Introduction to ...
4
votes
1answer
52 views

One to one correspondence between transcendental and uncomputable numbers

I know that both sets are uncountable infinite but the transcendentals are not a subset of the uncomputables. I don’t know if there exist uncomputable numbers that are not transcendental. But my ...
2
votes
3answers
59 views

Question about open interval with a finite decimal expansion

Let $Y$ denote the set of numbers in $(0, 1)$ with a decimal expansion that contains only $0$s and $1$s, and only finitely many $0$s. Decide if you think $Y$ is countably infinite or uncountable – I ...
1
vote
0answers
35 views

Existence proof for bijection

Consider two sets $A, B$ and two bijective maps $f_1, f_2$ defined between them, such that $$ f_1: A \rightarrow B, \text{ s.t. } h(a)\leq h(f_1(a)) \text{ for all } a \in A \\ f_2: B \rightarrow A, \...
1
vote
1answer
28 views

Size of Set Equal to 1? $|U \cap \{s,t\}| = 1$

I am not sure what to call this but in the preliminaries for chapter 2 on sets in Alexander Schrijver's Combinatorial Optimization book he states the following: A set $U$ is said to separate $s$ and $...
2
votes
1answer
41 views

How to prove this simple property for two sets?

We are given two vectors, $a = (a_1,\dots,a_n)$ and $b = (b_1,\dots,b_n)$ such that $0 \le a_i=b_i \le \varDelta$ for $i=1,\dots,n$. We want to modify each of these vectors in an iterative procedure ...
0
votes
0answers
25 views

Bijection between $[a,b)$ and $(a,b)$? [duplicate]

I know this question has been asked and answered before, but I am working on my own through an analysis textbook and just wanted to check if the following construction would be appropriate: Define $a|...
0
votes
1answer
26 views

How to prove this fact about the discrete closure? [closed]

The content is given two relationships: R₁ and R₂ prove that s(R₁ ∩ R₂)=s(R₁) ∩ s(R₂) My teacher has taught us the UNION versions in class, and I figure it's easy. Also I have already finished the ...
0
votes
2answers
45 views

Biject all points on a plane to the real line [closed]

I understand that the continuum hypothesis implies (since there are only two infinities; discrete and continuous) that the set of points on an n-dimensional plane is equal to (can be bijected to) the ...
1
vote
0answers
14 views

What does a “maximal $(f,g)$-chain” mean?

This is just a quick question. I am doing a problem that constructs the proof for the Schroeder-Bernstein theorem, but I am a little confused about the terminology. The problem is stated as follows. ...